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

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

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

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