一種針對(duì)正規(guī)樹(shù)模式的復(fù)雜事件查詢(xún)方法?

鄭利強(qiáng) 廖湖聲 蘇 航 高紅雨

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

1 引言

隨著 XML［1］的廣泛采用，如何在 XML 數(shù)據(jù)流上實(shí)現(xiàn)高效的復(fù)雜查詢(xún)也變得越來(lái)越重要。在諸如災(zāi)害預(yù)警和社交媒體的實(shí)時(shí)數(shù)據(jù)分析等領(lǐng)域［2］，經(jīng)常把事件響應(yīng)機(jī)制作為信息處理的計(jì)算模型。按照這種方法，半結(jié)構(gòu)化的流式數(shù)據(jù)可以抽象為復(fù)雜的事件流；復(fù)雜流式數(shù)據(jù)的處理表現(xiàn)為針對(duì)流式數(shù)據(jù)的復(fù)雜事件處理（Complex Event Processing，CEP）［3］，而復(fù)雜事件查詢(xún)就是從數(shù)據(jù)流中查找符合特定數(shù)據(jù)模式的數(shù)據(jù)。

Twig模式［4］匹配查詢(xún)方法是XML數(shù)據(jù)查詢(xún)的核心，它雖然能夠描述XML查詢(xún)中的結(jié)構(gòu)約束關(guān)系，但無(wú)法描述復(fù)雜事件查詢(xún)中的事件間時(shí)序關(guān)系。例如在海嘯預(yù)警中，由于海嘯在傳播時(shí)，浪高不到1m，如果沒(méi)有發(fā)生較高等級(jí)的地震作為前提，并不能判定為海嘯。所以這種情況可以概括為，先發(fā)生一定等級(jí)的地震，然后觀測(cè)點(diǎn)持續(xù)出現(xiàn)若干次海浪波高異常情況，就可以判定為有海嘯風(fēng)險(xiǎn)。而這種情況使用Twig模式并不能進(jìn)行描述。為了能夠同時(shí)描述這兩種約束關(guān)系，人們將正規(guī)式擴(kuò)展到Twig模式中，形成正規(guī)樹(shù)模式［5］。

本文針對(duì)XML流式數(shù)據(jù)，采用正規(guī)樹(shù)模式來(lái)描述復(fù)雜事件的結(jié)構(gòu)約束和時(shí)序約束關(guān)系，提出了一種基于自動(dòng)機(jī)的模式匹配算法，用于實(shí)現(xiàn)復(fù)雜事件檢測(cè)。本文的主要貢獻(xiàn)是：

1）擴(kuò)展了基于下推轉(zhuǎn)換機(jī)［6］的XML數(shù)據(jù)流查詢(xún)算法，滿(mǎn)足了正規(guī)樹(shù)模式匹配中結(jié)構(gòu)連接和多返回節(jié)點(diǎn)的需求。

2）面向XML流中的元素序列，設(shè)計(jì)了基于自動(dòng)機(jī)的正規(guī)式匹配算法，實(shí)現(xiàn)了正規(guī)樹(shù)模式匹配所需的當(dāng)前最長(zhǎng)元素子序列的實(shí)時(shí)檢測(cè)。

3）提出并實(shí)現(xiàn)了面向XML流數(shù)據(jù)的正規(guī)樹(shù)模式匹配算法。它能夠通過(guò)上述兩個(gè)算法的交叉協(xié)作，完成這種復(fù)雜事件查詢(xún)，能夠識(shí)別并獲取這種半結(jié)構(gòu)數(shù)據(jù)流中符合模式要求的實(shí)時(shí)數(shù)據(jù)。

2 相關(guān)工作

本文通過(guò)擴(kuò)展Twig模式和擴(kuò)展下推自動(dòng)機(jī)，并將這兩部分進(jìn)行結(jié)合，實(shí)現(xiàn)了正規(guī)樹(shù)模式的查詢(xún)。

2.1 Twig模式配算法

Twig模式匹配算法早期采用兩階段整體匹配方法［7］，后來(lái)又提出了單階段整體匹配方法［8～9］，但是都不能描述含有時(shí)序約束的請(qǐng)求；而CepEngine引擎［5］能夠支持含有時(shí)序約束的樹(shù)模式查詢(xún)，能夠用來(lái)描述復(fù)雜事件。

2.2 基于下推自動(dòng)機(jī)的流數(shù)據(jù)查詢(xún)方法

為了解決傳統(tǒng)算法不支持流數(shù)據(jù)的問(wèn)題，有人提出了基于自動(dòng)機(jī)的方法［10～13］，但是描述能力有限，而基于下推自動(dòng)機(jī)的ExPDT［14］雖然描述能力比較強(qiáng)，但不支持含有多個(gè)返回節(jié)點(diǎn)的查詢(xún)。而以可視下推自動(dòng)機(jī)［15］為基礎(chǔ)的 XSeq 語(yǔ)言［16～17］，也僅擴(kuò)展了XPath的查詢(xún)能力，但是這些方法對(duì)于同時(shí)含有結(jié)構(gòu)約束和時(shí)序約束的請(qǐng)求，描述能力仍然有限。

3 復(fù)雜事件查詢(xún)方法

鑒于目前使用下推自動(dòng)機(jī)的算法比較高效地解決了僅存在結(jié)構(gòu)約束的查詢(xún)請(qǐng)求，所以本文選擇以下推自動(dòng)機(jī)為基礎(chǔ)進(jìn)行擴(kuò)展。通過(guò)在樹(shù)模式中引入正規(guī)式，表達(dá)查詢(xún)中存在的時(shí)序約束，而正規(guī)式的識(shí)別，可以使用非確定自動(dòng)機(jī)實(shí)現(xiàn)。

3.1 正規(guī)樹(shù)模式

圖1是一個(gè)正規(guī)樹(shù)模式，它通過(guò)在Twig模式上增加正規(guī)式來(lái)描述時(shí)序約束關(guān)系。其中樹(shù)節(jié)點(diǎn)分為普通節(jié)點(diǎn)和正規(guī)節(jié)點(diǎn)，而正規(guī)節(jié)點(diǎn)是滿(mǎn)足正規(guī)式約束的節(jié)點(diǎn)。此外，模式中需要返回查詢(xún)結(jié)果的節(jié)點(diǎn)稱(chēng)為返回節(jié)點(diǎn)，在節(jié)點(diǎn)上加圈表示。圖1中A，B，C，F(xiàn)，G是普通節(jié)點(diǎn)，D和E是正規(guī)節(jié)點(diǎn)，且B和E還是返回節(jié)點(diǎn)。

圖1 正規(guī)樹(shù)模式

在正規(guī)樹(shù)模式的節(jié)點(diǎn)關(guān)系中，單杠（|）表示父子關(guān)系，雙杠（||）表示祖先后代關(guān)系，三角符號(hào)下面是滿(mǎn)足正規(guī)式約束的節(jié)點(diǎn)，與三角符號(hào)上面的節(jié)點(diǎn)保持父子關(guān)系。在正規(guī)式中，操作符包括*（克林閉包）、：（連接）和|（或），并且滿(mǎn)足同一正規(guī)式約束的節(jié)點(diǎn)處在同一層。通過(guò)這些操作符的組合，來(lái)描述樹(shù)模式節(jié)點(diǎn)間的時(shí)序約束關(guān)系。在圖1中，E和D滿(mǎn)足“E：D*”的正規(guī)式約束關(guān)系，即先出現(xiàn)一次E元素，然后必然要出現(xiàn)0到n次的D元素。

對(duì)于前文提到的海嘯預(yù)警問(wèn)題，就可以用圖1描述，設(shè)發(fā)生一定等級(jí)的地震為E，觀測(cè)點(diǎn)出現(xiàn)海浪波高異常情況為D，則持續(xù)出現(xiàn)若干次異常情況為D*，所以在一定等級(jí)地震發(fā)生后，觀測(cè)點(diǎn)出現(xiàn)持續(xù)的海浪波高異常，就可以表示為E：D*，而圖中其他節(jié)點(diǎn)可以表示為同時(shí)處理的一些其他數(shù)據(jù)，如氣溫、濕度等。

3.2 支持多返回節(jié)點(diǎn)的下推自動(dòng)機(jī)

在狀態(tài)轉(zhuǎn)移邊上定義特定操作使其具有查詢(xún)功能的下推自動(dòng)機(jī)稱(chēng)為下推轉(zhuǎn)換機(jī)（Pushdown Transducer，PDT）。圖2是由圖1 中的樹(shù)節(jié)點(diǎn)A、B、C建立的PDT。正規(guī)樹(shù)模式中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于PDT中每相鄰的兩個(gè)狀態(tài)，稱(chēng)為一個(gè)兩狀態(tài)自動(dòng)機(jī)。圖2的PDT分別是由1和2、2和3、2和4三個(gè)子PDT拼接而成。對(duì)于PDT中任意一個(gè)狀態(tài)，作如下規(guī)定：

1）當(dāng)s是當(dāng)前狀態(tài)，且輸入標(biāo)簽和狀態(tài)轉(zhuǎn)移邊上的標(biāo)簽匹配時(shí)，發(fā)生轉(zhuǎn)移，轉(zhuǎn)移到下一狀態(tài)；

2）check標(biāo)記表示check函數(shù)返回值為真時(shí)，才能進(jìn)行狀態(tài)轉(zhuǎn)移；

3）當(dāng)s是當(dāng)前狀態(tài)，且輸入標(biāo)簽序列與一個(gè)完整的XML元素序列匹配時(shí)，回到原來(lái)的狀態(tài)s；

4）其他不滿(mǎn)足的情況，不發(fā)生轉(zhuǎn)移；

5）當(dāng)輸入標(biāo)簽無(wú)法得到匹配時(shí)，說(shuō)明正規(guī)樹(shù)模式與輸入序列不匹配，終止自動(dòng)機(jī)的工作。

在圖1中，C節(jié)點(diǎn)對(duì)應(yīng)圖2的2和4狀態(tài)所屬的兩狀態(tài)子自動(dòng)機(jī)，因?yàn)镃節(jié)點(diǎn)與A節(jié)點(diǎn)是AD軸關(guān)系，所以在圖中用＜*＞表示讀取任意非當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)標(biāo)簽，即2狀態(tài)上的＜*＞表示任意非節(jié)點(diǎn)C對(duì)應(yīng)的標(biāo)簽＜c＞。此外，在匹配過(guò)程中需要對(duì)返回節(jié)點(diǎn)配置緩存，圖2中add和upload是狀態(tài)轉(zhuǎn)移邊上的操作，用于對(duì)緩存進(jìn)行處理；check為自動(dòng)機(jī)之間的檢查操作，以保證讀取的XML標(biāo)簽完全滿(mǎn)足正規(guī)樹(shù)模式，如圖2中2狀態(tài)可以到達(dá)3和4狀態(tài)，需要在2狀態(tài)增加check操作，保證讀取了a標(biāo)簽后既讀取了b標(biāo)簽又讀取了c標(biāo)簽。與此相似，對(duì)于D、F和G節(jié)點(diǎn)也可以構(gòu)成一組PDT。

圖2 正規(guī)樹(shù)模式中節(jié)點(diǎn)A、B、C構(gòu)建的PDT

3.3 支持正規(guī)式匹配的非確定有限狀態(tài)自動(dòng)機(jī)

正規(guī)樹(shù)模式中的正規(guī)式描述了兄弟節(jié)點(diǎn)之間的時(shí)序約束關(guān)系，而流數(shù)據(jù)處理要求獲取當(dāng)前時(shí)刻最長(zhǎng)匹配兄弟元素序列。本文采用常規(guī)方法，為每個(gè)正規(guī)式提供一個(gè)自動(dòng)機(jī)。圖3是對(duì)圖1所示的正規(guī)樹(shù)模式中的正規(guī)式部分“E：D*”構(gòu)建的自動(dòng)機(jī)。這里采用了非確定的有限狀態(tài)自動(dòng)機(jī)（Non-deterministic Automata，NFA）。

圖3 正規(guī)樹(shù)模式中“E：D*”構(gòu)建的NFA

本文的NFA不僅能夠識(shí)別數(shù)據(jù)片段，還能夠查詢(xún)出當(dāng)前時(shí)刻流數(shù)據(jù)中最長(zhǎng)匹配兄弟序列。例如當(dāng)前讀入的XML元素序列是“aedceddabd”時(shí)，傳統(tǒng)NFA判斷它能否被識(shí)別，而本文的NFA在每個(gè)時(shí)刻匹配的最長(zhǎng)兄弟元素序列是不同的。如表1，其中元素序列中的下劃線(xiàn)表示當(dāng)前匹配時(shí)刻。如在“aed”時(shí)刻，當(dāng)前匹配的結(jié)果是ed；在“aedc”時(shí)刻，無(wú)新的匹配結(jié)果輸出。

表1 NFA的當(dāng)前匹配結(jié)果

3.4 自動(dòng)機(jī)合并

為實(shí)現(xiàn)正規(guī)樹(shù)模式查詢(xún)，需要將多個(gè)PDT和NFA進(jìn)行合并。如圖4所示，它是一種新型的支持正規(guī)式匹配的自動(dòng)機(jī)RPDT（Regular Pushdown Transducer）。其中，首先將正規(guī)式“E：D*”構(gòu)造的NFA與圖32的PDT合并，然后將正規(guī)樹(shù)模式中的D、F和G節(jié)點(diǎn)構(gòu)造的PDT再與上述合并的自動(dòng)機(jī)合并。因?yàn)闃?shù)節(jié)點(diǎn)D、F和G既不是返回節(jié)點(diǎn)也不是到達(dá)返回節(jié)點(diǎn)路徑上的節(jié)點(diǎn)，所以對(duì)應(yīng)的PDT狀態(tài)轉(zhuǎn)移邊上只有檢查操作，沒(méi)有對(duì)緩存的操作。合并的方法如下：

1）從PDT內(nèi)部連接NFA時(shí)，在相應(yīng)的狀態(tài)（如狀態(tài)4）添加指向NFA的開(kāi)始狀態(tài)的空轉(zhuǎn)移和從NFA結(jié)束狀態(tài)指向該狀態(tài)的空轉(zhuǎn)移；

2）從NFA內(nèi)部連接PDT時(shí)，將相應(yīng)的狀態(tài)轉(zhuǎn)移（如D轉(zhuǎn)移）分解為：設(shè)置從該狀態(tài)（如狀態(tài)7）到原PDT的頭狀態(tài)（如狀態(tài)9）標(biāo)有其開(kāi)始標(biāo)簽的轉(zhuǎn)移，以及從原PDT的頭狀態(tài)（如狀態(tài)9）到該狀態(tài)（如狀態(tài)7）標(biāo)有其結(jié)束標(biāo)簽的轉(zhuǎn)移。

圖4 由正規(guī)樹(shù)模式構(gòu)造的RPDT

整個(gè)PDT從讀取標(biāo)簽流開(kāi)始，根據(jù)讀取的標(biāo)簽發(fā)生狀態(tài)轉(zhuǎn)移，當(dāng)讀取的標(biāo)簽是滿(mǎn)足正規(guī)式約束的第一個(gè)節(jié)點(diǎn)的開(kāi)始標(biāo)簽時(shí)，即讀取到＜e＞時(shí)，PDT從4狀態(tài)轉(zhuǎn)移到6狀態(tài)，切換到NFA執(zhí)行；當(dāng)NFA到達(dá)接受狀態(tài)時(shí)，讀取到的標(biāo)簽是滿(mǎn)足正規(guī)式約束的最后一個(gè)節(jié)點(diǎn)的結(jié)束標(biāo)簽，即讀取到＜/d＞時(shí)，NFA從8狀態(tài)轉(zhuǎn)移到4狀態(tài)，切換回PDT。

如果給定如圖5（1）的文檔樹(shù)，文檔樹(shù)左側(cè)的數(shù)字表示文檔樹(shù)的深度，就可以通過(guò)執(zhí)行圖34的自動(dòng)機(jī)進(jìn)行匹配，其匹配的兩個(gè)結(jié)果如圖5（2）和（3）。

圖5 文檔樹(shù)及匹配結(jié)果

4 查詢(xún)流程與RPDT設(shè)計(jì)

4.1 查詢(xún)流程

整個(gè)查詢(xún)流程分為構(gòu)建自動(dòng)機(jī)和執(zhí)行自動(dòng)機(jī)兩部分。對(duì)于構(gòu)造自動(dòng)機(jī)，首先以后序的方式訪(fǎng)問(wèn)樹(shù)模式節(jié)點(diǎn)，如果遇到普通節(jié)點(diǎn)，則建立子PDT，已建立的子PDT之間根據(jù)節(jié)點(diǎn)的關(guān)系進(jìn)行合并；如果遇到正規(guī)節(jié)點(diǎn)，則建立子NFA，然后將多個(gè)子NFA根據(jù)節(jié)點(diǎn)關(guān)系進(jìn)行合并，為了解決PDT和NFA的嵌套問(wèn)題，根據(jù)3.4節(jié)的合并方法進(jìn)行合并。其次是執(zhí)行自動(dòng)機(jī)的過(guò)程，首先讀取文檔樹(shù)，根據(jù)讀取的標(biāo)簽，自動(dòng)機(jī)發(fā)生狀態(tài)轉(zhuǎn)移，如果當(dāng)前狀態(tài)屬于PDT的狀態(tài)，則按照PDT的規(guī)則執(zhí)行，否則按照NFA的執(zhí)行規(guī)則執(zhí)行。在整個(gè)執(zhí)行過(guò)程中，通過(guò)配置緩存對(duì)多個(gè)返回節(jié)點(diǎn)涉及的數(shù)據(jù)進(jìn)行查詢(xún)處理。

4.2 RPDT的定義

本文設(shè)計(jì)了一種新型的支持多返回節(jié)點(diǎn)和正規(guī)式匹配的自動(dòng)機(jī)RPDT，它的形式化定義如下，將它定義為一個(gè)七元組（Q，∑，B，F(xiàn)，δ，h，q0），其中：

Q：有限狀態(tài)集合。

∑：XML文檔流的輸入事件的集合，讀取一個(gè)元素或者一個(gè)標(biāo)簽為一個(gè)事件。

B：RPDT中的緩存集合，用于保存沒(méi)有完全滿(mǎn)足正規(guī)樹(shù)模式的節(jié)點(diǎn)數(shù)據(jù)集。

F：轉(zhuǎn)移邊上動(dòng)作的集合，F(xiàn)=｛add，upload，check｝，其中add表示將當(dāng)前元素和對(duì)應(yīng)深度路徑加入到緩存中；而upload表示把當(dāng)前緩存?zhèn)鞯较鄳?yīng)的實(shí)例樹(shù)中；check為對(duì)于正規(guī)樹(shù)模式中含有分支節(jié)點(diǎn)時(shí)所建立的自動(dòng)機(jī)，以及不同類(lèi)型自動(dòng)機(jī)之間進(jìn)行跳轉(zhuǎn)的檢查操作。

δ：狀態(tài)轉(zhuǎn)移函數(shù)，該函數(shù)根據(jù)當(dāng)前狀態(tài)Q、輸入標(biāo)記∑，轉(zhuǎn)移到下一狀態(tài)Q，并執(zhí)行動(dòng)作F。

h：Q→B，緩沖區(qū)映射函數(shù)，為了保存返回節(jié)點(diǎn)的數(shù)據(jù)，為PDT的每一個(gè)狀態(tài)映射到唯一的緩沖區(qū)。

q0：自動(dòng)機(jī)的開(kāi)始狀態(tài)。

5 實(shí)驗(yàn)

本文對(duì)基于下推自動(dòng)機(jī)的復(fù)雜事件查詢(xún)算法進(jìn)行了對(duì)比實(shí)驗(yàn)，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析比較，證明了本實(shí)驗(yàn)方法的正確性和較為良好的性能。

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

本文的實(shí)驗(yàn)環(huán)境為一臺(tái)Intel Core i7 3.00GHz處理器和12GB內(nèi)存的工作站。使用的數(shù)據(jù)集分別來(lái)自真實(shí)數(shù)據(jù)集的DBLP（127MB）和TreeBank（82MB），以及根據(jù)參數(shù)人工生成的數(shù)據(jù)集XMark，分 別 為 XMark0.1（11MB）、XMark0.5（56MB）、XMark1（115MB）、XMark10（1136MB）和 XMark20（2273MB）。

對(duì)比實(shí)驗(yàn)分兩組，第一組為不含正規(guī)式的普通樹(shù)模式對(duì)比實(shí)驗(yàn)，與 ExPDT［14］進(jìn)行對(duì)比；第二組為正規(guī)樹(shù)模式對(duì)比實(shí)驗(yàn)，與CepEngine［5］進(jìn)行對(duì)比。表2為兩組對(duì)比實(shí)驗(yàn)的測(cè)試案例。

5.2 測(cè)試結(jié)果與分析

圖6是ExPDT和本文的RPDT的查詢(xún)時(shí)間對(duì)比。可以看出RPDT在查詢(xún)時(shí)間上相對(duì)于ExPDT均有提高。

圖6 普通樹(shù)模式查詢(xún)時(shí)間對(duì)比

圖7 是CepEngine和本文的RPDT的查詢(xún)時(shí)間對(duì)比。可以看出RPDT在查詢(xún)時(shí)間上相對(duì)于CepEngine也均有提高。

圖7 正規(guī)樹(shù)模式查詢(xún)時(shí)間對(duì)比

表2 查詢(xún)測(cè)試案例

圖8是本文提出的RPDT在不同查詢(xún)不同大小的數(shù)據(jù)集下的吞吐量趨勢(shì)。可以看出，隨著數(shù)據(jù)集的增長(zhǎng)，吞吐量整體呈現(xiàn)增長(zhǎng)趨勢(shì)，在2273MB的XMark數(shù)據(jù)集下，吞吐量可達(dá)1.61GB/s，平均可達(dá)1.54GB/s。

圖8 不同參數(shù)的XMark數(shù)據(jù)集在不同查詢(xún)下的吞吐量

6 結(jié)語(yǔ)

本文提出了一種基于下推自動(dòng)機(jī)的復(fù)雜事件查詢(xún)方法，該方法以下推自動(dòng)機(jī)為基礎(chǔ)進(jìn)行擴(kuò)展，配以非確定自動(dòng)機(jī)，通過(guò)給定的正規(guī)樹(shù)模式構(gòu)建支持正規(guī)式查詢(xún)的下推轉(zhuǎn)換機(jī)RPDT，通過(guò)擴(kuò)展對(duì)正規(guī)式的查詢(xún)，彌補(bǔ)了目前查詢(xún)模式對(duì)事件描述能力的不足，并且通過(guò)對(duì)比實(shí)驗(yàn)，證明了本文提出的RPDT在性能上相比ExPDT和CepEngine均有所提高，可以說(shuō)明它是一種具有較高性能的復(fù)雜事件的查詢(xún)處理方法。［1］ W3C.Extensible Markup Language（XML）［EB/OL］.（2016-10-11）.http：//www.w3.org/XML/.

［2］Alex C，Snoeren，Kenneth C，et al.Mesh-Based Content Routing using XML［C］//Proceedings of the eighteenth ACM symposium on Operating systems principles，2001：160-173.

［3］廖湖聲，蘇航，劉嘉.萬(wàn)維網(wǎng)數(shù)據(jù)表示與查詢(xún)處理語(yǔ)言［J］.中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊，2013，9（4）：8-13.LIAO Husheng，SU Hang，LIU Jia.Web data representation and query processing language［J］.Communications of the CCF，2013，9（4）：8-13

［4］廖湖聲.XQuery語(yǔ)言原理和實(shí)現(xiàn)技術(shù)［M］.北京：科學(xué)出版社，2013：89-91.LIAO Husheng.XQuery Language Principle and Implementation Technology［M］.Beijing：Science Press，2013：89-91.

［5］路遙.一種基于正規(guī)樹(shù)模式匹配的復(fù)雜事件檢測(cè)方法［D］.北京：北京工業(yè)大學(xué)，2016.LU Yao.Complex Event Detection based on Regular Tree Pattern Matching［D］.Beijing：Beijing University of Technology，2016.

［6］A Meduna.Finite and Pushdown Transducers.Automata and Languages［M］.London：Springer-Verlag London，2000：759-832.

［7］Bruno N，Koudas N，Srivastava D.Holistic twig joins：optimal XML pattern matching［C］//Proceedings of the 2002 ACM SIGMOD international conference on Management of data.ACM，2002：310-321.

［8］Chen S，Li H G，Tatemura J，et al.Twig2stack：Bottom-Upprocessing of generalized-tree pattern queries over XML documents［C］//Proceedings of the 32nd international conference on Very large data bases，2006：283-294.

［9］Lu Q，Jeffrey X Y，Ding B L.TwigList：Make twig pattern matching fast［C］//Proceedings of the 12th international conference on Database systems for advanced applications，2007：850-862.

［10］Altinel M，F(xiàn)ranklin M J.Efficient filtering of XML documents for selective dissemination of information［C］//Proceedings of the 26th International Conference on Very Large Data Bases，2000：53-64.

［11］Gupta A K，Suciu D.Stream processing of XPath queries with predicates［C］//Proceedings of the 2003 ACM SIGMOD international conference on Management of data，2003：419-430.

［12］Peng F，Chawathe S.XPath queries on streaming data［C］//Proceedings of the 2003 ACM SIGMOD international conference on Management of data，2003：431-443.

［13］Olteanu D.Evaluation of XPath queries against XML streams［D］.Germany：University of Munich，2005.

［14］李文珠，廖湖聲，蘇航.基于下推轉(zhuǎn)換機(jī)的XML流數(shù)據(jù)處理方法［J］.計(jì)算機(jī)工程與應(yīng)用.2016，52（8）：49-55.LI Wenzhu，LIAO Hushing，SU Hang.Pushdown transducer based query method over XML streams.Computer Engineering and Applications，2016，52（8）：49-55.

［15］Alur R，Madhusudan P.Visibly Pushdown Languages［C］//Proceedings of STOC’04，ACM Press，2004：202-211.

［16］K Zeng，M Yang，B Mozafari，et al.Complex Pattern Matching in Complex Structures：the XSeq Approach［C］//Proceedings of the 2013 IEEE International Conference on Data Engineering，2013：1328-1331.

［17］B Mozafari，K Zeng，C Zaniolo.High-performance complex event processing over xml streams［C］//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data，2012：253-264.