XML模式樹(shù)匹配查詢算法的研究與改進(jìn).pdf

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

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

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