TJDirect：一種基于IFED編碼的XML文檔小枝模式匹配算法.pdf

1、XML已成為Web上數(shù)據(jù)表示、集成和交換的標(biāo)準(zhǔn)，它的格式簡(jiǎn)單、自我描述能力強(qiáng)，實(shí)現(xiàn)了內(nèi)容、結(jié)構(gòu)和表現(xiàn)三者的分離，更適合于數(shù)據(jù)表示和交換。近年來，XML在各個(gè)領(lǐng)域得到了廣泛的使用，Web上已經(jīng)涌現(xiàn)了大量的XML數(shù)據(jù)。如何對(duì)XML文檔進(jìn)行有效地查詢成為一個(gè)重要的研究課題。 XML文檔的結(jié)構(gòu)查詢通常被轉(zhuǎn)化為兩個(gè)節(jié)點(diǎn)列表之間的結(jié)構(gòu)連接操作。結(jié)構(gòu)連接主要有兩種思想：一種是路徑分解法，將查詢的路徑表達(dá)式分解成多個(gè)簡(jiǎn)單路徑表達(dá)式，進(jìn)行匹配，然

2、后將結(jié)果連接起來。這種方法不可避免的要產(chǎn)生無(wú)用的中間結(jié)果。另一種是小枝模式匹配方法，將查詢表達(dá)式用樹的形式建模，稱為“小枝模式”(twig pattern)，再將小枝模式到XML文檔樹中進(jìn)行匹配，這種方法使得算法的I/O代價(jià)、CPU時(shí)間復(fù)雜度和空間復(fù)雜度降低，提高了查詢的效率。最近提出的基于ExtendedDewey編碼的小枝模式匹配算法--TJfast能較有效地處理XML文檔查詢，但是ExtendedDewey編碼不支持動(dòng)態(tài)插入，并且

3、TJfast算法的執(zhí)行效率有待進(jìn)一步提高。 本文針對(duì)以上兩個(gè)不足進(jìn)行改進(jìn)，主要工作如下： (1)提出了IFED(Insert-Friendly ExtendedDewey)編碼方法，它從ExtendedDewey編碼的基礎(chǔ)上改進(jìn)而來，既支持有效的查詢，又支持動(dòng)態(tài)插入。 (2)TJfast算法的I/O代價(jià)和CPU時(shí)間復(fù)雜度與輸入列表的大小和最后匹配結(jié)果大小的總和線性相關(guān)，但是，輸入列表中有些不參與連接的節(jié)點(diǎn)是可以被

4、跳過的。本文提出了 TJDirect 算法，它采用一種更為靈活的小枝模式匹配方法，跳過了一些不參與連接的節(jié)點(diǎn)，提高了算法的執(zhí)行效率，并且算法中不再用集合保存匹配的節(jié)點(diǎn)，使得空間復(fù)雜度降低。 (3) 通過實(shí)驗(yàn)比較了基于IFED 編碼的 TJDirect 算法和基于 IFED編碼的 TJfast 算法的執(zhí)行時(shí)間，結(jié)果顯示 TJDirect算法的執(zhí)行效率較高。 (4) 為 XML 文檔編碼，考察 IFED 編碼的存儲(chǔ)空間超出Exten