基于SLCA語義的不確定XML關(guān)鍵字查詢技術(shù)研究.pdf

1、近年來,XML數(shù)據(jù)的查詢技術(shù)已經(jīng)成為研究的熱點。根據(jù)查詢模式的不同, XML數(shù)據(jù)查詢分為XML結(jié)構(gòu)查詢和XML關(guān)鍵字查詢,但是對比XML結(jié)構(gòu)查詢,更多的用戶習(xí)慣于不需要專業(yè)領(lǐng)域知識的XML關(guān)鍵字查詢。隨著數(shù)據(jù)采集和處理技術(shù)的進步,真實世界中的大部分數(shù)據(jù)都是不確定的。不確定XML數(shù)據(jù)是近年來研究者們提出的一種新的不確定數(shù)據(jù)的表示形式,不確定XML數(shù)據(jù)已經(jīng)大量應(yīng)用到金融、電信、軍事等領(lǐng)域。目前對于不確定XML的關(guān)鍵字查詢的研究很少,并且由于

2、不確定XML關(guān)鍵字查詢的每一個結(jié)果都對應(yīng)一個概率值,所以用戶通常希望得到前k個概率值最大的結(jié)果。不確定XML的Top-k關(guān)鍵字查詢算法得到了廣泛的關(guān)注。
　　首先,已有的不確定XML關(guān)鍵字查詢都是基于棧結(jié)構(gòu)實現(xiàn)的,需要頻繁的進棧、出棧操作以及頻繁的字符串比較,時間效率低下。為了解決這一問題,本文提出一種基于動態(tài)Keyword數(shù)據(jù)倉的不確定XML關(guān)鍵字查詢算法PrList。算法首先初始化動態(tài)Keyword數(shù)據(jù)倉,然后自底向上、自左向

3、右遍歷Keyword數(shù)據(jù)倉中的節(jié)點求解SLCA節(jié)點,不需要進出棧和字符串的比較。其次,目前不確定XML的Top-k關(guān)鍵字查詢僅返回概率值排在前k的根節(jié)點,需要進一步的處理才能構(gòu)建滿足特定條件下的子樹,時間效率低下。為了解決這一問題,本文定義了一種新的基于最小相關(guān)聯(lián)通子樹的Top-k查詢語義SRCT-Top-k,SRCT-Top-k查詢返回概率值排在前k的最小相關(guān)聯(lián)通子樹。為了便于處理SRCT-Top-k查詢,對動態(tài)Keyword數(shù)據(jù)倉進

4、行了擴展,形成擴展動態(tài)Keyword數(shù)據(jù)倉,然后基于擴展動態(tài)Keyword數(shù)據(jù)倉提出了PrListTop-k算法來處理SRCT-Top-k查詢。PrListTop-k算法僅掃描一次擴展動態(tài)Keyword數(shù)據(jù)倉就能構(gòu)建滿足特定條件下的子樹,并且制定的過濾策略可以大量地減少中間結(jié)果。
　　本文進行了大量的對比實驗。通過設(shè)定不同的查詢條件,將提出的PrList算法與PrStack算法進行對比,并將提出的PrListTop-k算法與沒有過