不確定XML復(fù)雜Twig查詢(xún)處理技術(shù)研究.pdf

1、近年來(lái),隨著數(shù)據(jù)管理技術(shù)的飛速發(fā)展,人們對(duì)數(shù)據(jù)的認(rèn)知也在逐漸發(fā)生變化,研究者們突破對(duì)傳統(tǒng)數(shù)據(jù)的理想化定義,認(rèn)識(shí)到不確定性是數(shù)據(jù)的固有屬性。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展,一種結(jié)構(gòu)靈活的可擴(kuò)展標(biāo)記語(yǔ)言XML逐漸成為了數(shù)據(jù)存儲(chǔ)和信息傳遞的事實(shí)標(biāo)準(zhǔn),在Internet中扮演著越來(lái)越重要的角色。XML憑借其自身半結(jié)構(gòu)化、自描述性等特點(diǎn)突破傳統(tǒng)關(guān)系數(shù)據(jù)模型對(duì)數(shù)據(jù)模式的嚴(yán)格約束,更適用于對(duì)不確定性數(shù)據(jù)的描述。不確定XML管理技術(shù)越來(lái)越受到研究者們的關(guān)注。

2、目前大多數(shù)不確定XML查詢(xún)是基于結(jié)構(gòu)匹配和內(nèi)容查詢(xún),在現(xiàn)實(shí)世界中不確定XML查詢(xún)語(yǔ)義往往是比較復(fù)雜的,查詢(xún)模式不僅是簡(jiǎn)單的Twig查詢(xún),還有可能包括邏輯謂詞、通配符等來(lái)表達(dá)更豐富的查詢(xún)內(nèi)容。因此,如何處理不確定XML復(fù)雜Twig查詢(xún)成為亟待解決的問(wèn)題。
　　首先,通過(guò)大量分析總結(jié),針對(duì)目前已有的XML復(fù)雜Twig查詢(xún)處理算法并不適用于處理不確定XML復(fù)雜Twig查詢(xún),且查詢(xún)效率較低等問(wèn)題。提出針對(duì)包含邏輯謂詞AND、OR和NOT的

3、復(fù)雜Twig查詢(xún)匹配算法Prob-BooleanTwig,算法在REDewey編碼的基礎(chǔ)上,采用路徑索引聚集存儲(chǔ)具有相同路徑的節(jié)點(diǎn)編碼,加快葉子路徑匹配速度;查詢(xún)過(guò)程中僅需遍歷一次查詢(xún)模式,并根據(jù)謂詞類(lèi)型采取不同的匹配方式,有效提高了查詢(xún)效率。其次,針對(duì)不確定XML復(fù)雜Twig查詢(xún)中通配符匹配以及需要處理大量中間結(jié)果的問(wèn)題,提出一種優(yōu)化算法Prob-Boolean StarTwig,算法在原有路徑索引的基礎(chǔ)上設(shè)計(jì)LSPI索引,索引中增加

4、兄弟節(jié)點(diǎn)標(biāo)簽來(lái)提高AND和OR節(jié)點(diǎn)的匹配速度;提出路徑匹配有限狀態(tài)自動(dòng)機(jī),算法只需對(duì)查詢(xún)模式中的葉子節(jié)點(diǎn)進(jìn)行路徑匹配,通過(guò)路徑匹配有限狀態(tài)自動(dòng)機(jī)將通配符匹配問(wèn)題轉(zhuǎn)化成結(jié)構(gòu)匹配和層次約束問(wèn)題進(jìn)行處理;算法采用概率閾值、層次信息和路徑信息三層過(guò)濾的自底向上匹配策略,有效的過(guò)濾無(wú)用中間結(jié)果,減少算法在時(shí)間和空間上的消耗。
　　通過(guò)大量實(shí)驗(yàn)測(cè)試算法性能,控制變量主要包括文檔大小,概率閾值和查詢(xún)用例,實(shí)驗(yàn)在經(jīng)典DBLP數(shù)據(jù)集上隨機(jī)插入分布節(jié)