XML模式樹匹配查詢算法的研究與改進.pdf

1、XML作為Web發(fā)展所帶來的新技術中的代表，逐漸成為了學術界和工業(yè)界所關注的焦點。XML是一種自描述、可擴展的標記語言，廣泛地用于Web環(huán)境下數據的表示和共享。要搭建各種基于XML的應用，必須提供處理XML數據的核心技術來高效地生成、查詢、過濾、變換XML數據。由于XML數據具有不同于傳統(tǒng)數據形式的特點，使得傳統(tǒng)的數據庫技術不能有效地發(fā)揮作用，因此需要針對其特點研究新的處理方法。 由于XML文檔有類似樹狀的結構，所以和文件路徑類

2、似的路徑查詢表達式是XML數據查詢和過濾的基礎，同時XML查詢也指定了那些在某些特定的樹結構關系上的選擇謂詞的樣式。原始的XML樹結構關系是父．子關系或者是祖先-后代關系，在XML文檔中發(fā)現這些匹配關系是XML查詢處理的核心操作，在XML文檔中找到所有查詢模式樹的匹配是XML查詢代價估計中的核心問題，在本文中重點討論了模式樹匹配的查詢優(yōu)化問題。 本文詳細探討了一種典型的結構化連接算法-Twig Join算法，并針對其存在的不足提

3、出了一種基于Ctree索引的模式樹匹配算法-PattemMatch算法。通過具體分析可以看出，與。Twig Join算法相比，PattemMatch算法能夠在XML文檔中直接找到一個查詢模式樹的匹配結果，不會產生無用的中間結果集，而且所有的中間結果集在堆棧中保存起來，通過連接運算能夠很方便地形成最后的查詢匹配結果，提高了查詢匹配的成功概率。 本文首先介紹了模式樹匹配算法的研究背景和研究現狀，回顧了結構化連接算法的研究成果，接著