不確定XML復雜Twig查詢處理技術研究.pdf

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

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

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

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