王 鵬，張曉琳

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

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

查詢處理是數(shù)據(jù)管理的核心，對(duì)于不確定XML查詢處理的研究，國(guó)內(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)的。基于二元結(jié)構(gòu)連接的方法由于算法本身會(huì)產(chǎn)生無(wú)用的中間結(jié)果而限制查詢的效率，基于整體匹配的方法由于算法本身高內(nèi)聚的特點(diǎn)不方便進(jìn)行實(shí)例樹概率值計(jì)算和概率閾值過(guò)濾。

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)過(guò)濾過(guò)程合并，在子序列匹配同時(shí)進(jìn)行結(jié)構(gòu)過(guò)濾，使子序列匹配的結(jié)果就是查詢的最終結(jié)果，避免了子序列匹配過(guò)程產(chǎn)生過(guò)多不符合模式樹結(jié)構(gòu)的中間結(jié)果而影響查詢的效率。H－PrTRIM算法與PrTRIM算法相比具有如下優(yōu)勢(shì):(1)更適合查詢大文檔。(2)更適合查詢結(jié)構(gòu)復(fù)雜的語(yǔ)句。

1 背景知識(shí)

1.1 p－文檔模型

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

圖1 PrXML{ind，mux}模型

1.2 基于序列的Twig模式匹配

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

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

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

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

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

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

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

1.3 PSI索引

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

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

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

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

2 不確定XML整體小枝匹配

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

2.1 模式樹序列化

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

圖2 模式樹

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

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

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

圖3 子序列匹配示意

定義1假設(shè)兩棵樹T1和T2對(duì)應(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é)點(diǎn)，則Ci是Di的父節(jié)點(diǎn)，或者S2中Ci的最近祖先在位置Ai處與S1結(jié)構(gòu)一致。

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

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

2.3 概率閾值過(guò)濾

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

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

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

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

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

表2 實(shí)驗(yàn)用到的查詢用例

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

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

圖5 算法性能對(duì)比

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

4 結(jié)束語(yǔ)

本文在PrTRIM算法的基礎(chǔ)上對(duì)其進(jìn)行改進(jìn)，將PrTRIM算法中的子序列匹配和結(jié)構(gòu)過(guò)濾過(guò)程合并，在子序列匹配的同時(shí)進(jìn)行結(jié)構(gòu)過(guò)濾，使子序列匹配得到的結(jié)果就是查詢的最終結(jié)果。理論和實(shí)驗(yàn)表明盡管H－PrTRIM算法與PrTRIM算法相比少一次概率閾值過(guò)濾，但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查詢處理算法的研究與實(shí)現(xiàn)［D］.沈陽(yáng):東北大學(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查詢處理算法的研究與實(shí)現(xiàn)［D］.沈陽(yáng):東北大學(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］.計(jì)算機(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é)報(bào)，2007，18(6):1400－1418.