張曉琳，王 鵬

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

0 引 言

由于概率信息需要特殊處理，以往針對普通XML的小枝模式匹配方法［1，2］并不能直接應(yīng)用到不確定XML上，這就引發(fā)了不確定XML中小枝模式匹配等價性的研究。

目前，實現(xiàn)不確定XML小枝模式匹配的方法有二元結(jié)構(gòu)連接和整體匹配兩種。二元結(jié)構(gòu)連接［3］會產(chǎn)生大量無用的中間結(jié)果，影響查詢的效率。整體匹配的方法［4－7］由于查詢過程過于集中，概率信息需要進行單獨處理，對查詢效率也有一定的影響。本文將序列匹配應(yīng)用到不確定XML小枝模式匹配，可以避免二元結(jié)構(gòu)連接中繁復(fù)的結(jié)構(gòu)連接操作，并可以在查詢中對概率信息進行統(tǒng)一處理。具體使用的是序列匹配中經(jīng)典的LCS－TRIM算法［8］，所做的主要工作如下：①針對不確定XML中模式樹序列化等價性和子序列匹配等價性進行分析和證明，消除了假不予考慮。②針對不確定XML中結(jié)構(gòu)過濾等價性進行分析和證明，消除了假警報。③通過實驗驗證了不確定XML序列匹配算法的等價性及其效率。

1 相關(guān)定義

定義1 小枝模式匹配 （twig pattern matching），給定一個Twig Query查詢Q＝ （VQ，EQ）和一個XML數(shù)據(jù)庫D＝ （VD，ED），在D上匹配Q的過程就是Q的查詢節(jié)點到D 的元素節(jié)點的映射過程h：｛u：u∈Q｝→｛x：x∈D｝，滿足下列條件：

（1）對每一個查詢節(jié)點u∈Q，D的元素節(jié)點h（u）與u具有相同的TagName，且滿足u的謂詞要求；

（2）對Q中的每一條邊E（u，v），D的元素節(jié)點h（u）是h（v）的祖先 （或者父親）。

定義2 模式樹 （pattern tree），一個模式樹定義為P＝（T，F(xiàn)），其中T＝ （V，E）是一個節(jié)點標記和邊標記的樹，F(xiàn)是一個布爾式，并有：

（1）V中的每個節(jié)點標記了一個唯一的整數(shù)；

（2）E中的每條邊標記了pc（表示父子關(guān)系）或ad（表示祖先后裔關(guān)系）；

（3）F是作用在節(jié)點上的謂詞的布爾組合。

定義3 嵌入 （embedding），令P＝ （T，F(xiàn)）為一個模式，C為一個樹的集合。從P到C的嵌入是從T中的節(jié)點到C中節(jié)點的一個完全映射h：P→C，滿足：

（1）h保持了T中的結(jié)構(gòu)關(guān)系，即只要h定義在節(jié)點u和v上面，如果 （u，v）是一條pc（或ad）邊，那么h（v）是h（u）的孩子 （或后裔）；

（2）h的映像滿足布爾式F。

定義4 實例樹，witness tree.令C是樹的集合，P＝（T，F(xiàn)）是一個模式樹，h：P→C是一個嵌入，則實例樹如下定義：

（1）如果節(jié)點n根據(jù)映射h匹配某個模式樹節(jié)點，則n在實例樹中；

（2）對實例樹中的任意一對節(jié)點n和m，只要在所有實例樹節(jié)點中，根據(jù)C，m是n最近的祖先，則實例樹中包含邊 （m，n）；

（3）實例樹保持了C中節(jié)點的次序。

從定義1可以看出，小枝模式匹配只是限定了實例樹中節(jié)點的父子關(guān)系和祖先后裔關(guān)系，并沒有限定節(jié)點的兄弟關(guān)系。在LCS－TRIM算法中，由于序列匹配自身的特點限定了實例樹中節(jié)點兄弟之間的關(guān)系，查詢結(jié)果稱為嵌入子樹。

定義5 嵌入子樹 （embedded subtree），限定節(jié)點兄弟關(guān)系的實例樹稱為嵌入子樹。

通過模式樹序列化可以將嵌入子樹與實例樹統(tǒng)一，詳見2.1節(jié)。

序列匹配最重要的是匹配結(jié)果等價性問題，有兩種情況可能導(dǎo)致匹配結(jié)果不等價，分別是假警報和假不予考慮。

設(shè)D為XML文檔，Q為查詢，g為序列化方法。

定義6 假警報 （false alarm），g（Q）在g（D）中能找到一個匹配的子序列，但是Q在D中卻找不到對應(yīng)的樹片段。

定義7 假不予考慮 （false dismissal），g（Q）在g（D）中不能找到一個匹配的子序列，但是實際上Q在D中有對應(yīng)的樹片段。

2 序列匹配等價性

2.1 模式樹序列化等價性

不確定XML小枝模式匹配輸入的模式樹可以用路徑表達式來描述，其中 “／”表示父子關(guān)系， “／／”表示祖先后裔關(guān)系。如圖1所示的模式樹可以用路徑表達式R ［A／B］／／C來描述。序列化方法中模式樹的每個節(jié)點描述為 （postorder，tag，ppostorder，R），其中postorder為節(jié)點在模式樹中的后序遍歷編號，tag為節(jié)點的內(nèi)容，ppostorder為該節(jié)點父節(jié)點的postorder。R表示該節(jié)點與上下文節(jié)點之間的關(guān)系，R＝ “pc”表示父子關(guān)系，R＝“ad”表示祖先后關(guān)系。

圖1 模式樹

定義1只限定了父子關(guān)系和祖先后裔關(guān)系，并沒有限定兄弟之間的關(guān)系，因此路徑表達式R ［A／B］／／C實際對應(yīng)5種模式樹，如圖2所示。

圖2 R ［A／B］／／C對應(yīng)的模式樹

一個帶有分支結(jié)構(gòu)和祖先后裔關(guān)系的路徑表達式對應(yīng)多個模式樹，如果查詢時只針對一種模式樹進行序列化，只能得到部分結(jié)果，那么就存在假不予考慮，所以要進行正確的查詢必須將路徑表達式對應(yīng)的所有模式樹進行序列化。如圖2 （a）序列化為 （1，B，2，pc）， （2，A，4，pc），（3，C，4，ad）， （4，R，－，－），圖2 （b）序列化為（1，C，2，ad）， （2，B，3，pc）， （3，A，4，pc）， （4，R，－，－），圖2 （c）序列化為 （1，C，4，ad），（2，B，3，pc），（3，A，4，pc）， （4，R，－，－），圖2 （d）序列化為（1，B，3，pc）， （2，C，3，ad）， （3，A，4，pc）， （4，R，－，－），圖2 （e）序列化為 （1，C，3，ad），（2，B，3，pc），（3，A，4，pc）， （4，R，－，－），查詢的結(jié)果取它們的并集。與其它的查詢處理方法相比列舉出路徑表達式所對應(yīng)的所有模式樹需要額外的工作量，這也是序列匹配方法的缺陷，但在實際應(yīng)用中這種缺陷并不存在。

定理1 對于有序文檔并不需要針對所有的模式樹結(jié)構(gòu)進行查詢，只需查詢一種符合DTD結(jié)構(gòu)的模式樹就能得到所有的結(jié)果。

證明：通過對來自實際應(yīng)用中的眾多數(shù)據(jù)集進行分析發(fā)現(xiàn)，數(shù)據(jù)集中元素的出現(xiàn)次序是有序的。以具有普遍代表性的SIGMOD Record數(shù)據(jù)集［9］為例，如圖3所示，先出現(xiàn)元素title，然后出現(xiàn)元素initPage，最后出現(xiàn)元素end－Page，當title、initPage和endPage再次出現(xiàn)時依然按照這個次序，其它的元素同樣也是有序的。因此圖2（a）與圖2（c）不會同時出現(xiàn)，因為在實際XML文檔中節(jié)點A或者出現(xiàn)在節(jié)點C前面，或者出現(xiàn)在節(jié)點C后面，只存在一種順序，同理圖2（d）與圖2（e）也不會同時出現(xiàn)。

圖3 SIGMOD Record數(shù)據(jù)集片段

在實際應(yīng)用的XML文檔中元素的嵌套也是有序的 （依據(jù)DTD），如圖3所示，元素articles是元素authors的父節(jié)點，元素authors是元素author的父節(jié)點，當元素articles、authors和author再次出現(xiàn)時，仍然按照這個關(guān)系進行嵌套，其它具有嵌套關(guān)系的元素也是有序的。因此在一個文檔中圖2（a）、圖2（b）與圖2（d）不會同時出現(xiàn)，因為在實際的XML文檔中節(jié)點A、B、C只存在一種嵌套關(guān)系。證畢。

綜上，根據(jù)定理1在實際的文檔中圖2所示的5種模式樹結(jié)構(gòu)只能出現(xiàn)一種，如果在路徑表達式中限定兄弟關(guān)系，那么圖2（a）對應(yīng)的路徑表達式為R ［A／B］／／C，圖2（b）對應(yīng)的路徑表達式為R／A／B／／C，圖2（c）對應(yīng)的路徑表達式為R ［／／C］A／B，圖2 （d）對應(yīng)的路徑表達式為 R／A［B］［／／C］，圖2 （e）對應(yīng)的路徑表達式為 R／A ［／／C］［B］，這樣應(yīng)用到序列匹配中就能更明確查詢的結(jié)構(gòu)。

2.2 子序列匹配等價性

定義8 子序列 （subsequence），某個序列的子序列是從最初序列通過去除某些元素但不破壞余下元素的相對位置而形成的新序列。

定理2 子序列匹配在不確定XML和普通XML中是等價的，即不含假不予考慮。

證明：L文檔與普通XML文檔相比加入了概率分布節(jié)點，但加入概率分布節(jié)點之后并不改變后序遍歷文檔樹所生成的LS序列 （label sequence）和 NPS序列 （numbered prüfer sequence）中節(jié)點的順序。因為后序遍歷的順序是“左右根”，加入概率分布節(jié)點之后不會改變原XML文檔中節(jié)點的兄弟關(guān)系 （“左右根”中的 “左”和 “右”的關(guān)系），即在原文檔中為某節(jié)點左兄弟的節(jié)點在加入概率分布節(jié)點之后不會變成該節(jié)點的右兄弟。加入概率分布節(jié)點之后也不會改變原XML文檔中節(jié)點的祖先后裔關(guān)系 （“左右根”中的 “左右”和 “根”的關(guān)系），即原文檔中某節(jié)點的后裔節(jié)點在加入概率分布節(jié)點之后不會變成該節(jié)點的祖先節(jié)點，因此子序列匹配在不確定XML和普通XML中是等價的。證畢。

2.3 結(jié)構(gòu)過濾等價性

子序列匹配的結(jié)果只是模式樹內(nèi)容的匹配，一些結(jié)果的結(jié)構(gòu)并不符合模式樹的結(jié)構(gòu)，所以要進行結(jié)構(gòu)過濾篩選出結(jié)構(gòu)符合模式樹的最終結(jié)果，消除假警報。

算法：結(jié)構(gòu)過濾

輸入：序列化文檔樹Dtree，序列化模式樹Ptree

輸出：實例樹Wtree

定理3 結(jié)構(gòu)過濾在不確定XML和普通XML中是等價的，即可以消除假警報。

證明：結(jié)構(gòu)過濾的主要思想是模式樹中兩個相鄰節(jié)點與子序列匹配結(jié)果n元組中對應(yīng)的兩個相鄰節(jié)點的結(jié)構(gòu)進行對比。普通XML文檔與不確定XML文檔結(jié)構(gòu)過濾的差異只存在于當模式樹中兩個相鄰節(jié)點為父子關(guān)系時 （對應(yīng)結(jié)構(gòu)過濾算法4～15行），這時n元組中對應(yīng)的兩個相鄰節(jié)點除了可以是父子關(guān)系，還可以是只包含概率分布節(jié)點的祖先后裔關(guān)系，這樣就可以利用原來的結(jié)構(gòu)過濾算法把概率分布節(jié)點當作普通節(jié)點來處理。因此結(jié)構(gòu)過濾在不確定XML和普通XML中是等價的。證畢。

3 實 驗

實驗中的程序采用Java語言實現(xiàn)，實驗環(huán)境為PC機，Windows XP平臺，主頻2.0GHz，奔騰雙核處理器，內(nèi)存2GB。實驗所采用的數(shù)據(jù)集是在University Courses數(shù)據(jù)集［10］中的reed.xml（里德學(xué)院的課程信息）結(jié)構(gòu)基礎(chǔ)上隨機插入概率分布節(jié)點以及概率值生成的不確定數(shù)據(jù)集。實驗中使用的reed.xml大小為138KB，加入概率分布節(jié)點之后的reed.xml大小為145KB，通過反復(fù)疊加后形成的不確定XML文檔大小為58MB。實驗所用的查詢語句見表1。實驗中將LCS－TRIM算法應(yīng)用到普通XML文檔 （記為XML）和不確定XML文檔（記為PrXML），對2.2節(jié)定理2和2.3節(jié)定理3進行驗證，并與文獻 ［6］中Holistic Twig算法的效率進行對比。

表1 實驗用到的查詢語句

算法的查詢效率對比如圖4所示，在相同大小的PrXML（58MB）下，對于不同的查詢語句 （Q1～Q5），LCS－TRIM算法的效率都高于Holistic Twig算法，這是因為LCS－TRIM算法將概率分布節(jié)點當作普通節(jié)點來處理，統(tǒng)一的操作提高了查詢效率。子序列匹配等價性如圖5所示，對于不同的查詢語句 （Q1～Q5），在PrXML （145KB）和XML（138KB）中子序列匹配得到的相應(yīng)結(jié)果數(shù)量是相等的。結(jié)構(gòu)過濾等價性如圖6所示，對于不同的查詢語句（Q1～Q5），在 PrXML （145KB）和 XML （138KB）中結(jié)構(gòu)過濾得到的相應(yīng)結(jié)果數(shù)量也是相等的。說明序列匹配應(yīng)用到不確定XML與普通XML是等價的。

圖4 查詢效率對比

圖5 子序列匹配等價性

圖6 結(jié)構(gòu)過濾等價性

4 結(jié)束語

本文將序列匹配的方法應(yīng)用到不確定XML小枝模式匹配，并對不確定XML中序列匹配的假警報和假不予考慮問題進行分析和證明，為不確定XML序列匹配提供了一定的理論依據(jù)。理論分析和實驗結(jié)果表明不確定XML中序列匹配的假警報和假不予考慮問題同樣可以消除，序列匹配應(yīng)用到不確定XML與普通XML是等價的。在不確定XML中，序列匹配算法與整體匹配算法Holistic Twig相比，效率更高。下一步將根據(jù)不確定XML的特點對序列匹配算法LCS－TRIM進行優(yōu)化，進一步提高不確定XML序列匹配算法的效率。

［1］Chen S，Li H G，Tatemura J，et al.Twig 2stack：Bottomup processing of generalized－tree－pattern queries over XML documents ［C］／／Proceedings of the 32nd International Conference on Very Large Data Bases.New York：ACM Press，2006：283－294.

［2］Qin L，Yu J X，Ding B.TwigList：Make twig pattern matching fast ［C］／／Proceedings of the 12th International Conference on Database Systems for Advanced Applications.Berlin：Springer－Verlag，2007：850－862.

［3］Yun J H，Chung C W.Efficient probabilistic XML query processing using an extended labeling scheme and a lightweight index ［J］.Information Processing ＆ Management，2012，48（6）：1181－1202.

［4］ZHANG Xiaolin，LV Qing，LIU Lixin，et al.An efficient algorithm of continuous uncertain XML twig pattern matching［J］.Application Research of Computers，2013，30 （2）：364－366（in Chinese）.［張曉琳，呂慶，劉立新，等.一種高效的連續(xù)不確定XML小枝模式匹配算法 ［J］.計算機應(yīng)用研究，2013，30 （2）：364－366.］

［5］LIU Lixin，ZHANG Xiaolin，LV Qing，et al.Matching twig patterns in uncertain XML without merging ［J］.Computer Science，2013，40 （5）：198－200 （in Chinese）. ［劉立新，張曉琳，呂慶，等.一種非歸并不確定XML小枝模式查詢算法［J］.計算機科學(xué)，2013，40 （5）：198－200.］

［6］LI Yawen.Study on Holistically Twig matching algorithm over probabilistic XMLs ［D］.Shenyang：Northeastern University，2009 （in Chinese）.［李亞文.概率 XML文檔中 Holistic Twig查詢處理算法的研究與實現(xiàn) ［D］.沈陽：東北大學(xué)，2009.］

［7］LIU Pan.Study on Twig matching algorithm over probabilistic XMLs ［D］.Shenyang：Northeastern University，2010 （in Chinese）.［劉潘.概率XML文檔中Twig查詢處理算法的研究與實現(xiàn) ［D］.沈陽：東北大學(xué)，2010.］

［8］Tatikonda S，Parthasarathy S，Goyder M.LCS－TRIM：Dynamic programming meets XML indexing and querying ［C］／／Proceedings of the 33rd International Conference on Very Large Data Bases.New York：ACM Press，2007：63－74.

［9］Merialdo P.ACM SIGMOD record：XML version ［EB／OL］.［2013－06－06］.http：／／www.dia.uniroma3.it／Araneus／Sigmod／.

［10］Miklau G.University courses ［EB／OL］. ［2013－06－25］.http：／／www.cs.washington.edu／research／xmldatasets／www／repository.html＃courses.