基于Hole-Filler模型的XML流數(shù)據(jù)剪切分片和查詢處理技術(shù)研究.pdf

1、XML文檔具有比一般半結(jié)構(gòu)化數(shù)據(jù)更多描述信息的能力和手段，因此XML使得網(wǎng)絡(luò)在其應(yīng)用方面體現(xiàn)出強(qiáng)大的功能和靈活性。由于網(wǎng)絡(luò)中出現(xiàn)了XML數(shù)據(jù)流，針對(duì)它的查詢和處理成為了首先要解決的研究課題。本文是基于Hole-Filler模型，對(duì)XML文檔剪切策略以及查詢框架提出的XML分片數(shù)據(jù)流查詢處理研究。 由于數(shù)據(jù)流的不易預(yù)測(cè)性、無(wú)界性、多樣性等特性，使得數(shù)據(jù)流很難同步。為了達(dá)到同步的效果，并且滿足數(shù)據(jù)應(yīng)用中的時(shí)實(shí)性以及服務(wù)器對(duì)數(shù)據(jù)的重發(fā)

2、等要求，在傳統(tǒng)的數(shù)據(jù)流管理系統(tǒng)的體系結(jié)構(gòu)基礎(chǔ)上，產(chǎn)生了新的基于分片的數(shù)據(jù)流廣播模型XstreamCast。在這個(gè)模型中，服務(wù)器對(duì)數(shù)據(jù)流進(jìn)行無(wú)序廣播，為了記錄每個(gè)分片的相關(guān)性，Leonidas Fegaras等人提出了Hole-Filler模型(即基于剪切的XML數(shù)據(jù)流模型)。在模型中，filler所對(duì)應(yīng)的唯一標(biāo)識(shí)ID能夠記錄每個(gè)片段的相關(guān)性。首先參考了DP分片規(guī)則的算法。該算法的主導(dǎo)思想是將XML文檔樹(shù)中每層扇出大的非葉子節(jié)點(diǎn)作為一個(gè)片

3、段進(jìn)行剪切。第二種分片方法叫SP算法，它摒棄了一開(kāi)始就生成XML文檔樹(shù)的做法，采取了在SAX接口中將文檔進(jìn)行大塊剪切，在每一塊文檔中對(duì)進(jìn)行直接分片的方法。實(shí)驗(yàn)結(jié)果表明SP算法對(duì)寬樹(shù)型文檔的剪切性能最好，而且在增大分片粒度的同時(shí)，該算法也能保證管道的傳輸不受此變化的影響。 針對(duì)其中的SP算法生成的大量分片，在客戶端又提出了幾種查詢框架。 對(duì)XML流數(shù)據(jù)處理提出了一個(gè)查詢框架XFrag。在XFrag中，框架最大的優(yōu)點(diǎn)是能夠處理XQu

4、ery和節(jié)省內(nèi)存。但是XFrag的管道處理形式在維持關(guān)聯(lián)表的信息時(shí)仍舊會(huì)消耗掉大量?jī)?nèi)存。而且調(diào)度操作符也會(huì)增加查詢的處理時(shí)間。在相鄰的操作符中產(chǎn)生依靠性的時(shí)候它無(wú)法避免多余的操作符的大量操作。所以我們提出tid樹(shù)并且在其上通過(guò)消除多余的節(jié)點(diǎn)達(dá)到對(duì)tid樹(shù)的優(yōu)化。依據(jù)優(yōu)化的tid樹(shù)，提出了XFPro查詢框架，該框架可以更好的處理查詢，節(jié)省內(nèi)存。試驗(yàn)結(jié)果表明XFPro在處理時(shí)間和內(nèi)存上都比XFrag有效。 然而，無(wú)論是XFrag還是

5、XFPro，通過(guò)Hole-Filler模型里的簡(jiǎn)單編碼方式filler id和hole id的匹配來(lái)處理查詢?nèi)菀讓?dǎo)致查詢阻塞。這種編碼依據(jù)的是先序遍歷文檔得到的值，它可以直接找到兩個(gè)分片之間的父子關(guān)系，但是卻不能直接找到兩個(gè)分片的祖先后代關(guān)系。這是XFPro處理查詢的時(shí)候，無(wú)法加速查詢處理的主要原因。因此我們采用了范圍編碼的方法將其應(yīng)用到Hole-Filler模式中。并且提出了一系列技術(shù)來(lái)優(yōu)化查詢計(jì)劃包括線性模式優(yōu)化，TWig模式優(yōu)化和