基于有序對的不確定XML小枝模式查詢算法*

劉立新 王永平

(內蒙古科技大學信息工程學院 包頭 014010)

基于有序對的不確定XML小枝模式查詢算法*

劉立新 王永平

(內蒙古科技大學信息工程學院 包頭 014010)

隨著不確定數據的廣泛應用,不確定數據管理成為一個重要的研究方向。針對目前不確定XML小枝模式查詢技術并沒有很好解決含父子關系的查詢,論文提出基于有序對的ProOPCTwig算法。該算法以有序對的形式存儲查詢樹和P-文檔,通過查詢樹標簽流的流指針所指節點的有序對和P-文檔中該結點標簽流中的節點有序對來進行匹配進行查詢。有效處理了不確定XML中的分布節點、查詢結果概率的計算。且在有序對匹配時不需要逐條掃描刪除,提高匹配速度。理論分析和實驗結果證明了ProOPCTwig算法的查詢效率。

不確定XML數據; P-文檔; 小枝模式; 父子關系; 有序對

Class Number TP312.2

1 引言

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

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

上述關于概率XML小枝模式查詢算法并不能很好處理父子關系。在普通XML小枝模式查詢處理算法中,Twigstacklist算法[11]通過向前看的策略能較好地處理小枝模式中的父子關系,但當分支結點含父子關系時,仍有中間結果產生。陶[12～13]提出了基于有序對的算法處理父子關系,能克服Twigstacklist算法中存在的問題,但是有序對匹配時查找效率低。針對上述問題,本文提出基于有序對的不確定XML小枝模式查詢算法,重點研究基于有序對處理概率XML小枝模式查詢時分布節點的處理、查詢結果概率的計算以及有序對匹配效率的提高等問題。最后通過大量實驗分析了所提出的ProOPCTwig算法的效率。

2 相關知識

2.1 數據模型

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

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

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

圖1 P-文檔示例

2.2 不確定XML小枝模式查詢

不確定XML小枝模式查詢不僅需要在包含分布節點的概率XML數據中找出滿足小枝模式出現的所有匹配結果,而且同時還需要計算每個結果的概率值。為描述清晰,文中以帶下標的大寫字母表示P-文檔中的元素節點,以大寫字母表示小枝模式中的查詢節點。

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

1) 對于每一個查詢節點X∈V,VD中的元素節點Xi與X具有相同的標簽名,且滿足X的謂詞約束。

2)VD中的元素節點Xi和Yj之間的關系必須滿足V中相應查詢節點X和Y之間的結構約束關系,如P-C關系、A-D關系。

3) 計算查詢結果出現的概率值。

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

圖2 小枝模式Q′

2.3 有序對

定義2 結點有序對:在查詢樹中,某個結點的結點有序對是由該結點和其父親結點按先后順序組成,記做(結點,父親結點),沒有父親結點的設置父親結點為null。但在,在P-文檔中,分布節點不參與有序對的存儲,則結點有序對為(結點,從根結點到此結點的路徑上最近的普通結點),沒有父親結點的設置父親結點為null,例如:(A1,R1)。

定義3 查詢樹標簽流:按后序遍歷查詢樹中結點的順序排列,由查詢樹中所有結點對應的結點有序對組成。例如在圖2中的Q′的標簽流是(B,A),(C,A),(A,R),(R,null)。

定義4 元素結點標簽流:在P-文檔中,一個元素結點標簽流是指按先序遍歷P-文檔中該類型結點的順序排列,由所有該類型結點對應的結點有序對組成。例如Q′中A結點的元素結點標簽流對應P-文檔中的元素結點標簽流為(A1,R1),(A2,R1),(A3,R1)。

3 基于有序對的不確定XML小枝模式查詢算法

3.1 數據存儲

為查詢樹建立一個查詢表Query(name,pname,pnum,flag,level),存放所有查詢結點的相關信息,采取查詢結點按層遍歷查詢樹并由底向上的順序進入表。在表中,name表示當前節點類型,pname表示其父節點類型,pnum表示父節點的分支數,當在表中同一父節點分支數不為1且出現次數等于分支數時flag值為當前父節點類型,否則flag的值為null。level表示節點的層數,根節點所在的層數為1。例如Q′對應的查詢表如表1所示。

表1 Q′對應的查詢表Query

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

表2 圖1中P-文檔R類型節點對應的文檔表

表3 圖1中P-文檔A類型節點對應的文檔表

表4 圖1中P-文檔B類型節點對應的文檔表

表5 圖1中P-文檔C類型節點對應的文檔表

3.2 算法描述

ProOPCTwig算法是基于上述查詢表和文檔表進行查詢的,通過查詢樹標簽流的流指針所指節點的有序對和P-文檔中該結點標簽流中的節點有序對來進行匹配進行查詢。由于查詢表是按層遍歷由底向上入表的,保證了它之前的節點有序對是匹配的,從而避免了無用結果的產生。例如,當Q′標簽流所指節點有序對為(B,A),在P-文檔中的節點有序對為(B1,A1)(B2,A1),(B3,A2),(B4,A3)(B5,A3),通過相應的匹配方法進行查詢。

查詢樹中結點分為葉子節點、根節點和中間結點。葉子節點在P-文檔對應的查詢表中找到匹配的有序對中可能存在無用的有序對,這是因為分布節點mux的存在、以及其父親結點是否包含其應該包含的所有葉子節點。而對于中間結點,由于處理時先序遍歷查詢表,保證了在處理中間結點前已經處理了其所有孩子節點,可以根據中間結點是否包含了所有的應該包含的孩子節點,來刪除其孩子節點匹配時得到的有序對中的無用的有序對。對于根節點,只要保證其有所有的孩子節點,即可以得到最后的匹配結果。

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

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

2) 找到與P指向元素name相等的節點對應的文檔表,利用該文檔表進行有序對匹配,利用匹配結果初始化u。

3) 若P指向元素的flag不為null,P指針后移,找到與P指向元素name相等節點對應文檔表,利用該文檔表中進行有序對匹配,并利用匹配結果初始化v,合并u和v得到新的u。

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

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

6) (a)若P指向元素為葉子節點,找到與P指向元素name相等的節點對應的文檔表,利用該文檔表進行有序對匹配,利用匹配結果初始化x。(b)否則,P指向元素為中間節點,找到與P指向元素name相等的節點對應的文檔表,利用該文檔表進行有序對匹配,利用匹配結果初始化x,根據Lm+1中元素更新x。

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

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

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

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

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

算法中每當合并節點時,要考慮待處理的節點下面是否含有分布結點。如果含有ind節點,則待處理節點的孩子節點可以同時出現,可以繼續向上匹配;如果是mux節點,說明待處理節點的孩子節點不可以同時出現,停止關于此節點的查詢。

為提高匹配效率,結點在查詢過程中,為P-文檔中與它匹配的節點有序對建立hash表并以有序對中父結點的name和id為關鍵值。這樣,當發現某個中間結點不包含它應該包含的所有的孩子節點時,可以刪除對應的hash表中的幾條記錄,不用逐條掃描刪除記錄。

最后得到的每一個匹配結果都是以一定概率值出現,此概率值可以通過文檔表中存儲的概率信息來計算,即為得到的有序對的概率的乘積。

3.3 算法舉例

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

1)P指針指向查詢表中(B,A),進行有序對(B,A)匹配。到B節點對應的文檔表去進行匹配,得:

A1(mux2,B1)(mux2,B2)

A2(ind1,B3)

A3(ind2,B4)(ind2,B5)

2) 此時flag為null,P指針繼續后移,進行有序對(C,A)匹配。到C節點對應的文檔表去進行匹配,得:

A1(mux2,C1)

A2(ind1,C2)

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

3)P指針繼續后移,進行有序對(A,R)匹配,A為中間節點,到A節點對應的文檔表去進行匹配,得:

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

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

4)P指針繼續后續,進行有序對(R,null)匹配,得到最終結果R1(A2,(B3,C2)),最終概率為0.15。

3.4 算法分析

ProOPCTwig算法可以輸出整個小枝模式的匹配結果。目前大多數算法都需要對P-文檔中結點進行編碼和對查詢語句的解析,ProOPCTwig算法采用把P-文檔和查詢語句存入表格的方法,效率相當,所以這里不考慮構造表的時間和空間開銷,只考慮算法的查詢效率。

有n個節點的小枝模式查詢,最壞的情況下,ProOPCTwig算法的時間復雜度與n個查詢節點對應的元素節點標簽流Tq的大小和最后匹配結果大小總和成線性關系,即O(|T1|+…+|Ten|+|output|)。ProOPCTwig算法的空間復雜度最壞的情況下是查詢樹標簽流和他對應元素節點標簽流匹配節點的大小。

4 實驗結果與分析

實驗分為有序對匹配效率分析和ProOPCTwig算法效率分析。實驗的硬件環境為:CPU Inter(R) Core i3(3.2GHz),RAM為4G,操作系統為64位的Windows 7旗艦版SP-1,實驗工具為Eclipse SDK 3.7.1,JDK 6.0。實驗采用DBLP作為測試數據集,由于原始DBLP數據集不包括概率分布信息,根據文獻[15]中的方法對DBLP進行轉換得到概率XML數據集。實驗中使用五個不同的小枝模式查詢,查詢用例見表6。

表6 實驗中用到的小枝模式查詢用列表

4.1 有序對匹配效率對比分析

為準確分析有序對匹配的效率,本文同時實現文獻[13]中的PCTwig算法。鑒于PCTwig算法是在普通XML中處理父子關系查詢并不需要計算查詢結果的概率,所以實驗一和實驗二采用原始的數據集DBLP;并且ProOPCTwig算法暫時除去和分布節點及概率處理相關部分(簡稱OPCTwig算法)。對比OPCTwig算法和PCTwig算法的查詢效率

實驗一:采用原始DBLP數據集(大小為56.4M),小枝查詢模式變化(Q1～Q5)。對比測試OPCTwig算法和PCTwig算法的有序對匹配效率,實驗結果如圖3所示。

圖3 不同查詢模式下兩算法運行時間比較

實驗二:采用原始DBLP數據集(大小變化),小枝模式查詢固定(以Q1為例),對比測試OPCTwig算法和PCTwig算法的有序對匹配效率,實驗結果如圖4所示。

圖4 不同大小數據集下兩算法運行時間比較

實驗一測試在文檔相同而查詢模式不同情況下,兩算法的對比效率。實驗二測試查詢模式相同(以Q1為例)而文檔大小不同時,兩算法的效率。可以看出OPCTwig算法查找速度明顯優于PCTwig算法,這是因為OPCTwig算法當遇到不匹配的有序對時,可以同時刪除幾條記錄,而不需要逐條掃描刪除,提高了有序對匹配效率。

4.2 ProOPCTwig算法的查詢效率分析

為測試ProOPCTwig算法在不確定XML數據中處理父子關系的查詢效率,實驗數據集采用在DBLP數據集中隨機插入分布節點形成P-文檔。查詢時仍采用表6中的小枝模式。

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

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

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

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

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

5 結語

本文提出基于有序對的不確定XML小枝模式查詢算法ProOPCTwig。該算法不需要結構連接和歸并操作,且在有序對匹配時可以同時刪除幾條數據,而不需要逐條掃描,大大提高有序對匹配效率,在處理不確定XML僅含父子關系的小枝模式查詢時非常有效的。該算法的局限性是只能處理含父子邊的小枝模式進行查詢,下一步的工作目標是: 1) 基于有序對處理包含祖先后代關系的小枝模式; 2) 基于有序對處理包含謂詞的復雜的小枝模式查詢。

[1] 周傲英,金澈清,王國仁,等.不確定性數據管理技術研究綜述[J].計算機學報,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].軟件學報,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] 張曉琳,鄭珍珍,劉立新.連續概率XML數據查詢處理技術[J].計算機工程與科學,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].計算機學報,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關鍵字并行檢索算法[J].計算機科學,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] 王瑞,陶世群.一種基于有序對的小枝模式匹配算法[J].計算機研究與發展,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] 王瑞,陶世群.一種基于有序對的含父子邊的小枝模式匹配算法[J].計算機應用,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日

國家自然科學基金:連續不確定XML數據管理關鍵技術研究(編號:61163015);內蒙古高等學校科學研究項目:云計算環境下海量XML數據關鍵字查詢處理技術研究(編號:NJZY143);內蒙古科技大學創新基金(編號:2014QDL046)資助。

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

TP312.2

10.3969/j.issn.1672-9722.2017.03.018