基于版本樹的改進(jìn)XML枝匹配算法研究.pdf

1、當(dāng)前，XML(可擴(kuò)展標(biāo)識語言)已經(jīng)成為萬維網(wǎng)的數(shù)據(jù)表示和數(shù)據(jù)交換的標(biāo)準(zhǔn)。隨著XML數(shù)據(jù)越來越多，針對XML數(shù)據(jù)的查詢與處理引起了越來越多的關(guān)注。近來，大量基于將XML文檔視作樹形模型的XML查詢算法被相繼提出。然而，XML文檔的半結(jié)構(gòu)化性質(zhì)和用戶查詢需求的日益復(fù)雜性又給XML數(shù)據(jù)的高效處理帶來了如下新的挑戰(zhàn)：(1)XML查詢算法的輸入集規(guī)模和執(zhí)行時(shí)間將隨著XML文檔規(guī)模的增長而迅速增加；(2)由于XML的不規(guī)則性，算法返回的結(jié)果可能包含

2、重復(fù)元素，需要后序的處理工作。因此，如何高效準(zhǔn)確地查詢大量的XML數(shù)據(jù)成為目前值得研究的一個(gè)重要課題。
　　 本文在返回結(jié)果為匹配枝和返回結(jié)果為無冗余的目標(biāo)數(shù)據(jù)元素兩種情況下分別提出了高效且可擴(kuò)展的XML枝匹配算法Twig3Version和高效的AdvancedTwigVersion算法，針對其關(guān)鍵技術(shù)展開了研究，主要研究內(nèi)容和特色如下：
　　 (1)在返回結(jié)果是所有匹配枝的情況下，提出了一種將已有的在原文檔上的XML枝

3、匹配算法應(yīng)用于一個(gè)壓縮的索引結(jié)構(gòu)(版本樹)的思想，并提出了簡單高效的版本過濾模塊和歸并連接模塊。在精簡的版本樹上執(zhí)行結(jié)構(gòu)匹配以及在精簡的中間結(jié)果上執(zhí)行版本過濾和歸并連接大大提高了查詢算法的性能。
　　 (2)在返回結(jié)果是無冗余的目標(biāo)數(shù)據(jù)元素的情況下，AdvancedTwigVersion算法對TwigVersion算法進(jìn)行了改進(jìn)。通過盡可能多地利用祖先結(jié)點(diǎn)的標(biāo)簽信息，可以盡可能早地過濾掉不匹配的元素，加速了匹配的過程。另外，通過