INMDB中復(fù)合事件監(jiān)測(cè)機(jī)制的設(shè)計(jì)與實(shí)現(xiàn)

賀宏達(dá)　劉夢(mèng)赤

(武漢大學(xué)計(jì)算機(jī)學(xué)院　湖北 武漢 430072)

?

INMDB中復(fù)合事件監(jiān)測(cè)機(jī)制的設(shè)計(jì)與實(shí)現(xiàn)

賀宏達(dá)劉夢(mèng)赤

(武漢大學(xué)計(jì)算機(jī)學(xué)院湖北 武漢 430072)

對(duì)于大多數(shù)主動(dòng)數(shù)據(jù)庫(kù)來(lái)說(shuō)，復(fù)合事件監(jiān)測(cè)始終是個(gè)難題。介紹信息網(wǎng)模型INM(InformationNetworkModel)數(shù)據(jù)庫(kù)管理系統(tǒng)中的復(fù)合事件監(jiān)測(cè)機(jī)制，詳細(xì)描述利用事件樹(shù)模型監(jiān)測(cè)復(fù)合事件的思想，并提供具體的算法實(shí)現(xiàn)。經(jīng)分析，該算法在運(yùn)行效率和空間占用上均比常見(jiàn)的有限自動(dòng)機(jī)和Petri網(wǎng)有著更好的表現(xiàn)。

信息網(wǎng)模型主動(dòng)數(shù)據(jù)庫(kù)復(fù)合事件監(jiān)測(cè)事件樹(shù)

0　引　言

與傳統(tǒng)數(shù)據(jù)庫(kù)相比，主動(dòng)數(shù)據(jù)庫(kù)能夠?qū)?shù)據(jù)庫(kù)管理系統(tǒng)內(nèi)外發(fā)生的事件自動(dòng)作出響應(yīng)。這種自動(dòng)響應(yīng)機(jī)制通過(guò)主動(dòng)規(guī)則來(lái)實(shí)現(xiàn)。一般來(lái)說(shuō)，主動(dòng)規(guī)則由三部分組成：事件、條件和動(dòng)作[1]。事件，指數(shù)據(jù)庫(kù)系統(tǒng)中某一時(shí)刻的數(shù)據(jù)操作引發(fā)[2]。主動(dòng)規(guī)則定義之后，一旦對(duì)應(yīng)的事件發(fā)生，數(shù)據(jù)庫(kù)系統(tǒng)將對(duì)條件部分進(jìn)行求值，若條件為真，則執(zhí)行對(duì)應(yīng)的動(dòng)作。也就是說(shuō)，事件是整個(gè)主動(dòng)規(guī)則執(zhí)行過(guò)程的起點(diǎn)。因此，事件的監(jiān)測(cè)是主動(dòng)規(guī)則設(shè)計(jì)時(shí)的首要問(wèn)題。

要對(duì)事件進(jìn)行監(jiān)測(cè)，就必須先提供其描述。按照是否可分，事件通?？梢苑譃閮深悾?/p>

(1) 原子事件：指單個(gè)的某一類事件。比如插入元組，更新屬性，刪除元組等。

(2) 復(fù)合事件：由幾個(gè)原子事件或者復(fù)合事件通過(guò)事件代數(shù)中的操作符連接而成。

復(fù)合事件處理CEP(CompositeEventProcessing)的應(yīng)用極為廣泛，它能夠從看似毫無(wú)意義的原子事件組合中查找是否有更復(fù)雜的情況發(fā)生。信用卡防盜刷、安全監(jiān)控和商業(yè)活動(dòng)監(jiān)控等方面對(duì)此均有著強(qiáng)烈的應(yīng)用需求，知名企業(yè)如支付寶等均大量應(yīng)用CEP來(lái)處理網(wǎng)絡(luò)欺詐、網(wǎng)絡(luò)攻擊等安全威脅[3]。而IBM、Oracle和微軟等更是推出了一系列CEP產(chǎn)品來(lái)滿足用戶日益增長(zhǎng)的需求。

1　相關(guān)工作

復(fù)合事件監(jiān)測(cè)的主要難點(diǎn)在于建模。原子事件的監(jiān)測(cè)相對(duì)較為容易，因而通常采取的建模方法都是從復(fù)合事件與其子事件以及相關(guān)原子之間的關(guān)系入手，建立起抽象的數(shù)學(xué)模型。現(xiàn)有的復(fù)合事件監(jiān)測(cè)算法有Petri網(wǎng)、有限狀態(tài)自動(dòng)機(jī)、事件樹(shù)以及事件圖等。

Petri網(wǎng)是一種強(qiáng)大的建模工具，能夠簡(jiǎn)潔明確的描述各種各樣的復(fù)雜系統(tǒng)，因此常被用于復(fù)合事件建模。它將復(fù)合事件抽象為節(jié)點(diǎn)和節(jié)點(diǎn)之間轉(zhuǎn)換關(guān)系的集合。其中，輸出節(jié)點(diǎn)為待監(jiān)測(cè)的復(fù)合事件，而輸入節(jié)點(diǎn)為與之相關(guān)的原子事件。Petri網(wǎng)結(jié)構(gòu)中包含的信息由令牌標(biāo)記，令牌的轉(zhuǎn)移方式則代表了原子事件的發(fā)生對(duì)復(fù)合事件的影響，轉(zhuǎn)移方式保存在控制矩陣之中。當(dāng)令牌在節(jié)點(diǎn)之間轉(zhuǎn)移時(shí)，整個(gè)Petri網(wǎng)代表的復(fù)合事件的狀態(tài)也隨之發(fā)生變化。令牌每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)，就對(duì)此節(jié)點(diǎn)做標(biāo)記。當(dāng)Petri網(wǎng)中不再有未被標(biāo)記的節(jié)點(diǎn)時(shí)，就表示對(duì)應(yīng)的復(fù)合事件被監(jiān)測(cè)到。比較典型的應(yīng)用有SAMOS[4]和Hi-Fi[5]等。

有限狀態(tài)自動(dòng)機(jī)，將復(fù)合事件視為正則表達(dá)式，并由此構(gòu)造出對(duì)應(yīng)的自動(dòng)機(jī)。子事件的發(fā)生將引起自動(dòng)機(jī)狀態(tài)的改變。當(dāng)自動(dòng)機(jī)進(jìn)入終止?fàn)顟B(tài)時(shí)，則代表該終止?fàn)顟B(tài)對(duì)應(yīng)的復(fù)合事件發(fā)生。比較典型的應(yīng)用有ODE[6]和SASE[7]等。

事件樹(shù)，基于語(yǔ)法識(shí)別時(shí)復(fù)合事件表達(dá)式被解析為語(yǔ)法樹(shù)的思想，將復(fù)合事件抽象為相應(yīng)的樹(shù)結(jié)構(gòu)。樹(shù)結(jié)構(gòu)中的葉子節(jié)點(diǎn)表示原子事件，根節(jié)點(diǎn)表示需要監(jiān)測(cè)的復(fù)合事件，中間的各節(jié)點(diǎn)表示待監(jiān)測(cè)復(fù)合事件的子孫事件。只有當(dāng)一個(gè)節(jié)點(diǎn)的子事件都發(fā)生時(shí)，該節(jié)點(diǎn)對(duì)應(yīng)的事件才被監(jiān)測(cè)到。當(dāng)整棵事件樹(shù)中的所有子節(jié)點(diǎn)對(duì)應(yīng)事件均被監(jiān)測(cè)到時(shí)，就表示根節(jié)點(diǎn)對(duì)應(yīng)的復(fù)合事件的發(fā)生。比較典型的應(yīng)用有READY[8]和Zstream[9]等。

事件圖的思想與事件樹(shù)類似，用有向無(wú)環(huán)圖來(lái)表示復(fù)合事件，其中的葉子節(jié)點(diǎn)表示原子事件，非葉子節(jié)點(diǎn)表示事件復(fù)合操作。同一復(fù)合事件的不同實(shí)例，作為不同對(duì)象進(jìn)行處理。事件發(fā)生的消息從葉子節(jié)點(diǎn)向父節(jié)點(diǎn)傳遞，并標(biāo)記沿途節(jié)點(diǎn)。當(dāng)圖中所有節(jié)點(diǎn)均被標(biāo)記時(shí)，該事件圖對(duì)應(yīng)的復(fù)合事件被監(jiān)測(cè)到。比較典型的應(yīng)用有Snoop[10]和EVE[11]等。

目前學(xué)術(shù)界的主流研究方向大多集中于有限狀態(tài)自動(dòng)機(jī)和Petri網(wǎng)。前者的缺點(diǎn)主要在于系統(tǒng)中復(fù)合事件子事件的狀態(tài)數(shù)與子事件個(gè)數(shù)呈指數(shù)相關(guān)。例如，復(fù)合事件E=E1ANDE2ANDE3中每個(gè)子事件都有兩個(gè)狀態(tài)，從而需要8=23個(gè)狀態(tài)來(lái)表示該復(fù)合事件。而后者的缺點(diǎn)則在于表示和執(zhí)行太過(guò)復(fù)雜，處理較為簡(jiǎn)單的復(fù)合事件時(shí)顯得過(guò)于累贅。例如，復(fù)合事件C2 =E3THENE4，用PetriNets表示之后不僅需要多個(gè)對(duì)象來(lái)表示復(fù)合事件的狀態(tài)，還需要一個(gè)轉(zhuǎn)換矩陣來(lái)控制狀態(tài)之間的遷移，極為繁瑣。至于事件圖，該方法在表示復(fù)合事件時(shí)缺乏統(tǒng)一的形式框架，同時(shí)沒(méi)有統(tǒng)一的形式規(guī)范來(lái)描述復(fù)合事件監(jiān)測(cè)過(guò)程。

綜合分析以上幾種方法，事件樹(shù)的表現(xiàn)更為優(yōu)異。因此，本文結(jié)合INMDB的特性，基于事件樹(shù)的結(jié)構(gòu)作出改進(jìn)，提出了一種新型的事件樹(shù)結(jié)構(gòu)——高級(jí)事件樹(shù)AET(AdvancedEventTree)，并在此基礎(chǔ)上設(shè)計(jì)實(shí)現(xiàn)了INMDB中的復(fù)合事件的監(jiān)測(cè)機(jī)制。該監(jiān)測(cè)機(jī)制能夠準(zhǔn)確捕獲常見(jiàn)的幾種復(fù)合事件，具有較好的運(yùn)行效率和較低的空間占用，同時(shí)，又能夠與原有系統(tǒng)很好地耦合。

2　INMDB中的事件模型

信息網(wǎng)模型INM(InformationNetworkModel)是面向?qū)ο蟮恼Z(yǔ)義模型，它將現(xiàn)實(shí)世界的實(shí)體抽象為數(shù)據(jù)庫(kù)中的對(duì)象，具有相同特點(diǎn)的實(shí)體被抽象為類，實(shí)體間的關(guān)系轉(zhuǎn)換為對(duì)象之間的關(guān)系[12]?；贗NM實(shí)現(xiàn)的數(shù)據(jù)庫(kù)管理系統(tǒng)INMDB引入了角色關(guān)系、復(fù)雜關(guān)系、多元關(guān)系以及它們各自的逆關(guān)系等概念，表示對(duì)象之間的關(guān)系時(shí)顯得更為直觀、自然。

2.1原子事件

在INMDB中，事件區(qū)分類型和實(shí)例。按照事件代數(shù)中的約定，事件類型用大寫字母開(kāi)頭，可以包括數(shù)字，如Event、Event1或A等；而事件實(shí)例則用小寫字母開(kāi)頭，末尾加下標(biāo)數(shù)字，如event1、event11和a1等，下標(biāo)數(shù)字用于區(qū)分發(fā)生的先后次序，數(shù)字越小，對(duì)應(yīng)的事件實(shí)例越先發(fā)生。

前文提到，事件可以分為原子事件和復(fù)合事件兩類。INMDB中的原子事件主要包括：

(1) 方法事件。對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)對(duì)象進(jìn)行操作。

(2) 時(shí)序事件。當(dāng)系統(tǒng)時(shí)間運(yùn)行至某一特定時(shí)刻時(shí)觸發(fā)，用絕對(duì)時(shí)間表示。

(3) 抽象事件。與外部環(huán)境之間的通信，由應(yīng)用層的消息或用戶指令顯式觸發(fā)。

抽象事件的發(fā)生具有不確定性，因此，不在事件監(jiān)測(cè)的考慮范圍內(nèi)。時(shí)序事件與此類似，INMDB底層沒(méi)有計(jì)時(shí)機(jī)制，所以該部分通過(guò)開(kāi)放底層接口，由應(yīng)用層計(jì)時(shí)來(lái)實(shí)現(xiàn)。抽象事件和時(shí)序事件的監(jiān)測(cè)都由應(yīng)用層實(shí)現(xiàn)，因此，不在本文的討論范圍之內(nèi)。下文提到的原子事件只包含方法事件。

目前的INMDB包括類、對(duì)象和查詢?nèi)齻€(gè)部分，其中查詢不涉及對(duì)數(shù)據(jù)的修改，因此，原子事件主要與前兩者相關(guān)。

例1對(duì)類的操作：創(chuàng)建一個(gè)“大學(xué)”的類。其中帶“@”的指當(dāng)前類具有的屬性，而不帶“@”的則指當(dāng)前類與其他類之間的關(guān)系，inverse后為該關(guān)系的逆關(guān)系[13]。

createclass大學(xué)[

@建校日期：date,

所在市(N:1)：城市(inverse下轄大學(xué))，

@世界排名：int];

例2對(duì)對(duì)象的操作：創(chuàng)建一個(gè)對(duì)象"教授”，并指定他所指導(dǎo)的學(xué)生和教授的課程以及辦公室電話。

insert教授 張三[

指導(dǎo)學(xué)生：{李四，王五}，

教授課程：數(shù)據(jù)庫(kù)系統(tǒng)

];

例3對(duì)對(duì)象的操作：將對(duì)象“A大學(xué)”中的關(guān)系“地址”的值修改為“B市”。

updateA大學(xué)modify地址:B市;

對(duì)象數(shù)據(jù)庫(kù)中，通過(guò)向指定對(duì)象傳遞消息進(jìn)行底層數(shù)據(jù)的訪問(wèn)與操作。因此，每個(gè)方法事件都與特定的類名、方法名以及操作對(duì)象的名字相關(guān)。與一般對(duì)象數(shù)據(jù)庫(kù)有所區(qū)別的是，雖然INMDB中不同類型方法事件對(duì)應(yīng)的類不同，如例1、例2和例3，分別對(duì)應(yīng)SchmClass類、Instance類和UpdateModify類，但方法名都相同，均為execute()。因此，原子事件定義時(shí)，可以通過(guò)指定類名和操作對(duì)象名，并在此基礎(chǔ)上進(jìn)行封裝，來(lái)唯一標(biāo)識(shí)該事件。

為了便于索引及組成復(fù)合事件，所有事件都具有唯一的事件名。事件名與事件代數(shù)中用于表示事件類型和實(shí)例的標(biāo)識(shí)符不同，不受后者定義時(shí)對(duì)首字母的限制。

事件定義語(yǔ)句的文法描述如下：

CREATEEVENTeventNameEQUeventExpressionSEMICOLON

例4原子事件的定義：定義名為“updateJack”的原子事件，監(jiān)測(cè)對(duì)象“Jack”中的數(shù)據(jù)的修改。

createeventupdateJack=updateJackmodify;

該定義語(yǔ)句經(jīng)過(guò)語(yǔ)法解析之后，可以得到對(duì)應(yīng)的類名UpdateModify和操作對(duì)象名Jack。這些信息封裝在原子事件類primitiveEvent中，存入數(shù)據(jù)庫(kù)底層。針對(duì)原子事件建立兩個(gè)索引，分別以“類名+操作對(duì)象名”和“事件名”為鍵值。

在原子事件updateJack已被存入數(shù)據(jù)庫(kù)底層的前提下，當(dāng)用戶輸入命令“updateJackmodifyage:25;”時(shí)，原子事件監(jiān)測(cè)器會(huì)以操作類名updateModify和操作對(duì)象名Jack為鍵值在數(shù)據(jù)庫(kù)底層進(jìn)行查找，并成功返回。此時(shí)，即表示事件updateJack被監(jiān)測(cè)到。

2.2復(fù)合事件

復(fù)合事件的處理往往會(huì)涉及到時(shí)間范圍的限制。與一般主動(dòng)數(shù)據(jù)庫(kù)不同，INMDB中的時(shí)間間隔由子事件來(lái)標(biāo)識(shí)，而非絕對(duì)時(shí)間點(diǎn)。在需要使用絕對(duì)時(shí)間點(diǎn)的地方，可以先創(chuàng)建對(duì)應(yīng)的原子事件，對(duì)其進(jìn)行封裝。這樣的設(shè)計(jì)使得INMDB在可擴(kuò)展性方面表現(xiàn)更好。

按照事件操作符的不同，復(fù)合事件具體可以分為六類，操作符依據(jù)涉及的子事件個(gè)數(shù)又可分為二元操作符和三元操作符兩大類。

二元操作符對(duì)應(yīng)復(fù)合事件具有如下形式：

Event=Event1OPEvent2

具體分為：

合取:對(duì)應(yīng)操作符為AND，只有當(dāng)Event1、Event2均發(fā)生時(shí)，Event才發(fā)生；

析取:對(duì)應(yīng)操作符為OR，當(dāng)Event1或Event2已發(fā)生時(shí)，Event才發(fā)生；

順序:對(duì)應(yīng)操作符為THEN，只有當(dāng)Event1在Event2之前發(fā)生時(shí)，Event才發(fā)生；

二元事件的時(shí)間范圍默認(rèn)為同一事務(wù)中。

三元操作符對(duì)應(yīng)復(fù)合事件具有如下形式：

Event=OPEvent2inEvent1,Event3

Event1,Event3用于標(biāo)記一段時(shí)間間隔。

具體分為：

截止:對(duì)應(yīng)操作符為ALL，將指定時(shí)間間隔內(nèi)Event2的所有發(fā)生視為一次發(fā)生，并以此觸發(fā)Event的發(fā)生。

歷史:對(duì)應(yīng)操作符為mTIMES，只有當(dāng)Event2在指定時(shí)間間隔內(nèi)發(fā)生m次時(shí)，Event才發(fā)生。

否定:對(duì)應(yīng)操作符為NO，只有當(dāng)Event2在指定時(shí)間間隔內(nèi)沒(méi)有發(fā)生時(shí)，Event才發(fā)生。

復(fù)合事件的狀態(tài)隨子事件狀態(tài)的變化而變化。下面將用一個(gè)例子來(lái)大致闡述該過(guò)程。

例5定義事件instantiationOfA，監(jiān)測(cè)在類A創(chuàng)建之后插入其對(duì)象a的行為。

createeventcreateSchmA=createclassA;

createeventinsertInstA=insertAa;

createeventinstantiationOfA=createSchmAtheninsertInstA;

instantiationOfA為順序復(fù)合事件，該事件雖然是二元復(fù)合事件，卻與三元復(fù)合事件有著相似之處。當(dāng)子事件createSchmA未被監(jiān)測(cè)到時(shí)，無(wú)論另一個(gè)子事件insertInstA是否發(fā)生，均不會(huì)影響其狀態(tài)。而createSchmA發(fā)生后，則instantiationOfA被“激活”，開(kāi)始接受insertInstA狀態(tài)的影響。若insertInstA此時(shí)發(fā)生，則instantiationOfA狀態(tài)發(fā)生變化，標(biāo)識(shí)著該復(fù)合事件被監(jiān)測(cè)到，進(jìn)而觸發(fā)主動(dòng)規(guī)則中其他部分的執(zhí)行以及當(dāng)前事件的父事件狀態(tài)的變化。隨后，兩個(gè)子事件的狀態(tài)被重置，以便監(jiān)測(cè)下一次發(fā)生。

復(fù)合事件與其子事件之間狀態(tài)變化信息的傳遞通過(guò)高級(jí)事件樹(shù)AET(AdvancedEventTree)完成。

3　高級(jí)事件樹(shù)

高級(jí)事件樹(shù)AET的設(shè)計(jì)建立在事件樹(shù)的基礎(chǔ)之上。其構(gòu)建基于對(duì)復(fù)合事件定義語(yǔ)句進(jìn)行的語(yǔ)法解析。為了方便對(duì)復(fù)合事件進(jìn)行詞法分析和語(yǔ)法解析以獲得必要的信息，建立事件表達(dá)式的文法描述如下：

eventExpression:primitiveEventExpression

|compositeEventExpression

compositeEventExpression:binaryEventExpression

|ternaryEventExpression

binaryEventExpression:eventNameANDeventName

|eventNameOReventName

|eventNameTHENeventName

ternaryEventExpression:ALLeventNameINeventNameCOMMAeventName

|INT_STRTIMESeventNameINeventNameCOMMAeventName

|NOeventNameINeventNameCOMMAeventName

binaryEventExpression表示二元復(fù)合事件，ternaryEventExpression表示三元復(fù)合事件。INT_STR表示整型常量，eventName對(duì)應(yīng)事件名。

3.1節(jié)點(diǎn)

AET中的節(jié)點(diǎn)分為葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)兩類。節(jié)點(diǎn)與事件相對(duì)應(yīng)，在INMDB中存儲(chǔ)時(shí)以事件名為索引。事件可以與多條主動(dòng)規(guī)則相關(guān)，也可以作為其他復(fù)合事件的子事件。作為子事件時(shí)，事件的狀態(tài)將會(huì)對(duì)作為父事件的復(fù)合事件產(chǎn)生影響。對(duì)于順序復(fù)合事件和三元復(fù)合事件，只有特定位置的子事件狀態(tài)改變后，當(dāng)前復(fù)合事件的狀態(tài)才會(huì)發(fā)生變化。因此，存儲(chǔ)相關(guān)復(fù)合事件時(shí)，需要依據(jù)當(dāng)前事件的狀態(tài)是否會(huì)對(duì)其造成影響而分類，分別設(shè)為activeComEvents和passiveComEvents。同時(shí)，還需要保存當(dāng)前事件在相關(guān)復(fù)合事件中的位置。

因此，作為基類的Event類設(shè)計(jì)如下：

classEvent{

private:

stringeventName;

mapactiveComEvents;

//狀態(tài)會(huì)受當(dāng)前事件影響

mappassiveComEvents;

//狀態(tài)不受當(dāng)前事件影響

vectorrelatedRules;

};

與事件樹(shù)相同，AET中的葉子節(jié)點(diǎn)表示原子事件。不同之處在于，中間節(jié)點(diǎn)不再只表示待監(jiān)測(cè)復(fù)合事件的子孫事件，而可以表示其他待監(jiān)測(cè)復(fù)合事件。通過(guò)按事件名索引，AET將所有相關(guān)的復(fù)合事件合并在同一顆樹(shù)中，而不是每個(gè)復(fù)合事件都單獨(dú)占用一顆事件樹(shù)。

設(shè)有以下兩個(gè)復(fù)合事件表達(dá)式：

(1)A=BANDC

(2)C=DORE

用一般的事件樹(shù)表示，如圖1所示。

圖1　一般事件樹(shù)表示

用AET表示，如圖2所示。

圖2　AET表示

因此，在復(fù)合事件表達(dá)式相同時(shí)，AET的空間占用比一般的事件樹(shù)更少。

原子事件中封裝有對(duì)應(yīng)數(shù)據(jù)操作的類名和操作對(duì)象名。例如，createclassA[]; 操作對(duì)應(yīng)的類為SchmClassPre，而對(duì)應(yīng)的操作對(duì)象名為A。因此，AET中的葉子節(jié)點(diǎn)設(shè)計(jì)如下：

classPrimitiveEvent{

private:

stringoperationType;

stringoperationName;

};

其中，operationType為事件對(duì)應(yīng)的操作類型，而operationName為事件對(duì)應(yīng)的操作對(duì)象名。

依據(jù)文法描述，復(fù)合事件可以分為二元復(fù)合事件和三元復(fù)合事件兩種。對(duì)于二元復(fù)合事件，其狀態(tài)取決于兩個(gè)子事件的狀態(tài)。同時(shí)，子事件對(duì)齊影響方式取決于二元復(fù)合事件的類型。因此，二元復(fù)合事件類BinaryEvent設(shè)計(jì)如下：

classBinaryEvent:publicEvent{

private:

stringeventType;

boolleftStatus;

boolrightStatus;

stringleftEvent;

stringrightEvent;

};

其中，eventType為事件類型，leftEvent和rightEvent分別為左右子事件名。

考慮到三元復(fù)合事件與二元復(fù)合事件中的順序復(fù)合事件有所類似，不妨將事件表達(dá)式E=OPE2inE1,E3中的E2視為待監(jiān)測(cè)事件。截止、歷史和否定復(fù)合事件均需要記錄待監(jiān)測(cè)事件的發(fā)生次數(shù)，因此，三元復(fù)合事件類TernaryEvent設(shè)計(jì)如下：

classTernaryEvent:publicBinaryEvent{

private:

intmonitoredEventCount;

inttargetValue;

stringmonitoredEvent;

};

monitoredEventCount記錄待監(jiān)測(cè)事件的發(fā)生次數(shù)。targetValue保存待監(jiān)測(cè)事件的期望發(fā)生次數(shù)，在截止復(fù)合事件中默認(rèn)值為-1，歷史復(fù)合事件中與定義語(yǔ)句中相同，而否定復(fù)合事件中其值為0。

3.2邊

依據(jù)3.1節(jié)中Event類的描述，AET中的邊對(duì)應(yīng)著子事件指向相關(guān)復(fù)合事件的指針。子事件的狀態(tài)變化通過(guò)該指針進(jìn)行傳遞，表現(xiàn)在AET中便是狀態(tài)變化的消息沿葉子節(jié)點(diǎn)一直向上傳遞。

3.3AET的構(gòu)建

AET的構(gòu)建過(guò)程，主要分為事件表達(dá)式解析過(guò)程和預(yù)處理過(guò)程。前者主要目的在于通過(guò)事件表達(dá)式的語(yǔ)法解析，生成對(duì)應(yīng)的事件類；而后者的主要目的在于建立起新的事件與數(shù)據(jù)庫(kù)中已有事件之間的關(guān)系。

在INMDB中，事件定義語(yǔ)句具有如下形式：

createeventeventName=eventExpression;

語(yǔ)法解析過(guò)程中，對(duì)該定義語(yǔ)句進(jìn)行處理，可以獲得當(dāng)前事件的事件名。對(duì)于復(fù)合事件，還可獲得其子事件的事件名。結(jié)合前文中事件表達(dá)式的文法描述，便可構(gòu)建出相應(yīng)的Event類。

在預(yù)處理過(guò)程中，借助INMDB底層提供的查詢接口[14]，按照子事件名進(jìn)行查找，找到復(fù)合事件對(duì)應(yīng)的子事件，并依據(jù)復(fù)合事件的類型修改子事件中的activeComEvents或者passiveComEvents，從而將新的復(fù)合事件添加到INMDB中。該過(guò)程的AET表示，如圖3、圖4所示。

圖3　AET構(gòu)建前

圖4　AET構(gòu)建后

4　復(fù)合事件監(jiān)測(cè)算法

如第3節(jié)所述，事件定義語(yǔ)句中所包含的信息經(jīng)過(guò)語(yǔ)法解析后，用于構(gòu)造對(duì)應(yīng)的Event類，并存入數(shù)據(jù)庫(kù)底層。INMDB中的所有Event類彼此關(guān)聯(lián)，形成一棵完整的AET。PrimitiveEvent類是它的葉子節(jié)點(diǎn)，而B(niǎo)inaryEvent類及其子類對(duì)應(yīng)的事件則通過(guò)共同的子事件相關(guān)聯(lián)，作為中間節(jié)點(diǎn)，并且其中有一部分會(huì)成為AET的根節(jié)點(diǎn)。

當(dāng)數(shù)據(jù)操作命令輸入時(shí)，可以通過(guò)語(yǔ)法解析獲取操作類型對(duì)應(yīng)的類名operationType和操作對(duì)象名operationName。通過(guò)在數(shù)據(jù)庫(kù)中進(jìn)行查找，可以確定是否存在對(duì)應(yīng)的原子事件。如果能找到，則證明原子事件被監(jiān)測(cè)到。

此后的處理方式與復(fù)合事件被監(jiān)測(cè)到之后相同，即，將事件發(fā)生的消息傳遞給所有相關(guān)的父事件，即activeComEvents，并根據(jù)在父事件中的位置而做出不同的處理。設(shè)該部分對(duì)應(yīng)函數(shù)為invoke()，用算法描述如下：

Input：Event中的activeComEvents

Output：無(wú)

FORactiveComEvents中的每個(gè)activeComEvent

//即對(duì)

IFactiveComEvent.second==left:

//置對(duì)應(yīng)的左事件狀態(tài)為true

activeComEvent.first.leftStatus=true

ENDIF

IFactiveComEvent.second==right

//置對(duì)應(yīng)的右事件狀態(tài)為true

activeComEvent.first.rightStatus=true

ENDIF

IFactiveComEvent.second==middle

//將待監(jiān)測(cè)事件的計(jì)數(shù)增1

++activeComEvent.first.monitoredEventCount

ENDIF

ENDFOR

復(fù)合事件的監(jiān)測(cè)建立在子事件被監(jiān)測(cè)到的基礎(chǔ)之上，而不同類型的復(fù)合事件的監(jiān)測(cè)算法又有所不同。在介紹復(fù)合事件監(jiān)測(cè)算法前，引入兩個(gè)輔助函數(shù)，activateIn(subEvent)和deactivateIn(subEvent)。前者的功能為將當(dāng)前復(fù)合事件從指定子事件的passiveComEvents轉(zhuǎn)移到activeComEvents中。后者反之。

當(dāng)復(fù)合事件被監(jiān)測(cè)到之后，用于表示其子事件狀態(tài)的leftStatus、rightStatus等均被重置，以便等待下一次發(fā)生。

4.1二元復(fù)合事件

二元復(fù)合事件可以分為三類：合取復(fù)合事件、析取復(fù)合事件以及順序復(fù)合事件。

依據(jù)2.2節(jié)中的定義，當(dāng)且僅當(dāng)左右子樹(shù)對(duì)應(yīng)的事件均被監(jiān)測(cè)到時(shí)，合取復(fù)合事件才被監(jiān)測(cè)到；而只要左右子樹(shù)對(duì)應(yīng)的事件有一個(gè)被監(jiān)測(cè)到，則析取復(fù)合事件就被監(jiān)測(cè)到。

順序復(fù)合事件相對(duì)較為復(fù)雜。對(duì)于形如Event1THENEvent2的順序復(fù)合事件，只有兩個(gè)子事件按順序發(fā)生時(shí)，順序復(fù)合事件才被監(jiān)測(cè)到。即，若Event1未發(fā)生，則Event2的發(fā)生對(duì)復(fù)合事件而言沒(méi)有意義。該狀態(tài)可以通過(guò)將順序復(fù)合事件置于Event2對(duì)應(yīng)事件類的成員passiveComEvents中來(lái)表示。當(dāng)且僅當(dāng)Event1發(fā)生之后，Event2才被“激活”，從而能夠影響復(fù)合事件的狀態(tài)。相對(duì)應(yīng)地，通過(guò)調(diào)用activateIn(Event2)，順序復(fù)合事件從passiveComEvents轉(zhuǎn)移到activeComEvents中。

根據(jù)上述分析，可以設(shè)計(jì)出二元復(fù)合事件的監(jiān)測(cè)算法如下：

Input：BinaryEvent

Output: 無(wú)

SWITCHeventType:

CASEconjunction:

IFleftStatus&&rightStatus:

當(dāng)前復(fù)合事件被監(jiān)測(cè)到

invoke(activeComEvents)

//重置子事件狀態(tài)，等待下一次發(fā)生

leftStatus=false

rightStatus=false

ENDIF

CASEdisjunction:

IFleftStatus||rightStatus

當(dāng)前復(fù)合事件被監(jiān)測(cè)到

invoke(activeComEvents)

//重置子事件狀態(tài)，等待下一次發(fā)生

leftStatus=false

rightStatus=false

ENDIF

CASEsequence:

IFleftStaus

//在右子樹(shù)中激活

activateIn(rightEvent)

ENDIF

IFrightStatus

當(dāng)前復(fù)合事件被監(jiān)測(cè)到

invoke(activeComEvents)

//重置子事件狀態(tài)，等待下一次發(fā)生

leftStatus=false

rightStatus=false

deactivateIn(rightEvent)

ENDIF

4.2三元復(fù)合事件

三元復(fù)合事件主要用于監(jiān)測(cè)指定時(shí)間間隔內(nèi)，特定事件的發(fā)生次數(shù)。其左右子事件分別標(biāo)記這段時(shí)間間隔的開(kāi)始與結(jié)束，而三元復(fù)合事件類中的monitoredEvent成員則對(duì)應(yīng)特定事件。因此，只有當(dāng)左子事件發(fā)生之后，待監(jiān)測(cè)事件與右子事件才被“激活”。同樣，該步驟用activateIn()函數(shù)的調(diào)用來(lái)表示。

依據(jù)monitoredEvent發(fā)生次數(shù)的不同，三元復(fù)合事件可以分為截止復(fù)合事件、歷史復(fù)合事件和否定復(fù)合事件三類。指定時(shí)間間隔內(nèi)只要monitoredEvent發(fā)生，截止復(fù)合事件就被監(jiān)測(cè)到；反之，若monitoredEvent沒(méi)有發(fā)生，則否定復(fù)合事件被監(jiān)測(cè)到。而只有當(dāng)monitoredEvent發(fā)生指定次數(shù)時(shí)，歷史復(fù)合事件才會(huì)被監(jiān)測(cè)到。

三者均需要統(tǒng)計(jì)monitoredEvent的發(fā)生次數(shù)，用統(tǒng)一的成員變量monitoredEventCount來(lái)保存該值。特別地，歷史復(fù)合事件中還需用targetValue來(lái)保存指定的monitoredEvent發(fā)生次數(shù)。

根據(jù)上述分析，可以設(shè)計(jì)出三元復(fù)合事件的監(jiān)測(cè)算法如下：

Input:TernaryEvent

Outpu: 無(wú)

IFleftStatus

activateIn(monitoredEvent)

activateIn(rightEvent)

ENDIF

IFrightStatus

SWITCHeventType

CASEclosure

IFmonitoredEventCount> 0

當(dāng)前復(fù)合事件被監(jiān)測(cè)到

invoke(activateComEvents)

ENDIF

CASEhistory

CASEnot

IFmonitoredEventCount==targetValue

當(dāng)前復(fù)合事件被監(jiān)測(cè)到

invoke(activateComEvents)

ENDIF

//重置子事件狀態(tài)，等待下一次發(fā)生

leftStatus=false

monitoredEventCount= 0

rightStatus=false

deactivateIn(monitoredEvent)

deactivateIn(rightEvent)

ENDIF

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

目前的主流研究方向集中在有限狀態(tài)自動(dòng)機(jī)和Petri網(wǎng)上，因此，為了測(cè)試AET在復(fù)合事件監(jiān)測(cè)方面的性能，本文使用INMDB與SAMOS(采用Petri網(wǎng))和ODE(采用狀態(tài)機(jī))進(jìn)行比較。測(cè)試指標(biāo)為處理相同復(fù)合事件定義語(yǔ)句所需要的時(shí)間。本文中用到的測(cè)試環(huán)境為Intel(R)Xeon(R)CPUE5-2407v2 @2.40GHz，memory3GB，RedHatEnterpriseLinuxServerrelease6.4 (Santiago)。

5.1數(shù)據(jù)與實(shí)驗(yàn)設(shè)計(jì)

我們通過(guò)批量處理復(fù)合事件定義語(yǔ)句來(lái)計(jì)算其平均時(shí)間。因?yàn)閺?fù)合事件的處理極為耗時(shí)，實(shí)驗(yàn)主要測(cè)試了百、千、萬(wàn)級(jí)別的復(fù)合事件定義語(yǔ)句的處理時(shí)間。該時(shí)間取5次處理的平均值。每次處理前，數(shù)據(jù)庫(kù)中都只有必要的原子事件。

5.2實(shí)驗(yàn)結(jié)果

表1和圖5分別記錄了不同數(shù)據(jù)庫(kù)處理相同數(shù)量的復(fù)合事件定義語(yǔ)句的總時(shí)間和平均時(shí)間。

表1　復(fù)合事件定義語(yǔ)句總處理時(shí)間　　　單位:s

圖5　復(fù)合事件平均處理時(shí)間/ms

5.3結(jié)果分析

表1中的數(shù)據(jù)為多次實(shí)驗(yàn)的平均值，最大限度地排除了偶然誤差。從數(shù)據(jù)來(lái)看，處理100條復(fù)合事件時(shí)，INMDB只需2.451s，而SAMOS則需要7.193s，ODE更是耗時(shí)達(dá)14.387s。類似的情況也出現(xiàn)在處理千、萬(wàn)級(jí)別數(shù)量的復(fù)合事件定義語(yǔ)句時(shí)。因此，可以認(rèn)為，處理相同數(shù)量的復(fù)合事件定義語(yǔ)句，INMDB耗時(shí)比SAMOS和ODE更少。將復(fù)合事件定義語(yǔ)句總處理時(shí)間轉(zhuǎn)換為平均處理時(shí)間，用圖5中的柱狀圖表示，可以直觀地看出三者之間的性能差異。

綜上所述，實(shí)驗(yàn)結(jié)果表明，單位時(shí)間內(nèi)，INMDB能處理的復(fù)合事件語(yǔ)句數(shù)量比SAMOS和ODE更多，充分體現(xiàn)了AET在復(fù)合事件監(jiān)測(cè)方面的優(yōu)越性。

6　結(jié)　語(yǔ)

本文綜合分析對(duì)比了各種主流復(fù)合事件監(jiān)測(cè)算法之后，選擇了事件樹(shù)作為基礎(chǔ)，提出了AET的概念，并以此為模型在INMDB現(xiàn)有基礎(chǔ)之上設(shè)計(jì)并實(shí)現(xiàn)了復(fù)合事件監(jiān)測(cè)機(jī)制。經(jīng)過(guò)實(shí)驗(yàn)對(duì)比，該模型在單位時(shí)間內(nèi)處理復(fù)合事件的效率比主流的有限狀態(tài)自動(dòng)機(jī)和Petri網(wǎng)更為出色。

事件監(jiān)測(cè)是主動(dòng)規(guī)則中最重要的一部分，而復(fù)合事件監(jiān)測(cè)更是重中之重。該部分的順利完成為INMDB中整個(gè)主動(dòng)機(jī)制的實(shí)現(xiàn)打下了堅(jiān)實(shí)的基礎(chǔ)。放眼未來(lái)，分布式是數(shù)據(jù)庫(kù)發(fā)展的主流。目前的復(fù)合事件監(jiān)測(cè)機(jī)制主要針對(duì)單機(jī)環(huán)境，因此，下一步的工作是在保持單機(jī)環(huán)境下事件處理優(yōu)勢(shì)的前提下，實(shí)現(xiàn)分布式環(huán)境下的復(fù)合事件監(jiān)測(cè)。

[1]PatonNW,DíazO.Activedatabasesystems[J].ACMComputingSurveys(CSUR),1999,31(1):63-103.

[2] 郝忠孝.主動(dòng)數(shù)據(jù)庫(kù)系統(tǒng)理論基礎(chǔ)[M].北京:科學(xué)出版社,2009.

[3] 蔡學(xué)鏞.輕松理解復(fù)合事件處理[J].程序員,2010(6):112-113.

[4]GatziuS,DittrichKR.SAMOS:Anactiveobject-orienteddatabasesystem[J].IEEEDataEng.Bull.,1992,15(1-4):23-26.

[5]AlShaerE,AbdelWahabH,MalyK.Hifi:Anewmonitoringarchitecturefordistributedsystemsmanagement[C]//DistributedComputingSystems,1999.Proceedings.19thIEEEInternationalConferenceon.IEEE,1999:171-178.

[6]GehaniNH,JagadishHV.OdeasanActiveDatabase:ConstraintsandTriggers[C]//Proceedingsofthe17thInternationalConferenceonVeryLargeDataBases,Barcelona,Catalonia,Spain, 1991.SanFrancisco,California,USA:MorganKaufmann,1991:327-336.

[7]AgrawalJ,DiaoY,GyllstromD,etal.Efficientpatternmatchingovereventstreams[C]//Proceedingsofthe2008ACMSIGMODinternationalconferenceonManagementofdata.ACM,2008:147-160.

[8]GruberRE,KrishnamurthyB,PanagosE.ThearchitectureoftheREADYeventnotificationservice[C]//Proceedingsofthe19thInternationalConferenceonDistributedComputingSystems,Austin,TX,USA,1999.Washington,DC,USA:IEEE,1999:0108.

[9]MeiY,MaddenS.Zstream:acost-basedqueryprocessorforadaptivelydetectingcompositeevents[C]//Proceedingsofthe2009ACMSIGMODInternationalConferenceonManagementofdata.ACM,2009:193-206.

[10]ChakravarthyS,MishraD.Snoop:Anexpressiveeventspecificationlanguageforactivedatabases[J].Data&KnowledgeEngineering,1994,14(1):1-26.

[11]GeppertA,TombrosD.Event-baseddistributedworkflowexecutionwithEVE[C]//Middleware’98.SpringerLondon,1998:427-442.

[12]LiuM,HuJ.Informationnetworkingmodel[M]//ConceptualModeling-ER2009.SpringerBerlinHeidelberg,2009:131-144.

[13] 徐倩,胡婕,劉夢(mèng)赤.復(fù)雜語(yǔ)義關(guān)系的描述與操作[J].計(jì)算機(jī)科學(xué)與探索,2014,8(12):1432-1441.

[14] 金錚,劉夢(mèng)赤,胡婕.信息網(wǎng)數(shù)據(jù)庫(kù)管理系統(tǒng)的查詢優(yōu)化[J].計(jì)算機(jī)科學(xué)與探索,2015,9(3):300-309.

DESIGNANDIMPLEMENTATIONOFCOMPOSITEEVENTSDETECTIONMECHANISMININMDB

HeHongdaLiuMengchi

(SchoolofComputer,WuhanUniversity,Wuhan430072,Hubei,China)

Formostactivedatabasesystem,it’sdifficulttodetectcompositeevent.ThepaperintroducesthecompositeeventdetectingmechanisminINMDBmanagementsystem,describesindetailtheideaofusingeventtreemodeltodetectcompositeevents,andprovidesspecificalgorithmicimplementationaswell.Accordingtotheanalysis,thisalgorithmisbetterthanfiniteautomatonandPetrinets,whicharemuchmorecommon,inbothrunningefficiencyandmemoryoccupation.

Informationnetworkmodel(INM)ActivedatabasesCompositeeventsdetectionEventtree

2015-07-20。賀宏達(dá)，碩士，主研領(lǐng)域：數(shù)據(jù)庫(kù)技術(shù)。劉夢(mèng)赤，教授。

TP

ADOI:10.3969/j.issn.1000-386x.2016.10.010