王 鵬，張曉琳

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

可擴展標(biāo)記語言XML(eXtensible Markup Language)是標(biāo)準(zhǔn)通用標(biāo)記語言(SGML)的一種變體，由W3C(World Wide Web Consortium)工作組制定。隨著互聯(lián)網(wǎng)的飛速發(fā)展，XML格式的數(shù)據(jù)在信息世界隨處可見，使得XML成為當(dāng)前數(shù)據(jù)的通用格式，因此研究利用XML來管理不確定數(shù)據(jù)具有重要的理論價值和現(xiàn)實意義。

查詢處理是數(shù)據(jù)管理的核心，對于不確定XML查詢處理的研究，國內(nèi)外尚處起步階段。文獻(xiàn)［1］提出的不確定XML查詢算法是根據(jù)二元結(jié)構(gòu)連接方法中的Tree－Merge－Anc算法［2］改進(jìn)的，文獻(xiàn)［3］提出的不確定XML查詢算法是根據(jù)整體匹配方法中的TwigStack算法［4］改進(jìn)的，文獻(xiàn)［5］提出的不確定XML查詢處理方法是根據(jù)整體匹配方法中的TJFast算法［6］改進(jìn)的，文獻(xiàn)［7］提出的不確定XML查詢處理方法是根據(jù)整體匹配方法中的TwigList算法［8］改進(jìn)的?；诙Y(jié)構(gòu)連接的方法由于算法本身會產(chǎn)生無用的中間結(jié)果而限制查詢的效率，基于整體匹配的方法由于算法本身高內(nèi)聚的特點不方便進(jìn)行實例樹概率值計算和概率閾值過濾。

PrTRIM(Probabilistic TRee Indexing and Matching)算法是將基于序列匹配的LCS－TRIM算法［9］應(yīng)用到不確定XML的查詢。本文以PrTRIM算法作為基礎(chǔ)，提出了H－PrTRIM(Holistic Probabilistic TRee Indexing and Matching)算法。H－PrTRIM算法的思想是將PrTRIM算法中子序列匹配和結(jié)構(gòu)過濾過程合并，在子序列匹配同時進(jìn)行結(jié)構(gòu)過濾，使子序列匹配的結(jié)果就是查詢的最終結(jié)果，避免了子序列匹配過程產(chǎn)生過多不符合模式樹結(jié)構(gòu)的中間結(jié)果而影響查詢的效率。H－PrTRIM算法與PrTRIM算法相比具有如下優(yōu)勢:(1)更適合查詢大文檔。(2)更適合查詢結(jié)構(gòu)復(fù)雜的語句。

1 背景知識

1.1 p－文檔模型

p－文檔模型是一棵包含普通節(jié)點和概率分布節(jié)點的樹。普通節(jié)點來自XML文檔的元素、屬性名、文本值和屬性值，概率分布節(jié)點用來標(biāo)識文檔中的概率信息。圖1為一個PrXML{ind，mux}模型。

圖1 PrXML{ind，mux}模型

1.2 基于序列的Twig模式匹配

可定義Twig模式匹配問題為:給定T wig查詢模式Q和一個具有某種索引結(jié)構(gòu)的XML數(shù)據(jù)庫，所謂Twig模式匹配問題就是搜索XML數(shù)據(jù)庫得到所有滿足Q模式的XML數(shù)據(jù)片段，表示為n元組的形式［10］。對于不確定XML，匹配的輸入由模式樹和概率閾值組成，輸出由實例樹和實例樹的存在概率組成。概率閾值的意義是要求輸出的實例樹的存在概率要大于等于輸入的概率閾值。

序列匹配是一種比較新穎的查詢處理方法，它的基本思想是將整個XML文檔看作是一個整體，抽取XML文檔的內(nèi)容信息和結(jié)構(gòu)信息，映射到一個序列，建立整體索引。針對模式樹，同樣抽取內(nèi)容和結(jié)構(gòu)信息，映射為一個序列。利用模式樹的序列來匹配XML文檔序列，得到的匹配結(jié)果就是查詢在XML文檔上的查詢結(jié)果。

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

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

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

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

H－PrTRIM算法的序列化方法是PSI(Probabilistic Sequence－based Index)索引和模式樹序列化方法，H－PrTRIM算法的序列化方法不含有假不予考慮情況，但含有假警報情況，所以需要利用結(jié)構(gòu)過濾對假警報進(jìn)行消除。

1.3 PSI索引

如表1所示，PSI索引中每一個元素包括5個子元素。postorder為節(jié)點在XML文檔中后序遍歷的編號，唯一標(biāo)識一個節(jié)點。tag為節(jié)點的內(nèi)容。ppostorder為該節(jié)點父節(jié)點的postorder。cprob為節(jié)點的條件概率。marray記錄從XML文檔的根節(jié)點到該節(jié)點經(jīng)過的類型為mux的概率分布節(jié)點，用一個小數(shù)表示，概率分布節(jié)點mux的postorder為整數(shù)部分，概率分布節(jié)點mux孩子節(jié)點的postorder為小數(shù)部分，要求該孩子節(jié)點為該節(jié)點所在子樹的根節(jié)點。

圖1所示的PrXML{ind，mux}模型對應(yīng)的不確定XML文檔可以生成表1所示的PSI索引。通過PSI索引的postorder和ppostorder能夠找到從某一節(jié)點到XML文檔根節(jié)點的路徑，進(jìn)而可以利用PSI索引里cprob計算該節(jié)點的存在概率，即在遍歷路徑的同時將cprob相乘，遍歷到根節(jié)點時，cprob的乘積就是該節(jié)點的存在概率。

表1 PSI索引部分內(nèi)容

在實例樹中，類型為mux的同一概率分布節(jié)點下的不同分支的孩子/后裔不能同時存在，可以借助PSI索引中的marray來判斷。以表1中節(jié)點26和節(jié)點30為例，節(jié)點26和節(jié)點30的marray分別為32.26和32.31，整數(shù)部分相同表示經(jīng)過同一個類型為mux的概率分布節(jié)點32，小數(shù)部分不同表示節(jié)點26和節(jié)點30屬于節(jié)點32的不同分支，因此節(jié)點26和節(jié)點30不能同時在實例樹中存在。

2 不確定XML整體小枝匹配

H－PrTRIM算法查詢之前需要對模式樹進(jìn)行序列化處理，在子序列匹配同時進(jìn)行結(jié)構(gòu)過濾，在查詢的同時進(jìn)行兩次概率閾值過濾。

2.1 模式樹序列化

不確定XML的查詢語句可以用路徑表達(dá)式表示，其中“/”表示父子關(guān)系，“//”表示祖先后代關(guān)系，例如R［A/B］//C。R［A/B］//C可以用樹形結(jié)構(gòu)來描述，稱為模式樹，如圖2所示。

圖2 模式樹

序列化模式樹中的每個節(jié)點描述為(postorder，tag，ppostorder，R)，其中postorder，tag和ppostorder所代表的意義與PSI索引中元素代表的意義相同。R表示該節(jié)點與上下文節(jié)點之間的關(guān)系，R=“pc”表示該節(jié)點與上下文節(jié)點的關(guān)系為父子關(guān)系，R=“ad”表示該節(jié)點與上下文節(jié)點的關(guān)系為祖先后代關(guān)系。因此，圖2所示的模式樹序列化為(1，B，2，pc)，(2，A，4，pc)，(3，C，4，ad)，(4，R，－，－)。

2.2 子序列匹配與結(jié)構(gòu)過濾合并

子序列匹配通過PSI索引中的tag(序列A)和序列化模式樹中的tag(序列B)進(jìn)行，圖3所示為一個子序列匹配結(jié)果。結(jié)構(gòu)過濾的理論依據(jù)是文獻(xiàn)［5］中的定義1和定理1。

圖3 子序列匹配示意

定義1假設(shè)兩棵樹T1和T2對應(yīng)的序列S1=((A1，B1)…(Am，Bm))，S2=((C1，D1)…(Cm，Dm))，其中Ai和Ci定義了結(jié)構(gòu)，Bi和Di包含了標(biāo)記。S1和S2稱為在位置i處結(jié)構(gòu)一致，當(dāng)且僅當(dāng)以下條件滿足:(1)1≤i≤m。(2)Bi和Di相等。(3)如果T1中Ai是Bi的父節(jié)點，則Ci是Di的父節(jié)點，或者S2中Ci的最近祖先在位置Ai處與S1結(jié)構(gòu)一致。

定理1一個查詢Q與T結(jié)構(gòu)匹配，當(dāng)且僅當(dāng)Q與T在所有的位置k處都保持結(jié)構(gòu)一致，1≤k≤m。

H－PrTRIM算法在子序列匹配的同時進(jìn)行結(jié)構(gòu)過濾，每當(dāng)匹配到一個新的節(jié)點，就進(jìn)行結(jié)構(gòu)過濾，根據(jù)定義1檢查新匹配的節(jié)點所在的局部結(jié)構(gòu)是否符合對應(yīng)模式樹的局部結(jié)構(gòu)，如果不符合，則不匹配該節(jié)點。根據(jù)定理1，子序列匹配得到的結(jié)果就是查詢的最終結(jié)果。例如圖3所示的子序列匹配過程中，根據(jù)圖2所示的模式樹結(jié)構(gòu)，匹配過程中節(jié)點33，30，26都符合模式樹的結(jié)構(gòu)，因此都被接受。當(dāng)已接受節(jié)點33，30，26時，匹配新的節(jié)點16，根據(jù)模式樹的結(jié)構(gòu)節(jié)點26與新的節(jié)點16應(yīng)為父子關(guān)系，而實際上節(jié)點26與節(jié)點16并不是父子關(guān)系，因此節(jié)點16并不會被匹配。以下是在子序列匹配同時進(jìn)行結(jié)構(gòu)過濾的算法。

2.3 概率閾值過濾

由于組成實例樹的每個節(jié)點的存在概率是實例樹存在概率的子集，即在概率閾值的約束下，只有組成實例樹的每個節(jié)點的存在概率大于等于概率閾值，實例樹的存在概率才能大于等于概率閾值，因此可以在匹配選取節(jié)點時進(jìn)行第一次概率閾值過濾。第一次概率閾值過濾規(guī)則:在子序列匹配和結(jié)構(gòu)過濾過程中只選取那些存在概率大于等于概率閾值的節(jié)點。

在子序列匹配和結(jié)構(gòu)過濾的同時可以進(jìn)行第二次概率閾值過濾，一旦發(fā)現(xiàn)不符合概率閾值要求的局部結(jié)果可以及早地結(jié)束，這樣可以提高查詢的效率。第二次概率閾值過濾規(guī)則:在結(jié)構(gòu)過濾過程中每當(dāng)匹配到一個條件概率不等于1的節(jié)點，就將新計算得到的當(dāng)前概率值與概率閾值進(jìn)行比較，一旦小于概率閾值，立即終止。

3 實驗結(jié)果與分析

實驗中的算法采用Java語言實現(xiàn)，實驗通過HPrTRIM算法與PrTRIM算法對比進(jìn)行。實驗環(huán)境為Windows XP平臺，主頻2.0 GHz，奔騰雙核處理器，內(nèi)存2 GB。實驗所采用的數(shù)據(jù)集是在University Courses數(shù)據(jù)集中的reed.xml結(jié)構(gòu)基礎(chǔ)上隨機加入概率分布節(jié)點以及概率值人工合成的不確定數(shù)據(jù)集。

實驗用到的查詢用例如表2所示。實驗針對兩個算法分別從3個方面進(jìn)行:(1)概率閾值對算法響應(yīng)時間的影響:相同的查詢語句(Q3)，相同大小的數(shù)據(jù)集(58 MB)，不同的概率閾值(0.5～0.9)。(2)算法性能對比:不同的查詢語句(Q1～Q5)，相同大小的數(shù)據(jù)集(58 MB)，相同的概率閾值(0.5)。(3)數(shù)據(jù)集大小對算法響應(yīng)時間的影響:相同的查詢語句(Q3)，不同大小的數(shù)據(jù)集(18～58 MB)，相同的概率閾值(0.5)。實驗重復(fù)進(jìn)行10次，對數(shù)據(jù)進(jìn)行去掉極大值、極小值，然后取平均值的處理。

表2 實驗用到的查詢用例

概率閾值對算法響應(yīng)時間的影響如圖4所示，概率閾值越小，經(jīng)過第一次概率閾值過濾后參與查詢的節(jié)點就越多，所以H－PrTRIM算法與PrTRIM算法的響應(yīng)時間相差就越大。隨著概率閾值的增大，經(jīng)過第一次概率閾值過濾后參與查詢的節(jié)點減少，HPrTRIM算法與PrTRIM算法的響應(yīng)時間逐漸接近。算法性能對比如圖5所示，H－PrTRIM算法的響應(yīng)時間總體上小于PrTRIM算法的響應(yīng)時間，查詢語句Q4最為明顯，這是因為查詢語句Q4與其他查詢語句相比結(jié)構(gòu)更復(fù)雜，復(fù)雜的結(jié)構(gòu)更能發(fā)揮H－PrTRIM算法將子序列匹配和結(jié)構(gòu)過濾合并的優(yōu)勢。文檔大小對算法響應(yīng)時間的影響如圖6所示，隨著文檔增大，H－PrTRIM算法與PrTRIM算法響應(yīng)時間的差距明顯加大，這是因為文檔越大，參與查詢的節(jié)點越多。綜上，HPrTRIM算法在應(yīng)用于查詢大文檔和結(jié)構(gòu)復(fù)雜的查詢語句時更能體現(xiàn)出優(yōu)勢。

圖4 概率閾值對算法響應(yīng)時間的影響

圖5 算法性能對比

圖6 文檔大小對算法響應(yīng)時間的影響

4 結(jié)束語

本文在PrTRIM算法的基礎(chǔ)上對其進(jìn)行改進(jìn)，將PrTRIM算法中的子序列匹配和結(jié)構(gòu)過濾過程合并，在子序列匹配的同時進(jìn)行結(jié)構(gòu)過濾，使子序列匹配得到的結(jié)果就是查詢的最終結(jié)果。理論和實驗表明盡管H－PrTRIM算法與PrTRIM算法相比少一次概率閾值過濾，但H－PrTRIM算法效率仍然高于PrTRIM算法。H－PrTRIM算法與PrTRIM算法相比更適合應(yīng)用于大文檔和結(jié)構(gòu)復(fù)雜的查詢。

［1］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.

［2］AL－KHALIFA S，JAGADISH H V，KOUDAS N，et al.Structural joins:A primitive for efficient XML query pattern matching［C］.San Jose，California，USA:ICDE，2002.

［3］ 李亞文.概率XML文檔中Holistic Twig查詢處理算法的研究與實現(xiàn)［D］.沈陽:東北大學(xué)，2009.

［4］BRUNO N，KOUDAS N，SRIVASTAVA D.Holistic twig joins:Optimal XML pattern matching［C］.Madison，Wisconsin，USA:SIGMOD Conference，2002.

［5］ 劉潘.概率XML文檔中Twig查詢處理算法的研究與實現(xiàn)［D］.沈陽:東北大學(xué)，2010.

［6］LU J，LING T W，CHAN C Y，et al.From region encoding to extended dewey:on efficient processing of XML twig pattern matching［C］.Trondheim，Norway:VLDB，2005.

［7］ 張曉琳，呂 慶，劉立新，等.一種高效的連續(xù)不確定XML小枝模式匹配算法［J］.計算機應(yīng)用研究，2013，30(2):364－366.

［8］QIN L，YU J X，DING B.TwigList:make twig pattern matching fast［C］.Seoul，Korea:VLDB，2006.

［9］TATIKONDA S，PARTHASARATHY S，GOYDER M.LCSTRIM:dynamic programming meets XML indexing and querying［C］.Vienna，Austria:VLDB，2007.

［10］ 孔令波，唐世渭，楊冬青，等.XML數(shù)據(jù)的查詢技術(shù)［J］.軟件學(xué)報，2007，18(6):1400－1418.