一種基于Dewey編碼的XML小枝模式匹配方法.pdf

1、近幾年來，隨著數(shù)據(jù)庫和網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，XML（可擴(kuò)展標(biāo)記語言）已成為Web上數(shù)據(jù)表示、集成和交換的標(biāo)準(zhǔn)。相比其它的標(biāo)記語言，XML的格式簡單、自我描述能力強(qiáng)，實現(xiàn)了內(nèi)容、結(jié)構(gòu)和表現(xiàn)三者的分離，更適合于數(shù)據(jù)表示和交換，因此XML在科學(xué)研究、電子商務(wù)等各個領(lǐng)域得到了廣泛的使用。今天Web上已經(jīng)涌現(xiàn)了大量的XML數(shù)據(jù)，所以如何對XML文檔進(jìn)行有效地查詢已成為當(dāng)今數(shù)據(jù)庫領(lǐng)域的一個重要的研究課題。
　　查詢XML文檔，目前國內(nèi)外提出的算

2、法主要是基于以下兩種思想:第一種是路徑分解法，它把將要查詢的路徑表達(dá)式分解成多個簡單路徑表達(dá)式，然后再進(jìn)行匹配，最后將中間結(jié)果連接起來。這種方法不可避免地要產(chǎn)生許多無用的中間結(jié)果。另一種是小枝模式匹配方法，它將查詢表達(dá)式用樹的形式建模，稱為“小枝模式”(twigpattern)，再將小枝模式到XML文檔樹中進(jìn)行匹配，通過掃描一遍輸入結(jié)點列表就可得到所有的輸出結(jié)果。這種方法使得算法的I/O代價、CPU時間復(fù)雜度和空間復(fù)雜度都大大降低，從而

3、提高了查詢的效率。目前具有代表性的小枝模式匹配算法有TwigStack和TJfast等。但是，對于包含較多父子邊的查詢語句這些算法并不是最優(yōu)的，同時這些算法的一個共同點就是它們并沒有利用XML文檔的路徑索引。
　　為了進(jìn)一步提高小枝模式匹配算法的效率，本文利用了XML文檔的路徑索引JoinGuide，提出了一種新的基于Dewey編碼的小枝模式匹配方法TwigJoin，主要工作如下:
　　(1)綜合區(qū)域編碼和前綴編碼的優(yōu)點對X

4、ML文檔進(jìn)行了編碼，對于文檔中的實例結(jié)點我們使用了前綴編碼方案，而對XML文檔的路徑索引JoinGuide使用了區(qū)域編碼的方案。
　　(2)對小枝模式匹配算法TwigStack進(jìn)行了改進(jìn)，先使用TwigStack算法在XML文檔的索引圖JoinGuide上得到預(yù)匹配結(jié)果，然后再掃描預(yù)匹配結(jié)果中的葉子實例結(jié)點序列得到所需的查詢結(jié)果。
　　(3)在理論上和TwigStack和(Ⅰ)-XISS系統(tǒng)進(jìn)行了詳細(xì)的對比分析，說明了Twi

5、gJoin小枝模式匹配方法的優(yōu)點。
　　(4)最后構(gòu)建了一個實驗系統(tǒng)，實現(xiàn)了提出的小枝模式匹配方法，然后通過實驗把TwigJoin同TwigStack和(Ⅰ)-XISS進(jìn)行了對比，結(jié)果表明本文提出的小枝模式匹配方法的效率有了較大的提高。
　　今后的工作是，首先要提高TwigJoin系統(tǒng)中解析和建立路徑索引的效率，然后再完善TwigJoin系統(tǒng)中的查詢算法，增加TwigJoin系統(tǒng)中對XPath查詢語言中各種軸的查詢能力，以使