一種基于小枝模式匹配的XML數(shù)據(jù)查詢處理算法.pdf

1、XML作為Web發(fā)展所帶來的新技術(shù)中的代表，已經(jīng)成為網(wǎng)上數(shù)據(jù)表示和交換的標(biāo)準(zhǔn)，并逐漸成為了學(xué)術(shù)界和工業(yè)界所關(guān)注的焦點。由于XML數(shù)據(jù)具有不同于傳統(tǒng)數(shù)據(jù)形式的特點，因此，在各種基于XML的應(yīng)用中，如何有效地查詢XML數(shù)據(jù)已經(jīng)成為一個重要的研究課題。
　　近年來，小枝模式匹配問題已經(jīng)被廣泛地研究。一個小枝模式查詢Q在XML文檔樹T中的匹配，也就是找到這個查詢模式Q在T中出現(xiàn)的所有情況。以前的工作比如Holistic Twig和TJFa

2、st都是把小枝模式分解成多個從根結(jié)點到葉子結(jié)點的單個路徑，然后把這些路徑模式的匹配結(jié)果合并起來以得到小枝模式查詢Q的匹配結(jié)果。它們能夠有效地刪除不可能的路徑模式來避免產(chǎn)生大量的中間結(jié)果，但合并這些線性路徑會花費很高的計算代價。為了解決這個問題，最近又提出了Twig2Stack和TwigList算法，但它們都需要遍歷所有的輸入節(jié)點，另外，它們也沒有考慮有些查詢節(jié)點是不需要進(jìn)行處理的。本文對XML路徑查詢處理中尚存在的難點問題進(jìn)行了深入的研

3、究，并且在汲取了各種小枝模式匹配算法優(yōu)點的基礎(chǔ)上，提出了一種新的小枝模式匹配算法TwigEN。本文的主要工作如下:
　　(1)研究分析了現(xiàn)有的小枝模式匹配算法，并總結(jié)其實現(xiàn)方法;
　　(2)根據(jù)XML文檔的結(jié)構(gòu)特點提出了一種新的小枝模式匹配算法TwigEN，該算法只處理有解擴展的元素結(jié)點，因此，能夠較大限度的跳過輸入流中無用的元素結(jié)點;
　　(3)對算法TwigEN的復(fù)雜度和可行性進(jìn)行了分析，給出了TwigEN算法在最

4、壞情況下的時間和空間復(fù)雜度;
　　(4)最后構(gòu)建一個實驗系統(tǒng)，實現(xiàn)了本文提出的小枝模式匹配算法，然后通過實驗把TwigEN算法同TwigStack算法和TwigList算法進(jìn)行了比較，并對實驗結(jié)果進(jìn)行了分析。實驗證明，本文提出的小枝模式匹配算法的效率有了較大的提高。
　　本文提出的小枝模式匹配算法能夠根據(jù)XML文檔的結(jié)構(gòu)特點跳過那些在結(jié)構(gòu)連接中無用的元素結(jié)點，這樣不僅減少了待處理結(jié)點的數(shù)目，縮短了查詢處理時間，而且也節(jié)省了內(nèi)