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

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

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

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

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