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

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

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

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

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