邱 濤，丁建麗，夏秀峰，郗紅梅，謝沛良，周清怡

（1.沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136；2.沈陽飛機(jī)工業(yè)（集團(tuán)）有限公司 試飛站/試飛實(shí)驗(yàn)室，沈陽 110034）

0 引言

隨著射頻識別、傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)［1］等技術(shù)及應(yīng)用的快速發(fā)展，復(fù)雜事件匹配處理已經(jīng)成為檢測、處理、分析和挖掘事件流數(shù)據(jù)的一種有效手段［2］。復(fù)雜事件匹配處理是對滿足某些查詢模式的一些基本事件進(jìn)行識別操作，得到能夠分析事件發(fā)展或其環(huán)境變化狀態(tài)的復(fù)雜事件。例如在股票交易信息分析［3］、道路交通規(guī)劃［4］、數(shù)控機(jī)床系統(tǒng)［5］和海量航天數(shù)據(jù)分析［6］等方面都有廣泛的應(yīng)用。

盡管目前已有一些處理方法，例如SASE［7-8］、ZStream［9］、Siddhi［10］等，但這些方法在處理簡單查詢模式下的事件匹配時(shí)存在著一定的局限性。例如SASE 這種將查詢轉(zhuǎn)化為自動(dòng)機(jī)模型的方法，由于自動(dòng)機(jī)固定的狀態(tài)轉(zhuǎn)換使得它處理事件的靈活性受限，無法直接處理帶有屬性約束條件的否定查詢，同時(shí)也無法處理并發(fā)事件。基于邏輯模型的這種處理方法針對非正式語義對許多真實(shí)世界的應(yīng)用程序構(gòu)成限制的問題，繼而選擇采用一種正式的聲明性語義，但這種方式并不能處理屬性約束上帶有量化條件的情形，且基于邏輯的事件識別系統(tǒng)已被先前研究［11］證明效率總體效率偏低。而ZStream 這種基于樹型模型的方法，雖然克服了狀態(tài)難以靈活轉(zhuǎn)換操作的缺陷，但也存在中間結(jié)果數(shù)量多、大量重復(fù)計(jì)算、批處理操作漏解等問題。

為了既能滿足現(xiàn)有的復(fù)雜事件匹配處理的需求，又能進(jìn)一步提高復(fù)雜事件匹配的效率，本文提出了一種利用事件有序列表進(jìn)行遞歸遍歷的復(fù)雜事件匹配方法。首先將來臨的事件流數(shù)據(jù)進(jìn)行初步的過濾，過濾掉與查詢模式不相關(guān)事件類型的事件實(shí)例，并將相關(guān)的事件實(shí)例緩存到對應(yīng)的有序列表當(dāng)中；再在有序事件列表上執(zhí)行查詢過濾操作，利用遞歸遍歷的方式得到滿足查詢模式的復(fù)雜事件候選序列集合；最后對候選序列進(jìn)一步做屬性驗(yàn)證，最終得到完全滿足查詢模式的全部復(fù)雜事件結(jié)果。

綜上所述，本文的主要工作如下：

1）提出了一種將事件緩存到有序事件列表上進(jìn)行復(fù)雜事件匹配的方法，將查詢模式中的約束條件分解為不同類型，再對不同類型的約束分別設(shè)計(jì)校驗(yàn)。

2）設(shè)計(jì)了一種基于遞歸的ReCEP 算法來確定復(fù)雜事件候選序列，能夠在時(shí)間戳允許范圍內(nèi)，有效地校驗(yàn)是否有對應(yīng)的一個(gè)甚至多個(gè)事件實(shí)例構(gòu)成復(fù)雜事件候選序列。

3）通過在股票交易模擬數(shù)據(jù)集上對算法的性能進(jìn)行實(shí)驗(yàn)和分析，驗(yàn)證了所提方法和算法的有效性和高效性。

1 相關(guān)工作

隨著信息技術(shù)的迅猛發(fā)展，各類信息系統(tǒng)產(chǎn)生的數(shù)據(jù)呈指數(shù)增長，大規(guī)模的數(shù)據(jù)分析處理在各行各業(yè)都得到了廣泛的應(yīng)用。復(fù)雜事件匹配作為數(shù)據(jù)分析處理方式之一，在學(xué)術(shù)領(lǐng)域已經(jīng)被廣泛地研究。近些年來，對于該問題國內(nèi)外陸續(xù)提出了許多研究方法，這些方法主要可以概括為三類：基于自動(dòng)機(jī)模型、基于邏輯模型和基于樹型模型的方法。

目前，基于自動(dòng)機(jī)模型的處理方法是最流行的復(fù)雜事件匹配處理方式。這類方法將非確定性自動(dòng)機(jī)作為它的計(jì)算模型，把查詢模式表示為一系列必須檢測的狀態(tài)，當(dāng)且僅當(dāng)轉(zhuǎn)換為最終狀態(tài)時(shí)認(rèn)為該模式已匹配。例如，SASE、SASE+［12］、Flink CEP［13］、Siddhi、Cayuga［14-15］等都是基于自動(dòng)機(jī)模型的處理方法。SASE 定義了一種用于描述復(fù)雜事件需滿足的各類約束條件的查詢語言，但該方法不支持迭代操作，并且在否定操作上也需要中間大量的無效計(jì)算。SASE+在SASE 的基礎(chǔ)上支持了閉包操作。Flink CEP 在原理上和SASE 類似，最大的不同在于Flink CEP 沒有固定一種語言去定義查詢模式，用戶需要編寫模式，所以有更大的靈活性。Siddhi 是一種商用處理引擎，功能類似于Flink CEP，可以支持代數(shù)的所有運(yùn)算符，但與Flink CEP 相反，Siddhi 提供了一種定義模式的語言。Cayuga 與前面介紹的所有方法不同之處在于Cayuga 沒有窗口，把事件看作是持續(xù)時(shí)間的，它也不支持否定操作。這類基于自動(dòng)機(jī)的方法由于其模型性質(zhì)導(dǎo)致其具有很多局限性，如匹配事件的順序必須與狀態(tài)轉(zhuǎn)換順序一致。其次，當(dāng)查詢模式中存在否定操作時(shí)，自動(dòng)機(jī)難以通過狀態(tài)轉(zhuǎn)移表達(dá)出否定操作。

基于邏輯模型的復(fù)雜事件處理系統(tǒng)針對非正式語義對許多真實(shí)世界的應(yīng)用程序構(gòu)成的限制的問題，采用了基于邏輯的時(shí)序表達(dá)方式，使用一種正式的聲明性語義。記錄識別系統(tǒng)（Chronicle Recognition System）［16-17］是一個(gè)典型的采用邏輯模型的例子，它是一個(gè)純粹的時(shí)間推理系統(tǒng)，輸入語言依賴于一種具體化的時(shí)間邏輯，其中邏輯規(guī)則與具體的時(shí)序關(guān)系相關(guān)聯(lián)；同時(shí)，該系統(tǒng)不支持帶有時(shí)間變量約束的數(shù)學(xué)運(yùn)算符，也不支持事件屬性上的量化條件。

基于樹型模型的復(fù)雜事件匹配方法是近年提出的方法，其以樹型的數(shù)據(jù)結(jié)構(gòu)作為查詢匹配的計(jì)算模型來處理復(fù)雜事件查詢。ZStream 是最先提出的基于樹型模型的復(fù)雜事件匹配方法。它將查詢轉(zhuǎn)換為樹模型，樹的葉子節(jié)點(diǎn)存儲事件集合，內(nèi)部節(jié)點(diǎn)對應(yīng)于運(yùn)算符。這種方法不會(huì)對隨時(shí)到來的數(shù)據(jù)流進(jìn)行立即匹配操作，而是等事件達(dá)到觸發(fā)狀態(tài)時(shí)，成批地進(jìn)行操作。從查詢語言角度看，ZStream 所用的樹型模型與自動(dòng)機(jī)模型的所表達(dá)的查詢語義其實(shí)是一致的，不同之處在于它的事件匹配順序不再依賴自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移順序，而是取決于樹型結(jié)構(gòu)上選擇葉子節(jié)點(diǎn)的順序。此外，E-Cube［18］也是采用樹結(jié)構(gòu)的一個(gè)復(fù)雜事件處理系統(tǒng)，E-Cube的主要功能在于其多查詢優(yōu)化的能力，也就是當(dāng)匹配的模式共享某些公共結(jié)構(gòu)時(shí)，它具有匹配多個(gè)模式的能力，同時(shí)避免了冗余和重復(fù)的計(jì)算。相較于基于自動(dòng)機(jī)模型的方法，基于樹結(jié)構(gòu)的方法雖然能更好地處理查詢中具有層次關(guān)系的復(fù)雜事件，但需要在每個(gè)中間節(jié)點(diǎn)上都計(jì)算中間結(jié)果，從而導(dǎo)致存在大量的重復(fù)計(jì)算。

2 預(yù)備知識與問題定義

復(fù)雜事件匹配處理是一種面向事件流的分析技術(shù)，對大量來自不同數(shù)據(jù)源的基本事件執(zhí)行過濾、關(guān)聯(lián)、聚合等操作，其目標(biāo)為從大量的基本事件構(gòu)成的事件流當(dāng)中，找出滿足查詢模式語義的更高層次的復(fù)雜事件。

定義1事件流。事件流S（s1，s2，…，sn）由一系列的基本事件實(shí)例構(gòu)成。其中si∈S為事件實(shí)例，包含了事件的類型（如不同的股票名稱）、事件的屬性（如股票交易價(jià)格等）和事件發(fā)生的時(shí)間戳等數(shù)據(jù)信息。

本文使用大寫英文字母表示基本事件類型（如事件類型A、事件類型B），事件實(shí)例則用相應(yīng)的小寫字母表示（如A的事件實(shí)例au、B 的事件實(shí)例bv，其中下標(biāo)表示該有序事件列表上第幾個(gè)事件實(shí)例）。圖1所示為一段事件流的示例。圖中事件流S包含了A、B、C 三種不同類型的股票價(jià)格變化事件，每個(gè)事件實(shí)例都包含了時(shí)間戳與交易價(jià)格信息。例如，b1為B事件類型的第1個(gè)事件實(shí)例，其時(shí)間戳為3，交易的價(jià)格為706。

圖1 事件流示例Fig.1 Example of event stream

復(fù)雜事件是由事件流S（s1，s2，…，sn）上的若干基本事件實(shí)例構(gòu)成的一個(gè)復(fù)合事件，表示為R（r1，r2，…，rm）。復(fù)雜事件表示在事件流上發(fā)生的客觀存在的具體事件，其語義常用查詢模式進(jìn)行表示。

定義2復(fù)雜事件查詢模式。復(fù)雜事件查詢模式Q由一組定義在基本事件上的約束條件構(gòu)成，用以表示客觀存在的目標(biāo)事件的屬性特征。

當(dāng)前的研究工作中已提出多種形式的查詢模式用以描述復(fù)雜事件［19］，其中SASE 所提出查詢模式具有簡潔的語法規(guī)則，同時(shí)具備靈活的表達(dá)能力，被廣泛使用于諸多復(fù)雜事件匹配技術(shù)中。本文沿用SASE 中的查詢模式定義，其基本結(jié)構(gòu)如下：

PATTERN <目標(biāo)序列形式>

WHERE <屬性約束條件>

WITHIN <時(shí)間窗口大小>

RETURN <輸出表達(dá)形式>

上述查詢模式由4 個(gè)部分構(gòu)成：PATTERN 子句定義了查詢模式的事件目標(biāo)序列（E1，E2，…，Eh），其中Ei表示定義在事件類型上的序列操作；WHERE 子句描述了復(fù)雜事件中的事件實(shí)例在事件屬性上需要滿足的約束條件；WITHIN 子句限定了該復(fù)雜事件在一定的時(shí)間間隔內(nèi)發(fā)生；RETURN 子句定義了復(fù)雜事件匹配結(jié)果的輸出表達(dá)模式。

事實(shí)上，上述查詢模式的約束條件來自PATTERN 子句、WHERE 子句與WITHIN 子句。PATTERN 子句約束了目標(biāo)復(fù)雜事件在事件類型序列上的條件，WHERE 子句約束了目標(biāo)事件需滿足的屬性條件，WITHIN 子句用時(shí)間窗口約束了目標(biāo)事件發(fā)生必須滿足的時(shí)間范圍。

例1 股票交易中的模式查詢。用戶查詢想在眾多繁雜的交易數(shù)據(jù)當(dāng)中找到想要的交易記錄，從而分析股票交易數(shù)據(jù)。將股票交易市場的交易數(shù)據(jù)作為事件流，給定的查詢模式Q如下所示：

上述查詢模式Q中，PATTERN 子句表示關(guān)心的股票交易情況，其中發(fā)生的事件要滿足（A；B；C）的序列形式，即A、B、C 三種類型股票要先后有序的發(fā)生。WHERE 子句定義了股票事件實(shí)例的股票交易價(jià)格屬性的約束條件，即A 型股票交易價(jià)格在1 000 元以上，A 種股票的交易價(jià)格大于B 種股票的y個(gè)百分比漲幅后的價(jià)格，且A 種股票交易價(jià)格低于C 種股票在z個(gè)百分比跌幅后的價(jià)格。WITHIN 子句限制了該事件發(fā)生的時(shí)間在10 min 之內(nèi)。最后要求輸出的復(fù)雜事件結(jié)果以A，B，C 的格式輸出所有滿足的復(fù)雜事件集合。

本文采用的查詢模式中PATTERN 子句能夠支持3 種序列操作，用以描述不同情況下的事件序列，序列操作的具體描述如下所示：

1）順序操作（A；B）：表示A 類型的事件實(shí)例a發(fā)生之后，有B 類型的事件實(shí)例b在其后發(fā)生，即滿足條件a.timestamp

2）否定操作（！A）：否定操作符為“！”，用于表示A 事件類型的事件實(shí)例不發(fā)生。例如查詢模式“A；！B；C”表示C 事件類型的事件實(shí)例c跟隨在A事件類型的事件實(shí)例a之后，即a.timestamp

3）閉包操作（Ak）：表示A 事件類型中的事件實(shí)例連續(xù)發(fā)生至少k次。閉包操作的連續(xù)事件實(shí)例并不是指實(shí)例在事件流上連續(xù)出現(xiàn)，而是指在后續(xù)類型事件實(shí)例到達(dá)前閉包操作下的事件實(shí)例出現(xiàn)至少k次。例如，對于查詢“A；Bk；C”，它要求在實(shí)例a與c之間存在至少k個(gè)事件實(shí)例b。

定義3復(fù)雜事件匹配問題定義。給定事件流S和復(fù)雜事件查詢模式Q，復(fù)雜事件匹配即根據(jù)查詢模式Q中給定的各類約束條件，在事件流S的基本事件實(shí)例中匹配出滿足所有約束條件的全部復(fù)雜事件結(jié)果。

復(fù)雜事件匹配的處理流程如圖2 所示。以查詢模式Q和事件流S作為復(fù)雜事件處理系統(tǒng)的輸入，系統(tǒng)輸出即為事件流S中的事件實(shí)例組合，這些事件實(shí)例必須滿足查詢Q中的各類約束條件。

圖2 復(fù)雜事件匹配處理流程Fig.2 Flow of complex event processing

例2 給定圖1 所示事件流S與例1 所示的復(fù)雜事件查詢模式Q，假設(shè)Q中的x值設(shè)定為1 000，y值為44，z值為49，那么該事件流S（局部片段）將可以匹配到一個(gè)滿足Q的復(fù)雜事件a1，b1，c2。

3 高效的復(fù)雜事件匹配方法

本章將介紹本文提出的利用有序事件列表進(jìn)行遞歸遍歷的復(fù)雜事件匹配方法，其基本思想為將查詢模式中的約束條件分解為不同類型，再針對不同類型的約束分別設(shè)計(jì)相應(yīng)的校驗(yàn)方法。

3.1 復(fù)雜事件查詢處理框架

本文提出的復(fù)雜事件匹配方法包括：事件緩存、查詢過濾和屬性驗(yàn)證3個(gè)步驟，如圖3所示。匹配方法的輸入為查詢模式Q與事件流S，每個(gè)步驟都校驗(yàn)了Q中不同部分的約束條件，最后輸出的事件序列為滿足Q所有約束的匹配結(jié)果。

圖3 復(fù)雜事件匹配處理框架Fig.3 Framework of complex event matching

1）事件緩存：事件流中會(huì)包含大量與查詢模式不相關(guān)的事件實(shí)例。例如，例1 中的查詢Q僅和事件類型A、B、C 相關(guān)，事件流中的其他事件類型（如D、E 等）與Q不相關(guān)。事件緩存的目的即利用有序緩沖區(qū)將與Q相關(guān)的事件實(shí)例按照事件類型進(jìn)行緩存。

2）查詢過濾：經(jīng)過事件緩存處理后，處理系統(tǒng)將得到有序事件列表，即事件實(shí)例緩沖區(qū)。查詢過濾的作用為在事件實(shí)例緩沖區(qū)上找到滿足查詢模式Q中PATTERN 子句約束與WITHIN 子句約束的事件實(shí)例。例如，對于上文例1 中的查詢Q，查詢過濾需要在事件流S上找到事件實(shí)例序列等。

3）屬性驗(yàn)證：通過前面兩個(gè)步驟獲取到的事件實(shí)例序列已經(jīng)滿足了查詢Q中PATTERN 子句與WITHIN 子句的約束，最后的屬性驗(yàn)證步驟則是要進(jìn)一步校驗(yàn)獲取到的候選事件序列是否滿足WHERE子句中的約束條件，即屬性條件的驗(yàn)證。

3.2 事件緩存

如3.1 節(jié)所述，事件緩存的目的是將事件流上的事件實(shí)例按照查詢模式中的目標(biāo)序列形式緩存到相對應(yīng)的有序緩沖區(qū)中。給定查詢模式Q，PATTERN 目標(biāo)序列形式為（E1，E2，…，Eh），為目標(biāo)序列中每個(gè)元素Ei對應(yīng)的事件類型創(chuàng)建相應(yīng)的緩沖篩選器，進(jìn)而利用篩選器將事件流上的事件實(shí)例緩存到相應(yīng)的有序緩沖區(qū)I（Ei）當(dāng)中。

WHERE 子句的約束條件可以分為兩大類：一類是事件實(shí)例屬性與常量間的比較條件，本文稱為常量約束；另一類是不同事件實(shí)例之間的屬性比較，稱為關(guān)聯(lián)約束。例如，在例1 當(dāng)中，WHERE 子句的條件a.price >x，由于x為用戶給定的常量值，該條件即為一個(gè)常量約束。對于條件a.price >b.price，其中a與b均為事件實(shí)例，該條件即為一個(gè)關(guān)聯(lián)約束。

按照3.1 節(jié)步驟將WHERE 子句中的常量約束和關(guān)聯(lián)約束全部都放到屬性驗(yàn)證環(huán)節(jié)進(jìn)行校驗(yàn)。然而，事實(shí)上常量約束僅僅作用于單一的事件類型，事件緩沖篩選器也是作用于單一的事件類型。因此，可以考慮將常量約束的校驗(yàn)放到事件緩存步驟相應(yīng)的緩沖篩選器中。這種方式會(huì)預(yù)先篩選掉事件流上不滿足這些常量約束的事件實(shí)例進(jìn)入到緩沖區(qū)當(dāng)中，減少了事件緩存與查詢過濾步驟產(chǎn)生的中間結(jié)果，從而提升查詢處理效率。

例3 對于前文所示查詢模式Q與事件流S，查詢模式Q中包含的目標(biāo)序列為（A；B；C）。根據(jù)該目標(biāo)序列分別為A、B、C 三種事件類型創(chuàng)建緩沖篩選器，如圖4 所示。由于Q中有常量約束a.price>x（假設(shè)x取值為1 000），該條件則被添加到A 事件類型的篩選器中。經(jīng)過該三個(gè)篩選器得到相對應(yīng)的有序事件列表，即緩沖區(qū)，分別為I（A）、I（B）與I（C）。I（A）中存儲了事件類型為A 的且交易價(jià)格屬性大于1 000 的事件實(shí)例（如a1、a2、a3等，原事件流中的a3由于交易價(jià)格屬性不滿足篩選條件，未被加入緩沖區(qū)中）；I（B）與I（C）則分別存儲了類型為B 與C 的事件實(shí)例。

圖4 將事件實(shí)例進(jìn)行過濾并劃分到不同有序緩沖區(qū)Fig.4 Event instances are filtered and divided into different ordered buffers

3.3 查詢過濾

事件流上的事件實(shí)例經(jīng)過事件緩存步驟之后被存儲到了相應(yīng)有序緩沖區(qū)中，接下來在有序緩沖區(qū)上執(zhí)行的查詢過濾則是復(fù)雜事件匹配的核心操作，其作用是匹配出滿足復(fù)雜事件目標(biāo)序列形式約束（PATTERN 子句約束）與時(shí)間窗口限制（WITHIN 子句約束）的復(fù)雜事件候選序列。為了匹配出上述候選序列，本文采用的方法為先從事件緩沖區(qū)中確定候選序列的初始事件實(shí)例，再設(shè)計(jì)基于遞歸的方法從事件緩沖區(qū)中匹配出滿足條件的復(fù)雜事件候選序列。下面分別對上述過程進(jìn)行詳細(xì)介紹。

3.3.1 確定初始事件實(shí)例

給定相關(guān)事件緩沖區(qū)，為了從中找到滿足約束條件的候選序列，最簡單的方式是對緩沖區(qū)中的事件實(shí)例進(jìn)行枚舉組合，然后再檢查組合后的事件序列是否滿足了上述約束條件。顯然，這種方式會(huì)枚舉出大量的無效事件序列出來，導(dǎo)致系統(tǒng)匹配效率低。為此，本文采用了一種基于遞歸的方法從事件緩沖區(qū)中找到候選序列。

由于候選序列需滿足查詢模式中目標(biāo)序列形式，因此可以通過查詢模式的目標(biāo)序列來確定起始事件E0，并且在該事件對應(yīng)的緩沖區(qū)I（E0）上獲取初始事件實(shí)例。此時(shí)，這些初始事件實(shí)例僅是可能存在的候選序列的第一個(gè)事件實(shí)例，即候選序列的初始事件實(shí)例。對于一個(gè)初始事件實(shí)例ei，當(dāng)且僅當(dāng)在剩余的其他類型的有序緩沖區(qū)中存在滿足時(shí)間窗口范圍內(nèi)的事件實(shí)例，使得它們能構(gòu)成的集合滿足查詢模式目標(biāo)序列，那么以此ei作為起始的這個(gè)事件實(shí)例組合則是一個(gè)復(fù)雜事件候選序列。

本文設(shè)計(jì)了算法1 來實(shí)現(xiàn)上述匹配過程。算法首先找到目標(biāo)序列中起始事件的有序緩沖區(qū)I（E0）（第1）行），并且逐個(gè)校驗(yàn)該緩沖區(qū)上的事件實(shí)例ei（第2）～5）行）。對于每一個(gè)事件實(shí)例ei，算法為其創(chuàng)建一個(gè)集合r，用于存儲當(dāng)前序列已確定了的事件實(shí)例（即已滿足了Q中目標(biāo)序列約束的事件實(shí)例，ei作為序列中第一個(gè)事件實(shí)例，r創(chuàng)建時(shí)ei已被加入其中）。然后，調(diào)用算法MatchSubEvents（見3.3.2 節(jié)算法2）來校驗(yàn)在其余事件緩沖區(qū)中是否存在時(shí)間窗口范圍內(nèi)的事件實(shí)例滿足了目標(biāo)序列的約束條件。如果校驗(yàn)成功，則滿足的事件實(shí)例將作為一個(gè)復(fù)雜事件候選序列存儲到集合R中（第6）行）。

算法1 復(fù)雜事件候選序列匹配算法CandCEP。

輸入 查詢Q中的目標(biāo)序列Se，事件實(shí)例緩存區(qū)I，時(shí)間窗口大小tw；

輸出 匹配的事件序列集合R。

3.3.2 獲取候選事件序列

在其他事件有序緩沖區(qū)中的驗(yàn)證都可以歸結(jié)為：在一個(gè)時(shí)間戳允許范圍內(nèi)，判斷緩沖區(qū)上是否有對應(yīng)的事件實(shí)例存在。由于構(gòu)成候選序列的事件實(shí)例會(huì)存在多個(gè)，每個(gè)事件實(shí)例需利用緩存區(qū)判斷是否真實(shí)存在，本文提出基于遞歸的方法依次校驗(yàn)剩余的事件實(shí)例。

在事件緩沖區(qū)上校驗(yàn)滿足條件的事件實(shí)例的思路為：通過查詢模式Q中WITHIN 子句中的時(shí)間窗口大小tw來計(jì)算出事件實(shí)例發(fā)生的時(shí)間戳范圍［tx，ty］，然后在對應(yīng)事件緩沖區(qū)當(dāng)中判斷［tx，ty］時(shí)間戳范圍內(nèi)是否存在事件實(shí)例。如果構(gòu)成候選序列的事件實(shí)例均存在，則找到的事件實(shí)例可以組合為一個(gè)復(fù)雜事件實(shí)例候選序列。

本文設(shè)計(jì)了基于遞歸的算法從有序的事件緩沖區(qū)中找到候選事件序列，如算法2 所示。

算法2 候選序列匹配算法MatchSubEvents。

輸入 事件類型Ej，查詢Q中的目標(biāo)序列Se，匹配的事件序列集合R。

算法2 具有3 個(gè)輸入?yún)?shù)。Ej表示目標(biāo)序列上當(dāng)前已校驗(yàn)成功的事件類型（即對應(yīng)的事件實(shí)例緩沖區(qū)上具有滿足約束條件的事件實(shí)例），Se為查詢Q中的目標(biāo)序列，R用于存儲遞歸校驗(yàn)后得到的復(fù)雜事件序列結(jié)果。

算法2 先根據(jù)Ej得到其后繼事件類型Ei（第1）行）。對于Ej.Sr中的存儲的每一個(gè)集合r（表示當(dāng)前已經(jīng)部分滿足目標(biāo)序列約束的事件實(shí)例集合），根據(jù)r中的事件實(shí)例計(jì)算出Ei類型的事件實(shí)例允許出現(xiàn)的時(shí)間戳范圍［tx，ty］（第3）行）。由于Ei的序列操作類型不同，在其對應(yīng)的事件實(shí)例緩沖區(qū)上進(jìn)行的校驗(yàn)操作也不同，因此算法2 需分別對Ei的三種序列操作類型進(jìn)行討論。

當(dāng)Ei的序列操作類型為順序操作時(shí)（第4）～8）行），算法在Ei對應(yīng)的事件緩沖區(qū)I（Ei）上找到所有滿足時(shí)間戳范圍［tx，ty］的事件實(shí)例ei。由于每一個(gè)實(shí)例ei的加入，都表示一種新的部分匹配上的目標(biāo)序列，因此需將ei加入到r中，并創(chuàng)建得到新的集合r'。r'再存入Ei.Sr中，用于下輪遞歸調(diào)用時(shí)進(jìn)行校驗(yàn)。

當(dāng)Ei的序列操作類型為閉包操作時(shí)（第9）～18）行），需先獲取閉包參數(shù)k值。然后設(shè)置一個(gè)臨時(shí)變量count，用于對滿足時(shí)間戳范圍的事件實(shí)例進(jìn)行計(jì)數(shù)。同理，算法2 需在I(Ei)上找到滿足時(shí)間戳范圍的事件實(shí)例。不同于處理順序操作，僅當(dāng)實(shí)例的個(gè)數(shù)大于閉包參數(shù)值k時(shí)，才創(chuàng)建新的集合r'，用于表示新的部分匹配序列。

當(dāng)Ei的序列操作類型為否定操作時(shí)（第19）～22）行），其處理方法不同于順序操作與閉包操作。復(fù)雜事件匹配過程不能包含否定操作下的事件實(shí)例，算法2 利用出現(xiàn)在時(shí)間戳范圍內(nèi)的實(shí)例的時(shí)間戳，來更新當(dāng)前部分匹配集合r的終止時(shí)間，從而保證匹配得到的目標(biāo)序列所在時(shí)間戳范圍不會(huì)包含否定的事件實(shí)例。

Ej.Sr中所有集合r都處理完成后，則判斷當(dāng)前處理的Ei是否為查詢模式目標(biāo)序列中最后一個(gè)事件類型。如Ei為最后一個(gè)事件類型，則當(dāng)前獲得的Ej.Sr中任意一個(gè)集合都表示一個(gè)滿足約束的候選序列，并將其加入到R中（第26）～28）行）；如不是，則算法進(jìn)行遞歸調(diào)用，直到最后一個(gè)事件類型處理完畢（第23）～24）行）。

例4 本例沿用例3 當(dāng)中股票交易數(shù)據(jù)緩存到有序緩沖區(qū)的數(shù)據(jù)，由例3 得到的查詢模式的起始事件類型A 緩沖區(qū)中的起始事件實(shí)例為a1：2，將該事件實(shí)例放到相應(yīng)的集合中存儲，如圖5 中EA.Sr所示。計(jì)算其允許后續(xù)事件實(shí)例時(shí)間戳范圍為［2，12］，在后續(xù)B 事件類型的緩沖區(qū)中能匹配到b1：3、b2：8 和b3：9 三個(gè)B 類型的事件實(shí)例，因此會(huì)創(chuàng)建三個(gè)新的序列組合存儲到集合中，如圖5 中EB.Sr所示。相同的，再由當(dāng)前r中組合b事件實(shí)例的時(shí)間戳計(jì)算出允許其后續(xù)c事件實(shí)例的時(shí)間戳范圍，如圖中a1：2，b1：3 允許后續(xù)時(shí)間戳范圍為［3，12］，那么在C 事件類型的有序緩沖區(qū)當(dāng)中可以驗(yàn)證到c2：6 和c3：10 兩個(gè)事件實(shí)例，并且創(chuàng)建新的序列組合存儲到如圖5 的EC.Sr中。同理b2：8 和b3：9 也都能匹配到c3：10 這個(gè)事件實(shí)例。判斷C 事件類型為查詢模式中最后一個(gè)事件類型時(shí)，將當(dāng)前存儲的事件實(shí)例集合即復(fù)雜事件候選序列輸出，如圖5 中右側(cè)四個(gè)候選序列結(jié)果。

圖5 查詢過濾過程示意圖Fig.5 Schematic diagram of query filtering process

3.4 屬性驗(yàn)證

由于查詢模式WHERE 子句中的關(guān)聯(lián)約束難以在分區(qū)緩存的事件緩存和查詢過濾中做校驗(yàn)處理，所以在這兩個(gè)步驟之后得到的復(fù)雜事件候選序列并不能保證完全符合查詢模式的約束。因此，系統(tǒng)最后一步屬性驗(yàn)證的目的是進(jìn)一步檢查查詢模式中的關(guān)聯(lián)約束，篩除不滿足該約束的候選序列。

針對查詢過濾產(chǎn)生的復(fù)雜事件候選序列，結(jié)果驗(yàn)證步驟則需要在其上添加篩選器，將篩選條件設(shè)置為查詢模式中的關(guān)聯(lián)約束。復(fù)雜事件候選序列通過帶有關(guān)聯(lián)約束的篩選器，篩選器檢查其上的屬性是否均滿足設(shè)定的關(guān)聯(lián)約束條件，不滿足關(guān)聯(lián)約束的候選序列會(huì)被篩除掉，滿足的即為正確的復(fù)雜事件結(jié)果。

例5 對于前文給定的查詢示例，在經(jīng)過例4的查詢過濾處理之后，得到復(fù)雜事件候選序列如圖6 中所示，再針對這些復(fù)雜事件候選序列添加查詢模式中的關(guān)聯(lián)約束作為驗(yàn)證條件，即a.price>（1+y%）*b.price 和a.price<(1-z%)*c.price。圖6 中實(shí)線框內(nèi)的a1，b2，c3這一候選序列的a1：2 的交易價(jià)格雖然低于c3：10的49%跌幅，但是它并不高于b2：8的44%漲幅，所以它并不是正確的復(fù)雜事件結(jié)果。最終，得到的四個(gè)復(fù)雜事件候選序列中有3個(gè)復(fù)雜事件作為結(jié)果被輸出。

圖6 屬性驗(yàn)證過程示意圖Fig.6 Schematic diagram of attribute verification process

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

本章通過實(shí)驗(yàn)測試對提出的利用事件緩沖區(qū)進(jìn)行遞歸遍歷的復(fù)雜事件匹配方法進(jìn)行性能分析和評價(jià)。實(shí)驗(yàn)在基于Java 的原型系統(tǒng)中實(shí)現(xiàn)了前面章描述的所有查詢評估技術(shù)。在本章中展示了本文所提方法和算法的性能研究結(jié)果，這些結(jié)果可以反映各種因素對性能的影響，并證明了本文方法的有效性和高效性。

4.1 實(shí)驗(yàn)設(shè)置

為了測試和評價(jià)本文所提方法的性能，將本文提出的算法記為ReCEP 算法，并與以下基于自動(dòng)機(jī)模型中目前比較流行的SASE 方法［8］和文獻(xiàn)［10］中所提的流處理和復(fù)雜的事件處理驅(qū)動(dòng)系統(tǒng)Siddhi方法進(jìn)行實(shí)驗(yàn)對比。

實(shí)驗(yàn)數(shù)據(jù)集采用SASE 股票模擬數(shù)據(jù)事件流生成器生成的股票交易模擬數(shù)據(jù)，該數(shù)據(jù)集包含100萬個(gè)股票交易數(shù)據(jù)信息，其中帶有時(shí)間戳、交易價(jià)格、交易數(shù)量等屬性。在實(shí)驗(yàn)過程中，為保證實(shí)驗(yàn)的可比性，將復(fù)雜事件查詢在各個(gè)實(shí)驗(yàn)中做一致性處理，即相同的目標(biāo)序列，相同的事件類型個(gè)數(shù)，相同的屬性約束，相同的事件窗口大小。在本章實(shí)驗(yàn)中將復(fù)雜事件查詢匹配結(jié)果的處理時(shí)間作為實(shí)驗(yàn)的性能指標(biāo)來進(jìn)行評估。

以下實(shí)驗(yàn)所有程序均使用2021.2.2.0 版本的IntelliJ IDEA 編寫，JDK 版本為1.8。實(shí)驗(yàn)環(huán)境為Intel Core i7-10510U@2.5 GHz，8 GB 內(nèi)存，1 TB 硬盤，Windows 10 64 位操作系統(tǒng)。

4.2 實(shí)驗(yàn)分析

在本章實(shí)驗(yàn)中，首先將本文提出的ReCEP 算法與SASE、Siddhi 方法在同一查詢模式下進(jìn)行總體性能對比實(shí)驗(yàn)，其次又進(jìn)行了不同影響因素，如復(fù)雜事件類型個(gè)數(shù)、時(shí)間窗口大小下各個(gè)方法間性能的比較。

實(shí)驗(yàn)一 在相同的復(fù)雜事件查詢模式下，實(shí)驗(yàn)一評估了三種方法在處理復(fù)雜事件時(shí)的總體性能。在該實(shí)驗(yàn)中查詢序列模式使用三種事件類型即序列為PATTERN（A；B；C），同時(shí)給定每組查詢相同的屬性約束條件，并且設(shè)置事件發(fā)生2 min內(nèi)，即WITHIN=120時(shí)復(fù)雜事件處理的性能。

通過在SASE 股票模擬數(shù)據(jù)事件流生成器生成的100 萬個(gè)股票交易模擬數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)測試，將三種方法對復(fù)雜事件處理結(jié)果所用的運(yùn)行時(shí)間作為評估指標(biāo)，發(fā)現(xiàn)SASE處理方法運(yùn)行時(shí)間為1 675 ms，Siddhi處理方法運(yùn)行時(shí)間為1 574 ms，而本文提出的ReCEP 算法僅需1 438 ms則可完成復(fù)雜事件結(jié)果的匹配，ReCEP 算法比SASE 方法的處理時(shí)間降低了約14.15%，比Siddhi方法降低了約8.64%。

實(shí)驗(yàn)二 改變查詢模式中事件類型的長度。實(shí)驗(yàn)二評估了查詢模式中事件類型的個(gè)數(shù)對處理性能的影響。在實(shí)驗(yàn)二中設(shè)置復(fù)雜事件查詢模式均在同一時(shí)間窗口WITHIN=120時(shí)，改變查詢模式中事件類型個(gè)數(shù)，分別由2 個(gè)遞增到6 個(gè)事件類型時(shí)的5 組評估結(jié)果。將三種方法對復(fù)雜事件處理結(jié)果所用的運(yùn)行時(shí)間作為評估指標(biāo)，對比實(shí)驗(yàn)結(jié)果如圖7 所示，其中ReCEP 方法比SASE 方法的處理時(shí)間降低了約25.63%，比Siddhi方法降低了約18.32%。

圖7 查詢模式中事件類型的個(gè)數(shù)對性能的影響Fig.7 Influence of number of event types in query mode on performance

實(shí)驗(yàn)三 改變查詢模式中時(shí)間窗口約束的大小。實(shí)驗(yàn)三評估了查詢模式中時(shí)間約束窗口大小對處理性能的影響。在實(shí)驗(yàn)三當(dāng)中設(shè)置查詢中的序列模式為固定的三種事件類型順序操作，即PATTERN（A；B；C），同時(shí)給定每組查詢相同的屬性約束條件，分別測試了時(shí)間窗口WITHIN 從60 到300 之間的5 組評估結(jié)果。將三種方法對復(fù)雜事件處理結(jié)果所用的運(yùn)行時(shí)間作為評估指標(biāo)，對比實(shí)驗(yàn)結(jié)果如圖8 所示，其中ReCEP算法比SASE 方法的處理時(shí)間降低了約14.72%，比Siddhi 方法降低了約9.74%。

圖8 查詢模式中時(shí)間約束的大小對性能的影響Fig.8 Influence of size of time constraint in query mode on performance

上述實(shí)驗(yàn)結(jié)果表明，本文提出的在有序緩沖區(qū)上基于遞歸操作的復(fù)雜事件處理方法無論在處理查詢模式中事件類型較多或者時(shí)間窗口約束較大的情況下，都能夠有效得到復(fù)雜事件處理結(jié)果，并且在處理性能上可以更有效地減少處理時(shí)間。

5 結(jié)語

本文提出了新型的在有序緩沖區(qū)上的復(fù)雜事件匹配處理方法，并針對該方法設(shè)計(jì)了一種基于遞歸的查詢過濾算法ReCEP。根據(jù)給定的復(fù)雜事件查詢模式，通過對事件流進(jìn)行事件緩存、查詢過濾和屬性驗(yàn)證的一系列步驟之后，能夠正確地求解出所有復(fù)雜事件結(jié)果。通過利用SASE 提供的模擬真實(shí)股票交易數(shù)據(jù)的事件流生成器，模擬出股票交易數(shù)據(jù)，針對股票模擬數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測試和分析，實(shí)驗(yàn)結(jié)果表明本文方法能有效進(jìn)行復(fù)雜事件匹配。由于本文只考慮了事件流中事件實(shí)例均為正常順序來臨時(shí)產(chǎn)生的復(fù)雜事件匹配，實(shí)際中由于網(wǎng)絡(luò)延遲等原因數(shù)據(jù)的來臨可能產(chǎn)生亂序的情況，怎樣處理事件流中存在亂序的事件實(shí)例，將是下一步的研究方向。