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

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

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

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

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