陶 杰，廖湖聲，高紅雨

(北京工業(yè)大學(xué) 信息學(xué)部，北京 100124)

一種基于圖歸約的XPath高性能流數(shù)據(jù)查詢方法*

陶 杰，廖湖聲，高紅雨

(北京工業(yè)大學(xué) 信息學(xué)部，北京 100124)

作為網(wǎng)絡(luò)數(shù)據(jù)交換和數(shù)據(jù)共享的標(biāo)準(zhǔn)，XML數(shù)據(jù)越來(lái)越多地用于表示應(yīng)用系統(tǒng)的流數(shù)據(jù)。然而，受制于流數(shù)據(jù)處理有限空間開(kāi)銷等特征，如何高效地實(shí)現(xiàn)這種查詢成為值得探討的問(wèn)題。與傳統(tǒng)的基于自動(dòng)機(jī)或?qū)哟螚７椒ú煌?，文中提出了一種基于圖歸約的XML查詢自動(dòng)機(jī)(GRAT)，采用一種圖結(jié)構(gòu)來(lái)表示針對(duì)不同XML流元素的子查詢?nèi)蝿?wù)之間的關(guān)系，通過(guò)圖的歸約變化來(lái)實(shí)現(xiàn)XPath查詢。實(shí)驗(yàn)結(jié)果表明，基于GRAT的查詢算法能夠高效地完成復(fù)雜的XML查詢，流數(shù)據(jù)處理的吞吐量達(dá)到了較高水平。

XML；圖歸約；流數(shù)據(jù)

0 引言

網(wǎng)絡(luò)中有如傳感器網(wǎng)絡(luò)、氣象監(jiān)控、金融服務(wù)和網(wǎng)絡(luò)監(jiān)控等很多應(yīng)用系統(tǒng)會(huì)持續(xù)地自動(dòng)產(chǎn)生大量的數(shù)據(jù)。這些數(shù)據(jù)是一個(gè)隨著時(shí)間延續(xù)而無(wú)限遞增的動(dòng)態(tài)集合，稱為流數(shù)據(jù)。不同于傳統(tǒng)數(shù)據(jù)處理，流數(shù)據(jù)[1]無(wú)法控制自身到來(lái)的順序，并且到來(lái)的數(shù)據(jù)一經(jīng)處理，就不能再次被取出或者耗費(fèi)昂貴的代價(jià)取出，除非特意將數(shù)據(jù)保存。因此，流數(shù)據(jù)的處理需要滿足一次存取、持續(xù)處理、有限存儲(chǔ)和快速響應(yīng)的特點(diǎn)。網(wǎng)絡(luò)上用于傳輸和共享的數(shù)據(jù)的標(biāo)準(zhǔn)以半結(jié)構(gòu)化數(shù)據(jù)為準(zhǔn)[2]，而標(biāo)記擴(kuò)展語(yǔ)言 (eXtensible Markup Language, XML)因其自描述、半結(jié)構(gòu)化等特征，已經(jīng)成為了互聯(lián)網(wǎng)上主導(dǎo)的數(shù)據(jù)交換和數(shù)據(jù)共享的標(biāo)準(zhǔn)[3]。隨著近年來(lái)網(wǎng)絡(luò)數(shù)據(jù)吞吐量以及各行各業(yè)的網(wǎng)絡(luò)應(yīng)用的爆炸性增長(zhǎng)，數(shù)據(jù)量也在不斷地增加，以XML為主的流數(shù)據(jù)處理已成為研究人員普遍關(guān)注的一個(gè)熱點(diǎn)[4-5]。為了能夠快速高效地從海量持續(xù)不斷的數(shù)據(jù)中找出用戶需求的少量數(shù)據(jù)[6]，需要流數(shù)據(jù)處理的方法具備豐富的查詢功能和強(qiáng)大的查詢處理能力[7]的同時(shí)，也要避免占用過(guò)多的資源。

處理XML流數(shù)據(jù)的理論和技術(shù)已經(jīng)成為流數(shù)據(jù)領(lǐng)域中的一個(gè)重要分支[8]。在XML流數(shù)據(jù)的處理方法中，數(shù)據(jù)會(huì)以事件進(jìn)行驅(qū)動(dòng)，以開(kāi)始標(biāo)簽、內(nèi)容和結(jié)束標(biāo)簽的形式進(jìn)行處理，用戶的查詢則主要使用XML路徑語(yǔ)言(XML Path language, XPath)表示查詢。如何對(duì)XML流數(shù)據(jù)在一次掃描之后獲得所有正確的結(jié)果是個(gè)富有挑戰(zhàn)的問(wèn)題[9]。目前已經(jīng)出現(xiàn)了很多有關(guān)XML流數(shù)據(jù)查詢處理的方法和成果[10-11]。BFilter[12]使用向后匹配的算法，有效地處理了查詢，但是該方法只支持訂閱-發(fā)布這一類單一的系統(tǒng)，并不支持流數(shù)據(jù)處理；PFilter[13]采用基于序列的方法，支持值謂詞的查詢，也能夠應(yīng)對(duì)祖先后代關(guān)系等的復(fù)雜謂詞查詢，但是處理過(guò)程相對(duì)復(fù)雜，并且不支持嵌套謂詞的查詢處理，不能滿足當(dāng)今的復(fù)雜查詢；EFilter[14]使用查詢引導(dǎo)的方法，支持流數(shù)據(jù)查詢和twig查詢模式，然而該方法對(duì)于緩存要求比較高，而且實(shí)現(xiàn)相對(duì)復(fù)雜；HadoopXML[15]能夠高效處理大量數(shù)據(jù)，但是采用的是批處理形式，并不滿足流數(shù)據(jù)的實(shí)時(shí)性；宏森林自動(dòng)機(jī)[16]有效提高了XML的查詢，并且支持復(fù)雜謂詞的查詢，但是文章中并沒(méi)有給出實(shí)現(xiàn)自動(dòng)機(jī)的方法；Feng X在宏森林自動(dòng)機(jī)的基礎(chǔ)上實(shí)現(xiàn)了基于XPath的查詢方法[17]，滿足流數(shù)據(jù)的查詢處理和復(fù)雜謂詞的處理，但是實(shí)現(xiàn)的步驟復(fù)雜，不夠靈活，不容易擴(kuò)展。

以上這些方法基本上都采用自動(dòng)機(jī)[18-20]和復(fù)雜層次棧的方法[21]實(shí)現(xiàn)流數(shù)據(jù)處理。與上述所采用的方法不同，本文提出一種基于圖歸約的XML查詢技術(shù)——GRAT。該方法既可以避免預(yù)處理的時(shí)間開(kāi)銷，又使得查詢復(fù)雜性保持線性增長(zhǎng)，同時(shí)也足夠靈活，具備強(qiáng)大的加工能力來(lái)應(yīng)對(duì)更復(fù)雜的謂詞處理。本文提出的算法針對(duì)持續(xù)不斷產(chǎn)生的XML流數(shù)據(jù)進(jìn)行查詢處理，以XPath查詢作為查詢?nèi)蝿?wù)，能夠高效快速地查詢以XML為主的流數(shù)據(jù)。

1 預(yù)備知識(shí)

1.1 XML森林[22]

XML數(shù)據(jù)是由多個(gè)標(biāo)簽和文本遵循嚴(yán)格的嵌套規(guī)則組成的，具有樹(shù)形結(jié)構(gòu)。所謂XML流數(shù)據(jù)由多個(gè)XML元素組成，其中每個(gè)XML元素可以表示成順序遍歷的樹(shù)。這種連續(xù)的XML片段序列數(shù)據(jù)被稱為XML森林。

定義1：一個(gè)XML森林是序列t1，t2…tn，其中n≥0并且t1，t2…tn都是XML樹(shù)。一棵樹(shù)由一個(gè)帶有標(biāo)記的根節(jié)點(diǎn)和子樹(shù)序列組成。XML森林的形式化表示如下：

forest ::=ε| tree forest

tree ::= tag, tag∈∑

其中，forest代表XML森林，tree代表XML樹(shù)，tag代表XML標(biāo)簽，∑代表輸入字母表，是所有XML標(biāo)簽的集合，ε表示空序列。

1.2 XML查詢語(yǔ)言

XPath是用來(lái)確定XML文檔中節(jié)點(diǎn)位置的語(yǔ)言。XPath面向XML數(shù)據(jù)的樹(shù)狀結(jié)構(gòu)，使用路徑表達(dá)式尋找節(jié)點(diǎn)或節(jié)點(diǎn)集。

本文支持的XPath子集語(yǔ)法如下：

path ::= step | step path

step ::= axis::test preds

preds ::= nil | [step] preds

axis ::= child | descendant-or-self

test ::= tag

其中path代表查詢路徑，step代表查詢步，preds代表查詢謂詞，axis代表軸類型，test代表節(jié)點(diǎn)測(cè)試，tag代表標(biāo)簽?？梢钥闯?，一個(gè)XPath查詢路徑可以包含一個(gè)或多個(gè)查詢步，每個(gè)查詢步包含三個(gè)部分：軸類型、節(jié)點(diǎn)測(cè)試和查詢謂詞。

2 基于GRAT的XPath查詢?cè)?/h2>

一個(gè)XPath查詢請(qǐng)求中包含了查詢步和謂詞等多個(gè)子查詢。多個(gè)子查詢可能是針對(duì)同一個(gè)XML片段的查詢。但是流數(shù)據(jù)處理的特殊性要求查詢處理不能保存所有這些XML子元素，導(dǎo)致這些子查詢必須同時(shí)進(jìn)行。每當(dāng)XML流數(shù)據(jù)元素到達(dá)時(shí)，將有一組子查詢進(jìn)行處理，處理中將產(chǎn)生新的子查詢；與此同時(shí)也有一組子查詢?cè)诘却罄m(xù)XML元素的到來(lái)。

通過(guò)對(duì)XML流數(shù)據(jù)和XPath查詢特征的分析，筆者發(fā)現(xiàn)XPath查詢過(guò)程的每個(gè)時(shí)刻，后續(xù)查詢?nèi)蝿?wù)的關(guān)系可以表示為圖的結(jié)構(gòu)。針對(duì)每個(gè)XML元素的處理，查詢可以表示為圖的變換，并且這種變換可以表示為一組圖的歸約操作，從而形成一種高效的查詢自動(dòng)機(jī)：圖歸約方法轉(zhuǎn)換機(jī)(Graph Reduction Approaching Transducer, GRAT)。

2.1 XPath查詢?nèi)蝿?wù)圖

如上所述，圖1的2個(gè)XML流元素可以用2個(gè)XML樹(shù)來(lái)表示。為了描述方便，本文擴(kuò)展了一個(gè)虛根元素rt作為這些流數(shù)據(jù)元素的根，為了便于區(qū)分元素，元素添加了序號(hào)。

圖1 XML流數(shù)據(jù)元素表示成XML樹(shù)

本文將查詢?nèi)蝿?wù)task定義為子查詢query和XML森林forest組成的二元組。查詢開(kāi)始時(shí)，只有一個(gè)針對(duì)整個(gè)XML流的XPath全路徑查詢?nèi)蝿?wù)。隨著節(jié)點(diǎn)事件的發(fā)生，查詢?nèi)蝿?wù)轉(zhuǎn)換和新生成多個(gè)查詢?nèi)蝿?wù)。GRAT將這些任務(wù)看作任務(wù)節(jié)點(diǎn)，按照XPath的路徑查詢規(guī)則連接起來(lái)，就形成了XPath的查詢?nèi)蝿?wù)圖。例如，針對(duì)圖1所示的XML流數(shù)據(jù)的XPath查詢//A[//B[/C]][//D]//E的處理過(guò)程中，查詢?nèi)蝿?wù)圖初始只有一個(gè)任務(wù)節(jié)點(diǎn):

t0= ( //A[//B[/C]][//D]//E, {a1,a3… } )

隨后，按照標(biāo)簽的到達(dá)順序，也就是深度優(yōu)先的順序依次進(jìn)行處理，當(dāng)處理完節(jié)點(diǎn)b1，準(zhǔn)備處理節(jié)點(diǎn)a2時(shí)，針對(duì)其子孫節(jié)點(diǎn)、后續(xù)兄弟以及其他未處理的樹(shù)節(jié)點(diǎn)也需要進(jìn)行一系列的查詢。此時(shí)，由于節(jié)點(diǎn)a1已經(jīng)被處理，說(shuō)明XPath已經(jīng)識(shí)別了//A的信息，還需要針對(duì)子孫節(jié)點(diǎn)進(jìn)行[//B[/C]]、[//D]和//E等的查詢；同時(shí)，鑒于AD軸“//”的存在，后續(xù)查詢還要針對(duì)a1的后續(xù)兄弟節(jié)點(diǎn)和其余子孫節(jié)點(diǎn)進(jìn)行展開(kāi)。這些查詢可以表示為一個(gè)查詢?nèi)蝿?wù)圖，如圖2所示，其中每個(gè)查詢?nèi)蝿?wù)包含了一個(gè)XML節(jié)點(diǎn)序列及其子查詢，t1，t2…tn記作查詢?nèi)蝿?wù)節(jié)點(diǎn)。

圖2 a2節(jié)點(diǎn)到來(lái)時(shí)的查詢?nèi)蝿?wù)圖

2.2 查詢?nèi)蝿?wù)圖的歸約

當(dāng)一個(gè)標(biāo)簽到來(lái)時(shí)，如果有某個(gè)查詢滿足這個(gè)標(biāo)簽，GRAT按照對(duì)應(yīng)的XPath子查詢進(jìn)行圖歸約轉(zhuǎn)換。根據(jù)不同的歸約規(guī)則，就可以轉(zhuǎn)換成不同的圖，這個(gè)歸約的過(guò)程稱為圖歸約。一個(gè)XPath查詢匹配標(biāo)簽之后，根據(jù)規(guī)則，任務(wù)圖生成新的子查詢?nèi)蝿?wù)圖，這些節(jié)點(diǎn)可能包含多個(gè)謂詞查詢?nèi)蝿?wù)和至多一個(gè)路徑選擇查詢，此時(shí)原來(lái)的查詢?nèi)蝿?wù)圖需要組合新的查詢?nèi)蝿?wù)節(jié)點(diǎn)，與之前未匹配的查詢結(jié)合。例如上述例子中，XPath在a2匹配結(jié)束后，會(huì)在下一個(gè)事件遇到標(biāo)簽。這時(shí)t1的查詢與a2匹配成功，需要進(jìn)行圖歸約操作，得到3個(gè)新的子查詢，要用來(lái)匹配a2的子孫b2、e。圖3展示了匹配a2結(jié)束之后的歸約結(jié)果。

圖3 查詢a2結(jié)束后的查詢?nèi)蝿?wù)圖

在圖歸約過(guò)程中，XPath查詢被逐步分解成各個(gè)子查詢，處于葉節(jié)點(diǎn)的子查詢處理完成后，GRAT將根據(jù)各個(gè)謂詞查詢的結(jié)果進(jìn)行篩選，得到最終正確的查詢結(jié)果。

3 基于GRAT的XML流數(shù)據(jù)查詢

基于GRAT的XML流數(shù)據(jù)查詢由以下幾步組成：

(1)將XPath查詢請(qǐng)求翻譯為一種查詢樹(shù)；查詢?nèi)蝿?wù)圖最開(kāi)始只有一個(gè)節(jié)點(diǎn)(入口)，就是查詢樹(shù)的根節(jié)點(diǎn)。

(2)按照依次輸入的XML標(biāo)簽，針對(duì)入口節(jié)點(diǎn)使用GRAT規(guī)則進(jìn)行歸約操作，完成節(jié)點(diǎn)規(guī)定的任務(wù)，產(chǎn)生新的入口節(jié)點(diǎn)。

這些查詢樹(shù)節(jié)點(diǎn)與GRAT規(guī)則組成了一個(gè)查詢自動(dòng)機(jī)。

3.1 GRAT翻譯規(guī)則

從XPath查詢到查詢樹(shù)的翻譯分為三種：查詢路徑選擇的規(guī)則F1(path→N)、謂詞組的翻譯規(guī)則F2(preds→N)、單個(gè)謂詞的翻譯規(guī)則F3(step→N)。

每個(gè)XPath查詢根據(jù)這些規(guī)則轉(zhuǎn)換成一棵二叉樹(shù)。以下是詳細(xì)的翻譯規(guī)則：

其中，node代表GRAT的查詢?nèi)蝿?wù)節(jié)點(diǎn)，q代表生成的查詢樹(shù)的入口，nil代表無(wú)規(guī)則。每個(gè)node包含3個(gè)屬性：查詢樹(shù)的入口即q，節(jié)點(diǎn)測(cè)試成功規(guī)則，和節(jié)點(diǎn)測(cè)試失敗規(guī)則。根據(jù)以上規(guī)則，針對(duì)查詢//A[//B[/C]][//D]//E，GRAT翻譯成如圖4的查詢樹(shù)，其中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)查詢標(biāo)記q及其對(duì)應(yīng)的標(biāo)簽。

圖4 //A[//B[/C]][//D]/E查詢樹(shù)節(jié)點(diǎn)

3.2 查詢?nèi)蝿?wù)圖的歸約規(guī)則

定義2：查詢?nèi)蝿?wù)圖是一個(gè)三元組有向無(wú)環(huán)圖Dag=(N,I,H)，其中：

(1)N=Q+{skip, output, end}，是任務(wù)集合，Q是子查詢集合；

(2)I∈N，是入口列表；

(3)H：H→H是任務(wù)之間有向弧的集合。

定義中skip任務(wù)用來(lái)跳過(guò)無(wú)需匹配的XML元素；end任務(wù)用于結(jié)束匹配；output任務(wù)用來(lái)暫存未篩選的結(jié)果。

GRAT的圖歸約規(guī)則分為兩大部分：需要根據(jù)標(biāo)簽事件進(jìn)行歸約的規(guī)則和不需要標(biāo)簽事件進(jìn)行歸約的規(guī)則。查詢?nèi)蝿?wù)圖的初始形態(tài)只有一個(gè)節(jié)點(diǎn)，表示XPath全路徑查詢。例如//A[//B[/C]][//D]//E的查詢的初始狀態(tài)只有一個(gè)包含了q1-4的任務(wù)節(jié)點(diǎn)；大部分查詢?nèi)蝿?wù)圖的歸約是按照XML流數(shù)據(jù)標(biāo)簽開(kāi)始、結(jié)束和內(nèi)容作為事件驅(qū)動(dòng)進(jìn)行處理執(zhí)行的。當(dāng)觸發(fā)事件時(shí)，GRAT會(huì)匹配入口列表I中的每一個(gè)節(jié)點(diǎn)。如果GRAT查找到對(duì)應(yīng)的標(biāo)簽信息，就會(huì)按照規(guī)則將這個(gè)節(jié)點(diǎn)緩存到output任務(wù)中，并且只有當(dāng)觸發(fā)了對(duì)應(yīng)標(biāo)簽的結(jié)束事件后，結(jié)果才會(huì)根據(jù)謂詞的篩選規(guī)則決定是否滿足查詢請(qǐng)求而輸出；如果流數(shù)據(jù)標(biāo)簽和I中的節(jié)點(diǎn)不匹配，GRAT會(huì)包裹成skip任務(wù)，直到觸發(fā)對(duì)應(yīng)標(biāo)簽的結(jié)束事件。GRAT保留這些節(jié)點(diǎn)為后續(xù)任務(wù)服務(wù)，但skip任務(wù)不處理對(duì)應(yīng)標(biāo)簽的結(jié)束事件以外的事件；一部分查詢?nèi)蝿?wù)圖的歸約規(guī)則是不需要任何事件觸發(fā)的，當(dāng)出現(xiàn)當(dāng)前任務(wù)會(huì)立即歸約成新的任務(wù)圖。

圖5和圖6給出了輸入tag標(biāo)簽和輸入其他標(biāo)簽的完整的GRAT圖歸約規(guī)則。其中，空心箭頭所指的節(jié)點(diǎn)是I列表中的節(jié)點(diǎn)；out代表output任務(wù)；q代表當(dāng)前圖節(jié)點(diǎn)對(duì)應(yīng)的查詢樹(shù)節(jié)點(diǎn)，規(guī)則中給出了輸入標(biāo)簽匹配目標(biāo)狀態(tài)和不匹配目標(biāo)狀態(tài)這兩種情況的圖歸約規(guī)則；q′和q″分別是樹(shù)節(jié)點(diǎn)q的謂詞查詢和路徑選擇查詢；y1和y2分別表示當(dāng)前查詢結(jié)束后需要查詢的任務(wù)，若沒(méi)有后續(xù)任務(wù)，則y1為空。

圖5 有條件的GRAT歸約規(guī)則

圖6 無(wú)條件的GRAT歸約規(guī)則

當(dāng)XML流數(shù)據(jù)觸發(fā)開(kāi)始標(biāo)簽時(shí)根據(jù)以上規(guī)則進(jìn)行歸約；當(dāng)觸發(fā)結(jié)束標(biāo)簽時(shí)，普通的入口任務(wù)節(jié)點(diǎn)會(huì)指向右側(cè)連接的節(jié)點(diǎn)。skip任務(wù)會(huì)檢查是否是右側(cè)節(jié)點(diǎn)對(duì)應(yīng)的結(jié)束標(biāo)簽，若不是，則不需要更改狀態(tài)；否則，和其他任務(wù)一樣，入口指向右側(cè)連接的節(jié)點(diǎn)。

無(wú)條件歸約的節(jié)點(diǎn)不會(huì)長(zhǎng)時(shí)間存在于任務(wù)圖中，每當(dāng)發(fā)現(xiàn)這些不需要事件觸發(fā)的任務(wù)，立即執(zhí)行規(guī)則歸約成新的任務(wù)圖，直到不出現(xiàn)任何無(wú)條件歸約的任務(wù)節(jié)點(diǎn)為止。例如，圖4查詢樹(shù)上q2-2和q1-2是q1-4的子節(jié)點(diǎn)。如果輸入標(biāo)簽是目標(biāo)狀態(tài)，則GRAT會(huì)生成q2-2、q1-2和q1-4這3個(gè)節(jié)點(diǎn)，按照以上規(guī)則連接起來(lái)之后發(fā)現(xiàn)存在無(wú)條件歸約的節(jié)點(diǎn)，那么立即根據(jù)規(guī)則進(jìn)行再次歸約。

3.3 GRAT定義

定義3：一個(gè)GRAT查詢自動(dòng)機(jī)被定義為一個(gè)四元組M=(Q,R,T,q0)，其中：

(1)Q是自動(dòng)機(jī)所有的狀態(tài)集合，也就是所有查詢?nèi)蝿?wù)的集合；

(2)T是XML節(jié)點(diǎn)開(kāi)始標(biāo)記和結(jié)束標(biāo)記的集合；

(3)R是歸約規(guī)則的集合，一個(gè)查詢?nèi)蝿?wù)有向無(wú)環(huán)圖Dag：Dag×T→Dag；

(4)q0∈Q，是起始狀態(tài)，是由XPath查詢請(qǐng)求和查詢樹(shù)的根節(jié)點(diǎn)組成的查詢?nèi)蝿?wù)。

綜上，查詢通過(guò)翻譯規(guī)則得到查詢樹(shù)；由樹(shù)根和給定的XPath組成的查詢?nèi)蝿?wù)，作為唯一的節(jié)點(diǎn)，形成了任務(wù)圖；然后GRAT按照XML數(shù)據(jù)流標(biāo)簽和當(dāng)前任務(wù)，對(duì)任務(wù)圖進(jìn)行歸約，參照查詢樹(shù)建立子查詢的任務(wù)，形成另一個(gè)任務(wù)圖；據(jù)此，每一個(gè)標(biāo)簽事件的到來(lái)反復(fù)歸約這個(gè)任務(wù)圖，通過(guò)skip任務(wù)跳過(guò)無(wú)關(guān)的元素，通過(guò)output任務(wù)來(lái)緩存或輸出查詢結(jié)果。

4 GRAT自動(dòng)機(jī)的實(shí)現(xiàn)算法和實(shí)驗(yàn)結(jié)果

4.1 實(shí)現(xiàn)算法

GRAT的實(shí)現(xiàn)算法包括開(kāi)始標(biāo)簽算法和關(guān)閉標(biāo)簽算法。算法的參數(shù)包括查詢?nèi)蝿?wù)節(jié)點(diǎn)node，輸入標(biāo)簽tag，當(dāng)前標(biāo)簽層數(shù)layer以及當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的規(guī)則集rule。算法處理的是上一狀態(tài)的入口節(jié)點(diǎn)列表QL，返回的結(jié)果是入口節(jié)點(diǎn)列表QLNEW。

算法迭代處理入口列表。首先通過(guò)第3行RuleF方法進(jìn)行GRAT查詢?nèi)蝿?wù)圖的歸約，RuleF和RuleFUncon分別是圖5和圖6的具體實(shí)現(xiàn)；每個(gè)已經(jīng)歸約之后的新入口節(jié)點(diǎn)進(jìn)行下一步的處理：判斷這些節(jié)點(diǎn)中是否存在q2-1或q2-2這類不需要條件進(jìn)行歸約的節(jié)點(diǎn)，如果存在，使用RuleFUncon方法對(duì)節(jié)點(diǎn)再次歸約。這個(gè)歸約過(guò)程是一個(gè)遞歸的過(guò)程，會(huì)檢查所有的節(jié)點(diǎn)直到?jīng)]有無(wú)條件歸約的節(jié)點(diǎn)為止。之后將這些節(jié)點(diǎn)列表合并到結(jié)果隊(duì)列QLNEW中；最后，返回新的節(jié)點(diǎn)列表，為下一個(gè)標(biāo)簽到來(lái)做準(zhǔn)備。

對(duì)于處理結(jié)束標(biāo)簽的過(guò)程中，需要在處理之前判斷node節(jié)點(diǎn)是否是output緩存結(jié)果任務(wù)，如果是，則需要輸出結(jié)果。

由于文獻(xiàn)[17]所述的XML流數(shù)據(jù)查詢結(jié)果要優(yōu)于其他的一些查詢方法，因此本文選擇GRAT與文獻(xiàn)[17]的方法進(jìn)行對(duì)比。

4.2 實(shí)驗(yàn)方案

GRAT使用Java和Scala語(yǔ)言實(shí)現(xiàn)了GRAT自動(dòng)機(jī)和面向XPath的流數(shù)據(jù)查詢。測(cè)試環(huán)境為一臺(tái)HP Z400臺(tái)式工作站，配置4核CPU、4G內(nèi)存、64位Windows 10操作系統(tǒng)，運(yùn)行環(huán)境為 Java(JRE)版本1.8。

測(cè)試使用了真實(shí)的數(shù)據(jù)集DBLP和Tree Bank，以及比較數(shù)據(jù)集XMark，如表1所示。其中，測(cè)試使用了不同大小的6組XMark數(shù)據(jù)集，如表2所示。

表1 3個(gè)XML基準(zhǔn)數(shù)據(jù)集

表2 不同大小的XMark數(shù)據(jù)集(XMark Benchmark 集合)

測(cè)試使用的查詢?nèi)绫?，分為5組，其中，Q1.1～Q1.3是DBLP上的查詢，Q2.1～Q2.3 是Tree Bank上的查詢，Q3.1～Q5.3是XMark上的查詢；Q3.1～Q3.3包含AD關(guān)系而不包含謂詞，Q4.1～Q4.3包含帶有PC軸的謂詞，Q5.1～Q5.3包含嵌套謂詞和并列謂詞。

表3 測(cè)試使用的XPath查詢(XPath 測(cè)試集)

4.3 實(shí)驗(yàn)結(jié)果

圖7反映了表3中各個(gè)測(cè)試用例在表2中編號(hào)為6的XMark 測(cè)試用例上的執(zhí)行時(shí)間。其中Q3.1、Q3.2、Q3.3的用例不包含謂詞，Q4.1和Q4.2包含一個(gè)PC關(guān)系的謂詞，Q4.3包含多個(gè)謂詞。測(cè)試用例Q5.1、Q5.2和Q5.3包含多個(gè)復(fù)雜謂詞，因此所需的時(shí)間也最多。

圖7 不同查詢?cè)赬Mark數(shù)據(jù)集上的表現(xiàn)

圖8反映了表3中Q1、Q2和Q3這三組查詢?cè)诒?中不同的XMark測(cè)試用例上對(duì)Q1.1、Q2.1、Q3.1的平均運(yùn)行時(shí)間?？梢缘贸鯭1、Q2、Q3在路徑選擇平均步數(shù)相同時(shí)，謂詞的數(shù)量越多，查詢?cè)娇臁?/p>

圖8 查詢不同大小的XMark上的表現(xiàn)

圖9反映了GRAT算法在不同數(shù)據(jù)集上運(yùn)行時(shí)間，圖10展示了GRAT算法和文獻(xiàn)[17]的對(duì)比實(shí)驗(yàn)結(jié)果。該實(shí)驗(yàn)采用表2中編號(hào)為6的測(cè)試數(shù)據(jù)。如圖10所示，存在簡(jiǎn)單謂詞的情況下GRAT的查詢效果更好。

根據(jù)以上測(cè)試結(jié)果，可以得出GRAT算法的吞吐量，通過(guò)數(shù)據(jù)量與運(yùn)行時(shí)間的比值，得出最高吞吐量達(dá)到1 073 MB/s，平均為876 MB/s。也得出，數(shù)據(jù)量越多，吞吐量越趨于穩(wěn)定。

圖9 查詢?cè)诓煌瑪?shù)據(jù)集上的運(yùn)行時(shí)間

圖10 GRAT與文獻(xiàn)[17]對(duì)比結(jié)果

5 結(jié)論

本文提出了一種基于圖歸約的XPath高性能流數(shù)據(jù)查詢的方法。該方法支持在流數(shù)據(jù)上的多層多謂詞的嵌套查找。通過(guò)圖的數(shù)據(jù)結(jié)構(gòu)使得該方法保證了查詢的靈活性，又由于該方法產(chǎn)生的狀態(tài)圖以及圖的歸約步驟都是在系統(tǒng)內(nèi)存中運(yùn)行的，因此保證了數(shù)據(jù)的高效性。通過(guò)以上介紹本文所使用的GRAT算法和測(cè)試的結(jié)果，可以得出基于GRAT的XPath查詢滿足高性能和嵌套查詢。下一步工作是將此查詢方法應(yīng)用到分布式系統(tǒng)中以及改善XPath的復(fù)雜查詢[23]。

[1] NISHIZAWA I, IMAKI T. Stream data processing system and stream data processing method[P]. US, US7644110. 2010.

[2] 路瑤, 廖湖聲, 蘇航, 等. 面向XML流數(shù)據(jù)的樹(shù)模式匹配方法[J]. 軟件工程與應(yīng)用, 2016, 5(2): 103-113.

[3] DAMIGOS M, GERGATSOULIS M, KALOGEROS E. Distributed evaluation of XPath queries over large integrated XML data[C]. Panhellenic Conference on Informatics, 2014:1-6.

[4] ENK A, VALENTA M, BENN W. Distributed evaluation of XPath axes queries over large XML documents stored in MapReduce clusters[C]. International Workshop on Database and Expert Systems Applications, 2014:253-257.

[5] MULLANGI P R, PENEMATSA G, RAMASWAMY L. Scalable XPath evaluation on large-scale continuously evolving XML repositories[C]. International Congress on Big Data. IEEE, 2014:546-553.

[6] BELYAEV K, RAY I. Towards efficient dissemination and filtering of XML data streams[C]. International Conference on Dependable, Autonomic and Secure Computing. IEEE, 2015:1870-1877.

[7] KIM S H, LEE Y J, LEE J J. Matrix-based XML stream processing using a GPU[C]. International Congress on Big Data. IEEE, 2015:694-697.

[8] 張鵬, 李鵬霄, 任彥,等. 面向大數(shù)據(jù)的分布式流處理技術(shù)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2014(S2):1-9.

[9] BARROS E G. Parallelizing multiple keyword queries over XML streams[C]. International Conference on Data Engineering Workshops. IEEE, 2016:169-172.

[10] OLTEANU D. SPEX: streamed and progressive evaluation of XPath[J]. Transactions on Knowledge and Data Engineering. IEEE, 2007, 19(7):934-949.

[11] CONG G, FAN W, KEMENTSIETSIDIS A, et al. Partial evaluation for distributed XPath query processing and beyond[J]. ACM Transactions on Database Systems, 2012, 37(4):2498-2501.

[12] DAI L, LUNG C H, MAJUMDAR S. BFilter-a XML message filtering and matching approach in publish/subscribe systems[C]. Global Telecommunications Conference.IEEE,2010:1-6.

[13] SAXENA P, KAMAL R. System architecture and effect of depth of query on XML document filtering using PFilter[C]. Sixth International Conference on Contemporary Computing, 2013:192-195.

[14] HSU W C, LI C F, LIAO I E. EFilter: An efficient filter for supporting twig query patterns in XML streams[C]. International Conference on E-Business. IEEE, 2013:1-8.

[15] CHOI H, LEE K H, KIM S H, et al. HadoopXML: a suite for parallel processing of massive XML data with multiple twig pattern queries[C]. Conference on Information and Knowledge Management, 2012:2737-2739.

[16] HAKUTA S, MANETH S, NAKANO K, et al. XQuery streaming by forest transducers[C]. International Conference on Data Engineering. IEEE, 2014:952-963.

[17] FENG X, LIAO H, SU H. Construction of macro forest transducers from XPath[J]. Transactions on Computer Science and Technology. IEEE, 2015, 4(3):50-58.

[18] BOU S, AMAGASA T, KITAGAWA H. Filtering XML streams by XPath and keywords[C]. Iiwas′14 Proceedings of the International Conference on Information Integration and Web-Based Applications and Services, 2014:410-419.

[19] ALRAMMAL M, HAINS G. Forward XPath stream processing: end-to-end confidentiality and scalability[C]. International Conference on Innovations in Information Technology, 2014:24-29.

[20] 陳沖, 蔣夏軍. 一種支持通配符查詢的XML模式匹配算法[J]. 計(jì)算機(jī)與現(xiàn)代化, 2016(4):65-73.

[21] 李文珠, 廖湖聲, 蘇航. 基于下推轉(zhuǎn)換機(jī)的XML流數(shù)據(jù)處理方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2016, 52(8):49-55.

[22] PERST T, SEIDL H. Macro forest transducers[J]. Information Processing Letters, 2004, 89(3):141-149.

[23] 郭金磊, 張玉生, 胡愛(ài)蘭. 基于NIO的高速數(shù)據(jù)傳輸技術(shù)的實(shí)現(xiàn)[J]. 微型機(jī)與應(yīng)用, 2016, 35(13):19-20.

A high-performance XPath query streaming approach by graph reduction

Tao Jie, Liao Husheng, Gao Hongyu

(Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China)

As a standard of network data exchanging and sharing, XML data is increasingly used to represent streaming data of an application system. However, it is a challenging task that implements efficiently the querying approach for limited by various features such as cost of space while handling the streaming data. Distinguished from the traditional approach which based on transducers or level stacks, this paper put forward an approach of querying XML based on graph reduction, which is called Graph Reduction Approach Transducers (GRAT). It uses a graph structure to represent the relationship between the sub query tasks for different XML stream elements, and the XPath query is implemented by the reduction of the graph. The experimental results show that this algorithm is able to accomplish complex querying XML with high-performance, and the throughput has been reached a higher level.

XML; graph reduction; streaming data

北京市自然科學(xué)基金項(xiàng)目(4122011) ；國(guó)家自然科學(xué)基金青年基金項(xiàng)目(61202074)

TP31

A

10.19358/j.issn.1674- 7720.2017.15.005

陶杰，廖湖聲，高紅雨.一種基于圖歸約的XPath高性能流數(shù)據(jù)查詢方法[J].微型機(jī)與應(yīng)用，2017,36(15)：16-21.

2017-03-21)

陶杰(1990-)，通信作者，男，碩士研究生，主要研究方向：流數(shù)據(jù)查詢技術(shù)。E-mail：315090132@qq.com。

廖湖聲(1954-)，男，碩士，教授，主要研究方向：軟件自動(dòng)化方法、數(shù)據(jù)集成技術(shù)等。

高紅雨(1968-)，男，碩士，副教授，主要研究方向：軟件自動(dòng)化、編譯技術(shù)與程序理論等。