基于有序?qū)Φ牟淮_定XML小枝模式查詢算法*

劉立新 王永平

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 包頭 014010)

基于有序?qū)Φ牟淮_定XML小枝模式查詢算法*

劉立新 王永平

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 包頭 014010)

隨著不確定數(shù)據(jù)的廣泛應(yīng)用,不確定數(shù)據(jù)管理成為一個(gè)重要的研究方向。針對目前不確定XML小枝模式查詢技術(shù)并沒有很好解決含父子關(guān)系的查詢,論文提出基于有序?qū)Φ腜roOPCTwig算法。該算法以有序?qū)Φ男问酱鎯Σ樵儤浜蚉-文檔,通過查詢樹標(biāo)簽流的流指針?biāo)腹?jié)點(diǎn)的有序?qū)蚉-文檔中該結(jié)點(diǎn)標(biāo)簽流中的節(jié)點(diǎn)有序?qū)磉M(jìn)行匹配進(jìn)行查詢。有效處理了不確定XML中的分布節(jié)點(diǎn)、查詢結(jié)果概率的計(jì)算。且在有序?qū)ζヅ鋾r(shí)不需要逐條掃描刪除,提高匹配速度。理論分析和實(shí)驗(yàn)結(jié)果證明了ProOPCTwig算法的查詢效率。

不確定XML數(shù)據(jù); P-文檔; 小枝模式; 父子關(guān)系; 有序?qū)?/p>

Class Number TP312.2

1 引言

不確定性數(shù)據(jù)在經(jīng)濟(jì)、軍事、物流、金融、電信等領(lǐng)域中普遍存在[1],離散型不確定數(shù)據(jù)通常是以一定概率出現(xiàn)的離散值,連續(xù)型不確定數(shù)據(jù)常用概率密度函數(shù)表示[2～3]。半結(jié)構(gòu)化數(shù)據(jù)XML以其靈活性、可擴(kuò)展性、自描述性等特點(diǎn)為不確定數(shù)據(jù)提供了更自然的表達(dá)方式。概率XML數(shù)據(jù)是近年來提出的一種新的不確定數(shù)據(jù)表示方法,目前應(yīng)用概率XML管理不確定數(shù)據(jù)已經(jīng)取得一系列的研究成果,包括概率XML數(shù)據(jù)模型、概率XML代數(shù)和查詢[4]、關(guān)鍵字查詢[5～6]、原型系統(tǒng)等內(nèi)容,其中概率XML小枝模式查詢是其中一個(gè)重要的分支。

不確定XML小枝模式查詢,即Twig Pattern查詢,是概率XML查詢處理的重要方法,目前大多算法是擴(kuò)展普通XML小枝模式查詢。文獻(xiàn)[7]根據(jù)查詢語義將小枝模式查詢分為布爾查詢語義、完全語義查詢和不完全語義查詢。文獻(xiàn)[8]擴(kuò)展區(qū)間編碼后使用整體小枝模式的方法查詢,需要存儲中間結(jié)果和歸并中間結(jié)果。考慮概率小的查詢結(jié)果可能沒有意義,文獻(xiàn)[9]擴(kuò)展杜威編碼查找大于一定概率閾值的小枝模式,采用兩步過濾策略加快查詢。文獻(xiàn)[10]擴(kuò)展杜威編碼查找概率值最大的Top-K小枝模式,并采用按概率大小對元素流進(jìn)行排序的方法來提高查詢效率。

上述關(guān)于概率XML小枝模式查詢算法并不能很好處理父子關(guān)系。在普通XML小枝模式查詢處理算法中,Twigstacklist算法[11]通過向前看的策略能較好地處理小枝模式中的父子關(guān)系,但當(dāng)分支結(jié)點(diǎn)含父子關(guān)系時(shí),仍有中間結(jié)果產(chǎn)生。陶[12～13]提出了基于有序?qū)Φ乃惴ㄌ幚砀缸雨P(guān)系,能克服Twigstacklist算法中存在的問題,但是有序?qū)ζヅ鋾r(shí)查找效率低。針對上述問題,本文提出基于有序?qū)Φ牟淮_定XML小枝模式查詢算法,重點(diǎn)研究基于有序?qū)μ幚砀怕蔢ML小枝模式查詢時(shí)分布節(jié)點(diǎn)的處理、查詢結(jié)果概率的計(jì)算以及有序?qū)ζヅ湫实奶岣叩葐栴}。最后通過大量實(shí)驗(yàn)分析了所提出的ProOPCTwig算法的效率。

2 相關(guān)知識

2.1 數(shù)據(jù)模型

目前概率XML數(shù)據(jù)模型主要包括P-文檔、PXDB、PXML、PrXML等,其中P-文檔是其他幾種模型的基礎(chǔ),目前大多數(shù)概率XML數(shù)據(jù)查詢處理都是基于P-文檔模型。

在P-文檔模型中有普通節(jié)點(diǎn)和分布式節(jié)點(diǎn)兩種類型的節(jié)點(diǎn)。每一個(gè)普通節(jié)點(diǎn)都有一個(gè)標(biāo)簽和一個(gè)唯一的標(biāo)識符,普通節(jié)點(diǎn)可能出現(xiàn)在樣本空間的文件中,分布式節(jié)點(diǎn)僅用于定義產(chǎn)生隨機(jī)文件的概率過程。分布式節(jié)點(diǎn)有[14]: 1) 獨(dú)立分布節(jié)點(diǎn)ind,其孩子節(jié)點(diǎn)在P-文檔樹中的存在互相獨(dú)立,互不影響。 2) 互斥分布節(jié)點(diǎn)mux,其孩子只能出現(xiàn)一個(gè),或者全部都不出現(xiàn)。 3) 事件驅(qū)動(dòng)節(jié)點(diǎn)cie,其孩子節(jié)點(diǎn)的存在是互相獨(dú)立的,每個(gè)節(jié)點(diǎn)的存在由外部事件變量e1,e2,…,en所決定,對應(yīng)一個(gè)外部事件。 4) 組合節(jié)點(diǎn)exp,它包含多個(gè)孩子節(jié)點(diǎn),可選擇不同的孩子節(jié)點(diǎn)組成exp節(jié)點(diǎn)集合,且所有孩子節(jié)點(diǎn)的存在概率和為1。 5) 確定型節(jié)點(diǎn)det,這種節(jié)點(diǎn)類型是上述四種節(jié)點(diǎn)類型的特例,它要求確定型節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)必須存在。 6) 連續(xù)概率分布節(jié)點(diǎn)cont,cont描述當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)分布情況符合哪種連續(xù)概率分布曲線,如二項(xiàng)分布、高斯分布和泊松分布等,存儲概率密度函數(shù)及其參數(shù)。在上述六種分布節(jié)點(diǎn)類型中,獨(dú)立分布節(jié)點(diǎn)和互斥分布節(jié)點(diǎn)類型所組成的模型應(yīng)用最為廣泛。

在P-文檔模型中概率值附加到文檔樹的邊上,各節(jié)點(diǎn)的概率依賴于其祖先的概率。一條邊e的權(quán)重,記為Pr(e),它表示分布節(jié)點(diǎn)選擇孩子節(jié)點(diǎn)的概率。在P-文檔中,一個(gè)節(jié)點(diǎn)Vi在文檔中出現(xiàn)的概率等于從根節(jié)點(diǎn)到節(jié)點(diǎn)Vi經(jīng)過的所有的邊的概率的乘積。圖1為一包含mux,ind兩種類型的分布節(jié)點(diǎn)的P-文檔,可表示為PrXMLmux,ind,節(jié)點(diǎn)B1出現(xiàn)的概率Pr(B1)=0.2*0.3=0.06。

圖1 P-文檔示例

2.2 不確定XML小枝模式查詢

不確定XML小枝模式查詢不僅需要在包含分布節(jié)點(diǎn)的概率XML數(shù)據(jù)中找出滿足小枝模式出現(xiàn)的所有匹配結(jié)果,而且同時(shí)還需要計(jì)算每個(gè)結(jié)果的概率值。為描述清晰,文中以帶下標(biāo)的大寫字母表示P-文檔中的元素節(jié)點(diǎn),以大寫字母表示小枝模式中的查詢節(jié)點(diǎn)。

定義1 不確定XML小枝模式查詢:給定一個(gè)小枝模式查詢Q=(V,E)和一個(gè)P-文檔D=(VD,ED),其中V和E分別表示小枝模式中的節(jié)點(diǎn)集合和邊集合,VD和ED分別表示P-文檔中的節(jié)點(diǎn)集合和邊集合。小枝模式匹配就是在D上匹配Q的過程,是Q中的查詢節(jié)點(diǎn)到D中的元素節(jié)點(diǎn)的映射過程,滿足以下條件:

1) 對于每一個(gè)查詢節(jié)點(diǎn)X∈V,VD中的元素節(jié)點(diǎn)Xi與X具有相同的標(biāo)簽名,且滿足X的謂詞約束。

2)VD中的元素節(jié)點(diǎn)Xi和Yj之間的關(guān)系必須滿足V中相應(yīng)查詢節(jié)點(diǎn)X和Y之間的結(jié)構(gòu)約束關(guān)系,如P-C關(guān)系、A-D關(guān)系。

3) 計(jì)算查詢結(jié)果出現(xiàn)的概率值。

圖2是XPath為R/A[/C]/B對應(yīng)的小枝模式Q′,Q′在圖1的P-文檔上的一個(gè)查詢結(jié)果是(R1,A2,B3,C2),出現(xiàn)的概率:0.5*0.6*0.5=0.15。而(R1,A2,B1,C1)不是查詢結(jié)果,因?yàn)锽1,C1是同一個(gè)互斥分布節(jié)點(diǎn)mux的孩子,不能同時(shí)存在。

圖2 小枝模式Q′

2.3 有序?qū)?/p>

定義2 結(jié)點(diǎn)有序?qū)?在查詢樹中,某個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)有序?qū)κ怯稍摻Y(jié)點(diǎn)和其父親結(jié)點(diǎn)按先后順序組成,記做(結(jié)點(diǎn),父親結(jié)點(diǎn)),沒有父親結(jié)點(diǎn)的設(shè)置父親結(jié)點(diǎn)為null。但在,在P-文檔中,分布節(jié)點(diǎn)不參與有序?qū)Φ拇鎯?則結(jié)點(diǎn)有序?qū)?結(jié)點(diǎn),從根結(jié)點(diǎn)到此結(jié)點(diǎn)的路徑上最近的普通結(jié)點(diǎn)),沒有父親結(jié)點(diǎn)的設(shè)置父親結(jié)點(diǎn)為null,例如:(A1,R1)。

定義3 查詢樹標(biāo)簽流:按后序遍歷查詢樹中結(jié)點(diǎn)的順序排列,由查詢樹中所有結(jié)點(diǎn)對應(yīng)的結(jié)點(diǎn)有序?qū)M成。例如在圖2中的Q′的標(biāo)簽流是(B,A),(C,A),(A,R),(R,null)。

定義4 元素結(jié)點(diǎn)標(biāo)簽流:在P-文檔中,一個(gè)元素結(jié)點(diǎn)標(biāo)簽流是指按先序遍歷P-文檔中該類型結(jié)點(diǎn)的順序排列,由所有該類型結(jié)點(diǎn)對應(yīng)的結(jié)點(diǎn)有序?qū)M成。例如Q′中A結(jié)點(diǎn)的元素結(jié)點(diǎn)標(biāo)簽流對應(yīng)P-文檔中的元素結(jié)點(diǎn)標(biāo)簽流為(A1,R1),(A2,R1),(A3,R1)。

3 基于有序?qū)Φ牟淮_定XML小枝模式查詢算法

3.1 數(shù)據(jù)存儲

為查詢樹建立一個(gè)查詢表Query(name,pname,pnum,flag,level),存放所有查詢結(jié)點(diǎn)的相關(guān)信息,采取查詢結(jié)點(diǎn)按層遍歷查詢樹并由底向上的順序進(jìn)入表。在表中,name表示當(dāng)前節(jié)點(diǎn)類型,pname表示其父節(jié)點(diǎn)類型,pnum表示父節(jié)點(diǎn)的分支數(shù),當(dāng)在表中同一父節(jié)點(diǎn)分支數(shù)不為1且出現(xiàn)次數(shù)等于分支數(shù)時(shí)flag值為當(dāng)前父節(jié)點(diǎn)類型,否則flag的值為null。level表示節(jié)點(diǎn)的層數(shù),根節(jié)點(diǎn)所在的層數(shù)為1。例如Q′對應(yīng)的查詢表如表1所示。

表1 Q′對應(yīng)的查詢表Query

為不同類型的節(jié)點(diǎn)分別建立文檔表Document(name,id,pname,pid,path,pro),存放其所有結(jié)點(diǎn)的信息,結(jié)點(diǎn)按照先序遍歷P-文檔的順序進(jìn)入表。其中,name和pname分別指當(dāng)前節(jié)點(diǎn)類型和其父節(jié)點(diǎn)類型,id指當(dāng)前節(jié)點(diǎn)的編號,pid指父節(jié)點(diǎn)的編號,path表示由父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)經(jīng)過的分布節(jié)點(diǎn),pro為父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的概率值。圖1中P-文檔對應(yīng)的文檔表如表2～表5所示。

表2 圖1中P-文檔R類型節(jié)點(diǎn)對應(yīng)的文檔表

表3 圖1中P-文檔A類型節(jié)點(diǎn)對應(yīng)的文檔表

表4 圖1中P-文檔B類型節(jié)點(diǎn)對應(yīng)的文檔表

表5 圖1中P-文檔C類型節(jié)點(diǎn)對應(yīng)的文檔表

3.2 算法描述

ProOPCTwig算法是基于上述查詢表和文檔表進(jìn)行查詢的,通過查詢樹標(biāo)簽流的流指針?biāo)腹?jié)點(diǎn)的有序?qū)蚉-文檔中該結(jié)點(diǎn)標(biāo)簽流中的節(jié)點(diǎn)有序?qū)磉M(jìn)行匹配進(jìn)行查詢。由于查詢表是按層遍歷由底向上入表的,保證了它之前的節(jié)點(diǎn)有序?qū)κ瞧ヅ涞?從而避免了無用結(jié)果的產(chǎn)生。例如,當(dāng)Q′標(biāo)簽流所指節(jié)點(diǎn)有序?qū)?B,A),在P-文檔中的節(jié)點(diǎn)有序?qū)?B1,A1)(B2,A1),(B3,A2),(B4,A3)(B5,A3),通過相應(yīng)的匹配方法進(jìn)行查詢。

查詢樹中結(jié)點(diǎn)分為葉子節(jié)點(diǎn)、根節(jié)點(diǎn)和中間結(jié)點(diǎn)。葉子節(jié)點(diǎn)在P-文檔對應(yīng)的查詢表中找到匹配的有序?qū)χ锌赡艽嬖跓o用的有序?qū)?這是因?yàn)榉植脊?jié)點(diǎn)mux的存在、以及其父親結(jié)點(diǎn)是否包含其應(yīng)該包含的所有葉子節(jié)點(diǎn)。而對于中間結(jié)點(diǎn),由于處理時(shí)先序遍歷查詢表,保證了在處理中間結(jié)點(diǎn)前已經(jīng)處理了其所有孩子節(jié)點(diǎn),可以根據(jù)中間結(jié)點(diǎn)是否包含了所有的應(yīng)該包含的孩子節(jié)點(diǎn),來刪除其孩子節(jié)點(diǎn)匹配時(shí)得到的有序?qū)χ械臒o用的有序?qū)?。對于根?jié)點(diǎn),只要保證其有所有的孩子節(jié)點(diǎn),即可以得到最后的匹配結(jié)果。

當(dāng)給定小枝模式Q和P-文檔,得到對應(yīng)的查詢表Query和文檔表,并得到Q的層數(shù)為m。ProOPCTwig算法主要步驟如下:

1) 指針P指向查詢表Query的第一個(gè)元素。

2) 找到與P指向元素name相等的節(jié)點(diǎn)對應(yīng)的文檔表,利用該文檔表進(jìn)行有序?qū)ζヅ?利用匹配結(jié)果初始化u。

3) 若P指向元素的flag不為null,P指針后移,找到與P指向元素name相等節(jié)點(diǎn)對應(yīng)文檔表,利用該文檔表中進(jìn)行有序?qū)ζヅ?并利用匹配結(jié)果初始化v,合并u和v得到新的u。

4) 重復(fù)3)將u加入中間結(jié)果鏈表Lm中,P指針后移。

5) 若P指向元素層數(shù)為m,重復(fù)2)～4);m=m-1。

6) (a)若P指向元素為葉子節(jié)點(diǎn),找到與P指向元素name相等的節(jié)點(diǎn)對應(yīng)的文檔表,利用該文檔表進(jìn)行有序?qū)ζヅ?利用匹配結(jié)果初始化x。(b)否則,P指向元素為中間節(jié)點(diǎn),找到與P指向元素name相等的節(jié)點(diǎn)對應(yīng)的文檔表,利用該文檔表進(jìn)行有序?qū)ζヅ?利用匹配結(jié)果初始化x,根據(jù)Lm+1中元素更新x。

7) 若P指向元素的flag不為null,P指針后移,找到與P指向元素中name相等節(jié)點(diǎn)對應(yīng)的文檔表。若P指向元素為葉子節(jié)點(diǎn),利用6)(a)初始化y,否則利用6)(b)初始化y;合并x,y得到新x。

8) 重復(fù)7),將x加入到中間鏈表Lm中,P指針后移。

9) 若P指向元素的層數(shù)m,重復(fù)6)～8);m=m-1。

10) 重復(fù)6)～9),直到P指向元素為空。

上述步驟中,1)～5)為處理第m層的節(jié)點(diǎn),每次合并u和v得到新的u繼續(xù)合并,結(jié)果保存在Lm中。6)開始由底層向上處理,(a)為中間層節(jié)點(diǎn)中葉子節(jié)點(diǎn)的情況(b)中間層節(jié)點(diǎn)中非葉子節(jié)點(diǎn)的情況,此時(shí)要考慮其上有父親節(jié)點(diǎn)匹配和下有孩子節(jié)點(diǎn)的匹配問題。7)～9)實(shí)現(xiàn)循環(huán)處理中間層節(jié)點(diǎn),直至根節(jié)點(diǎn)處理完畢,即查詢表為空為止。

算法中每當(dāng)合并節(jié)點(diǎn)時(shí),要考慮待處理的節(jié)點(diǎn)下面是否含有分布結(jié)點(diǎn)。如果含有ind節(jié)點(diǎn),則待處理節(jié)點(diǎn)的孩子節(jié)點(diǎn)可以同時(shí)出現(xiàn),可以繼續(xù)向上匹配;如果是mux節(jié)點(diǎn),說明待處理節(jié)點(diǎn)的孩子節(jié)點(diǎn)不可以同時(shí)出現(xiàn),停止關(guān)于此節(jié)點(diǎn)的查詢。

為提高匹配效率,結(jié)點(diǎn)在查詢過程中,為P-文檔中與它匹配的節(jié)點(diǎn)有序?qū)ash表并以有序?qū)χ懈附Y(jié)點(diǎn)的name和id為關(guān)鍵值。這樣,當(dāng)發(fā)現(xiàn)某個(gè)中間結(jié)點(diǎn)不包含它應(yīng)該包含的所有的孩子節(jié)點(diǎn)時(shí),可以刪除對應(yīng)的hash表中的幾條記錄,不用逐條掃描刪除記錄。

最后得到的每一個(gè)匹配結(jié)果都是以一定概率值出現(xiàn),此概率值可以通過文檔表中存儲的概率信息來計(jì)算,即為得到的有序?qū)Φ母怕实某朔e。

3.3 算法舉例

以圖1的P-文檔圖2的小枝模式Q′為例來說明ProOPCTwig算法的工作原理,執(zhí)行步驟如下:

1)P指針指向查詢表中(B,A),進(jìn)行有序?qū)?B,A)匹配。到B節(jié)點(diǎn)對應(yīng)的文檔表去進(jìn)行匹配,得:

A1(mux2,B1)(mux2,B2)

A2(ind1,B3)

A3(ind2,B4)(ind2,B5)

2) 此時(shí)flag為null,P指針繼續(xù)后移,進(jìn)行有序?qū)?C,A)匹配。到C節(jié)點(diǎn)對應(yīng)的文檔表去進(jìn)行匹配,得:

A1(mux2,C1)

A2(ind1,C2)

此時(shí)flag不為null,合并結(jié)果,得到中間結(jié)果A2(ind1,B3,C2),概率為0.3。

3)P指針繼續(xù)后移,進(jìn)行有序?qū)?A,R)匹配,A為中間節(jié)點(diǎn),到A節(jié)點(diǎn)對應(yīng)的文檔表去進(jìn)行匹配,得:

R1(mux1,A1)(mux1,A2)(mux1,A3)

此時(shí),R的所有孩子節(jié)點(diǎn)已經(jīng)匹配結(jié)束。需要尋找可以和2)得到的中間結(jié)果可以匹配的結(jié)果,可以得出R1(mux1,A2)可以匹配。在此合并,得R1(mux1,A2(ind1,B2,C2)),概率為0.15。

4)P指針繼續(xù)后續(xù),進(jìn)行有序?qū)?R,null)匹配,得到最終結(jié)果R1(A2,(B3,C2)),最終概率為0.15。

3.4 算法分析

ProOPCTwig算法可以輸出整個(gè)小枝模式的匹配結(jié)果。目前大多數(shù)算法都需要對P-文檔中結(jié)點(diǎn)進(jìn)行編碼和對查詢語句的解析,ProOPCTwig算法采用把P-文檔和查詢語句存入表格的方法,效率相當(dāng),所以這里不考慮構(gòu)造表的時(shí)間和空間開銷,只考慮算法的查詢效率。

有n個(gè)節(jié)點(diǎn)的小枝模式查詢,最壞的情況下,ProOPCTwig算法的時(shí)間復(fù)雜度與n個(gè)查詢節(jié)點(diǎn)對應(yīng)的元素節(jié)點(diǎn)標(biāo)簽流Tq的大小和最后匹配結(jié)果大小總和成線性關(guān)系,即O(|T1|+…+|Ten|+|output|)。ProOPCTwig算法的空間復(fù)雜度最壞的情況下是查詢樹標(biāo)簽流和他對應(yīng)元素節(jié)點(diǎn)標(biāo)簽流匹配節(jié)點(diǎn)的大小。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)分為有序?qū)ζヅ湫史治龊蚉roOPCTwig算法效率分析。實(shí)驗(yàn)的硬件環(huán)境為:CPU Inter(R) Core i3(3.2GHz),RAM為4G,操作系統(tǒng)為64位的Windows 7旗艦版SP-1,實(shí)驗(yàn)工具為Eclipse SDK 3.7.1,JDK 6.0。實(shí)驗(yàn)采用DBLP作為測試數(shù)據(jù)集,由于原始DBLP數(shù)據(jù)集不包括概率分布信息,根據(jù)文獻(xiàn)[15]中的方法對DBLP進(jìn)行轉(zhuǎn)換得到概率XML數(shù)據(jù)集。實(shí)驗(yàn)中使用五個(gè)不同的小枝模式查詢,查詢用例見表6。

表6 實(shí)驗(yàn)中用到的小枝模式查詢用列表

4.1 有序?qū)ζヅ湫蕦Ρ确治?/p>

為準(zhǔn)確分析有序?qū)ζヅ涞男?本文同時(shí)實(shí)現(xiàn)文獻(xiàn)[13]中的PCTwig算法。鑒于PCTwig算法是在普通XML中處理父子關(guān)系查詢并不需要計(jì)算查詢結(jié)果的概率,所以實(shí)驗(yàn)一和實(shí)驗(yàn)二采用原始的數(shù)據(jù)集DBLP;并且ProOPCTwig算法暫時(shí)除去和分布節(jié)點(diǎn)及概率處理相關(guān)部分(簡稱OPCTwig算法)。對比OPCTwig算法和PCTwig算法的查詢效率

實(shí)驗(yàn)一:采用原始DBLP數(shù)據(jù)集(大小為56.4M),小枝查詢模式變化(Q1～Q5)。對比測試OPCTwig算法和PCTwig算法的有序?qū)ζヅ湫?實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 不同查詢模式下兩算法運(yùn)行時(shí)間比較

實(shí)驗(yàn)二:采用原始DBLP數(shù)據(jù)集(大小變化),小枝模式查詢固定(以Q1為例),對比測試OPCTwig算法和PCTwig算法的有序?qū)ζヅ湫?實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同大小數(shù)據(jù)集下兩算法運(yùn)行時(shí)間比較

實(shí)驗(yàn)一測試在文檔相同而查詢模式不同情況下,兩算法的對比效率。實(shí)驗(yàn)二測試查詢模式相同(以Q1為例)而文檔大小不同時(shí),兩算法的效率?？梢钥闯鯫PCTwig算法查找速度明顯優(yōu)于PCTwig算法,這是因?yàn)镺PCTwig算法當(dāng)遇到不匹配的有序?qū)r(shí),可以同時(shí)刪除幾條記錄,而不需要逐條掃描刪除,提高了有序?qū)ζヅ湫省?/p>

4.2 ProOPCTwig算法的查詢效率分析

為測試ProOPCTwig算法在不確定XML數(shù)據(jù)中處理父子關(guān)系的查詢效率,實(shí)驗(yàn)數(shù)據(jù)集采用在DBLP數(shù)據(jù)集中隨機(jī)插入分布節(jié)點(diǎn)形成P-文檔。查詢時(shí)仍采用表6中的小枝模式。

實(shí)驗(yàn)三:采用轉(zhuǎn)換后的DBLP數(shù)據(jù)集。P-文檔大小固定(大小為56.4M),小枝查詢模式變化(Q1～Q5),測試ProOPCTwig算法的查詢效率,實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 不同查詢模式下ProOPCTwig算法的查詢效率

實(shí)驗(yàn)四:采用轉(zhuǎn)換后的DBLP數(shù)據(jù)集。P-文檔大小變化,小枝查詢模式固定(以Q1為例),測試ProOPCTwig算法的查詢效率,實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同大小文檔下ProOPCTwig算法的查詢效率

實(shí)驗(yàn)三和實(shí)驗(yàn)四分別在P-文檔相同而查詢語句不同,和P-文檔不同而查詢語句相同的情況下測試ProOPCTwig算法的查詢效率,實(shí)驗(yàn)結(jié)果表明ProOPCTwig算法能有效處理不確定XML中包含父子關(guān)系的小枝模式查詢。實(shí)驗(yàn)一、二和實(shí)驗(yàn)三、四的運(yùn)行時(shí)間相差很大,這是因?yàn)椴淮_定XML中分布節(jié)點(diǎn)的存在,使得符合條件的查詢結(jié)果減少。

5 結(jié)語

本文提出基于有序?qū)Φ牟淮_定XML小枝模式查詢算法ProOPCTwig。該算法不需要結(jié)構(gòu)連接和歸并操作,且在有序?qū)ζヅ鋾r(shí)可以同時(shí)刪除幾條數(shù)據(jù),而不需要逐條掃描,大大提高有序?qū)ζヅ湫?在處理不確定XML僅含父子關(guān)系的小枝模式查詢時(shí)非常有效的。該算法的局限性是只能處理含父子邊的小枝模式進(jìn)行查詢,下一步的工作目標(biāo)是: 1) 基于有序?qū)μ幚戆嫦群蟠P(guān)系的小枝模式; 2) 基于有序?qū)μ幚戆^詞的復(fù)雜的小枝模式查詢。

[1] 周傲英,金澈清,王國仁,等.不確定性數(shù)據(jù)管理技術(shù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2009,32(1):1-16. ZHOU Aoying, JIN Cheqing, WANG Guoren, et al. A Surey on the Management of Uncertain Data[J]. Chinese Journal of Computer,2009,32(1):1-16.

[2] 李文鳳,彭智勇,李德毅.不確定性Top-k查詢處理[J].軟件學(xué)報(bào),2012,26(3):1-19. LI Wenfeng, PENG Zhiyong, LI Deyi. Top-k Query Processing Techniques on Uncertain Data[J]. Journal of Software,2012,26(3):1-19.

[3] LI Jian, Amol Deshpande. Ranking Continuous Probabilistic Datasets[C]//Proceeding of the 36thInternational Conference on Very Large Data Bases.Singapore: VLDB Endowment,2010:13-17.

[4] 張曉琳,鄭珍珍,劉立新.連續(xù)概率XML數(shù)據(jù)查詢處理技術(shù)[J].計(jì)算機(jī)工程與科學(xué),2012,34(12):134-139. ZHANG Xiaolin, ZHENG Zhenzhen, LIU Lixin. Query Processing Techniques on Continuous Probabilistic XML Data[J]. Computer Engineering and Science,2012,34(12):134-139.

[5] 張晨靜,王曉玲,周傲英.基于概率的SCLA的XML過濾[J].計(jì)算機(jī)學(xué)報(bào),2014,37(9):1959-1971. ZHANG Chenjing, WANG Xiaoling, ZHOU Aoying. Filtering SLCA on Probabilistic XML[J]. Journal of Computers,2014,37(9):1959-1971.

[6] 周小平,史一民,張俊.概率XML文檔Top-k關(guān)鍵字并行檢索算法[J].計(jì)算機(jī)科學(xué),2013,40(3):232-236. ZHOU Xiaoping, SHI Yimin, ZHANG Jun. Parallel algorithm of Top-k keyword query on Probabilistic XML document[J]. Computer Science,2013,40(3):232-236.

[7] Benny Kimelfeld, Yehoshua Sagiv. Matching Twigs in Probabilistic XML[C]//Proceeding of the 33thInternational Conference on Very Large Data Bases. Vienna: VLDB Endowment,2007:23-28.

[8] LI Yawen, WANG Guoren, XIN Juanchang. Holistically Twig Matching in Probabilistic XML[C]//Proceedings of the 25th International Conference on Data Engineering. Shanghai: IEEE,2009:1649-1656.

[9] LIU Siqi, WANG Guoren. Boosting Twig Joins in Probabilistic XML[C]//Proceeding of the 22ed International Conference on Database and Expert Systems Applications. France: Springer-Verlag,2011:51-58.

[10] Bo Ning, LIU Chengfei, Jeffrey Xu Yu, et al. Matching Top-k Answers of Twig Patterns in Probabilistic XML[C]//Proceeding of the 15th International Conference on Database Systems for Advanced Applications. Tsukuba: Springer-Verlag,2010:125-139.

[11] LU Jiaheng, CHEN Ting, Ling T W. Efficient processing of XML twig patterns with parent child edges: A look-ahead approach[C]//Proc of the ACM conference on information and Knowledge Management. New York: ACM,2004:533-542.

[12] 王瑞,陶世群.一種基于有序?qū)Φ男≈δＪ狡ヅ渌惴╗J].計(jì)算機(jī)研究與發(fā)展,2009,46(Suppl.):69-73. WANG Rui, TAO Shiqun. A Match Algorithm for Twig Patterns Based on Ordered Pair[J]. Journal Of Computer Research and Development,2009,46(Suppl.):69-73.

[13] 王瑞,陶世群.一種基于有序?qū)Φ暮缸舆叺男≈δＪ狡ヅ渌惴╗J].計(jì)算機(jī)應(yīng)用,2009,10(3):2778-2780. WANG Rui, TAO Shiqun. Matching Algorithm for Twig Pattern with Parent-Child Edges based on ordered pair[J]. Journal of Computer Applications,2009,10(3):2778-2780.

[14] Nierman A, Jagadish H V. Probabilistic data in XML[C]//Proceeding of the 28th international conference on Very Large Data Bases, Hong Kong: Springer-Verlag,2002:646-657.

[15] Kimelfeld B, Sagiv Y. Modeling and querying probabilistic XML data[J]. SIGMOD Record,2008,37(4):69-77.

Matching Twig Patterns in Uncertain XML Based on Ordered Pair

LIU Lixin WANG Yongping

(Information Engineering School, Inner Mongolia University of Science and Technology, Baotou 014010)

As the current uncertain XML twig pattern queries do not solve the patent-child relationship effectively, this paper proposes ProOPCTwig algorithms based on ordered pair. The algorithm stores query tree and P-document by ordered pair. It compares the ordered pair of query tree pointed by pointer of stream nodes and the ordered pair with the same label in P-document to query. The main works include dealing with the distributed nodes effectively, calculating probability of every result, and improving efficiency of matching ordered pair. Theoretical analysis and experimental results prove the efficiency of ProOPCTwig.

uncertain XML data, P-document, twig pattern, patent-child relationship, ordered pair

2016年9月3日,

2016年10月17日

國家自然科學(xué)基金:連續(xù)不確定XML數(shù)據(jù)管理關(guān)鍵技術(shù)研究(編號:61163015);內(nèi)蒙古高等學(xué)?？茖W(xué)研究項(xiàng)目:云計(jì)算環(huán)境下海量XML數(shù)據(jù)關(guān)鍵字查詢處理技術(shù)研究(編號:NJZY143);內(nèi)蒙古科技大學(xué)創(chuàng)新基金(編號:2014QDL046)資助。

劉立新,女,碩士,講師,研究方向:數(shù)據(jù)挖掘,數(shù)據(jù)庫技術(shù)。

TP312.2

10.3969/j.issn.1672-9722.2017.03.018