復(fù)雜事件處理中多聚合查詢共享方法

摘 要：復(fù)雜事件處理技術(shù)是在持續(xù)不斷的流數(shù)據(jù)中檢測(cè)滿足特定事件序列或?qū)ζヅ涞氖录M(jìn)行統(tǒng)計(jì)的一種流數(shù)據(jù)處理技術(shù)。在處理帶有Kleene操作符的事件趨勢(shì)聚合查詢時(shí)，需緩存中間結(jié)果來(lái)實(shí)現(xiàn)不定數(shù)量事件序列的匹配，故對(duì)查詢系統(tǒng)的資源需求較大。利用多個(gè)查詢之間存在的共享機(jī)會(huì)，生成用于指導(dǎo)查詢處理的共享計(jì)劃，可以有效提高事件趨勢(shì)聚合查詢的處理效率。但現(xiàn)有的聚合查詢處理方法生成的共享計(jì)劃無(wú)法做到隨執(zhí)行環(huán)境的變化而進(jìn)行實(shí)時(shí)調(diào)整，來(lái)支持查詢系統(tǒng)的持續(xù)高效處理。針對(duì)上述問(wèn)題，提出了一種可以動(dòng)態(tài)更新的多聚合查詢共享方法，以支持實(shí)時(shí)變化的復(fù)雜事件檢測(cè)的持續(xù)高效處理。通過(guò)提出共享圖數(shù)據(jù)結(jié)構(gòu)和代價(jià)模型，實(shí)現(xiàn)對(duì)所生成共享計(jì)劃的實(shí)時(shí)調(diào)整，并引入在線增量聚合執(zhí)行共享方法，進(jìn)一步提升帶有Kleene操作符的事件趨勢(shì)聚合查詢的處理效率。在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)，并與其他處理聚合查詢的方法進(jìn)行了實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)結(jié)果表明，提出方法能夠有效降低查詢延遲，提高整體查詢的處理性能。

關(guān)鍵詞：復(fù)雜事件處理； 增量聚合； 多查詢共享； 事件趨勢(shì)

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

文章編號(hào)：1001-3695（2024）10-031-3100-10

doi：10.19734/j.issn.1001-3695.2024.02.0037

Multi-aggregate query sharing method in complex event processing

Dong Panpan， Su Hang， Gao Hongyu

（Faculty of Information， Beijing University of Technology， Beijing 100124， China）

Abstract：Complex event processing technology is a streaming data processing technique that detects specific event sequences or performs statistics on matching events in continuously flowing data. When processing trend aggregation queries with Kleene operators， caching intermediate results is necessary to match an indefinite number of event sequences， thus requiring significant resources from the query system. Exploiting opportunities for sharing among multiple queries， generating shared plans to guide query processing can effectively enhance the processing efficiency of trend aggregation queries. However， existing me-thods for handling aggregate queries do not dynamically adjust the generated shared plans in real-time to support continuous and efficient processing of complex event detection in response to changes in the execution environment. Addressing these issues， this paper proposed a dynamically updatable method for multiple aggregate query sharing to support the continuous and efficient processing of real-time changing complex event detection. By introducing the shared graph data structure and cost model， this method achieved real-time adjustment of the generated shared plans. And by using the online incremental aggregation execution sharing method， it further enhanced the processing efficiency of event trend aggregation queries with Kleene operators. This paper conducted experiments on both real and simulated datasets， compared the method with other approaches for handling aggregate queries. The results of the experiments indicate that the method effectively reduces query latency and improves the overall processing performance of queries.

Key words：complex event processing（CEP）; incremental aggregate; multi-query sharing; event trend

0 引言

復(fù)雜事件處理（CEP）是一種在事件存儲(chǔ)前對(duì)連續(xù)的事件流進(jìn)行處理的技術(shù)［1］，其目的是根據(jù)一組預(yù)定義的模式實(shí)時(shí)地識(shí)別有意義的事件或者事件組合［2，3］。CEP廣泛應(yīng)用于股票、交通運(yùn)輸和公共衛(wèi)生等領(lǐng)域［4］。這些應(yīng)用通常依賴于使用包含Kleene操作符的復(fù)雜查詢模式。用Kleene操作符表示的子模式能夠匹配一個(gè)或者多個(gè)與該模式匹配的事件序列（稱為事件趨勢(shì)）［5］。由于事件趨勢(shì)是任意長(zhǎng)度的，所以帶來(lái)的計(jì)算成本非常高，對(duì)于這類查詢的大量工作負(fù)載，實(shí)時(shí)響應(yīng)難以保證［6，7］。

在實(shí)際應(yīng)用中，CEP往往需要同時(shí)處理多個(gè)查詢，并且查詢之間存在大量共享數(shù)據(jù)［8］。事件趨勢(shì)的多查詢優(yōu)化技術(shù)涵蓋了對(duì)聚合函數(shù)的處理和多查詢的共享優(yōu)化。作為復(fù)雜事件處理的核心研究方向之一，其主要目標(biāo)是通過(guò)共享工作負(fù)載中的查詢計(jì)算，以有效降低并發(fā)查詢的處理成本［9］。在處理事件趨勢(shì)聚合查詢時(shí)，優(yōu)化技術(shù)首先需識(shí)別Kleene模式的共享機(jī)會(huì)，其次需要確定如何充分利用這些共享機(jī)會(huì)以加快指定工作負(fù)載的執(zhí)行過(guò)程。

在聚合查詢處理領(lǐng)域，已經(jīng)有了豐富的研究成果。最初的兩步法首先構(gòu)造所有的事件趨勢(shì)，再?gòu)倪@些事件趨勢(shì)中統(tǒng)計(jì)聚合值［6］。Poppe等人［2］為應(yīng)對(duì)CET（complex event trend）中共享公共事件子序列導(dǎo)致的性能問(wèn)題，提出了CET圖的概念，對(duì)所有查詢匹配的CET進(jìn)行編碼。接收到新事件時(shí)，系統(tǒng)從每個(gè)結(jié)束事件節(jié)點(diǎn)向前遍歷以查找與新事件匹配的事件。因此這種設(shè)計(jì)方法在新事件發(fā)生時(shí)會(huì)增加CET圖遍歷的成本，存在因部分結(jié)果呈指數(shù)增長(zhǎng)而導(dǎo)致內(nèi)存爆炸的問(wèn)題。Zhang等人［10］對(duì)CEP中的模式查詢進(jìn)行了深入分析，詳細(xì)闡述了導(dǎo)致趨勢(shì)聚合代價(jià)高昂的查詢特征。并將現(xiàn)有的CEP系統(tǒng)映射到相同的層次結(jié)構(gòu)中，為比較不同系統(tǒng)提供了一致的理論框架。這種兩步法處理聚合查詢時(shí)需要先進(jìn)行模式匹配，生成所有的事件序列之后進(jìn)行統(tǒng)計(jì)。尤其是在處理Kleene操作符時(shí)，相同的事件可能會(huì)被存儲(chǔ)上百至千次，不僅需要大量的內(nèi)存存儲(chǔ)中間結(jié)果，還需要額外的時(shí)間開(kāi)銷用于統(tǒng)計(jì)聚合值，導(dǎo)致處理效率較低。

在線聚合方法［11］將聚合操作整合到模式匹配階段，避免了先構(gòu)建事件趨勢(shì)的復(fù)雜性，將計(jì)算復(fù)雜度從指數(shù)級(jí)降低到線性。然而在線聚合方法在處理特定場(chǎng)景下存在兩個(gè)關(guān)鍵限制。表1按照三個(gè)維度對(duì)現(xiàn)有的在線聚合方法進(jìn)行了優(yōu)劣對(duì)比。

首先，模式中可以包含SEQ和Kleene操作符，在對(duì)包含Kleene模式的查詢處理上，現(xiàn)有方法大多限制或完全禁止事件趨勢(shì)聚合中的Kleene模式［13］。MCEP［10］僅支持共享非嵌套Kleene模式，而Sharon［6］僅支持共享固定長(zhǎng)度的SEQ模式，不支持共享Kleene模式。對(duì)Kleene模式的這種限制降低了共享方法的適用性。其次，現(xiàn)有方法對(duì)共享決策施加嚴(yán)格的限制。Sharon引入了共享沖突的概念，限制一個(gè)子模式參與多個(gè)共享查詢組。Hamlet［12］和Static［13］方法是事件趨勢(shì)聚合查詢處理方法，均對(duì)Kleene操作符和查詢之間的共享執(zhí)行進(jìn)行了優(yōu)化，是目前處理效果較好的兩個(gè)方法，但是分別具有不同的局限性。Hamlet僅關(guān)注非嵌套Kleene子模式的單一事件類型的共享機(jī)會(huì)。Static方法通過(guò)預(yù)先生成共享計(jì)劃，然后按照生成的共享計(jì)劃嚴(yán)格執(zhí)行聚合計(jì)算。這種不關(guān)注動(dòng)態(tài)變化信息的方法通常會(huì)導(dǎo)致次優(yōu)的共享計(jì)劃，錯(cuò)過(guò)潛在的共享機(jī)會(huì)。

在查詢優(yōu)化方面，主要涉及對(duì)多個(gè)查詢的共享和對(duì)嵌套查詢的處理［14］。多查詢共享技術(shù)通常利用查詢操作符的交換性和結(jié)合性來(lái)支持查詢中的語(yǔ)義等價(jià)［15］，即原始查詢可能會(huì)更改為不同的形式，但輸出應(yīng)保持不變。SASE［16］和ZStream［17］分別利用自動(dòng)機(jī)和樹(shù)結(jié)構(gòu)處理單一查詢模式，在處理包含Kleene操作符的查詢和嵌套查詢時(shí)性能較差且不支持查詢共享。MOTTO［15］利用合并、分解和操作符轉(zhuǎn)換共享三種技術(shù)減少模式查詢的冗余計(jì)算，設(shè)計(jì)多查詢優(yōu)化器提高并發(fā)模式查詢的性能，但不支持包含Kleene操作符的查詢。處理嵌套查詢時(shí)，存在兩個(gè)主要問(wèn)題：首先，某些可共享的內(nèi)部查詢的完整結(jié)果可能在共享結(jié)果前被直接丟棄［18］；其次，嵌套否定子表達(dá)式中只需檢測(cè)到其中一個(gè)事件即可否定整個(gè)結(jié)果，但是執(zhí)行時(shí)仍需要生成完整的結(jié)果［19］，導(dǎo)致資源浪費(fèi)。大多數(shù)CEP系統(tǒng)通常通過(guò)轉(zhuǎn)變操作符來(lái)處理包含嵌套模式的查詢［20］。NEEL［20］使用查詢重寫技術(shù)處理嵌套模式查詢，使用基于堆棧的查詢?cè)u(píng)估策略和迭代嵌套執(zhí)行策略處理嵌套查詢。但在處理帶有Kleene操作符的查詢時(shí)仍存在指數(shù)級(jí)時(shí)間復(fù)雜度。

針對(duì)以上問(wèn)題，給定包含SEQ和Kleene操作符以及嵌套模式的事件趨勢(shì)聚合查詢工作負(fù)載。本文設(shè)計(jì)共享圖數(shù)據(jù)結(jié)構(gòu)，將共享優(yōu)化問(wèn)題映射為圖路徑搜索問(wèn)題，獲取所有可能的共享計(jì)劃。設(shè)計(jì)生成和修剪圖的代價(jià)模型，考慮事件流和工作負(fù)載的特征，確定查詢?cè)谧幽Ｊ缴系墓蚕矸桨福?shí)時(shí)調(diào)整共享計(jì)劃。引入在線增量聚合執(zhí)行共享方法，提升事件趨勢(shì)聚合查詢的處理效率。

綜上所述，本文的主要貢獻(xiàn)如下：

a）提出了一種共享優(yōu)化方法，用于處理包含Kleene模式的事件趨勢(shì)聚合查詢。將涉及Kleene子模式工作負(fù)載的共享問(wèn)題抽象為加權(quán)有向無(wú)環(huán)圖的最短路徑搜索問(wèn)題，為工作負(fù)載提供了靈活的共享策略。在生成圖的過(guò)程中進(jìn)行修剪，以降低后續(xù)路徑搜索的時(shí)間復(fù)雜度，從而提高執(zhí)行效率。

b）設(shè)計(jì)了一種綜合考慮事件流和工作負(fù)載特征的代價(jià)模型，將其引入到共享圖的生成和路徑搜索過(guò)程中，在這些特征發(fā)生變化時(shí)高效更新共享計(jì)劃，并應(yīng)用于執(zhí)行過(guò)程。

c）引入在線趨勢(shì)聚合方法，使用動(dòng)態(tài)更新的共享計(jì)劃指導(dǎo)多聚合查詢結(jié)果的增量計(jì)算。

d）在真實(shí)和模擬數(shù)據(jù)集上對(duì)本文方法進(jìn)行對(duì)比實(shí)驗(yàn)和分析，驗(yàn)證了動(dòng)態(tài)更新共享計(jì)劃方法的適用性和高效性。

1 相關(guān)概念

1.1 基本概念

定義1 事件流。事件流I由事件源［21］（如車輛和移動(dòng)設(shè)備）生成的一組連續(xù)的事件組成。事件e是描述應(yīng)用程序所關(guān)注事件的數(shù)據(jù)元組，每個(gè)事件含有一個(gè)由事件源分配的時(shí)間戳e.time［22］。原始事件e屬于一個(gè)特定的事件類型E，表示為e.type=E，由指定該事件屬性集及值域的模式來(lái)描述該事件。E的特定屬性attr表示為E.attr。本文假定事件按時(shí)間戳順序到達(dá)，文中的符號(hào)和解釋如表2所示。

定義2 事件序列模式P。事件序列模式P定義事件流中的特定事件序列或結(jié)構(gòu)，由操作符和事件類型組成。模式P的形式可以包含E，P1+，（NOT P1），SEQ（P1，P2），（P1∨P2），（P1∧P2），其中E是一個(gè)事件類型、P1和P2是模式、+表示Kleene操作符，NOT表示否定，SEQ是事件序列，∨是析取，∧是合取，P1和P2稱為P的子模式。

定義3 Kleene模式。在定義2中的事件序列模式P中，如果P中包含Kleene操作符，那么P就是一個(gè)Kleene模式，如果P中的一個(gè)Kleene模式的結(jié)果應(yīng)用于另一個(gè)Kleene模式，那么P就是一個(gè)嵌套Kleene模式［23］。否則，P是一個(gè)平坦Kleene模式。

定義4 聚合。在數(shù)據(jù)庫(kù)和數(shù)據(jù)處理領(lǐng)域，聚合是指通過(guò)匯總、組合或計(jì)算數(shù)據(jù)集的值，生成單一的結(jié)果。這個(gè)結(jié)果可以是一個(gè)總和、平均值、計(jì)數(shù)，或者其他統(tǒng)計(jì)性質(zhì)的值。

定義5 事件趨勢(shì)聚合查詢。事件趨勢(shì)聚合查詢由5個(gè)子句組成。

RETURN子句：返回的聚合結(jié)果值；

PATTERN子句：定義2中介紹的事件序列模式；

WHERE子句：謂詞（可選）；

GROUPBY子句：分組（可選）；

WITHIN/SLIDE子句：窗口。

定義6 可共享的模式。一個(gè)工作負(fù)載Q由一組查詢組成。如圖1所示，工作負(fù)載Q1={qa，qb，qc}。給定一個(gè)事件趨勢(shì)聚合查詢的模式P和一個(gè)工作負(fù)載Q，如果P出現(xiàn)在至少兩個(gè)查詢的模式子句中，則這個(gè)模式P是可共享的。在圖1中，三個(gè)查詢都包含子模式（P，T）+，（P，T）+即可共享的子模式。

Uber（主要業(yè)務(wù)是提供網(wǎng)約車服務(wù)和食品配送服務(wù)）和Door Dash（在線食品配送平臺(tái)）使用復(fù)雜的事件趨勢(shì)聚合查詢來(lái)進(jìn)行價(jià)格計(jì)算、預(yù)測(cè)和路線選擇［12］。由于每個(gè)地區(qū)有數(shù)百名用戶、數(shù)千次交易和全國(guó)數(shù)百萬(wàn)個(gè)地區(qū)，實(shí)時(shí)事件分析成為一項(xiàng)具有挑戰(zhàn)性的任務(wù)。

如圖1所示，查詢工作負(fù)載計(jì)算各種行程統(tǒng)計(jì)信息，例如每個(gè)地區(qū)的訂單總數(shù)、總持續(xù)時(shí)間和平均速度。工作負(fù)載Q1包含qa，qb，qc三個(gè)事件趨勢(shì)聚合查詢，每個(gè)查詢匹配不同的訂單事件趨勢(shì)。每個(gè)事件類型對(duì)應(yīng)客戶或送餐員的操作，例如AppOrder和WebOrder分別表示來(lái)自APP和網(wǎng)頁(yè)上的訂單。事件流中的每個(gè)事件都是由客戶和送餐員標(biāo)識(shí)符、操作、地區(qū)和時(shí)間戳組成的元組。實(shí)際應(yīng)用中，送餐員通常會(huì)在附近接多個(gè)訂單，以縮短行駛路程，因此事件趨勢(shì)中可出現(xiàn)任意次數(shù)的（P，T）+。查詢qa的返回值為在任意平臺(tái)下單并在30 min內(nèi)完成配送的訂單數(shù)量。謂詞［driver_id］要求訂單中的所有事件必須具有相同的送餐員標(biāo)識(shí)符。查詢qb返回在APP下單且送餐地點(diǎn)為泳池的訂單數(shù)量。查詢qc的返回值為在APP下單但是送餐員行駛速度小于10，因此客戶取消的訂單數(shù)量。三個(gè)查詢都包含可共享的子模式SEQ（R，（P，T）+），然而共享SEQ（R，（P，T）+）并不是唯一的共享方案。qa和qb可以共享更長(zhǎng)的子模式SEQ（R，（P，T）+，D），而qb和qc包含另一個(gè)更長(zhǎng)的子模式SEQ（A，R，（P，T）+）。因此在實(shí)際應(yīng)用中，共享包含SEQ和Kleene子模式的查詢，并解決多個(gè)相互沖突的共享機(jī)會(huì)，以最大化共享收益，是一項(xiàng)復(fù)雜的任務(wù)［24］。

聚合函數(shù)。本文關(guān)注可以遞增計(jì)算的聚合函數(shù)，對(duì)一組值執(zhí)行計(jì)算并返回單一的統(tǒng)計(jì)結(jié)果值［25］。令e為E事件類型的事件，attr為e的屬性。COUNT（*）返回事件趨勢(shì)的數(shù)量，MIN/MAX（E.attr）返回所有事件趨勢(shì)中事件e的attr最?。ㄗ畲螅┲?，SUM（E.attr）/AVG（E.attr）計(jì)算事件趨勢(shì)事件e的attr值的總和或平均值。本文使用COUNT（*）作為默認(rèn)聚合函數(shù)。

1.2 事件趨勢(shì)聚合共享問(wèn)題

為了便于分析多個(gè)查詢之間的共享機(jī)會(huì)，采用SASE中的方法將查詢工作負(fù)載表示為有限狀態(tài)自動(dòng)機(jī)，稱為模板。模板中的每個(gè)節(jié)點(diǎn)表示查詢中的事件類型E，結(jié)束事件類型的節(jié)點(diǎn)加粗表示。模板中的“→”（轉(zhuǎn)換）對(duì)應(yīng)事件序列模式P中的操作符，連接P中的兩個(gè)相鄰的事件類型Ei和Ej，表示為convert（Ei，Ej）。在查詢q中，Ej之前的事件類型Ei表示為pe（Ej，q）。查詢工作負(fù)載Q2由四個(gè)查詢組成，Q2={q1，q2，q3，q4}，分別為：q1=SEQ（F， D），q2=SEQ（ D），q3=SEQ（E，C，D），q4=SEQ（B，C，D，G）。

按照SASE中的模板生成方法，Q2生成的模板如圖2所示。模版中存在多個(gè)共享機(jī)會(huì)，查詢q1，q2可以共享SEQ（A，B，C）的轉(zhuǎn)換，查詢q1，q2，q4可共享SEQ（B，C，D）的轉(zhuǎn)換。

每個(gè)convert上的共享方案將一個(gè)工作負(fù)載中具有該convert的所有查詢劃分為一個(gè)查詢集QS，以確保每個(gè)QS中的查詢可以分別共享由該convert建模的執(zhí)行過(guò)程。圖2中convert（B，C）上的（1，2），4分別表示查詢q1，q2，q4，若查詢q1，q2在執(zhí)行時(shí)進(jìn)行共享，那么convert（B，C）的一個(gè)Qs為{q1，q2}。

定義7 工作負(fù)載共享計(jì)劃。給定工作負(fù)載Q的模板，模板中所有convert的共享方案組成一個(gè)工作負(fù)載共享計(jì)劃。

2 動(dòng)態(tài)共享方法

給定事件趨勢(shì)聚合查詢工作負(fù)載Q和高速事件流I，多事件趨勢(shì)聚合查詢問(wèn)題就是在事件流I上評(píng)估工作負(fù)載Q，使得Q中所有查詢的平均查詢延遲時(shí)間最小［12］。

2.1 動(dòng)態(tài)共享方法框架

聚合查詢的動(dòng)態(tài)共享方法分為共享計(jì)劃生成方法和聚合查詢執(zhí)行方法兩部分。共享計(jì)劃生成方法首先將查詢工作負(fù)載轉(zhuǎn)換成模板，并分析潛在的共享機(jī)會(huì)。分析事件流和工作負(fù)載的特征以及共享收益，構(gòu)建出代價(jià)模型。根據(jù)模板和代價(jià)模型生成加權(quán)有向無(wú)環(huán)圖，編碼所有可能的共享機(jī)會(huì)。在生成圖的過(guò)程中對(duì)圖進(jìn)行修剪，最優(yōu)的共享計(jì)劃對(duì)應(yīng)圖中權(quán)重最小的路徑。圖3展示了動(dòng)態(tài)共享方法的框架。

執(zhí)行方法使用共享計(jì)劃生成方法生成的共享計(jì)劃，在事件流I上評(píng)估工作負(fù)載Q。引入在線聚合方法［12］，將中間聚合從已經(jīng)匹配過(guò)的事件傳播到新的事件，利用快照維護(hù)每個(gè)查詢的中間聚合值，以增量方式計(jì)算趨勢(shì)聚合值，避免中間結(jié)果的構(gòu)造。當(dāng)事件流統(tǒng)計(jì)信息或者工作負(fù)載發(fā)生變化時(shí)，將信息反饋回共享計(jì)劃生成方法中，根據(jù)當(dāng)前事件流狀態(tài)更新共享計(jì)劃并重新作用于執(zhí)行過(guò)程中。

2.2 執(zhí)行方法

執(zhí)行過(guò)程采用在線增量聚合的方法支持非共享和共享執(zhí)行。通過(guò)以下例子說(shuō)明執(zhí)行代價(jià)，工作負(fù)載Q3={q2，q4}，其中q2=SEQ（ D），q4=SEQ（B，C，D，G），兩個(gè)查詢的返回值均為COUNT（*）。Q3在事件流S（a1，a2，b1，c1，c2，d1，d2，g1）上進(jìn)行查詢，并且Q3中有一個(gè)共享查詢集QS={q2，q4}。

a）非共享執(zhí)行聚合。在執(zhí)行過(guò)程中，對(duì)于匹配事件e的每個(gè)查詢，維護(hù)一個(gè)中間聚合值，表示q匹配的以e結(jié)尾的聚合數(shù)。在執(zhí)行過(guò)程中e的值遞增，遞增的值為由q匹配的e的前驅(qū)事件的中間聚合的總和。如果e是q的結(jié)束事件類型，則將此聚合值作為查詢q的最終結(jié)果輸出。

圖4為工作負(fù)載Q3在事件流I上的非共享執(zhí)行情況。當(dāng)b1到達(dá)時(shí)，分別為q2和q4創(chuàng)建新的計(jì)數(shù)，其中間聚合值對(duì)于查詢q2和q4來(lái)說(shuō)分別為2和1。當(dāng)事件c1到達(dá)時(shí)，其對(duì)于q2和q4的中間聚合從它的前置事件b1傳播得到。對(duì)于后續(xù)每個(gè)事件，在為每個(gè)查詢傳播聚合值時(shí)將前置事件的聚合值求和得到其中間聚合值。最后當(dāng)d1到達(dá)時(shí)，其中間聚合結(jié)果4作為查詢q2的最終聚合值輸出。查詢q2和q4的執(zhí)行成本在于將中間聚合值從前置事件傳播到新到達(dá)事件的聚合值中。例如：cost（c1，q2）=cost（c1，q4）=1，cost（c2，q2）=cost（c2，q4）=1。對(duì)于工作負(fù)載Q3，所有C類事件的非共享執(zhí)行代價(jià)為cost（C，Q3）=1×2+1×2=4（由b1指向c1和c2均有兩個(gè)箭頭）。

因此得出對(duì)于給定的工作負(fù)載Q，事件類型E非共享執(zhí)行時(shí)的代價(jià)為

costnonshare（E，Q）=∑q∈Q ∑Ep∈pe（E，q）|E|×|Ep|（1）

其中：q為工作負(fù)載Q中的查詢；|E|和|Ep|分別表示E的事件統(tǒng)計(jì)信息和E的前置事件Ep的事件統(tǒng)計(jì)信息。

b）共享執(zhí)行聚合。非共享在線聚合會(huì)導(dǎo)致對(duì)多個(gè)查詢的公共子模式進(jìn)行重復(fù)計(jì)算，如圖4所示，對(duì)于q2和q4來(lái)說(shuō)，b1到c1的中間聚合均需要被傳播一次。為了避免這種重復(fù)計(jì)算，利用快照來(lái)支持高效共享?？煺湛梢允桥c查詢的中間聚合相對(duì)應(yīng)的一個(gè)變量，也可以是一個(gè)由多個(gè)快照值組成的表達(dá)式。執(zhí)行方法在傳播過(guò)程中通過(guò)對(duì)其前置快照進(jìn)行求和不斷更新快照值。共享快照的所有查詢對(duì)應(yīng)的中間聚合值以map的形式存儲(chǔ)在快照中，執(zhí)行時(shí)只需要從前置事件到當(dāng)前事件進(jìn)行一次快照傳播。如果e的事件類型為查詢q的結(jié)束事件類型，則會(huì)進(jìn)行快照值的計(jì)算，并輸出聚合結(jié)果。

圖5為Q3的共享執(zhí)行情況。查詢q2和q4在共享公共子模式SEQ（B，C，D）時(shí)使用事件類型B的快照進(jìn)行共享，表示為（2，4）B。b1到達(dá)時(shí)，q2和q4的中間聚合值分別為2和1，將每個(gè)查詢對(duì)應(yīng)的值存儲(chǔ)到新的快照spb1，之后將spb1插入到快照數(shù)組中。對(duì)于共享查詢集QS即整個(gè)工作負(fù)載Q3，到事件類型C的傳播由4次減為2次：cost（C，QS）=cost（C，Q3）=2。

得出一個(gè)查詢集QS將快照傳播到事件類型E的代價(jià)為

costshare（E，QS）=|Ep|×|snap（Ep，Qs）|=

（Ep==Esn）？|Ep|：|Ep|×|Esn|（2）

其中：Ep表示事件類型E的前置事件；snap（Ep，QS）為Ep對(duì)于QS的快照事件表達(dá)式，表示為Esn；|Esn|為其事件發(fā)生頻率。滿足括號(hào)中的等式時(shí)選取“：”前的表達(dá)式進(jìn)行計(jì)算，不滿足時(shí)選取冒號(hào)后的表達(dá)式進(jìn)行計(jì)算。若一個(gè)工作負(fù)載Q中有多個(gè)QS，則Q對(duì)于事件類型E的共享執(zhí)行代價(jià)為

costshare（E，Q）=∑QSQcostshare（E，QS）（3）

其中：Q表示工作負(fù)載;QS為Q中的共享查詢集;costshared（E，QS）為式（2）中QS對(duì)事件類型E的執(zhí)行代價(jià)。

如果E是查詢q的結(jié)束事件類型或者需要?jiǎng)?chuàng)建新的快照，就會(huì)觸發(fā)對(duì)快照表達(dá)式的求值。對(duì)于事件類型D，當(dāng)d1到達(dá)時(shí)，需要為q2輸出聚合結(jié)果：costeval（D，Q4）=cost（D，q2）=|B|×|D|=2。

對(duì)于一個(gè)工作負(fù)載Q，快照表達(dá)式的計(jì)算代價(jià)為

costeval（E，Q）=∑q∈Q|Ep|×|snap（E，q）|（4）

3 動(dòng)態(tài)更新圖方法

本文設(shè)計(jì)共享計(jì)劃圖模型，將工作負(fù)載共享計(jì)劃問(wèn)題轉(zhuǎn)換為最佳路徑搜索問(wèn)題。給定工作負(fù)載模板，分析模板中每個(gè)轉(zhuǎn)換的共享機(jī)會(huì)。根據(jù)模板生成共享計(jì)劃圖，涵蓋工作負(fù)載中所有可能的共享計(jì)劃，為生成最優(yōu)的共享計(jì)劃提供搜索空間，使共享收益最大化。

3.1 共享計(jì)劃圖模型

定義7 共享計(jì)劃圖。共享計(jì)劃圖（簡(jiǎn)稱為共享圖）是一個(gè)具有節(jié)點(diǎn)集和有向邊集的加權(quán)有向無(wú)環(huán)圖。圖6（c）為一個(gè)共享圖模型，圖中的節(jié)點(diǎn)nk表示convert（Ei，Ej）的一個(gè)共享方案，Ei和Ej為兩個(gè)相鄰的事件類型，Eh為Ej的后置事件。開(kāi)始節(jié)點(diǎn)nqst指示一個(gè)查詢q的開(kāi)始，結(jié)束節(jié)點(diǎn)nqed指示一個(gè)查詢q的結(jié)束，如果部分查詢Qe具有相同的結(jié)束事件類型，則可以為Qe生成同一個(gè)結(jié)束節(jié)點(diǎn)nQeed。convert（Ei，Ej）的所有候選共享方案節(jié)點(diǎn)（candidate sharing node，CSN）組成CSN（Ei，Ej）。如果存在nk和nm屬于相鄰的兩個(gè)CSN，則有向加權(quán)邊edge（nk，nm）連接nk到nm。設(shè)QS為nk（convert（Ei，Ej））和nm（convert（Ej，Eh））的一個(gè)共享查詢集，那么edge（nk，nm）的代價(jià)w代表在執(zhí)行nk到nm的共享方案時(shí)整個(gè)工作負(fù)載Q中所有的QS對(duì)Ej的執(zhí)行代價(jià)（cost（Ej，Q））。

工作負(fù)載Q4包含3個(gè)查詢，Q4={q1，q2，q3}，其中q1=SEQ（F， D），q2=SEQ（ D），q3=SEQ（E，C，D）。圖6（c）中CSN（A，B）對(duì)應(yīng)的convert（A，B）的共享方案有n2和n3，CSN（B，C）對(duì)應(yīng)的convert（B，C）的共享方案有n4，n5，n6。n2上的（1，2）A表示查詢q1和q2通過(guò)共享事件類型A的快照?qǐng)?zhí)行快照的傳播，n3上的（1）（2）表示查詢q1和q2各自執(zhí)行聚合結(jié)果的計(jì)算。nq1st，nq2st，nq3st分別表示查詢q1，q2，q3的開(kāi)始。

CSN（A，B）和CSN（B，C）這樣的連續(xù)CSN中的節(jié)點(diǎn)相連，每個(gè)nk∈CSN（A，B）都有一條出邊指向nm∈CSN（B，C）。圖6（b）中convert（A，B）上有兩個(gè)查詢q1和q2，在圖6（c）中n2到n5的共享方案中兩個(gè)查詢共享執(zhí)行，因此edge（n2，n5）.w=costshare（B，Q4）=cost（B，q1）（或cost（B，q2））。n3到n6查詢q1和q2非共享執(zhí)行，因此edge（n3，n6）.w=costnonshare（B，Q4）=cost（B，q1）+cost（B，q2）。由于工作負(fù)載Q4中的三個(gè)查詢具有相同的結(jié)束事件，所以nQ4ed表示整個(gè)工作負(fù)載的結(jié)束。

共享圖中的所有開(kāi)始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的路徑表示整個(gè)工作負(fù)載中的所有共享計(jì)劃，代價(jià)最小的路徑對(duì)應(yīng)當(dāng)前情況下的最優(yōu)共享計(jì)劃。圖6（c）中當(dāng)前最優(yōu)共享計(jì)劃為加粗表示的路徑。

3.2 共享圖生成

3.2.1 節(jié)點(diǎn)生成原則

如果兩個(gè)連續(xù)的節(jié)點(diǎn)共享不同的查詢或者快照，執(zhí)行時(shí)需要按照式（4）不斷進(jìn)行快照的計(jì)算和更新，以適應(yīng)具有不同QS和快照的共享計(jì)劃，從而損害共享收益。為了使共享收益最大化，為盡可能多的convert保留一個(gè)QS。因此在生成節(jié)點(diǎn)時(shí)，不是在每個(gè)CSN中獨(dú)立枚舉節(jié)點(diǎn)［18］，而是從一個(gè)節(jié)點(diǎn)nk∈CSN（Ei，Ej）生成下一個(gè)節(jié)點(diǎn)nm∈CSN（Ej，Eh）。CSN（Ei，Ej）中的節(jié)點(diǎn)nk可以在CSN（Ej，Eh）中生成多個(gè)節(jié)點(diǎn)，但是并非所有節(jié)點(diǎn)都值得生成。如果已知生成的節(jié)點(diǎn)nm∈CSN（Ej，Eh）的入邊和出邊的權(quán)重大于同一個(gè)CSN中的其他節(jié)點(diǎn)，與其他節(jié)點(diǎn)相比，這樣的局部高代價(jià)節(jié)點(diǎn)nm不會(huì)生成。

假設(shè)在節(jié)點(diǎn)nk中，工作負(fù)載Q5={q5，q6，q7，q8}中有兩個(gè)共享查詢集：Q1S={q5，q6}，Q2S={q7，q8}。nk的共享方案為查詢q5和q6共享事件類型E0的快照，查詢q7和q8共享事件類型E1的快照，在圖7中表示為節(jié)點(diǎn)nk上的（5，6）E0，（7，8）E1。由節(jié)點(diǎn)nk∈CSN（Ei，Ej）生成CSN（Ej，Eh）中的節(jié)點(diǎn)有四種可能，如圖7所示。case 1繼承所有來(lái)自nk的查詢集和快照；case 2保持nk的查詢集不變，為查詢集Q2S生成新的快照；case 3合并所有的查詢集并為新的查詢集生成新的快照；case 4更新了nk的所有查詢集。根據(jù)式（4）得出，case 4生成的節(jié)點(diǎn)對(duì)應(yīng)的入邊和出邊權(quán)重都很大，這樣的局部高代價(jià)節(jié)點(diǎn)沒(méi)有潛在的共享收益，因此不會(huì)生成這樣的節(jié)點(diǎn)。下面根據(jù)case 1到case 3的三種情況，提出了三個(gè)節(jié)點(diǎn)生成原則。

a）節(jié)點(diǎn)生成原則1（繼承原則）。給定一個(gè)節(jié)點(diǎn)nk∈CSN（Ei，Ej），生成節(jié)點(diǎn)nm∈CSN（Ej，Eh），nm繼承所有來(lái)自nk的QS和快照。

對(duì)于這種情況生成的節(jié)點(diǎn)，如圖7中的case 1所示，nm1維持nk的共享方案，繼承來(lái)自nk的共享查詢集和快照事件類型。在按照該計(jì)劃執(zhí)行時(shí)，只需要將快照傳播到后續(xù)事件，不必按照代價(jià)模型計(jì)算式（4）進(jìn)行快照表達(dá)式的計(jì)算。因此生成的節(jié)點(diǎn)只需要考慮共享成本，根據(jù)式（2）得出，nm1的入邊權(quán)重為Q1s和Q2s的共享代價(jià)。繼承原則生成的節(jié)點(diǎn)具有最小的入邊權(quán)重：

edge（nk，nm1）.w=cost（Ej，Q5）=

costshare（Ej，Q1s）+costshare（Ej，Q2s）

b）節(jié)點(diǎn)生成原則2（更新快照原則）。給定一個(gè)節(jié)點(diǎn)nk∈CSN（Ei，Ej），當(dāng)Ej的發(fā)生頻率小于之前的快照事件類型的發(fā)生頻率時(shí)，生成節(jié)點(diǎn)nm∈CSN（Ej，Eh），nm重用來(lái)自nk的QS并創(chuàng)建Ej的快照。

使用繼承原則生成的節(jié)點(diǎn)沒(méi)有考慮出邊權(quán)重，經(jīng)過(guò)nm1節(jié)點(diǎn)的路徑可能在nm1之前具有較輕的權(quán)重但是在nm1之后具有較重的權(quán)重，導(dǎo)致后續(xù)利用該共享方案執(zhí)行時(shí)具有較大的代價(jià)。因此需要考慮入邊權(quán)重較大但是出邊權(quán)重變小的情況，降低后續(xù)的執(zhí)行代價(jià)。使用更新快照原則生成的節(jié)點(diǎn)需要額外的代價(jià)為共享查詢集創(chuàng)建當(dāng)前事件類型的快照，但是具有較小的出邊權(quán)重。如case 2生成的節(jié)點(diǎn)nm2所示，nm2繼承nk的共享查詢集，當(dāng)|Ej|<|E1|時(shí)，為Q2s創(chuàng)建事件類型Ej的快照。因此根據(jù)式（4），nm2的入邊權(quán)重還需加上為Q2s生成Ej的新快照的代價(jià)。但是使用nm2這種共享方案在后續(xù)將快照傳播到Eh時(shí)，Q2s的共享執(zhí)行代價(jià)由式（2）中“：”前的計(jì)算表達(dá)式確定，具有較小的后續(xù)執(zhí)行代價(jià)。nm2入邊權(quán)重為

edge（nk，nm2）·w=cost（Ej，Q5）=costshare（Ej，Q1s）+

costshare（Ej，Q2s）+costeval（Ej，Q2s）

c）節(jié)點(diǎn)生成原則3（合并原則）。給定一個(gè)節(jié)點(diǎn)nk∈CSN（Ei，Ej），生成節(jié)點(diǎn)nm∈CSN（Ej，Eh），nm合并nk的QS并創(chuàng)建Ej的快照。

另一種降低執(zhí)行代價(jià)的情況是工作負(fù)載中的所有查詢都可以共享Ej的快照，可以合并所有的QS并為其創(chuàng)建Ej的快照。使用這種原則生成的節(jié)點(diǎn)雖然入邊權(quán)重較大，但是后續(xù)只需要為一個(gè)共享查詢集傳播快照，降低后續(xù)事件Eh的執(zhí)行成本。如case 3生成的節(jié)點(diǎn)所示，nm3合并所有的QS，因此不僅需要對(duì)Q1s和Q2s分別輸出前一個(gè)共享查詢集的聚合值，還要為新的共享查詢集創(chuàng)建新的快照。得出nm3的權(quán)重代價(jià)為

edge（nk，nm3）·w=cost（Ej，Q5）=costshare（Ej，Q1s）+

costshare（Ej，Q2s）+costeval（Ej，Q1s）+costeval（Ej，Q2s）

使用合并原則生成的節(jié)點(diǎn)入邊權(quán)重均大于繼承和更新快照原則，但是后續(xù)執(zhí)行時(shí)只需要為一個(gè)共享查詢集傳播快照，其執(zhí)行代價(jià)由式（2）中“：”前的表達(dá)式確定。

綜上所述，在構(gòu)造共享圖時(shí)，從開(kāi)始節(jié)點(diǎn)按照生成原則1～3構(gòu)造每個(gè)CSN中的節(jié)點(diǎn)。為每個(gè)節(jié)點(diǎn)nk∈CSN（Ei，Ej），生成多個(gè)nm∈CSN（Ej，Eh）并為其生成邊和相應(yīng)的代價(jià)，直至生成結(jié)束節(jié)點(diǎn)。

3.2.2 修剪原則

在構(gòu)造圖的過(guò)程中通過(guò)修剪邊和每個(gè)CSN中的節(jié)點(diǎn)以減少圖中的節(jié)點(diǎn)數(shù)量，這種策略雖然可能修剪掉更新時(shí)需要用到的節(jié)點(diǎn)，但是可以避免共享圖在早期出現(xiàn)節(jié)點(diǎn)爆炸的現(xiàn)象，有利于初始共享計(jì)劃的路徑搜索［12，18］。以圖6（a）所示的工作負(fù)載Q4為例，說(shuō)明在生成共享圖時(shí)的修剪過(guò)程。初始流統(tǒng)計(jì)信息為：|A|=3， |B|=5，|C|=8，|D|=4，|E|=3，|F|=5，工作負(fù)載Q4={q1，q2，q3}，對(duì)應(yīng)的開(kāi)始事件分別為A、B、F，因此為三個(gè)查詢各生成一個(gè)開(kāi)始節(jié)點(diǎn)，并為查詢q1和q2生成共享計(jì)劃。如圖8（a）所示。

節(jié)點(diǎn)nq1st→n1需要考慮查詢q1的開(kāi)始事件F，由圖6（b）可知F并未與任何查詢共享，因此cost（F，q1）=|F|=5。由convert（F，A）可知下一步需要將聚合值傳播到事件類型A并生成下一個(gè)共享方案節(jié)點(diǎn)n1。節(jié)點(diǎn)n1→n2需要為查詢q1將聚合值傳播到事件類型A并創(chuàng)建事件類型A的快照。因此cost（A，q1）=costshare（A，q1）=|F|×|A|。

生成的后置節(jié)點(diǎn)如圖8（b）所示，在由節(jié)點(diǎn)n2生成后繼節(jié)點(diǎn)的時(shí)候按照3.2.1節(jié)所述有兩種選擇。原則1：繼續(xù)維持事件類型A的快照（節(jié)點(diǎn)n4）；原則2：創(chuàng)建事件類型B的快照（節(jié)點(diǎn)n5）。對(duì)于n2→n4，由于事件類型B的前置事件就是A，所以只需要對(duì)A的快照進(jìn)行統(tǒng)計(jì)即可，且q1和q2共享A的快照，有cost（B，Q4）=costshare（B，Q4）=|A|=5；對(duì)于n2→n5，不僅需要將A的快照傳播到B，還需要分別為q1和q2生成B的快照，因此cost（B，Q4）=costshare（B， Q4）+costeval（B，Q4）=|A|+2×|A|×|B|=33。后續(xù)節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)生成原則生成整個(gè)共享圖，結(jié)果如圖9（a）所示。

如圖9中的n5所示，nq2st到n5有兩條路徑，對(duì)于n2→n5，nq2st到n5的代價(jià)為36；對(duì)于n3→n5，nq2st到n5的代價(jià)為103。因此n3→n5的邊可以修剪，修剪的邊不影響共享計(jì)劃的最優(yōu)性。

邊修剪原則：給定一個(gè)節(jié)點(diǎn)nm，當(dāng)從起始節(jié)點(diǎn)到nm有多條路徑時(shí)，只需保留權(quán)重最小的最優(yōu)路徑，其他路徑通過(guò)的邊可以安全地修剪。

命題1 按照邊修剪原則修剪邊之后，不會(huì)影響共享計(jì)劃的最優(yōu)性。

證明 通過(guò)反證法證明命題一，給定一個(gè)節(jié)點(diǎn)nm∈CSN（Ej，Eh），n0和n1分別是來(lái)自CSN（Ei，Ej）的兩個(gè)節(jié)點(diǎn)，對(duì)應(yīng)的邊分別為edge（n0，nm）和edge（n1，nm），假設(shè)n0.ds+edge（n0，nm）.w<n1.ds+edge（n1，nm）.w。如果最優(yōu)路徑P沿edge（n1，nm）經(jīng)過(guò)n1和nm，將P分為兩部分，第一部分P1為所有的開(kāi)始節(jié)點(diǎn)到節(jié)點(diǎn)nm，第二部分P2為nm到所有的結(jié)束節(jié)點(diǎn)。路徑P的代價(jià)為：P.w=P1.w+P2.w=n1.ds+edge（n1，nm）.w+P2.w。當(dāng)經(jīng)過(guò)n0訪問(wèn)nm時(shí)對(duì)應(yīng)的路徑為代價(jià)為：.w=n0.ds+edge（n0，nm）.w+P2.w，得出.w<P.w，因此P不是最優(yōu)路徑，edge（n1，nm）可以安全地修剪。

節(jié)點(diǎn)n4和n5屬于相同的QS={q1，q2}，但是分別具有不同事件類型的快照A和B，由于|A|<|B|，由式（2）和（4）得出n4.ds<n5.ds，并且n4.de<n5.de，節(jié)點(diǎn)n5可以安全地修剪，并且節(jié)點(diǎn)n9完全由n5生成，所以n9也會(huì)被安全地修剪。修剪后每個(gè)節(jié)點(diǎn)代價(jià)如圖9（b）所示，根據(jù)兩個(gè)修剪原則，圖9（a）中的虛線部分的邊和n5，n9，n10節(jié)點(diǎn)可以安全地被修剪。

給定同一個(gè)CSN中的兩個(gè)節(jié)點(diǎn)，如果這兩個(gè)節(jié)點(diǎn)屬于同一個(gè)共享查詢集，那么這兩個(gè)節(jié)點(diǎn)是可比節(jié)點(diǎn)。

節(jié)點(diǎn)修剪原則：給定兩個(gè)可比節(jié)點(diǎn)nm和nk，如果nm到所有開(kāi)始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)的權(quán)重都比nk大，那么節(jié)點(diǎn)nm可以安全地修剪，并且該節(jié)點(diǎn)的出邊和完全由該節(jié)點(diǎn)生成的后置節(jié)點(diǎn)也可以安全地修剪。

命題2 按照節(jié)點(diǎn)修剪原則修剪節(jié)點(diǎn)之后，不會(huì)影響共享計(jì)劃的最優(yōu)性。

證明 通過(guò)代價(jià)模型證明命題2，給定CSN（Ej，Eh）中分別共享事件類型A和B的兩個(gè)節(jié)點(diǎn)nk和nm，其中|A|<|B|。根據(jù)式（2）得出，由于nk的快照事件發(fā)生頻率較小，應(yīng)用nm的共享成本小于應(yīng)用nk的成本。后續(xù)如果需要進(jìn)行快照計(jì)算，根據(jù)式（4）得出A快照的計(jì)算成本小于B的計(jì)算成本，因此從nk到所有結(jié)束節(jié)點(diǎn)的路徑權(quán)重比nm都小，并且nk.ds<nm.ds。因此節(jié)點(diǎn)nm可以安全地修剪。

3.2.3 對(duì)Kleene模式的優(yōu)化

在執(zhí)行過(guò)程中，Kleene模式可以匹配任意多個(gè)滿足模式的事件趨勢(shì)，其匹配的事件數(shù)量呈指數(shù)增長(zhǎng)。因此本節(jié)重點(diǎn)關(guān)注對(duì)Kleene模式的共享優(yōu)化，將Kleene模式的優(yōu)化同其他部分隔離，為其構(gòu)建Kleene子圖。若需要同其他部分連接，則將Kleene子圖的最優(yōu)共享計(jì)劃插入到共享圖的相應(yīng)位置，并在整個(gè)圖中進(jìn)一步修剪，得到全局最優(yōu)共享計(jì)劃。

為了更有效地展示對(duì)Kleene模式的優(yōu)化方法，本節(jié)以工作負(fù)載Q6={q9，q10}的共享計(jì)劃生成過(guò)程為例進(jìn)行介紹。假設(shè)工作負(fù)載Q6中的兩個(gè)查詢需要共享子模式SEQ（A，（B，C）+，D）+。圖10（a）為Q6的工作負(fù)載模板，在該模板中存在兩條可以構(gòu)成循環(huán)的convert，分別為convert（C，B）和convert（D，A），將這種convert稱為Kleene convert。

在共享圖模型中，連續(xù)的兩個(gè)CSN中的節(jié)點(diǎn)相連。圖10（a）中的兩個(gè)Kleene convert為convert（C，B）和convert（D，A），這兩個(gè)convert的候選共享方案分別為CSN（C，B）和CSN（D，A）。兩個(gè)CSN中的節(jié)點(diǎn)同樣在Kleene子圖也會(huì)構(gòu)成循環(huán)。為方便區(qū)分，將Kleene子圖的路徑稱為循環(huán)路徑。在Kleene子圖的所有循環(huán)路徑中，具有不同的共享方案的路徑會(huì)導(dǎo)致較高的執(zhí)行代價(jià)，這樣的路徑?jīng)]有必要生成。

命題3 具有不同共享方案節(jié)點(diǎn)的循環(huán)路徑可以安全地修剪。

證明 設(shè)nk和nm是循環(huán)路徑P中的兩個(gè)節(jié)點(diǎn)，共享查詢集為QS，證明共享方案：nk=nm。若nk和nm通過(guò)不同事件類型的快照對(duì)QS進(jìn)行共享（分別為E0和E1）。假設(shè)|E0|>|E1|，則根據(jù)節(jié)點(diǎn)生成原則（更新快照），由于nk的快照多于nm的快照，nk到nm之間一定存在一條具有潛在收益的路徑。然而，由于P是一個(gè)循環(huán)，從nm到nk也存在一條路徑。根據(jù)節(jié)點(diǎn)生成原則（更新快照原則），將快照數(shù)量從E0和增加到E1伴隨著額外的計(jì)算成本，并不會(huì)帶來(lái)共享好處。因此P.w一定會(huì)大于P′.w（P′經(jīng)過(guò)的所有節(jié)點(diǎn)均通過(guò)事件類型E1的快照對(duì)QS進(jìn)行共享）。P不是最優(yōu)路徑，循環(huán)路徑P可以被安全地修剪。

排除上述不會(huì)生成的循環(huán)路徑之后。提出循環(huán)路徑生成原則：假設(shè)模板中存在平坦的Kleene子模式SEQ（E0，E1，…，Ek）+，該子模式的Kleene子圖有k+1個(gè)CSN，其中k個(gè)是SEQ的CSN（Ei，Ei+1）（0≤i<k），一個(gè)是Kleene循環(huán)CSN（Ek，E0）。Kleene子圖中的路徑P是一個(gè)循環(huán)，包含每個(gè)CSN中的一個(gè)節(jié)點(diǎn)。當(dāng)且僅當(dāng)路徑P經(jīng)過(guò)的所有節(jié)點(diǎn)使用的是相同事件類型的快照共享相同的QS時(shí)，才會(huì)生成循環(huán)路徑P，否則，所有節(jié)點(diǎn)上的共享方案均是非共享執(zhí)行。

循環(huán)路徑生成原則同樣適用于嵌套Kleene子模式的Kleene子圖，對(duì)應(yīng)的路徑是嵌套循環(huán)路徑。由于每個(gè)單循環(huán)路徑中的節(jié)點(diǎn)具有相同的共享方案，那么嵌套循環(huán)路徑中的所有節(jié)點(diǎn)同樣具有相同的共享方案。

以工作負(fù)載Q6為例，事件流統(tǒng)計(jì)信息分別為：|A|=10，|B|=5，|C|=3，|D|=15。圖10（b）表示從節(jié)點(diǎn)nk∈CSN（Ei，Ej）生成節(jié)點(diǎn)nm∈CSN（Ej，Eh）時(shí)需要傳播的事件類型的執(zhí)行代價(jià)，圖10（e）（f）分別為選取不同事件類型的快照進(jìn)行共享的嵌套循環(huán)路徑。路徑中的每條邊都用代價(jià)模型計(jì)算的權(quán)重進(jìn)行標(biāo)記。

同樣對(duì)Kleene子圖采用修剪原則，對(duì)高代價(jià)的節(jié)點(diǎn)進(jìn)行修剪。對(duì)于每條路徑，都有一條來(lái)自Kleene子圖前一部分共享圖的邊，以及作為后續(xù)延伸的源節(jié)點(diǎn)nk，令nk.ds為各路徑的權(quán)重。工作負(fù)載Q6都從事件類型A開(kāi)始，n1到n4來(lái)自同一個(gè)節(jié)點(diǎn)，入邊權(quán)重均為10。各節(jié)點(diǎn)到開(kāi)始節(jié)點(diǎn)的代價(jià)如表3所示。

選取事件類型C為快照事件類型時(shí)，整個(gè)共享執(zhí)行過(guò)程代價(jià)最小，因此選擇C為此工作負(fù)載的快照事件類型。

3.3 共享計(jì)劃更新方法

在處理事件趨勢(shì)聚合查詢時(shí)，可能發(fā)生變化的信息有事件流統(tǒng)計(jì)信息和工作負(fù)載信息。當(dāng)工作負(fù)載減少時(shí)，直接從當(dāng)前共享計(jì)劃中刪除對(duì)應(yīng)的查詢，并且不再為該查詢傳播聚合值以及生成最后結(jié)果。當(dāng)工作負(fù)載增加時(shí)，由于在已經(jīng)生成的共享圖中搜索可共享的節(jié)點(diǎn)需要消耗大量的內(nèi)存，所以只為新的工作負(fù)載單獨(dú)生成共享計(jì)劃，不再參與之前的共享。

本文設(shè)計(jì)了檢測(cè)更新計(jì)劃的代價(jià)模型，用于實(shí)時(shí)更新共享計(jì)劃方法，提高事件趨勢(shì)聚合查詢的處理性能。當(dāng)事件流統(tǒng)計(jì)信息發(fā)生變化時(shí)，對(duì)于帶有Kleene操作符的工作負(fù)載，在3.2.3節(jié)已經(jīng)詳細(xì)闡述過(guò)Kleene模式和SEQ模式單獨(dú)分析共享機(jī)會(huì)，因此只需單獨(dú)進(jìn)行更新。

在事件流信息發(fā)生變化時(shí)，需要考慮以下兩個(gè)問(wèn)題：a）是否需要更新共享計(jì)劃；b）需要更新計(jì)劃時(shí)，如何更新節(jié)點(diǎn)的信息。分析發(fā)現(xiàn)，未參與共享的事件類型頻率發(fā)生變化，或者快照事件類型的發(fā)生頻率變小時(shí)，根據(jù)式（2）得出不會(huì)更改共享的快照事件類型，因此不需要更新共享計(jì)劃，按照原計(jì)劃執(zhí)行；參與共享的快照事件類型頻率變大或者快照事件類型的后置事件頻率變小，則需要考慮更新共享計(jì)劃，并將新的共享計(jì)劃應(yīng)用到后續(xù)的執(zhí)行過(guò)程中。判斷條件如下。

以SEQ模式為例，在一個(gè)共享的查詢集QS中，查詢的數(shù)量為|QS|。圖11為QS的共享圖中的一部分，節(jié)點(diǎn)n1處的共享方案是以Ej為QS的快照事件類型進(jìn)行共享，之后需要將快照傳播到事件類型Eh。P1和P2分別為虛線表示的初始路徑和實(shí)線表示的更新后的路徑。

圖11中三部分的代價(jià)計(jì)算如表4所示。

在初始條件為|Ej|<|Eh|時(shí)，每個(gè)部分的代價(jià)均有P1.w<P2.w，得出總路徑代價(jià)P1.w<P2.w，因此選取P1為共享計(jì)劃。但是當(dāng)Ej和Eh的事件頻率發(fā)生變化之后，三部分的代價(jià)均發(fā)生變化。當(dāng)P1.w>P2.w時(shí)，該查詢集的共享計(jì)劃需要進(jìn)行調(diào)整。

表4中|QS|為共享查詢 集中查詢的數(shù)量，|Ej|、|Eh|和|Es|分別為QS 共享的快照事件類型Ej、Eh和Eh的所有后綴事件Es的事件發(fā)生頻率，Eed為當(dāng)前QS共享的最后一個(gè)事件類型。

本文設(shè)計(jì)了動(dòng)態(tài)更新共享計(jì)劃的算法以適應(yīng)實(shí)時(shí)變化的事件流信息，如算法1所示。

算法1具有四個(gè)輸入?yún)?shù)。P為原始路徑，SE為事件流統(tǒng)計(jì)信息，工作負(fù)載模板T中存儲(chǔ)了工作負(fù)載中查詢的信息，E1為檢測(cè)到事件發(fā)生頻率產(chǎn)生變化的事件類型。

算法1首先將原始路徑P以及對(duì)應(yīng)的路徑代價(jià)賦值給更新后的路徑P′（第1行）。之后在模板T中通過(guò)廣度優(yōu)先搜索算法得到事件發(fā)生頻率變化的事件類型E1對(duì)應(yīng)的convert，得到其前置和后置事件類型，并分別將前置和后置事件類型存儲(chǔ)在對(duì)應(yīng)的集合中（第2～4行）。

第5行中snapSet為當(dāng)前QS的快照事件類型集合，檢測(cè)E1是否在snapSet中。若E1是快照事件類型，則檢測(cè)E1是否比后置事件類型Es的事件發(fā)生頻率大（第6，7行），當(dāng)E1的事件發(fā)生頻率大于Es的時(shí)候，需要檢測(cè)E1和Es是否滿足式（5）以更新共享計(jì)劃（第8行）。如果滿足不等式，則在原始路徑P中找到convert（E1，Es）對(duì)應(yīng)的節(jié)點(diǎn)n1（第9行）。在n1之后按照節(jié)點(diǎn)生成原則（更新快照）生成以Es為快照事件類型的共享方案節(jié)點(diǎn)（第10行）。updatePath（）方法將生成的節(jié)點(diǎn)插入到新的共享計(jì)劃P′中，并更新相應(yīng)的代價(jià)，之后按照節(jié)點(diǎn)生成原則（繼承）生成后續(xù)節(jié)點(diǎn)直至得到新的共享計(jì)劃P′（第11行）。

若E1不是快照事件類型，需要在路徑P中搜索到convert（E0，Es）對(duì)應(yīng)的共享方案節(jié)點(diǎn)n2，在n2中得到共享查詢集QS以及共享的快照事件類型Esn（第12～15行）。當(dāng)|E1|<|Esn|時(shí)，需要檢測(cè)Esn和E1是否滿足式（5）以更新共享計(jì)劃（第16行）。如果滿足不等式，則在n2之后按照節(jié)點(diǎn)生成原則（更新快照）生成以E1為快照事件類型的共享方案節(jié)點(diǎn)，直至得到新的共享計(jì)劃P′（第17，18行）。最后返回新的共享計(jì)劃P′（第19行）。

算法1 共享計(jì)劃更新算法updateSharingPlan

輸入：原始路徑P；事件流統(tǒng)計(jì)信息SE；工作負(fù)載模板T；事件發(fā)生頻率產(chǎn)生變化的事件類型E1。

輸出：更新后的路徑P′。

1 P′←P，P′.w←P.w；

2 在模板T中搜索到convert（Ep，E1）以及convert（E1，Es）；

3 prefixSet←Ep；

4 suffixSet←Es；

5 if E1 in snapSet

6 for each Es in suffixSet

7 if |E1|>|Es| then

8 if E1和Es滿足式（5） then

9 在P中找到convert（E1，Es）對(duì)應(yīng)的節(jié)點(diǎn)n1；

10 n1.rightNode←generateNode（n′，Es）；

11 updatePath（P′，P′.w，n′）；

12 else for each Ep in prefixSet

13 在P中找到convert（Ep，E1）對(duì)應(yīng)的節(jié)點(diǎn)n2；

14 QS←node.getSet（）；

15 Esn←snap（Ep，QS）；

16 if |E1|<|Esn| then

17 n2.rightnode←generateNode（n′，E1）；

18 updatePath（P′，P′.w，n′）；

19 return P′；

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

通過(guò)實(shí)驗(yàn)對(duì)本文提出的動(dòng)態(tài)更新共享計(jì)劃方法的有效性進(jìn)行了分析和驗(yàn)證。硬件環(huán)境為12th Gen Intel CoreTM i7-1260P，64 GB內(nèi)存，2.5 GHz頻率。軟件平臺(tái)為Ubuntu 22.04，編程語(yǔ)言是Java，使用OpenJDK 16.0.1實(shí)現(xiàn)了方法的編寫并運(yùn)行實(shí)驗(yàn)。從多個(gè)維度對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析說(shuō)明，每個(gè)實(shí)驗(yàn)平均運(yùn)行15次。通過(guò)性能對(duì)比證明本文方法的有效性。

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

4.1.1 事件流數(shù)據(jù)集

在三個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，兩個(gè)數(shù)據(jù)集是真實(shí)的股票和公交車數(shù)據(jù)集，一個(gè)數(shù)據(jù)集是通過(guò)事件流生成方法生成的模擬數(shù)據(jù)流，事件的變化頻率為3～5倍。

股票數(shù)據(jù)集包含NASDAQ 20年的股票價(jià)格歷史記錄。每條記錄代表一個(gè)事件，包含公司標(biāo)識(shí)符、時(shí)間戳（分鐘）、開(kāi)盤價(jià)和收盤價(jià)、最高價(jià)和最低價(jià)以及交易量。事件類型與3 258個(gè)唯一的公司標(biāo)識(shí)符相對(duì)應(yīng)。

公交車GPS數(shù)據(jù)集為2018年收集的都柏林公交車GPS記錄組成。每條記錄都是帶有時(shí)間戳的元組（微秒），包含線路ID、車輛行程ID、擁堵指示、坐標(biāo)和延遲時(shí)間。有4 368個(gè)唯一行程ID。

模擬數(shù)據(jù)流是ABC類型的事件流，每個(gè)事件都帶有時(shí)間戳以及各自的屬性值。根據(jù)自定義的事件類型數(shù)量、屬性個(gè)數(shù)和屬性值的范圍生成相應(yīng)的事件流，事件流中的每個(gè)事件都根據(jù)指定的頻率隨機(jī)生成和變化，包含5 000個(gè)原始事件。

4.1.2 工作負(fù)載數(shù)據(jù)集

為了評(píng)估共享計(jì)劃更新方法在不同查詢負(fù)載下的有效性，在每個(gè)數(shù)據(jù)集上設(shè)置了三種類型的工作負(fù)載。SEQ工作負(fù)載具有不同的可共享SEQ模式、分組、謂詞和聚合函數(shù)（count（*）、max等）。Kleene模式的工作負(fù)載分為可共享的平坦Kleene模式和嵌套Kleene模式，Kleene子模式的長(zhǎng)度為2～10；嵌套Kleene子模式的嵌套層數(shù)為1～5層，謂詞、時(shí)間窗口和聚合設(shè)置與SEQ工作負(fù)載相同?；旌瞎ぷ髫?fù)載包括SEQ子模式和Kleene子模式，Kleene模式占比由20%調(diào)整到100%。

4.1.3 衡量指標(biāo)

對(duì)于執(zhí)行工作負(fù)載的優(yōu)化，以秒為單位度量執(zhí)行時(shí)間，即接收工作負(fù)載與生成聚合結(jié)果的平均時(shí)間差。包括模板構(gòu)建、圖構(gòu)建、路徑搜索、圖更新和生成聚合結(jié)果值的時(shí)間。峰值內(nèi)存是執(zhí)行過(guò)程中消耗的最大內(nèi)存。執(zhí)行時(shí)，使用以秒為單位的延遲時(shí)間作為產(chǎn)生聚合結(jié)果的時(shí)間與最后一個(gè)相關(guān)事件到達(dá)時(shí)間的平均時(shí)間差。吞吐量是所有查詢每秒處理的平均事件數(shù)。

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

實(shí)驗(yàn)1 首先比較了本文方法Dynamic和當(dāng)前處理聚合查詢效果較好的兩個(gè)方法（Static［12］和Hamlet［11］）執(zhí)行的延遲時(shí)間和吞吐量。這兩種方法均支持處理Kleene操作符以及共享查詢之間的執(zhí)行。但是Static方法所生成的共享計(jì)劃并不適用于實(shí)時(shí)變化的動(dòng)態(tài)數(shù)據(jù)流。在事件流或工作負(fù)載出現(xiàn)波動(dòng)時(shí)，Static方法的性能顯著下降。Hamlet方法只針對(duì)E+這種平坦的Kleene模式進(jìn)行了優(yōu)化，將短時(shí)間內(nèi)發(fā)生的同一事件類型的事件視為突發(fā)事件。每次發(fā)生突發(fā)事件時(shí)，都需要進(jìn)行共享決策，導(dǎo)致執(zhí)行效率不高。

Kleene模式占比為固定的60%，將工作負(fù)載查詢數(shù)量從12增加至120在股票數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。圖12（a）（b）分別為延遲時(shí)間和吞吐量的對(duì)比。在延遲時(shí)間上本文方法分別比Hamlet和Static方法性能提升大約9倍和3倍，吞吐量上分別比Hamlet和Static提高了80%和50%。Dynamic方法在動(dòng)態(tài)數(shù)據(jù)流環(huán)境下，不斷分析當(dāng)前的執(zhí)行信息和共享計(jì)劃，評(píng)估共享收益以選擇不同事件類型的快照，進(jìn)行動(dòng)態(tài)調(diào)整。因此能夠更高效地評(píng)估工作負(fù)載。

實(shí)驗(yàn)2 比較了本文的Dynamic方法和由嚴(yán)格的共享計(jì)劃指導(dǎo)方法的整體運(yùn)行時(shí)間，包括生成圖和共享計(jì)劃，處理聚合查詢工作負(fù)載并生成最后的結(jié)果值。并對(duì)修剪和未修剪的方法分別進(jìn)行了對(duì)比實(shí)驗(yàn)。

對(duì)于SEQ工作負(fù)載，分別評(píng)估了對(duì)修剪和不修剪的共享圖上更新共享計(jì)劃的延遲時(shí)間。工作負(fù)載中的查詢數(shù)量由40增加到200，事件頻率變化為3～5倍，評(píng)估了對(duì)公交車數(shù)據(jù)集的處理時(shí)間。執(zhí)行過(guò)程中，判斷是否需要更新共享計(jì)劃需要占用一定的時(shí)間和內(nèi)存空間，未修剪共享圖的路徑搜索時(shí)間大于修剪之后的搜索時(shí)間，但是如果需要更新共享計(jì)劃，修剪的共享圖在生成圖時(shí)可能會(huì)刪除更新之后的候選共享計(jì)劃中的節(jié)點(diǎn)，因此需要重新生成新的節(jié)點(diǎn)并重新對(duì)圖進(jìn)行修剪。如圖13（a）所示，本文方法始終優(yōu)于靜態(tài)共享計(jì)劃執(zhí)行的3～5倍。綜上所述，動(dòng)態(tài)更新共享計(jì)劃有效地加快了聚合查詢的執(zhí)行速度。

對(duì)于Kleene子模式，比較了在包含9lyT4iOY4zEq1w5wDJ5fT7Zh61UhSOP1c5/tEvMOal0=平坦Kleene子模式的100個(gè)查詢的工作負(fù)載，將Kleene子模式的長(zhǎng)度由2變化到10。本文方法對(duì)于給定的Kleene工作負(fù)載，如圖13（b）所示，為Kleene子模式生成的子圖總是很小，因此在更新共享計(jì)劃時(shí)會(huì)消耗更少的時(shí)間和更低的內(nèi)存。對(duì)于嵌套的Kleene子模式，將Kleene子模式的嵌套層數(shù)從1層調(diào)整到5層進(jìn)行了對(duì)比實(shí)驗(yàn)，如圖13（c）所示，隨著嵌套層數(shù)的增加，靜態(tài)方法的執(zhí)行時(shí)間增加得越多，而本文方法可以對(duì)共享計(jì)劃進(jìn)行動(dòng)態(tài)調(diào)整，因此對(duì)比靜態(tài)方法，執(zhí)行時(shí)間顯著減少。

對(duì)于混合工作負(fù)載，圖13（d）展示了在包含100個(gè)查詢的混合工作負(fù)載下動(dòng)態(tài)更新和靜態(tài)共享計(jì)劃的執(zhí)行時(shí)間。將包含Kleene模式的查詢（以下簡(jiǎn)稱為Kleene查詢）所占百分比從20%調(diào)整到100%。隨著Kleene查詢數(shù)量的增加，本文方法的優(yōu)化性能達(dá)到靜態(tài)執(zhí)行方法的3倍。當(dāng)Kleene查詢的比例增加到40%時(shí)，SEQ查詢的數(shù)量減少，降低了SEQ查詢處理的復(fù)雜度。當(dāng)Kleene查詢的比例大于50%時(shí)，優(yōu)化時(shí)間主要用于優(yōu)化Kleene查詢共享的時(shí)間。由于對(duì)Kleene子圖采用了修剪原則，所以優(yōu)化性能隨著Kleene查詢的增多而減少。

實(shí)驗(yàn)3 圖14（a）（b）分別為在股票和公交車數(shù)據(jù)集上將工作查詢負(fù)載中的查詢從12增加到120的峰值內(nèi)存的對(duì)比結(jié)果。由于動(dòng)態(tài)調(diào)整了共享計(jì)劃，減少了不必要的快照傳播的代價(jià)，本文方法在兩個(gè)數(shù)據(jù)集上的峰值內(nèi)存消耗占靜態(tài)方法內(nèi)存消耗的50%～70%。

上述實(shí)驗(yàn)表明，本文提出的動(dòng)態(tài)更新共享計(jì)劃的方法能夠有效適應(yīng)實(shí)時(shí)變化的事件流和工作負(fù)載，無(wú)論是在SEQ模式還是在Kleene模式下，都表現(xiàn)出較好的性能。

5 結(jié)束語(yǔ)

本文研究了應(yīng)對(duì)動(dòng)態(tài)變化的數(shù)據(jù)信息時(shí)處理聚合查詢的問(wèn)題。針對(duì)包含Kleene操作符的多個(gè)聚合查詢，設(shè)計(jì)了共享圖模型，將查詢之間的共享問(wèn)題抽象為加權(quán)有向無(wú)環(huán)圖的最佳路徑搜索問(wèn)題。綜合考慮了實(shí)時(shí)變化的事件流和工作負(fù)載信息，設(shè)計(jì)出代價(jià)模型，以最大化共享收益。將代價(jià)模型應(yīng)用到圖生成過(guò)程，并在生成圖時(shí)對(duì)其進(jìn)行修剪，加快了生成共享計(jì)劃的時(shí)間。降低了處理聚合查詢的延遲時(shí)間，提高了系統(tǒng)的吞吐量，實(shí)現(xiàn)了高效的更新共享計(jì)劃。實(shí)驗(yàn)結(jié)果驗(yàn)證了動(dòng)態(tài)更新共享計(jì)劃方法對(duì)執(zhí)行性能的有效提升，在處理動(dòng)態(tài)數(shù)據(jù)的聚合查詢時(shí)提供了有力的解決方案。

參考文獻(xiàn)：

［1］邱濤， 謝沛良， 鄧國(guó)鵬， 等. 面向?qū)崟r(shí)事件流的復(fù)雜事件處理方法［J］. 計(jì)算機(jī)應(yīng)用研究， 2022， 39（9）： 2677-2682， 2688. （Qiu Tao， Xie Peiliang， Deng Guopeng， et al. Complex event processing method over real-time event streams［J］. Application Research of Computers， 2022， 39（9）： 2677-2682，2688.）

［2］Poppe O， Lei Chuan， Ahmed S， et al. Complete event trend detection in high-rate event streams［C］//Proc of the ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2017： 109-124.

［3］夏秀峰， 武孟達(dá)， 張楊， 等. 基于動(dòng)態(tài)匹配策略的復(fù)雜事件處理方法［J］. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（11）： 3341-3347. （Xia Xiu-feng， Wu Mengda， Zhang Yang， et al. Efficient complex event processing based on dynamic matching strategy［J］. Application Research of Computers， 2023， 40（11）： 3341-3347.）

［4］喬雅正， 程良倫， 王濤，等. 地鐵列車環(huán)境中多依賴復(fù)雜事件處理研究［J］. 計(jì)算機(jī)應(yīng)用研究， 2019， 36（8）： 2355-2358， 2367. （Qiao Yazheng， Cheng Lianglun， Wang Tao， et al. Study on multi-dependency complex event processing in subway train environment［J］. Application Research of Computers， 2019， 36（8）： 2355-2358，2367.）

［5］Kolchinsky I， Schuster A. Real-time multi-pattern detection over event streams［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2019： 589-606.

［6］Poppe O， Rozet A， Lei Chuan， et al. Sharon： shared online event sequence aggregation［C］//Proc of the 34th ICDE International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2018： 737-748.

［7］Poppe O， Lei Chuan， Rundensteiner E A， et al. GRETA： graph-based real-time event trend aggregation［J］. The VLDB Endowment， 2017， 11（1）： 80-92.

［8］Perera K P D， Ahangama S. A review of query optimization techniques for complex event processing［C］//Proc of the 4th ICITR International Conference on Information Technology Research. Piscata-way， NJ： IEEE Press， 2019： 1-7.

［9］Hong M， Riedewald M， Koch C， et al. Rule-based multi-query optimization［C］//Proc of the 12th ACM EDBT International Conference on Extending Database Technology： Advances in Database Techno-logy. New York： ACM Press， 2009： 120-131.

［10］Zhang Haopeng， Diao Yanlei， Immerman N. On complexity and optimization of expensive queries in complex event processing［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2014： 217-228.

［11］Qi Yingmei， Cao Lei， Ray M， et al. Complex event analytics： online aggregation of stream sequence patterns［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2014： 229-240.

［12］Poppe O， Lei Chuan， Ma Lei， et al. To share， or not to share online event trend aggregation over bursty event streams［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2021： 1452-1464.

［13］Mei Huiyao， Chen Hanhua， Jin Hai， et al. Efficient complete event trend detection over high-velocity streams［C］//Proc of the 50th ACM ICPP International Conference on Parallel Processing. New York： ACM Press， 2021： 1-12.

［14］趙會(huì)群， 李會(huì)峰， 劉金鑾. RFID物聯(lián)網(wǎng)復(fù)雜事件模式聚類算法研究［J］. 計(jì)算機(jī)應(yīng)用研究， 2018， 35（2）： 339-341. （Zhao Huiqun， Li Huifeng， Liu Jinluan. Study on RFID complex event pattern clustering algorithm of Internet of Things［J］. Application Research of Computers， 2018， 35（2）： 339-341.）

［15］Zhang Shuhao， Vo H T， Dahlmeier D， et al. Multi-query optimization for complex event processing in SAP ESP［C］//Proc of the 33rd ICDE International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2017： 1213-1224.

［16］Wu E， Diao Yanlei， Rizvi S. High-performance complex event processing over streams［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2006： 407-418.

［17］Mei Yuan， Madden S. Zstream： a cost-based query processor for adaptively detecting composite events［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2009： 193-206.

［18］Ma Lei， Lei Chuan， Poppe O， et al. Gloria： graph-based sharing optimizer for event trend aggregation［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2022： 1122-1135.

［19］Liu Mo， Rundensteiner E， Dougherty D， et al. High-performance nested CEP query processing over event streams［C］//Proc of the 27th International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2011： 123-134.

［20］Liu Mo， Ray M， Rundensteiner E A， et al. Processing nested complex sequence pattern queries over event streams［C］//Proc of the 7th ACM DMSN International Workshop on Data Management for Sensor Networks. New York： ACM Press， 2010： 14-19.

［21］邱濤， 丁建麗， 夏秀峰，等. 基于有序事件列表的高效復(fù)雜事件匹配算法［J］. 計(jì)算機(jī)應(yīng)用， 2023， 43（2）： 423-429. （Qiu Tao， Ding Jianli， Xia Xiufeng， et al. Efficient complex event matching algorithm based on ordered event lists［J］. Journal of Computer App-lication， 2023， 43（2）： 423-429.）

［22］施建明， 王偉， 王功. 基于Flink復(fù)雜事件處理的空間站實(shí)驗(yàn)柜排廢氣安全監(jiān)測(cè)［J］. 載人航天， 2023， 29（1）： 102-109. （Shi Jianming， Wang Wei， Wang Gong. Safety monitoring of exhaust gas discharge of experimental rack onboard space station based on Flink CEP［J］. Manned Spaceflight， 2023， 29（1）： 102-109.）

［23］Schultz-Mller N P， Migliavacca M， Pietzuch P. Distributed complex event processing with query rewriting［C］//Proc of the 3rd ACM DEBS International Conference on Distributed Event-Based Systems. New York： ACM Press， 2009： 1-12.

［24］Ray M， Lei Chuan， Rundensteiner E A. Scalable pattern sharing on event streams［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2016： 495-510.

［25］Liu Mo， Rundensteiner E， Greenfield K， et al. E-cube： multi-dimensional event sequence analysis using hierarchical pattern query sharing［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2011： 889-900.

［26］Poppe O， Lei Chuan， Rundensteiner E A， et al. Event trend aggregation under rich event matching semantics［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2019： 555-572.