張曉琳，韓雨童，蘇龍超，劉立新

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

0 引 言

真實(shí)世界中的大部分?jǐn)?shù)據(jù)都是不確定的，不確定XML數(shù)據(jù)在工業(yè)，通信，金融和軍事等諸多領(lǐng)域得到廣泛應(yīng)用。現(xiàn)在已出現(xiàn)很多關(guān)于不確定XML數(shù)據(jù)的Twig查詢(xún)處理算法，這些算法的本質(zhì)是基于文檔結(jié)構(gòu)，內(nèi)容選擇和概率閾值的查詢(xún)，而在實(shí)際應(yīng)用中XML查詢(xún)是比較復(fù)雜的，Twig查詢(xún)語(yǔ)句中通常包含AND，OR和NOT等邏輯謂詞，稱(chēng)為復(fù)雜Twig查詢(xún)。目前針對(duì)不確定XML復(fù)雜Twig查詢(xún)的研究還很少。

在深入研究XML復(fù)雜Twig查詢(xún)算法的基礎(chǔ)上，提出了一種適合不確定XML特性的復(fù)雜Twig查詢(xún)處理算法，算法提出一種路徑葉子節(jié)點(diǎn)索引結(jié)構(gòu)，將具有相同路徑標(biāo)簽的節(jié)點(diǎn)聚集在一起，提高路徑匹配效率；實(shí)現(xiàn)基于不確定XML包含復(fù)雜謂詞的小枝匹配，快速得到滿(mǎn)足條件的查詢(xún)結(jié)果。

1 相關(guān)研究

目前針對(duì)不確定XML的查詢(xún)處理，研究者們基于簡(jiǎn)單小枝模式匹配已經(jīng)提出了一些快速有效的方法。2009年，Yawen Li等人提出了Holistically Twig算法［1］，該算法采用區(qū)間編碼，匹配的過(guò)程中處理分布類(lèi)型的節(jié)點(diǎn)。2011年，Siqi Liu等人提出了一種基于概率閾值的PXML查詢(xún)算法［2］，該算法是在查詢(xún)的同時(shí)給出一個(gè)概率閾值，將與查詢(xún)模式匹配并且概率值大于該閾值的結(jié)果返回給用戶(hù)，該算法是基于TJFast算法提出的，是一類(lèi)基于歸并的算法，無(wú)法避免小枝歸并時(shí)大量結(jié)構(gòu)連接操作。

對(duì)于普通XML復(fù)雜Twig查詢(xún)處理的研究還處于起步階段。文獻(xiàn)［3］提出一種整體匹配算法可以同時(shí)處理OR，AND和NOT謂詞的BTwig－Merge算法。查詢(xún)前先對(duì)查詢(xún)模式進(jìn)行B－twig規(guī)范化，算法利用棧結(jié)構(gòu)過(guò)濾掉部分不參與最終結(jié)果的節(jié)點(diǎn)。對(duì)于查詢(xún)模式中的PC關(guān)系，該算法有明顯的優(yōu)勢(shì)。文獻(xiàn)［4］在GTwig Merge的基礎(chǔ)上提出了一種能夠處理All－Twig模式查詢(xún)的算法All Twig Merge，并定義了一種將All－Twig模式規(guī)范化的方法。但是在查詢(xún)中存在重復(fù)查詢(xún)節(jié)點(diǎn)的情況。文獻(xiàn)［5］擴(kuò)展Twig List算法，針對(duì)同時(shí)包含OR，AND和NOT謂詞的All－Twig模式查詢(xún)，提出一種整體匹配算法All Twig List，查詢(xún)時(shí)將All－Twig模式作為一個(gè)整體，掃描相關(guān)的XML節(jié)點(diǎn)，留下符合查詢(xún)模式的節(jié)點(diǎn)，最后采用自頂向下的方法對(duì)這些節(jié)點(diǎn)進(jìn)行結(jié)果匹配。但算法采用棧存儲(chǔ)中間結(jié)果，進(jìn)棧出棧在一定程度上造成時(shí)間空間的浪費(fèi)。文獻(xiàn)［6］提出了一種路徑分區(qū)編碼，能夠有序聚集存儲(chǔ)具有相同路徑的節(jié)點(diǎn)，并且提出XPattern的概念，對(duì)查詢(xún)模式進(jìn)行簡(jiǎn)化，還提出整體匹配算法MPTwig，利用路徑分區(qū)編碼的性質(zhì)，找到滿(mǎn)足查詢(xún)模式的輸出節(jié)點(diǎn)集。但該算法在查詢(xún)過(guò)程中通過(guò)遞歸，反復(fù)遍歷查詢(xún)模式，并存儲(chǔ)大量中間結(jié)果，造成時(shí)間空間上的浪費(fèi)。Jian liu等人在文獻(xiàn)［7］中提出了一種針對(duì)不確定XML復(fù)雜謂詞整體匹配的查詢(xún)處理算法LTwig。算法以數(shù)據(jù)流的形式處理文檔樹(shù)中對(duì)應(yīng)查詢(xún)模式中標(biāo)簽的所有元素，但LTwig查詢(xún)過(guò)程中需要多次掃描查詢(xún)模式并存在大量的入棧出棧操作。

從上述相關(guān)研究分析可以看出，目前處理普通XML復(fù)雜Twig查詢(xún)算法存在諸多問(wèn)題，有些算法在處理不確定XML查詢(xún)時(shí)會(huì)受到一定條件的制約。如重復(fù)處理查詢(xún)節(jié)點(diǎn)；查詢(xún)過(guò)程中產(chǎn)生大量中間結(jié)果；反復(fù)遍歷查詢(xún)模式等。并且目前還沒(méi)有關(guān)于不確定XML數(shù)據(jù)復(fù)雜Twig查詢(xún)處理的算法。

2 算法理論基礎(chǔ)

2.1 不確定XML數(shù)據(jù)模型

不確定XML文檔可以看作一棵包含概率關(guān)系的文檔樹(shù)。本文采用P－文檔模型Pr XML｛mux，ind｝［8，9］。如圖1在不確定XML文檔樹(shù)中，把概率屬性節(jié)點(diǎn)的分布類(lèi)型分為2種:一是獨(dú)立類(lèi)型節(jié)點(diǎn)ind，獨(dú)立節(jié)點(diǎn)在PXML樹(shù)中出現(xiàn)的概率是相互獨(dú)立的，不受其它節(jié)點(diǎn)的影響。二是互斥類(lèi)型節(jié)點(diǎn)mux，互斥節(jié)點(diǎn)在PXML樹(shù)中只能出現(xiàn)一個(gè)節(jié)點(diǎn)且不出現(xiàn)其它兄弟節(jié)點(diǎn)，或者全都不出現(xiàn)。

2.2 BooleanTwig查詢(xún)模式

不確定XML文檔的Twig模式查詢(xún)的本質(zhì)是在不確定XML文檔中查找到所有滿(mǎn)足Twig模式的XML數(shù)據(jù)片段，并計(jì)算出每個(gè)片段存在的概率值。這類(lèi)查詢(xún)中還可以同時(shí)包含OR，AND，NOT和wildcard等謂詞的復(fù)雜Twig模式，稱(chēng)之為Boolean Twig查詢(xún)模式。

Boolean Twig查詢(xún)模式是由XPath語(yǔ)句轉(zhuǎn)換成一棵查詢(xún)樹(shù)，樹(shù)中的節(jié)點(diǎn)由Qnode，Onode，Anode和Nnode組成。如圖2為查詢(xún)語(yǔ)句Q1＝/S［/E OR//A［//C AND//D］］對(duì)應(yīng)的查詢(xún)模式，其中Onode和Anode節(jié)點(diǎn)分別有兩個(gè)Qnode孩子A，E和C，D。

圖1 不確定XML文檔

圖2 查詢(xún)模式BT

定義1 存在查詢(xún)模式BT，對(duì)于查詢(xún)模式中的任意Qnode節(jié)點(diǎn)n。若n為根節(jié)點(diǎn)，則n.path＝n.name。否則存在路徑n.path＝n.name＋n.parent.path，n.path就是查詢(xún)節(jié)點(diǎn)n的查詢(xún)單枝路徑。其中n.paren t是n的所有祖先節(jié)點(diǎn)中離n最近的Qnode祖先節(jié)點(diǎn)，n.name是謂詞“/”或“//”與節(jié)點(diǎn)標(biāo)簽的組合。

3 不確定XML復(fù)雜Twig查詢(xún)算法Prob－Boolean－Twig

3.1 REDewey編碼

采用（Dewey ID，Prob，Path Prob）元組對(duì)不確定XML文檔中的每個(gè)節(jié)點(diǎn)進(jìn)行REDewey編碼。普通節(jié)點(diǎn)的De－wey ID用一位表示，即它的EDewey編碼值［10］；分布節(jié)點(diǎn)的Dewey ID編碼用兩位表示，其中ind，mux第一位分別用－2，－3表示，第二位是該節(jié)點(diǎn)對(duì)應(yīng)的EDewey編碼值。如圖3為表達(dá)方便省略了Pro b和Path Prob（分別記錄節(jié)點(diǎn)條件概率和存在概率）的兩個(gè)屬性值。因此，根據(jù)節(jié)點(diǎn)的REDewey編碼可以快速判斷節(jié)點(diǎn)之間的關(guān)系。

圖3 REDewey編碼后的不確定XML文檔

關(guān)系判斷:對(duì)任意兩個(gè)節(jié)點(diǎn)u，v，當(dāng)且僅當(dāng)L（u）是L（v）的前綴，則u是v的祖先節(jié)點(diǎn)。當(dāng)且僅當(dāng)L（u）是L（v）的前綴且L（u）比L（v）多且只多一個(gè)“.”連接符，則u是v的父親節(jié)點(diǎn)。

為了表示方便和更好的說(shuō)明Prob－Boolean Twig算法的整體思想，后續(xù)部分以圖1的不確定XML文檔作為例子進(jìn)行闡述。如無(wú)特殊說(shuō)明，以帶下標(biāo)的小寫(xiě)字母表示節(jié)點(diǎn)的標(biāo)簽名稱(chēng)，如s1，a2等，Boolean Twig查詢(xún)模式中的查詢(xún)節(jié)點(diǎn)用大寫(xiě)字母表示。

3.2 路徑葉子索引

在實(shí)際應(yīng)用中，不確定XML文檔可能包含數(shù)量龐大的節(jié)點(diǎn)，表示不確定關(guān)系的分布節(jié)點(diǎn)使不確定XML文檔的結(jié)構(gòu)更復(fù)雜，但文檔中總是存在大量重復(fù)的簡(jiǎn)單路徑。在文檔中，簡(jiǎn)單路徑的種類(lèi)遠(yuǎn)遠(yuǎn)小于節(jié)點(diǎn)的數(shù)量，而且是有限的。例如，116 M經(jīng)典數(shù)據(jù)及XMark包含多達(dá)1.78＊106個(gè)節(jié)點(diǎn)，但是其中的簡(jiǎn)單路徑僅有546個(gè)。通過(guò)統(tǒng)計(jì)文檔中的簡(jiǎn)單路徑，根據(jù)編碼后不確定XML文檔樹(shù)，為不確定XML文檔樹(shù)中的所有可能路徑建立索引。不考慮分布節(jié)點(diǎn)ind和mux，設(shè)計(jì)路徑葉子節(jié)點(diǎn)標(biāo)簽索引，即根據(jù)所有可能路徑葉子節(jié)點(diǎn)標(biāo)簽建立索引項(xiàng)，對(duì)應(yīng)節(jié)點(diǎn)標(biāo)簽聚集存儲(chǔ)簡(jiǎn)單路徑信息及其節(jié)點(diǎn)編碼，將具有相同路徑的節(jié)點(diǎn)聚集在一起，加快了路徑匹配的速度，有效地提高查詢(xún)效率。

如圖4用大寫(xiě)字母表示路徑葉子節(jié)點(diǎn)的標(biāo)簽，即索引項(xiàng)，以帶下標(biāo)的小寫(xiě)字母表示文檔中節(jié)點(diǎn)編碼值。例如C是路徑葉子節(jié)點(diǎn)的標(biāo)簽，將C作為索引項(xiàng)，索引中記錄所有以標(biāo)簽C為葉子節(jié)點(diǎn)并且去除分布節(jié)點(diǎn)的簡(jiǎn)單路徑R/S/F/A/C，及文檔樹(shù)中對(duì)應(yīng)節(jié)點(diǎn)的編碼值c1＝0.0.0.0.－20.0。

圖4 不確定XML文檔的路徑葉子索引結(jié)構(gòu)

3.3 FA路徑匹配

定義2 路徑匹配有限狀態(tài)自動(dòng)機(jī)（finite automation of twig pattern，F(xiàn)ATP）是一個(gè)五元組:M＝（Q，∑，δ，q0，F(xiàn)）。其中，

Q—狀態(tài)的非空有窮集合。和q∈Q，q稱(chēng)為M的一個(gè)狀態(tài)。狀態(tài)個(gè)數(shù)為查詢(xún)單枝路徑中節(jié)點(diǎn)的個(gè)數(shù)加1。

∑—文檔中節(jié)點(diǎn)標(biāo)簽集合。

δ—狀態(tài)轉(zhuǎn)移函數(shù)，δ:Q×∑→Q，δ（q，a）＝p。

q0—M的開(kāi)始狀態(tài)，也可稱(chēng)為起始狀態(tài)或啟動(dòng)狀態(tài)，q0∈Q。

F—M的終止?fàn)顟B(tài)集合。F被Q包含。q∈F，q稱(chēng)為M的終止?fàn)顟B(tài)。

圖5（a）表示查詢(xún)節(jié)點(diǎn)C對(duì)應(yīng)的查詢(xún)單枝路徑為S//A//C，起始狀態(tài)為q0，終止?fàn)顟B(tài)為q3，∑＝｛R，S，A，C，D，E，M｝，圖5（b）表示查詢(xún)節(jié)點(diǎn)D對(duì)應(yīng)的查詢(xún)單枝路徑為S//A//D，起始狀態(tài)為q0，終止?fàn)顟B(tài)為q3，∑＝｛R，S，A，C，D，E，M｝。

圖5 路徑匹配有限狀態(tài)自動(dòng)機(jī)

3.4 Prob－BooleanTwig算法描述

該算法的主要思想:首先根據(jù)不確定XML文檔建立路徑索引結(jié)構(gòu)，其次采用非歸并的整體小枝匹配算法，將葉子節(jié)點(diǎn)的查詢(xún)單枝路徑與索引中的路徑進(jìn)行FA路徑匹配，得到查詢(xún)模式中葉子節(jié)點(diǎn)對(duì)應(yīng)的解析模式集。根據(jù)擴(kuò)展后編碼的性質(zhì)，遞歸調(diào)用Prob－Boolean Twig算法，不同的邏輯謂詞采取不同的處理方式，最終返回滿(mǎn)足查詢(xún)模式的小枝及其存在概率值。

Prob－Boolean Twig算法主函數(shù)為boolean Twig－Solution（），遞歸實(shí)現(xiàn)處理不確定XML復(fù)雜Twig查詢(xún)。

算法:boolean TwigSolution（iroot，node）

輸入:索引文檔根節(jié)點(diǎn)和Boolean Twig查詢(xún)模式的根節(jié)點(diǎn)

輸出:滿(mǎn)足查詢(xún)模式的小枝和其存在概率值

1.if（node.get Leaf Flag（）＝＝1）//葉子節(jié)點(diǎn)

2.｛

3.leaf Result＝leafSolution（iroot，node）；

4. //葉子節(jié)點(diǎn)查詢(xún)處理算法

5. return leafResult；

6.｝

7.else

8.｛if（node.getElement Name（）＝＝"AND"）

9. //實(shí)現(xiàn)AND邏輯

10.｛

11. get Together Node（）；//獲得孩子節(jié)點(diǎn)返回的結(jié)果，并合并具有共同祖先的節(jié)點(diǎn)

12. cartesian（）；//計(jì)算節(jié)點(diǎn)之間笛卡爾積，并向上層傳遞中間結(jié)果

13.｝

14.else if（node.getElement Name（）＝＝"OR"）

15.//實(shí)現(xiàn)OR邏輯

16.｛

17. get Together Node（）；//獲得孩子節(jié)點(diǎn)返回的結(jié)果，并合并具有共同祖先的節(jié)點(diǎn)

18. combiantion（）；//計(jì)算節(jié)點(diǎn)之間排列組合，并向上層傳遞中間結(jié)果

19.｝

20.else //非葉子節(jié)點(diǎn)的Qnode節(jié)點(diǎn)

21.｛ children List＝node.getChild（）；

22.for（all child in children List）

23. ｛

24. get Together Node（）；//獲得孩子節(jié)點(diǎn)返回的結(jié)果，并合并具有共同祖的節(jié)點(diǎn)

25. return leaf Result；

26. ｝

27. ｝

28.｝

其中，leaf Solution（i root，node）函數(shù)根據(jù)葉子節(jié)點(diǎn)標(biāo)簽在索引中匹配相應(yīng)的Tab值，經(jīng)過(guò)路徑匹配獲得滿(mǎn)足小枝的所有路徑及其對(duì)應(yīng)的文檔樹(shù)中的節(jié)點(diǎn)。

3.5 Prob－Boolean Twig算法示例

下面以圖2所示的查詢(xún)模式為例來(lái)說(shuō)明Prob－Boolean Twig算法的執(zhí)行過(guò)程。

首先遞歸調(diào)用boolean Twig Solution（），查詢(xún)模式中C的查詢(xún)路徑為S//A//C，進(jìn)行路徑匹配后得到如圖6所示的解析模式集。因此，最后返回葉子節(jié)點(diǎn)C的解析模式集為｛（c1，c2），ind1，a1｝，｛（c3），ind2，a2｝，｛（c4），ind3，a3｝，葉子節(jié)點(diǎn)D的解析模式集為｛（d1），ind1，a1｝，｛（d2，d3），ind2，a2｝，｛（d4），ind3，a3｝。執(zhí)行boolean TwigSolution（AND，A）函數(shù)，將底層返回的解析模式集，依據(jù)共同的祖先節(jié)點(diǎn)（查詢(xún)路徑中上層節(jié)點(diǎn)標(biāo)簽）進(jìn)行合并得到｛（（c1，c2）d1），ind1，a1｝，｛（c3（d2，d3）），ind2，a2｝，｛（c4，d4），ind3，a3｝。因?yàn)楫?dāng)前的查詢(xún)節(jié)點(diǎn)為Anode節(jié)點(diǎn)，執(zhí)行cartesian（）函數(shù)，計(jì)算節(jié)點(diǎn)之間組合的滿(mǎn)足“與”邏輯和路徑存在的概率值，實(shí)現(xiàn)AND邏輯。因?yàn)楦怕书撝禐?.2，則｛（c1，d1），ind1，a1｝－－0.144，｛（c2，d1），ind1，a1｝－－0.144，｛（c3，d3），ind2，a2｝－－0.144結(jié)果被舍棄。繼續(xù)向上層遞歸，當(dāng)執(zhí)行到當(dāng)前查詢(xún)節(jié)點(diǎn)為Onode節(jié)點(diǎn)時(shí)，執(zhí)行combiantion（）函數(shù)，計(jì)算節(jié)點(diǎn)之間滿(mǎn)足“或”邏輯的組合結(jié)果，實(shí)現(xiàn)OR邏輯并進(jìn)行閾值過(guò)濾，返回給上層解析模式集為｛（c3，d2），ind2，a2，m1，s1｝，｛（c4，d4），ind3，a3，mux1，s2｝，｛e1，mux1，s2｝，其中MUX為互斥節(jié)點(diǎn)，舍棄結(jié)果｛（c4，d4），ind3，（a3，e1），mux1，s2｝。最后返回滿(mǎn)足查詢(xún)模式的查詢(xún)小枝及小枝存在的概率｛（c3，d2），ind2，a2，m1，s1｝－－0.224，｛（c4，d4），ind3，a3，mux1，s2｝－－0.6，｛e1，mux1，s2｝－－0.4。

3.6 算法復(fù)雜度分析

Prob－Boolean Twig算法執(zhí)行過(guò)程概括為2個(gè)階段:

圖6 查詢(xún)模式葉子節(jié)點(diǎn)路徑匹配結(jié)果

（1）葉子節(jié)點(diǎn)路徑匹配的過(guò)程；

（2）自底向上匹配小枝模式，得到滿(mǎn)足查詢(xún)模式的小枝。

時(shí)間復(fù)雜度為:階段（1）查詢(xún)?nèi)~子節(jié)點(diǎn)標(biāo)簽對(duì)應(yīng)的路徑索引，最壞的情況掃描所有標(biāo)簽，時(shí)間復(fù)雜度為O（n），其中n表示節(jié)點(diǎn)標(biāo)簽數(shù)；階段（2）自底向上匹配過(guò)程中，合并有共同祖先的節(jié)點(diǎn)標(biāo)簽。函數(shù)get Together Node（）最壞情況的時(shí)間復(fù)雜度為L(zhǎng)ist中每個(gè)child Nod e匹配路徑個(gè)數(shù)的積∏L（c），其中L（c）為child Node中匹配路徑的個(gè)數(shù)。因此，Prob－Boolean Twig算法在最壞情況下的時(shí)間復(fù)雜度為O（n＋∏L（c））。

空間復(fù)雜度為:在get Together Node（List child Node）階段，最壞的情況下的空間復(fù)雜度是O（d＊∑L（c）），所有child Node都沒(méi)有共同祖先節(jié)點(diǎn)，其中d表示路徑長(zhǎng)度，最壞的情況為文檔樹(shù)的深度。因此Prob－Boolean Twig算大的空間復(fù)雜度為O（d＊∑L（c））。

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

采用Java語(yǔ)言實(shí)現(xiàn)Prob－Boolean Twig算法，并與經(jīng)典的All Twig List，MPTwig算法進(jìn)行對(duì)比。實(shí)驗(yàn)的硬件環(huán)境為:CPU Inter（R）Core i3（2.26 GHz），RAM為2G，操作系統(tǒng)為32位的Windows XP，實(shí)驗(yàn)工具為MyEclipse 8.5，JDK 6.0。實(shí)驗(yàn)測(cè)試所用數(shù)據(jù)集是在XML經(jīng)典數(shù)據(jù)集DBLP文檔的基礎(chǔ)之上，利用一個(gè)隨機(jī)化的算法隨機(jī)加入一些分布節(jié)點(diǎn)，合成具有不確定性節(jié)點(diǎn)的XML數(shù)據(jù)集。一般情況下，文檔中節(jié)點(diǎn)的個(gè)數(shù)要遠(yuǎn)遠(yuǎn)高于文檔中路徑的個(gè)數(shù)。因此，大小不同的DBLP文檔中的節(jié)點(diǎn)數(shù)量和路徑數(shù)量見(jiàn)表1。

表1 文檔相關(guān)屬性

實(shí)驗(yàn)部分共有三組測(cè)試來(lái)對(duì)比兩種算法，第一組測(cè)試條件是不同概率閾值，相同文檔，相同的查詢(xún)語(yǔ)句；第二組測(cè)試條件是相同的文檔、不同的查詢(xún)語(yǔ)句；第三組測(cè)試條件是不同的文檔、相同的查詢(xún)語(yǔ)句。每組實(shí)驗(yàn)均重復(fù)10次，得到的實(shí)驗(yàn)數(shù)據(jù)采用去掉最大值和最小值，取平均值的方法記錄整理。實(shí)驗(yàn)用到的查詢(xún)用例見(jiàn)表2。

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

第一組實(shí)驗(yàn)選取大小為48.7MB的文檔，選擇Q3作為查詢(xún)用例，分別選取不同的概率閾值進(jìn)行測(cè)試的響應(yīng)時(shí)間，如圖7所示。第二組實(shí)驗(yàn)選取大小為82.5MB的文檔，查詢(xún)的概率閾值設(shè)定為0.5，分別執(zhí)行表2所示的4個(gè)查詢(xún)用例，如圖8所示。第三組測(cè)試選擇Q4作為查詢(xún)用例，查詢(xún)的概率閾值設(shè)定為0.5，選取大小不同的5個(gè)文檔進(jìn)行測(cè)試，如圖9所示。從中可以明顯看出，Prob－Boolean Twig算法性能上優(yōu)于MPTwig和All Twig List算法。因?yàn)镻rob－Boolean Twig算法在查詢(xún)過(guò)程中僅需要遍歷一次查詢(xún)模式，提高了查詢(xún)速率；只對(duì)查詢(xún)模式中的葉子節(jié)點(diǎn)進(jìn)行路徑匹配并且根據(jù)概率閾值過(guò)濾掉不滿(mǎn)足條件的中間結(jié)果，在很大程度上節(jié)約存儲(chǔ)中間結(jié)果所消耗的時(shí)間和空間。而MPTwig算法在查詢(xún)過(guò)程中需要反復(fù)遍歷查詢(xún)模式，并且在執(zhí)行查詢(xún)前匹配查詢(xún)模式中所有Qnode節(jié)點(diǎn)的解析模式集，浪費(fèi)了大量的存儲(chǔ)空間。All Twig List算法則需要遍歷查詢(xún)模式中標(biāo)簽匹配的所有文檔節(jié)點(diǎn)，匹配過(guò)程需要大量的入棧出棧操作。

圖7 閾值不同時(shí)間對(duì)比

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

提出一種針對(duì)不確定XML復(fù)雜Twig查詢(xún)匹配處理算法:Prob－Boolean Twig算法。在REDewey編碼方案的基礎(chǔ)上構(gòu)建路徑葉子節(jié)點(diǎn)索引；僅對(duì)查詢(xún)模式中葉子節(jié)點(diǎn)進(jìn)行路徑匹配，再采用自底向上的方式對(duì)查詢(xún)模式進(jìn)行匹配；根據(jù)概率閾值對(duì)中間結(jié)果進(jìn)行過(guò)濾，得到最終匹配小枝及其存在概率值。在理論分析和實(shí)驗(yàn)證明方面都表明Prob－Boolean Twig算法在時(shí)間和空間上都具有一定的優(yōu)勢(shì)。未來(lái)工作是對(duì)算法進(jìn)行擴(kuò)展，來(lái)支持wildcard匹配和左右兄弟關(guān)系等復(fù)雜謂詞的Twig查詢(xún)。

圖8 查詢(xún)用例不同時(shí)間對(duì)比

圖9 文檔大小不同時(shí)間對(duì)比

［1］Li Yawen，Wang Guoren，Xin Junchang，et al.Holistically twig matching in probabilistic XML［C］//Shanghai，China:Proceedings of the IEEE International Conference on Data Engineering，2009:1649－1656.

［2］Liu Siqi，Wang Guoren.Boosting twig joins in probabilistic XML［C］//Toulouse，F(xiàn)rance:Proceedings of the 22nd International Conference on Database and Expert Systems Applications，2011:51－58.

［3］Che D，Ling T，Hou W.Holistic boolean－twig pattern matching for efficient XML query processing［J］.Knowledge and Data Engineering，IEEE，2012，24（11）:2008－2024.

［4］Che Dunren.Holistically processing XML twig queries with AND，OR and NOT predicates［C］//Brussels，Belgium:Proceedings of the 2nd International Conference on Scalable Information Systems，2007:1－4.

［5］GUO Hong，WANG Jianhui.Processing algorithm for complex twig with OR，AND，and Not predicates［J］.Journal of Chinese Computer Systems，2010，31（7）:1396－1401（in Chinese）.［郭紅，王劍輝.包含OR，AND和NOT謂詞的復(fù)雜Twig查詢(xún)處理算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2010，31（7）:1396－1401.］

［6］Xu X，F(xiàn)eng Y，Wang F.Efficient processing of XML twig queries with all predicates［C］//Shanghai，China:Proceedings of Computer and Information Science，2009:457－462.

［7］Ma ZM，Liu Jian，Li Yan.Matching twigs in fuzzy XML［J］.Information Sciences，2011，181（1）:184－200.

［8］Abiteboul S，Chan T H，Kharlamov E.Aggregate queries for discrete and continuous probabilistic XML［C］//Lausanne，Switzerland:Proceedings of the 13th International Conference on Database Theory，2010:50－61.

［9］Abiteboul S，Kimelfeld B，Sagiv Y，et al.On the expressiveness of probabilistic XML models［J］.The VLDB Journal，2009，18（5）:1041－1064.

［10］ZHAO Shengmeng，ZHAO Lei.Extended dewey encoding algorithm of twig pattern query without merging［J］.Journal of Chinese Computer Systems，2011，32（5）:837－839（in Chinese）.［趙圣猛，趙雷.一種采用擴(kuò)展Dewey編碼非歸并的小枝模式查詢(xún)算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，32（5）:837－839.］