摘要： 針對(duì)現(xiàn)有復(fù)雜事件匹配處理方法存在匹配代價(jià)高的問題，提出了一種在有序事件列表上選擇最佳匹配順序進(jìn)行遞歸遍歷的復(fù)雜事件匹配方法OptiSeq。將事件實(shí)例按照查詢模式中不同事件類型緩存到有序事件列表中，并通過事件列表中事件實(shí)例的數(shù)量選擇最優(yōu)的查詢匹配起點(diǎn)及查詢匹配順序，之后在有序列表上對(duì)不同約束分別進(jìn)行遞歸校驗(yàn)，最終輸出完全滿足查詢模式的所有復(fù)雜事件結(jié)果。該方法克服了使用自動(dòng)機(jī)模型固定狀態(tài)轉(zhuǎn)換的弊端，也避免了使用樹型模型批處理操作漏解的問題，并且合理優(yōu)化了匹配順序，進(jìn)一步提高查詢匹配效率。在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)測(cè)試與分析，與當(dāng)前流行的SASE、Siddhi兩種復(fù)雜事件處理方法進(jìn)行比較。實(shí)驗(yàn)表明，所提出的方法能夠在保證匹配正確性的同時(shí)，有效地減少匹配過程中的冗余計(jì)算，提高整體匹配效率。

關(guān)鍵詞： 復(fù)雜事件匹配；遞歸比較；有序事件列表；查詢過濾；屬性驗(yàn)證

中圖分類號(hào)： TP315" " " " 文獻(xiàn)標(biāo)志碼： A

doi：10.3969/j.issn.2095-1248.2023.02.005

Complex event matching based on recursive comparison of event list

XIA Xiu-feng， DING Jian-li， QIU Tao， XIE Pei-liang

（College of Computer Science， Shenyang Aerospace University， Shenyang 110136，China）

Abstract： Aiming at the problem of high matching cost in the existing complex event matching processing methods， a complex event matching method OptiSeq was proposed， which selected the best matching order on the ordered event list for recursive traversal. The event instances were cached in the ordered event list according to the different event types in the query mode， and the optimal query matching starting point and query matching order were selected by judging the number of event instan ces in the event list. Then， the OptiSeq method performed recursive validation and ultimately output all complex event results that fully met the query pattern.This method overcame the drawbacks of using automata model to fix state transitions， and also avoided the problem of missing solutions in batch operations using tree models， and optimized the matching order reasonably， further improved query matching efficiency. Experiments were tested and analyzed on simulated datasets and real datasets， and compared with the current popular SASE and Siddhi complex event processing methods. The experiments show that the proposed method can effectively reduce the redundant calculations in the matching process and improve the overall matching efficiency while ensuring the correctness of matching.

Key words： complex event matching；recursive comparison；ordered event list；query filtering；attribute verification

隨著信息技術(shù)產(chǎn)業(yè)發(fā)展的進(jìn)一步深化及物聯(lián)網(wǎng)技術(shù)、傳感器網(wǎng)絡(luò)和射頻識(shí)別等技術(shù)與應(yīng)用的快速發(fā)展，大規(guī)模的流式數(shù)據(jù)從各式各樣的應(yīng)用系統(tǒng)中不斷產(chǎn)生和涌現(xiàn)，包括設(shè)備運(yùn)行狀態(tài)數(shù)據(jù)、企業(yè)信息化數(shù)據(jù)、生產(chǎn)參數(shù)數(shù)據(jù)等。面對(duì)這些大量的描述性物理數(shù)據(jù)，用戶迫切地希望能夠在這些海量數(shù)據(jù)中及時(shí)發(fā)現(xiàn)、挖掘一些有意義的數(shù)據(jù)，如何根據(jù)特定的匹配條件高效地獲取并處理有價(jià)值的數(shù)據(jù)信息成為研究的熱點(diǎn)，復(fù)雜事件匹配處理技術(shù)也因此應(yīng)運(yùn)而生。例如在股票交易信息分析［1］、道路交通規(guī)劃［2］、傳感器網(wǎng)絡(luò)［3］、數(shù)控機(jī)床系統(tǒng)［4］和海量航天數(shù)據(jù)分析［5］等方面都有廣泛的應(yīng)用。

盡管目前已有一些復(fù)雜事件匹配處理方法，例如SASE［6-7］、ZStream［8］、Siddhi［9］等，但這些方法在處理簡(jiǎn)單查詢模式下的事件匹配時(shí)存在一定局限性。SASE方法將查詢轉(zhuǎn)化為一種自動(dòng)機(jī)模型，其自然表達(dá)方式是一系列狀態(tài)轉(zhuǎn)換。顯然這種固定的狀態(tài)轉(zhuǎn)換形式限制了事件匹配的順序，使事件處理的靈活性有很大的限制。一旦查詢模式中存在否定事件類型與非否定事件類型之間的關(guān)聯(lián)約束時(shí)，固定處理順序的狀態(tài)轉(zhuǎn)換模式很難直接跨過否定事件狀態(tài)去執(zhí)行后續(xù)事件狀態(tài)的匹配操作。ZStream是基于樹型模型的方法，雖然克服了自動(dòng)機(jī)的固定狀態(tài)轉(zhuǎn)換操作，但也存在中間結(jié)果數(shù)量多、大量重復(fù)計(jì)算、批處理操作漏解等問題。另外，目前大多數(shù)方法都沒有研究最佳的查詢匹配順序，僅按照查詢模式下目標(biāo)序列的順序執(zhí)行復(fù)雜事件查詢匹配操作。

為了既能滿足現(xiàn)有的復(fù)雜事件匹配處理的需求，又能進(jìn)一步提高復(fù)雜事件匹配的效率，本文提出了一種在有序事件列表上選擇最佳匹配順序進(jìn)行遞歸遍歷的復(fù)雜事件匹配方法。不同于現(xiàn)有的轉(zhuǎn)換模型，該方法在有序事件列表上執(zhí)行操作，即將有序事件列表作為事件流中事件實(shí)例的有序緩沖區(qū)，同時(shí)優(yōu)化了查詢匹配順序，通過判別事件列表中事件實(shí)例數(shù)量，來選擇對(duì)查詢計(jì)劃最優(yōu)的查詢匹配起點(diǎn)及更優(yōu)的查詢匹配順序。

1 相關(guān)工作

復(fù)雜事件處理是從事件驅(qū)動(dòng)業(yè)務(wù)出發(fā)的，將系統(tǒng)中產(chǎn)生的每一條數(shù)據(jù)記錄都看成是一個(gè)事件，復(fù)雜事件執(zhí)行引擎會(huì)根據(jù)事先制定好的描述規(guī)則對(duì)事件流進(jìn)行相應(yīng)的判斷、過濾、關(guān)聯(lián)等操作，然后給用戶輸出一系列更高層次的復(fù)合事件。其中復(fù)雜事件描述規(guī)則一般包含用戶感興趣的事件語義或?qū)I(yè)領(lǐng)域中某種既定的標(biāo)準(zhǔn)和規(guī)范。也就是說，復(fù)雜事件能夠在實(shí)時(shí)事件流中處理識(shí)別某個(gè)人為定義的復(fù)合事件，并向用戶反饋?zhàn)R別的結(jié)果。近年來，隨著復(fù)雜事件處理技術(shù)的廣泛使用，國(guó)內(nèi)外針對(duì)此問題的研究方法也被陸續(xù)提出，由Giatrakos等［10］的總結(jié)工作發(fā)現(xiàn)，目前現(xiàn)有的復(fù)雜事件處理技術(shù)大致可以概括為基于自動(dòng)機(jī)模型、基于邏輯模型以及基于樹的模型3類。

基于自動(dòng)機(jī)模型的處理方法是當(dāng)前研究工作中最多的一類技術(shù)，例如Diao等［11］提出的SASE方法以及其衍生研究SASE+方法、Demers等［12-13］提出的Cayuga方法、Siddhi方法以及應(yīng)用到工業(yè)中的Flink CEP［14］方法等。此類方法均把查詢模式轉(zhuǎn)換在自動(dòng)機(jī)模型上進(jìn)行操作，將查詢模式表示為一系列必須檢測(cè)的狀態(tài)，當(dāng)且僅當(dāng)狀態(tài)轉(zhuǎn)換為終止?fàn)顟B(tài)時(shí)，才產(chǎn)生匹配結(jié)果。自動(dòng)機(jī)方法存在一定的局限性，因?yàn)樽詣?dòng)機(jī)的自然表達(dá)方式是一系列狀態(tài)轉(zhuǎn)換，因此此類方法強(qiáng)加了由該狀態(tài)轉(zhuǎn)換圖確定的固定評(píng)估順序。這不僅導(dǎo)致復(fù)雜事件查詢處理靈活性降低，也會(huì)使否定操作的處理難以在狀態(tài)中簡(jiǎn)單地完成，同時(shí)也很難支持并發(fā)事件即聯(lián)合查詢的處理。

與自動(dòng)機(jī)相比，基于邏輯的復(fù)雜事件處理系統(tǒng)關(guān)注點(diǎn)有所不同，此類方法傾向于忽略查詢規(guī)則中各種選擇和消費(fèi)策略的存在，關(guān)注的是事件發(fā)生的時(shí)序邏輯關(guān)系。例如Dousson［15］提出的CRS方法、Artikis等［16］提出的RTEC方法等?；谶壿嫷姆椒ū举|(zhì)上是一組由時(shí)間限制聯(lián)系在一起的事件，其發(fā)生可能取決于上下文在時(shí)間邏輯上的推理，因此除了時(shí)間限制外，這類方法很難支持包含數(shù)學(xué)運(yùn)算符、屬性條件約束等條件的操作。

基于樹型模型的處理方法是利用樹的查詢計(jì)劃結(jié)構(gòu)來表示復(fù)雜事件查詢模式，例如Yuan 等提出的ZStream方法［8］、Liu等［17］提出的E-Cube方法、喻學(xué)軍等［18］提出的Esper方法，還有鄭利強(qiáng)等［19］研究的針對(duì)正規(guī)樹模式的復(fù)雜事件查詢方法等。這類方法將查詢模式解析并轉(zhuǎn)換為樹型結(jié)構(gòu)的表示形式，葉緩沖區(qū)用來存儲(chǔ)來自事件流的原始事件實(shí)例，內(nèi)部節(jié)點(diǎn)緩沖區(qū)存儲(chǔ)來自子樹緩沖區(qū)、滿足一定查詢模式的中間結(jié)果組合。雖然使用樹型結(jié)構(gòu)模型可以解決固定狀態(tài)轉(zhuǎn)換不足的問題，使得復(fù)雜事件處理操作更加靈活，但事實(shí)上這類方法依舊存在著大量的重復(fù)計(jì)算，批處理操作存在漏解等弊端。

基于以上研究可以發(fā)現(xiàn)，無論是基于自動(dòng)機(jī)還是基于樹的方法來實(shí)現(xiàn)復(fù)雜事件處理，為保證復(fù)雜事件匹配結(jié)果的正確性和完整性，均需要存儲(chǔ)大量的事件實(shí)例或進(jìn)行大量的重復(fù)匹配，給處理器計(jì)算能力和存儲(chǔ)器等硬件資源都帶來了不小的負(fù)荷。因此本文尋求一種既能滿足現(xiàn)有復(fù)雜事件的匹配處理需求，又能進(jìn)一步提高匹配效率的復(fù)雜事件處理方法。

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

定義1" 事件流 事件流S（s1，s2，…，sn）由一系列的基本事件實(shí)例構(gòu)成。其中si∈S，為事件實(shí)例，它包含了事件的類型、屬性和事件發(fā)生時(shí)的時(shí)間戳等信息。本文使用大寫英文字母表示基本事件類型（如事件類型A、事件類型B），事件實(shí)例則用相應(yīng)的小寫字母表示 （如A的事件實(shí)例a、B的事件實(shí)例b） ，如圖1所示。

定義2" 簡(jiǎn)單事件與復(fù)雜事件 事件包含簡(jiǎn)單事件和復(fù)雜事件。簡(jiǎn)單事件可以看作一個(gè)活動(dòng)點(diǎn)的發(fā)生，它不包含事件關(guān)系；而復(fù)雜事件是簡(jiǎn)單事件通過事件關(guān)系進(jìn)行組合的更深層次事件。

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

Grea等［20］的研究工作中已提出多種形式的復(fù)雜事件描述語言，用于定義復(fù)雜事件查詢，其中SASE提出了最具有代表性的復(fù)雜事件描述語言，本文沿用SASE的語言形式，總體結(jié)構(gòu)如下：

PATTERN lt;目標(biāo)序列形式gt;

WHERE lt;屬性約束條件gt;

WITHIN lt;時(shí)間窗口大小gt;

RETURN lt;輸出表達(dá)形式gt;

其中，目標(biāo)序列形式定義了復(fù)雜事件處理結(jié)果需滿足基本形式以及序列查詢操作（例如順序操作、否定操作等），屬性約束條件限制了事件實(shí)例在事件屬性上需要滿足的約束條件，時(shí)間窗口大小約束了復(fù)雜事件結(jié)果中事件實(shí)例發(fā)生的時(shí)間間隔，輸出表達(dá)形式表明了輸出結(jié)果樣式。本文采用的查詢模式中PATTERN子句能夠支持3種序列操作，用以描述不同情況下的事件序列，序列操作的具體描述如下：

（1） 順序操作（A；B）

表示A類型的事件實(shí)例a發(fā)生之后，有B類型的事件實(shí)例b在其后發(fā)生，即其發(fā)生的時(shí)間戳滿足條件a.timestamplt;b.timestamp，并且滿足時(shí)間范圍約束b.timestamp-a.timestamp≤tw。

（2） 否定操作（！A）

表示A事件類型的事件實(shí)例不發(fā)生。例如查詢模式“A；！B；C”表示C事件類型的事件實(shí)例c跟隨在A事件類型的事件實(shí)例a之后發(fā)生，即a.timestamplt;c.timestamp，且在這之間沒有b的事件實(shí)例發(fā)生。

（3） 閉包操作（Ak）

表示A事件類型中的事件實(shí)例連續(xù)發(fā)生至少k次。例如，對(duì)于查詢“A；Bk；C”，要求在事件實(shí)例a與c之間存在至少k個(gè)事件實(shí)例b。

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

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

Q ： PATTERN A；B；C；D

WHERE a.pricegt;x

AND a.pricegt;（1+y%）×b.price

AND c.pricelt;（1-z%）×d.price

WITHIN 10 min

RETURN A，B，C，D

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

3 查詢匹配計(jì)劃

本節(jié)在有序事件列表上選擇最佳匹配順序，并通過遞歸遍歷進(jìn)行復(fù)雜事件匹配的方法，其基本思想是把事件流中的事件實(shí)例緩存到有序事件列表上，對(duì)前期部分事件流片段進(jìn)行數(shù)據(jù)采樣，計(jì)算各事件列表上緩存事件實(shí)例的數(shù)量，利用數(shù)量的多少作為后期選擇事件匹配處理順序的依據(jù)。再對(duì)列表上的事件實(shí)例執(zhí)行查詢匹配操作，其中包含確定最優(yōu)的起始序列、選擇合適匹配順序并在其余事件列表中校驗(yàn)滿足的事件實(shí)例，再組成復(fù)雜事件候選結(jié)果，最終通過進(jìn)一步的屬性驗(yàn)證得到完全正確的復(fù)雜事件匹配結(jié)果。本文所提方法的主要處理框架如圖3所示。

3.1 事件緩存

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

查詢模式中的所有約束條件都應(yīng)放在屬性驗(yàn)證步驟中進(jìn)行校驗(yàn)，然而這種方式明顯會(huì)使查詢匹配過程中保留大量無效的中間結(jié)果，造成時(shí)間及空間上的浪費(fèi)。事實(shí)上有些約束條件可以更早地執(zhí)行判斷。因此，本文將WHERE子句的約束條件分為兩大類，一類是事件實(shí)例屬性與常量間的比較條件，本文稱為常量約束；另一類是不同事件實(shí)例之間的屬性比較，稱為關(guān)聯(lián)約束。例如，在例1當(dāng)中，WHERE子句的條件a.pricegt;x，由于x為用戶給定的常量值，該條件即為一個(gè)常量約束。對(duì)于條件a.pricegt;b.price，其中a與b均為事件實(shí)例，該條件即為一個(gè)關(guān)聯(lián)約束。常量約束僅作用于單一的事件類型，而事件緩沖篩選器也僅作用于單一的事件類型。因此，可以考慮將常量約束的校驗(yàn)放到事件緩存步驟相應(yīng)的緩沖篩選器中。這種方式會(huì)預(yù)先篩選掉事件流上不滿足這些常量約束的事件實(shí)例，避免其進(jìn)入緩沖區(qū)，減少了事件緩存與查詢過濾步驟產(chǎn)生的中間結(jié)果，從而提高查詢處理效率。

例2" 結(jié)合前文圖1所示的事件流S以及例1給出的查詢模式Q進(jìn)行事件緩存，如圖4所示。按照查詢模式中目標(biāo)序列形式添加篩選器，需構(gòu)建4個(gè)有序事件列表，即緩沖區(qū)分別為I（A）、I（B）、I（C）與I（D）。與查詢模式無關(guān)的事件類型會(huì)被過濾掉，如事件f1、 f2。同時(shí)篩選器中添加常量約束條件，不滿足常量約束a.pricegt;x （設(shè)x值為1 000）的事件實(shí)例也會(huì)被過濾掉，如a5。

3.2 數(shù)據(jù)采樣

數(shù)據(jù)采樣的目的是確定更優(yōu)的匹配處理順序，使用更少的匹配次數(shù)獲得復(fù)雜事件匹配結(jié)果。在目標(biāo)序列形式（E1，E2，…，Eh）相應(yīng)的有序緩沖區(qū)I（Ei）（i∈1，2，…，h）中，對(duì)前期來自事件流的部分緩存事件實(shí)例進(jìn)行采樣計(jì)數(shù)，計(jì)算各事件列表上緩存事件實(shí)例的數(shù)量，即有序列表的長(zhǎng)度Numi（i∈1，2，…，h），利用各有序緩沖區(qū)上事件實(shí)例數(shù)量的多少作為后期確定最優(yōu)的起始序列，選擇適合匹配順序的依據(jù)。由圖4緩存得到的有序列表中的部分事件流片段可知，A事件列表中事件實(shí)例很多，而B中的事件實(shí)例數(shù)量相對(duì)較少。顯而易見，將B作為查詢匹配的起始列表，會(huì)產(chǎn)生更少的結(jié)果，從而使匹配次數(shù)減少。

3.3 查詢過濾

經(jīng)過事件緩存步驟之后，事件流上的事件實(shí)例被存儲(chǔ)到相應(yīng)有序緩沖區(qū)中，接下來在有序緩沖區(qū)上執(zhí)行的查詢過濾則是復(fù)雜事件匹配的核心操作，其作用是匹配出滿足復(fù)雜事件目標(biāo)序列形式約束（PATTERN子句約束）與時(shí)間窗口限制（WITHIN子句約束）的復(fù)雜事件候選序列。為了減少開銷，提高匹配效率，對(duì)中間執(zhí)行匹配操作的次數(shù)越少越好。因此本文采用的方法為利用采樣獲取各個(gè)事件類型中事件實(shí)例的多少，選取數(shù)量最少的事件列表作為初始事件實(shí)例，并通過計(jì)算初始事件列表前、后兩側(cè)其余事件列表上平均事件實(shí)例數(shù)量來選擇合適的匹配順序，再基于遞歸的方法從事件緩沖區(qū)中匹配出滿足條件的復(fù)雜事件候選序列。

3.3.1 確定起始序列

常規(guī)的查詢匹配方式是在前文給定的相關(guān)事件緩沖區(qū)中按照查詢模式中PATTERN子句目標(biāo)序列的順序進(jìn)行查詢匹配，顯然當(dāng)目標(biāo)序列中第一個(gè)事件類型有大量實(shí)例被緩存時(shí)，這種匹配方式會(huì)產(chǎn)生大量的中間查詢結(jié)果，從而導(dǎo)致匹配次數(shù)大量增加，影響了查詢匹配效率。為減少查詢匹配次數(shù)，提高效率，本文選取有序事件列表上事件實(shí)例緩存數(shù)量最少的事件作為查詢的初始事件。

為了確定一個(gè)最優(yōu)的起始事件，選取前文采樣中事件實(shí)例緩存數(shù)量最少Numk對(duì)應(yīng)的事件列表Ek作為查詢過濾的起始事件列表，并且在該事件對(duì)應(yīng)的緩沖區(qū)I（Ek）上獲取初始事件實(shí)例em，em為該事件緩沖區(qū)上的事件實(shí)例。此時(shí)，這些初始事件實(shí)例僅僅是可能存在的候選序列上的某一個(gè)事件實(shí)例。針對(duì)其余的事件序列，若要查詢匹配的可能組成候選序列的事件實(shí)例，可采用基于遞歸的方法，從其余各個(gè)事件緩沖區(qū)中找到候選序列。對(duì)于一個(gè)初始事件實(shí)例em，當(dāng)且僅當(dāng)在剩余的其他類型的有序緩沖區(qū)中存在滿足時(shí)間窗口范圍內(nèi)的事件實(shí)例，使得它們能構(gòu)成的集合滿足查詢模式目標(biāo)序列時(shí)，以em作為起始事件的事件組合就是一個(gè)復(fù)雜事件候選序列。本文設(shè)計(jì)了算法1來實(shí)現(xiàn)上述匹配過程。

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

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

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

（1）Ek←采樣確定的含有最少事件實(shí)例的有序事件列表Se.getSimpleMinEvent（）；

（2）while （em←I（Ek）.nextEvent（）amp;em！=1） do

（3） 通過em創(chuàng)建新集合r；

（4） 將r 加入Ek.Sr中；

（5） MatchSubEvents（Ek，Se，R）；

（6）return R；

算法通過采樣確定的含有最少事件實(shí)例Numk的有序事件列表Ek，將Ek對(duì)應(yīng)的有序緩沖區(qū)I（Ek）作為查詢匹配的起始事件列表（第1行），并且逐個(gè)校驗(yàn)該事件列表上的事件實(shí)例em （第2～5行）。對(duì)于每一個(gè)事件實(shí)例em，算法為其創(chuàng)建一個(gè)集合r，用于存儲(chǔ)當(dāng)前序列已確定了的事件實(shí)例（即已滿足了Q中目標(biāo)序列約束的事件實(shí)例，em作為序列中第一個(gè)事件實(shí)例，r創(chuàng)建時(shí)em已被加入其中）。然后，調(diào)用算法VerifyEvents （見3.3.2算法2）來校驗(yàn)在其余事件緩沖區(qū)中，是否存在時(shí)間窗口范圍內(nèi)的事件實(shí)例滿足目標(biāo)序列的約束條件。如果校驗(yàn)成功，則滿足的事件實(shí)例將作為一個(gè)復(fù)雜事件候選序列存儲(chǔ)到集合R中（第6行）。

3.3.2 獲取候選序列

在其他事件有序緩沖區(qū)中的驗(yàn)證都可以歸結(jié)為：在一個(gè)時(shí)間戳允許范圍內(nèi)，判斷事件列表緩沖區(qū)上是否有對(duì)應(yīng)的事件實(shí)例存在。由于構(gòu)成候選序列的事件實(shí)例存在多個(gè)，每個(gè)事件實(shí)例需利用緩存區(qū)判斷是否真實(shí)存在，本文提出基于遞歸的方法依次校驗(yàn)剩余的事件實(shí)例。與常規(guī)方式不同的是，該方法中起始事件不再是目標(biāo)序列中的第一個(gè)事件類型，因此需要以起始事件為起點(diǎn)，向查詢模式目標(biāo)序列前、后兩側(cè)其余的事件列表進(jìn)行校驗(yàn)。

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

為了減少匹配次數(shù)，考慮以確定的起始事件列表為起點(diǎn)，選取優(yōu)先向前校驗(yàn)或者優(yōu)先向后校驗(yàn)中更好的查詢匹配順序。在本文中，通過初始事件列表前、后兩側(cè)其余事件列表上平均事件實(shí)例數(shù)量Num前和Num后的大小來作為優(yōu)先向前校驗(yàn)或者向后校驗(yàn)的依據(jù)。其中Num前表示在事件序列Ek前面的E1～Ek-1個(gè)事件序列上，對(duì)事件實(shí)例采樣個(gè)數(shù)求取平均值，即（Num1+…+Numk-1）/（k-1）。同樣的，Num后表示在事件序列Ek后面的Ek+1～Eh個(gè)事件序列上，對(duì)事件實(shí)例采樣個(gè)數(shù)求取平均值，即（Numk+1+…+Numh）/（h-k）。

本文設(shè)計(jì)了帶有選擇最優(yōu)查詢匹配順序的基于遞歸的優(yōu)化算法，從事件列表緩沖區(qū)中找到候選事件序列，如算法2 所示。

算法2" 候選序列匹配算法VerifyEvents

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

輸出：無。

（1）if Num前gt;Num后

（2） Ei←Se.getNextEk（Ej） ； //先查詢校驗(yàn)Ek后面各個(gè)事件列表上的事件實(shí)例

（3） for each set r in Ej.Sr do

（4） ［tx，ty］←computeTimeRange（Ei，r） ； //計(jì)算后面時(shí)間戳允許的范圍

（5） if Ei.op_type=序列操作 then

（6） for each event ei in I（Ei） s.t. ei.timestamp∈［tx，ty］ do

（7） 通過r創(chuàng)建新集合r'；

（8） 將ei 加入r' 中；

（9） 將r' 加入Ei.Sr中；

（10） else if Ei.op_type=閉包操作 then

（11） k←Ei上的閉包參數(shù)；

（12） count←0 ； S'←? ；

（13） for each event ei in I（Ei） s.t. ei.timestamp∈［tx，ty］ do

（14） count ++；

（15） add ei to S'；

（16） if count≥k then

（17） 通過r創(chuàng)建新集合r'；

（18） 將 S' 中所有事件實(shí)例加入r' 中；

（19） 將r' 加入Ei. Sr中；

（20） else if Ei.op_type=否定操作 then

（21） for each event ei in I（Ei） s.t. ei.timestamp∈［tx，ty］ do

（22） 將ei的時(shí)間戳設(shè)置成r的時(shí)間窗口的終止時(shí)間；

（23） break； //（5）～（13）行為判別各個(gè)事件列表操作類型，執(zhí)行校驗(yàn)操作

（24） if Ei ！= Se.lastEvent（） then

（25） MatchSubEvents（Ei，Se后，R）；

（26） else

（27） Ei←Se.getPrevEk （Ej） ； //再去查詢校驗(yàn)Ek前面各個(gè)事件列表上的事件實(shí)例

（28） for each set r in Ej.Sr do

（29） ［tx，ty］←computeTimeRange（r，Ei） ； //計(jì)算前面時(shí)間戳允許的范圍

（30） 執(zhí)行（5）～（13）行的校驗(yàn)操作；

（31） if Ei ！= Se.firstEvent（） then

（32） MatchSubEvents（Ei，Se前，R）；

（33） else

（34） for each set r in Ei.Sr do

（35） 將r中事件序列加入R中；

（36） Ei.Sr←?；

（37） return R；

（38） else Num前l(fā)t;Num后

（39） Ei←Se.getPrevEk （Ej） ； //先查詢校驗(yàn)Ek前面各個(gè)事件列表上的事件實(shí)例

（40） for each set r in Ej.Sr do

（41） ［tx，ty］←computeTimeRange（r，Ei） ； //計(jì)算前面時(shí)間戳允許的范圍

（42） 執(zhí)行（5）～（13）行的校驗(yàn)操作；

（43） if Ei ！= Se.firstEvent（） then

（44） MatchSubEvents（Ei，Se前，R）；

（45） else

（46） Ei←Se.getNextEk （Ej） ； //再查詢校驗(yàn)Ek后面各個(gè)事件列表上的事件實(shí)例

（47） for each set r in Ej.Sr do

（48） ［tx，ty］←computeTimeRange（Ei，r） ； //計(jì)算后面時(shí)間戳允許的范圍

（49） 執(zhí)行（5）～（13）行的校驗(yàn)操作；

（50） if Ei ！= Se.lastEvent（） then

（51） MatchSubEvents（Ei，Se后，R）；

（52） else

（53） for each set r in Ei.Sr do

（54） 將r中事件序列加入R中；

（55） Ei.Sr←?；

（56） return R；

算法2有3個(gè)輸入?yún)?shù)，其中Ej表示目標(biāo)序列上當(dāng)前已校驗(yàn)成功的事件類型（即對(duì)應(yīng)的事件實(shí)例緩沖區(qū)上具有滿足約束條件的事件實(shí)例），Se為查詢Q中的目標(biāo)序列，R用于存儲(chǔ)遞歸校驗(yàn)后得到的復(fù)雜事件序列結(jié)果。算法2先計(jì)算初始事件列表前側(cè)的其余事件列表上平均事件實(shí)例數(shù)量Num前和后側(cè)的其余事件列表上平均事件實(shí)例數(shù)量Num后的大小，選擇事件實(shí)例數(shù)量小的一側(cè)優(yōu)先校驗(yàn)。如果Num前gt;Num后，則優(yōu)先校驗(yàn)起始序列Ek后面的各個(gè)事件列表上的事件實(shí)例（第1～37行）。當(dāng)Ek后面所有事件列表均校驗(yàn)完畢，即Ei為最后一個(gè)事件列表時(shí)，再對(duì)Ek前面的各事件列表進(jìn)行校驗(yàn)，直至校驗(yàn)到第一個(gè)事件列表，即對(duì)所有事件列表校驗(yàn)完成，則當(dāng)前獲得的Ej.Sr中任意一個(gè)集合都表示一個(gè)滿足約束的候選序列，并將其加入到R中。同理，如果Num前l(fā)t;Num后，則優(yōu)先校驗(yàn)起始序列Ek前面的各個(gè)事件列表上的事件實(shí)例（第37～56行）。對(duì)于Ej.Sr中存儲(chǔ)的每一個(gè)集合r （表示當(dāng)前已經(jīng)部分滿足目標(biāo)序列約束的事件實(shí)例集合），根據(jù)r中的事件實(shí)例計(jì)算出Ei類型的事件實(shí)例允許前面或者后面出現(xiàn)的時(shí)間戳范圍［tx，ty］。

由于Ei的序列操作類型不同，在其對(duì)應(yīng)的事件實(shí)例緩沖區(qū)上進(jìn)行的校驗(yàn)操作也不同，因此算法2需分別對(duì)Ei的3種序列操作類型進(jìn)行討論：

當(dāng)Ei的序列操作類型為順序操作時(shí)，算法在Ei對(duì)應(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í)，需先獲取閉包參數(shù)k值。然后設(shè)置一個(gè)臨時(shí)變量count，對(duì)滿足時(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í)，其處理方法不同于順序操作與閉包操作。由于復(fù)雜事件序列不能包含否定操作下的事件實(shí)例，目標(biāo)序列無法跨過否定操作的事件實(shí)例?；谠撔再|(zhì)，復(fù)雜事件匹配過程不能包含否定操作下的事件實(shí)例。算法2利用出現(xiàn)在時(shí)間戳范圍內(nèi)實(shí)例的時(shí)間戳更新當(dāng)前部分匹配集合r的終止時(shí)間，從而保證匹配得到的目標(biāo)序列所在時(shí)間戳范圍不包含否定的事件實(shí)例。

例3" 本例沿用例2中股票交易數(shù)據(jù)緩存到有序緩沖區(qū)的數(shù)據(jù)，由前文對(duì)事件流片段的采樣可知，B中事件實(shí)例的數(shù)量較少，因此選擇以B事件列表作為起始列表。同時(shí)在該采樣片段中B事件列表后面的C、D列表中，事件實(shí)例數(shù)量分別為NumC=3、NumD=2，而前面A事件列表中事件實(shí)例數(shù)量NumA=5，因此優(yōu)先選擇向后校驗(yàn)會(huì)產(chǎn)生更少的匹配次數(shù)。以b1：5為例，其向后校驗(yàn)I（C）上的事件實(shí)例，計(jì)算其后允許的時(shí)間戳范圍為［5，15］，因此在I（C）上可以找到c2：7和c3：15兩個(gè)實(shí)例，同理遞歸校驗(yàn)在I（D）上的事件實(shí)例。當(dāng)判斷I（D）是向后最后一個(gè)事件列表時(shí)，則向后校驗(yàn)結(jié)束，需再向前校驗(yàn)起始列表前面的事件實(shí)例，即I（A）上可滿足時(shí)間戳范圍的事件實(shí)例。此時(shí)判斷I（A）為向前第一個(gè)事件列表，可以確定向前校驗(yàn)已經(jīng)完成，此時(shí)將當(dāng)前存儲(chǔ)的事件實(shí)例集合即復(fù)雜事件候選序列輸出，如圖5中右側(cè)給出的5個(gè)候選序列結(jié)果。

3.4 屬性驗(yàn)證

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

針對(duì)查詢過濾產(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é)果。

例4" 例3在經(jīng)過如圖4的查詢過濾處理之后，得到如圖5所示部分復(fù)雜事件候選序列。針對(duì)這些復(fù)雜事件候選序列添加查詢Q中的關(guān)聯(lián)約束作為驗(yàn)證條件進(jìn)行進(jìn)一步的屬性驗(yàn)證，（設(shè)y值為38，z值為40）。圖6中陰影部分的兩個(gè)候選序列的并不滿足a.pricegt;（1+38%）*b.price這一關(guān)聯(lián)約束條件，所以它并不是正確的復(fù)雜事件結(jié)果，因此這兩個(gè)候選序列會(huì)被過濾掉。

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

通過實(shí)驗(yàn)對(duì)比，對(duì)本文提出的在有序事件列表上選擇最佳匹配順序進(jìn)行遞歸遍歷的復(fù)雜事件匹配方法的有效性進(jìn)行了分析和驗(yàn)證。采用Java實(shí)現(xiàn)了優(yōu)化方法的編寫。本節(jié)將從多個(gè)維度對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析說明，并通過性能對(duì)比證明其有效性。

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

本文優(yōu)化方法將與目前比較流行的SASE方法和Siddhi方法進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)本文提出的在有序事件列表上選擇最佳匹配順序進(jìn)行遞歸遍歷的復(fù)雜事件匹配方法記為OptiSeq。

實(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)的可比性，在各個(gè)實(shí)驗(yàn)中將復(fù)雜事件查詢做一致性處理，即目標(biāo)序列相同，事件類型個(gè)數(shù)相同，屬性約束相同，事件窗口大小相同。在本節(jié)實(shí)驗(yàn)中將復(fù)雜事件查詢匹配結(jié)果的處理時(shí)間作為實(shí)驗(yàn)的性能指標(biāo)進(jìn)行評(píng)估。

以下所有的實(shí)驗(yàn)均是在實(shí)驗(yàn)環(huán)境配置如表1所示的服務(wù)器上進(jìn)行。

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

為證明本文提出算法的有效性和高效性，首先對(duì)所提出的OptiSeq算法與SASE、Siddhi方法在同一查詢模式下進(jìn)行總體性能對(duì)比實(shí)驗(yàn)，其次又檢驗(yàn)了不同影響因素，如復(fù)雜事件類型個(gè)數(shù)、時(shí)間窗口大小在各個(gè)方法間性能的比較。設(shè)置以下3個(gè)實(shí)驗(yàn)進(jìn)行對(duì)比測(cè)試。

實(shí)驗(yàn)1：在數(shù)據(jù)集上對(duì)3種方法各測(cè)試了3組查詢，保證每組查詢中這些復(fù)雜事件查詢的序列長(zhǎng)度為4，同時(shí)為了排除時(shí)間窗口約束的影響，將時(shí)間窗口統(tǒng)一為2 min，對(duì)應(yīng)的值則是該組查詢的運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果如圖7所示，其中OptiSeq算法比SASE算法的處理時(shí)間平均降低了15.46%，比Siddhi方法降低了9.41%。

實(shí)驗(yàn)2：評(píng)估目標(biāo)序列長(zhǎng)度對(duì)運(yùn)行時(shí)間的影響。為排除其他因素的影響，在實(shí)驗(yàn)2中設(shè)置復(fù)雜事件查詢模式均在同一時(shí)間窗口為2 min時(shí)，改變查詢模式中事件類型個(gè)數(shù)，分別由3個(gè)遞增到6個(gè)事件類型時(shí)的4組評(píng)估結(jié)果。將3種方法對(duì)復(fù)雜事件處理結(jié)果所用的運(yùn)行時(shí)間作為評(píng)估指標(biāo)，對(duì)比實(shí)驗(yàn)結(jié)果如圖8所示，其中OptiSeq算法比SASE算法的處理時(shí)間平均降低了21.19%，比Siddhi方法降低了18.55%。并且通過圖8可以發(fā)現(xiàn)，隨著目標(biāo)序列長(zhǎng)度的增加，OptiSeq比另外兩個(gè)方法的性能提升更大。

實(shí)驗(yàn)3：評(píng)估時(shí)間窗口約束對(duì)運(yùn)行時(shí)間的影響。在實(shí)驗(yàn)3中設(shè)置查詢中的目標(biāo)序列長(zhǎng)度為4個(gè)，即PATTERN（A；B；C；D），同時(shí)給定每組查詢相同的屬性約束條件，分別測(cè)試了時(shí)間窗口約束從1～5 min的5組評(píng)估結(jié)果。如圖9所示，在不同的時(shí)間窗口約束下，OptiSeq的處理性能優(yōu)于其余兩個(gè)方法。實(shí)驗(yàn)對(duì)比結(jié)果中，當(dāng)時(shí)間窗口為240 s時(shí)，OptiSeq的處理性能比SASE提升了16.02%，比Siddhi提升了22.93%。

5 結(jié)論

本文提出了一種新型的利用有序列表緩存事件實(shí)例的結(jié)構(gòu)，通過該結(jié)構(gòu)避免了臨時(shí)匹配的集中式存儲(chǔ)及使用。提出了通過比較列表中事件實(shí)例的多少來選擇最優(yōu)匹配順序進(jìn)行過濾查詢的方法，以及候選序列匹配算法StartCEP和候選序列匹配算法VerifyEvents。通過這兩個(gè)算法，能夠在減少中間匹配結(jié)果和匹配次數(shù)的情況下，保證復(fù)雜事件處理匹配結(jié)果的正確性和完整性。在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上對(duì)優(yōu)化方法的性能進(jìn)行對(duì)比實(shí)驗(yàn)和分析，實(shí)驗(yàn)結(jié)果表明，本文提出的在有序事件列表上選擇最優(yōu)匹配順序進(jìn)行遞歸遍歷的復(fù)雜事件匹配方法，在處理查詢模式中事件類型較多或者時(shí)間窗口約束較大的情況下，都能夠有效得到復(fù)雜事件處理結(jié)果，并且在處理性能上可以更有效地避免大量重復(fù)計(jì)算，減少處理時(shí)間。

參考文獻(xiàn)（References）：

［1］ 產(chǎn)院東，郭喬進(jìn)，梁中巖，等.規(guī)則引擎發(fā)展綜述［J］.信息化研究，2021，47（2）：1-6.

［2］ 喬雅正，程良倫，王濤，等. 地鐵列車環(huán)境中多依賴復(fù)雜事件處理研究［J］. 計(jì)算機(jī)應(yīng)用研究，2019，36（8）： 2355-2358，2367.

［3］ Rahmani A M，Babaei Z，Souri A.Event-driven IoT architecture for data analysis of reliable healthcare application using complex event processing［J］.Cluster Computing，2021，24（2）：1347-1360.

［4］ 王亞輝，鄭聯(lián)語，樊偉. 云架構(gòu)下基于標(biāo)準(zhǔn)語義模型和復(fù)雜事件處理的制造車間數(shù)據(jù)采集與融合［J］. 計(jì)算機(jī)集成制造系統(tǒng)，2019，25（12）： 3103-3115.

［5］ 鮑軍鵬，左宏良，楊科. 基于事件流的航天大數(shù)據(jù)復(fù)雜事件挖掘框架［C］//2018軟件定義衛(wèi)星高峰論壇摘要集.西安：西安電子科技大學(xué)出版社，2018： 74-80.

［6］ Agrawal J，Diao Y L，Gyllstrom D，et al.Efficient pattern matching over event streams［C］//Procee dings of the 2008 ACM SIGMOD International Conference on Management of Data.Vancouver，Canada：ACM，2008：147-160.

［7］ Wu E，Diao Y L，Rizvi S.High-performance complex event processing over streams［C］//Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data.Chicago，USA：ACM，2006：407-418.

［8］ Mei Y，Madden S.ZStream：a cost-based query processor for adaptively detecting composite events［C］//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data.New York，USA：ACM，2009：193-206.

［9］ Suhothayan S， Kasun G， Isaure L N， et al. Siddhi： a second look at complex event processing architectures［C］//Proceedings of the 2011 ACM SC Workshop on Gateway Computing Environments， Seattle， USA：ACM， 2011：43-50.

［10］ Giatrakos N，Alevizos E，Artkis A，et al.Complex event recognition in the big data era： a survey［J］. The VLDB Journal，2020： 29（1）： 313-352

［11］ Diao Y L，Immerman N，Gyllstrom D. Sase+：an agile language for kleene closure over event streams［J］. UMass Technical Report，2007， 7（3）： 1-13.

［12］ Demers A，Gehrke J，Hong M S，et al．Towards expressive publish/subscribe systems［M］//Lecture Notes in Computer Science．Berlin：Springer-Verlag，2006：627-644．

［13］ Demers A，Gehrke J，Panda B，et al. Cayuga： a general purpose event monitoring system［C］//Proceedings of the 2007 International Conference on Innovation Database Research.Asilomar，USA：ACM，2007： 412-422.

［14］ 趙潤(rùn)發(fā)，婁淵勝，葉楓，等．基于Flink的工業(yè)大數(shù)據(jù)平臺(tái)研究與應(yīng)用［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2022，43（3）886-894.

［15］ Dousson C．Extending and unifying chronicle representation with event counters［C］//Proceedings of the 15th European Conference on Artificial Intelligence．New York，USA：ACM，2002：257-261．

［16］ Artikis A，Sergot M，Paliouras G．An event calculus for event recognition［J］．IEEE Transactions on Knowledge and Data Engineering，2015，27（4）：895-908．

［17］ Liu M，Rundensteiner E，Greenfield K，et al．E-Cube：multi-dimensional event sequence analysis using hierarchical pattern query sharing［C］//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data.New York，USA：ACM，2011：889-900．

［18］ 喻學(xué)軍，肖蓓. 一種高效的復(fù)雜事件處理引擎Esper［J］. 數(shù)字技術(shù)與應(yīng)用，2020，38（11）：50-52.

［19］ 鄭利強(qiáng)，廖湖聲，蘇航，等.一種針對(duì)正規(guī)樹模式的復(fù)雜事件查詢方法［J］.計(jì)算機(jī)與數(shù)字工程， 2018，46（5）：966-971.

［20］ Grea A，Riveros C， Ugarte M.A formal framework for complex event recognition ［J］.ACM Transactions on Database Systems，2021，46（4）：1-49.

（責(zé)任編輯：劉劃" 英文審校：杜文友）