XML查詢中Twig模式匹配算法的研究.pdf

1、XML由于其所具有的自描述性、靈活的數(shù)據(jù)結構以及豐富的數(shù)據(jù)表示能力等特點,逐漸成為Web上數(shù)據(jù)表示、存儲和交換的事實上的標準。越來越多的XML數(shù)據(jù)成為信息共享的載體。大量XML數(shù)據(jù)的涌現(xiàn)促進了XML數(shù)據(jù)管理技術的快速發(fā)展,Twig模式匹配算法作為XML文檔查詢處理模塊的核心內容,成為眾多學者研究的熱點問題。在XML結構查詢中,可以通過編碼來確定節(jié)點間的結構關系,避免了對XML文檔樹的重復掃描,提高了查詢效率。早期的二元結構連接算法會產生

2、許多無用的中間結果,降低了性能,針對這一關鍵問題,論文在分析經(jīng)典算法PathStack算法和TwigStack算法的基礎上展開了深入研究。
　　首先,針對傳統(tǒng)XML文檔小枝模式查詢算法中,與模式樹中標簽名相同的節(jié)點均入緩存,易造成很大的空間浪費問題,提出了ListFWM模式匹配算法。算法在對XML文檔編碼的基礎上,依據(jù)節(jié)點間的結構關系過濾標簽列表中無用的中間節(jié)點,且不用歸并,通過實驗比較,驗證了ListFWM算法比TwigStac

3、k算法具有更高的查詢性能。其次,針對傳統(tǒng)算法需要對整個文檔節(jié)點進行編碼,從而導致查詢效率大大降低這一缺陷,論文提出了TwigStack算法的核心內容—PathStack算法的改進算法:LocalPathStack算法。以此為基礎,提出了一種適用于 XML流數(shù)據(jù)的新的算法: PathList算法,并根據(jù)所處理的XML流數(shù)據(jù)的特點,通過查詢根過濾方法優(yōu)化了這一算法。最后,通過對不同文件大小以及不同查詢路徑長度的比較實驗,驗證了PathLis