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

陶 杰，廖湖聲，高紅雨

(北京工業大學 信息學部，北京 100124)

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

陶 杰，廖湖聲，高紅雨

(北京工業大學 信息學部，北京 100124)

作為網絡數據交換和數據共享的標準，XML數據越來越多地用于表示應用系統的流數據。然而，受制于流數據處理有限空間開銷等特征，如何高效地實現這種查詢成為值得探討的問題。與傳統的基于自動機或層次棧方法不同，文中提出了一種基于圖歸約的XML查詢自動機(GRAT)，采用一種圖結構來表示針對不同XML流元素的子查詢任務之間的關系，通過圖的歸約變化來實現XPath查詢。實驗結果表明，基于GRAT的查詢算法能夠高效地完成復雜的XML查詢，流數據處理的吞吐量達到了較高水平。

XML；圖歸約；流數據

0 引言

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

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

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

1 預備知識

1.1 XML森林[22]

XML數據是由多個標簽和文本遵循嚴格的嵌套規則組成的，具有樹形結構。所謂XML流數據由多個XML元素組成，其中每個XML元素可以表示成順序遍歷的樹。這種連續的XML片段序列數據被稱為XML森林。

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

forest ::=ε| tree forest

tree ::= tag, tag∈∑

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

1.2 XML查詢語言

XPath是用來確定XML文檔中節點位置的語言。XPath面向XML數據的樹狀結構，使用路徑表達式尋找節點或節點集。

本文支持的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代表節點測試，tag代表標簽。可以看出，一個XPath查詢路徑可以包含一個或多個查詢步，每個查詢步包含三個部分：軸類型、節點測試和查詢謂詞。

2 基于GRAT的XPath查詢原理

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

通過對XML流數據和XPath查詢特征的分析，筆者發現XPath查詢過程的每個時刻，后續查詢任務的關系可以表示為圖的結構。針對每個XML元素的處理，查詢可以表示為圖的變換，并且這種變換可以表示為一組圖的歸約操作，從而形成一種高效的查詢自動機：圖歸約方法轉換機(Graph Reduction Approaching Transducer, GRAT)。

2.1 XPath查詢任務圖

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

圖1 XML流數據元素表示成XML樹

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

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

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

圖2 a2節點到來時的查詢任務圖

2.2 查詢任務圖的歸約

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

圖3 查詢a2結束后的查詢任務圖

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

3 基于GRAT的XML流數據查詢

基于GRAT的XML流數據查詢由以下幾步組成：

(1)將XPath查詢請求翻譯為一種查詢樹；查詢任務圖最開始只有一個節點(入口)，就是查詢樹的根節點。

(2)按照依次輸入的XML標簽，針對入口節點使用GRAT規則進行歸約操作，完成節點規定的任務，產生新的入口節點。

這些查詢樹節點與GRAT規則組成了一個查詢自動機。

3.1 GRAT翻譯規則

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

每個XPath查詢根據這些規則轉換成一棵二叉樹。以下是詳細的翻譯規則：

其中，node代表GRAT的查詢任務節點，q代表生成的查詢樹的入口，nil代表無規則。每個node包含3個屬性：查詢樹的入口即q，節點測試成功規則，和節點測試失敗規則。根據以上規則，針對查詢//A[//B[/C]][//D]//E，GRAT翻譯成如圖4的查詢樹，其中每個節點對應查詢標記q及其對應的標簽。

圖4 //A[//B[/C]][//D]/E查詢樹節點

3.2 查詢任務圖的歸約規則

定義2：查詢任務圖是一個三元組有向無環圖Dag=(N,I,H)，其中：

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

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

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

定義中skip任務用來跳過無需匹配的XML元素；end任務用于結束匹配；output任務用來暫存未篩選的結果。

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

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

圖5 有條件的GRAT歸約規則

圖6 無條件的GRAT歸約規則

當XML流數據觸發開始標簽時根據以上規則進行歸約；當觸發結束標簽時，普通的入口任務節點會指向右側連接的節點。skip任務會檢查是否是右側節點對應的結束標簽，若不是，則不需要更改狀態；否則，和其他任務一樣，入口指向右側連接的節點。

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

3.3 GRAT定義

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

(1)Q是自動機所有的狀態集合，也就是所有查詢任務的集合；

(2)T是XML節點開始標記和結束標記的集合；

(3)R是歸約規則的集合，一個查詢任務有向無環圖Dag：Dag×T→Dag；

(4)q0∈Q，是起始狀態，是由XPath查詢請求和查詢樹的根節點組成的查詢任務。

綜上，查詢通過翻譯規則得到查詢樹；由樹根和給定的XPath組成的查詢任務，作為唯一的節點，形成了任務圖；然后GRAT按照XML數據流標簽和當前任務，對任務圖進行歸約，參照查詢樹建立子查詢的任務，形成另一個任務圖；據此，每一個標簽事件的到來反復歸約這個任務圖，通過skip任務跳過無關的元素，通過output任務來緩存或輸出查詢結果。

4 GRAT自動機的實現算法和實驗結果

4.1 實現算法

GRAT的實現算法包括開始標簽算法和關閉標簽算法。算法的參數包括查詢任務節點node，輸入標簽tag，當前標簽層數layer以及當前節點對應的規則集rule。算法處理的是上一狀態的入口節點列表QL，返回的結果是入口節點列表QLNEW。

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

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

由于文獻[17]所述的XML流數據查詢結果要優于其他的一些查詢方法，因此本文選擇GRAT與文獻[17]的方法進行對比。

4.2 實驗方案

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

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

表1 3個XML基準數據集

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

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

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

4.3 實驗結果

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

圖7 不同查詢在XMark數據集上的表現

圖8反映了表3中Q1、Q2和Q3這三組查詢在表2中不同的XMark測試用例上對Q1.1、Q2.1、Q3.1的平均運行時間。可以得出Q1、Q2、Q3在路徑選擇平均步數相同時，謂詞的數量越多，查詢越快。

圖8 查詢不同大小的XMark上的表現

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

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

圖9 查詢在不同數據集上的運行時間

圖10 GRAT與文獻[17]對比結果

5 結論

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

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

[2] 路瑤, 廖湖聲, 蘇航, 等. 面向XML流數據的樹模式匹配方法[J]. 軟件工程與應用, 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] 張鵬, 李鵬霄, 任彥,等. 面向大數據的分布式流處理技術綜述[J]. 計算機研究與發展, 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]. 計算機與現代化, 2016(4):65-73.

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

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

[23] 郭金磊, 張玉生, 胡愛蘭. 基于NIO的高速數據傳輸技術的實現[J]. 微型機與應用, 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

北京市自然科學基金項目(4122011) ；國家自然科學基金青年基金項目(61202074)

TP31

A

10.19358/j.issn.1674- 7720.2017.15.005

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

2017-03-21)

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

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

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