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

陶 杰，廖湖聲，高紅雨

(北京工業(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ù)越來越多地用于表示應(yīng)用系統(tǒng)的流數(shù)據(jù)。然而，受制于流數(shù)據(jù)處理有限空間開銷等特征，如何高效地實現(xiàn)這種查詢成為值得探討的問題。與傳統(tǒng)的基于自動機或?qū)哟螚７椒ú煌?，文中提出了一種基于圖歸約的XML查詢自動機(GRAT)，采用一種圖結(jié)構(gòu)來表示針對不同XML流元素的子查詢?nèi)蝿?wù)之間的關(guān)系，通過圖的歸約變化來實現(xiàn)XPath查詢。實驗結(jié)果表明，基于GRAT的查詢算法能夠高效地完成復(fù)雜的XML查詢，流數(shù)據(jù)處理的吞吐量達到了較高水平。

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

0 引言

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

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

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

1 預(yù)備知識

1.1 XML森林[22]

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

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

forest ::=ε| tree forest

tree ::= tag, tag∈∑

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

1.2 XML查詢語言

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

本文支持的XPath子集語法如下：

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é)點測試，tag代表標(biāo)簽?？梢钥闯?，一個XPath查詢路徑可以包含一個或多個查詢步，每個查詢步包含三個部分：軸類型、節(jié)點測試和查詢謂詞。

2 基于GRAT的XPath查詢原理

一個XPath查詢請求中包含了查詢步和謂詞等多個子查詢。多個子查詢可能是針對同一個XML片段的查詢。但是流數(shù)據(jù)處理的特殊性要求查詢處理不能保存所有這些XML子元素，導(dǎo)致這些子查詢必須同時進行。每當(dāng)XML流數(shù)據(jù)元素到達時，將有一組子查詢進行處理，處理中將產(chǎn)生新的子查詢；與此同時也有一組子查詢在等待后續(xù)XML元素的到來。

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

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

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

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

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

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

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

圖2 a2節(jié)點到來時的查詢?nèi)蝿?wù)圖

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

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

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

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

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

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

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

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

這些查詢樹節(jié)點與GRAT規(guī)則組成了一個查詢自動機。

3.1 GRAT翻譯規(guī)則

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

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

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

圖4 //A[//B[/C]][//D]/E查詢樹節(jié)點

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

定義2：查詢?nèi)蝿?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ù)用來跳過無需匹配的XML元素；end任務(wù)用于結(jié)束匹配；output任務(wù)用來暫存未篩選的結(jié)果。

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

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

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

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

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

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

3.3 GRAT定義

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

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

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

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

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

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

4 GRAT自動機的實現(xiàn)算法和實驗結(jié)果

4.1 實現(xiàn)算法

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

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

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

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

4.2 實驗方案

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

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

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

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

測試使用的查詢?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 測試使用的XPath查詢(XPath 測試集)

4.3 實驗結(jié)果

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

圖7 不同查詢在XMark數(shù)據(jù)集上的表現(xiàn)

圖8反映了表3中Q1、Q2和Q3這三組查詢在表2中不同的XMark測試用例上對Q1.1、Q2.1、Q3.1的平均運行時間?？梢缘贸鯭1、Q2、Q3在路徑選擇平均步數(shù)相同時，謂詞的數(shù)量越多，查詢越快。

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

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

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

圖9 查詢在不同數(shù)據(jù)集上的運行時間

圖10 GRAT與文獻[17]對比結(jié)果

5 結(jié)論

本文提出了一種基于圖歸約的XPath高性能流數(shù)據(jù)查詢的方法。該方法支持在流數(shù)據(jù)上的多層多謂詞的嵌套查找。通過圖的數(shù)據(jù)結(jié)構(gòu)使得該方法保證了查詢的靈活性，又由于該方法產(chǎn)生的狀態(tài)圖以及圖的歸約步驟都是在系統(tǒng)內(nèi)存中運行的，因此保證了數(shù)據(jù)的高效性。通過以上介紹本文所使用的GRAT算法和測試的結(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ù)的樹模式匹配方法[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]. 計算機研究與發(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]. 計算機與現(xiàn)代化, 2016(4):65-73.

[21] 李文珠, 廖湖聲, 蘇航. 基于下推轉(zhuǎn)換機的XML流數(shù)據(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] 郭金磊, 張玉生, 胡愛蘭. 基于NIO的高速數(shù)據(jù)傳輸技術(shù)的實現(xiàn)[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é)基金項目(4122011) ；國家自然科學(xué)基金青年基金項目(61202074)

TP31

A

10.19358/j.issn.1674- 7720.2017.15.005

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

2017-03-21)

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

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

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