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

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

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

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