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

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

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

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

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