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

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

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

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

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