基于擴展Petri網(wǎng)的ECA規(guī)則集表示及終止性分析

張立臣，王小明，竇文陽

（陜西師范大學(xué) 計算機科學(xué)學(xué)院，陜西 西安 710062）

1 引言

基于觸發(fā)機制的ECA(event-condition-action)規(guī)則能夠描述主動知識，是人工智能和知識表示處理領(lǐng)域的研究熱點[1]。應(yīng)用ECA規(guī)則[2,3]和ECA規(guī)則集的動態(tài)行為特性(如可終止性、匯流性等)分析[4～10]得到研究人員的高度關(guān)注。如果從任何初始狀態(tài)下開始，ECA規(guī)則集的執(zhí)行過程都會在有限步之內(nèi)停止，那么稱ECA規(guī)則集是可終止的[4]。但是，由于ECA規(guī)則集之間存在復(fù)雜的規(guī)則結(jié)構(gòu)和規(guī)則特性，如復(fù)合事件(composed event)、復(fù)合條件(composed condition)、觸發(fā)關(guān)系(triggering relation)、活化關(guān)系(activating relation)和墮化關(guān)系(deactivating relation)等，導(dǎo)致 ECA規(guī)則集的可終止性分析問題十分困難，在考慮所有規(guī)則特性的情況下，ECA規(guī)則集的可終止性分析問題是不可判定的[5]，因此，研究人員通常只考慮部分結(jié)構(gòu)特性。

截至目前，在 ECA規(guī)則集可終止性分析方法中，基于圖理論和基于Petri網(wǎng)的分析方法是主要的2類方法。觸發(fā)圖(TG, triggering graph)分析方法只考慮了規(guī)則間的觸發(fā)關(guān)系[6]，而活化圖(AG, activating graph)的分析方法針對的是活化關(guān)系[7]。Baralis提出了結(jié)合TG圖和AG圖的終止性分析方法[8]，在此基礎(chǔ)上，Montesi定義了進(jìn)化圖[9]，郝忠孝等提出了含環(huán)觸發(fā)圖的分析方法[10]。在基于圖理論的分析方法中，規(guī)則用圖的節(jié)點表示，規(guī)則間觸發(fā)、活化或墮化關(guān)系則用圖的有向邊描述。若圖中存在一條回路，則表明所對應(yīng)的 ECA規(guī)則集是不可終止的。但是簡單的圖形并不能體現(xiàn) ECA規(guī)則之間的細(xì)粒度規(guī)則特性(如復(fù)合事件、規(guī)則耦合模式等)，導(dǎo)致了基于圖理論的終止性分析方法的分析粒度較粗，準(zhǔn)確性較差。

Petri網(wǎng)是動態(tài)系統(tǒng)建模和行為分析方面的形式化工具[2,3,11]，被廣泛應(yīng)用于 ECA規(guī)則集的可終止性分析領(lǐng)域[12～15]。Latifa[12]基于 Petri網(wǎng)分析含優(yōu)先級的 ECA規(guī)則集的終止性，但是沒有考慮復(fù)合事件和復(fù)合條件等結(jié)構(gòu)特性。Bostan-Korpeoglu[14]基于模糊有色Petri網(wǎng)分析模糊ECA規(guī)則集的可終止性，但只考慮了復(fù)合事件。

綜上所述，現(xiàn)有 ECA規(guī)則集的可終止性分析方法只考慮 ECA規(guī)則之間的部分結(jié)構(gòu)特性，導(dǎo)致算法判定的準(zhǔn)確性較低。為了提高 ECA規(guī)則集的可終止性判定算法準(zhǔn)確性，筆者首先提出可有效描述 ECA規(guī)則各種規(guī)則特性的擴展 Petri網(wǎng)(EPN,extended Petri net)模型，然后在充分利用EPN所包含的規(guī)則結(jié)構(gòu)信息的基礎(chǔ)上，綜合分析 ECA規(guī)則集的可終止性，并提出了相應(yīng)的可終止性判定算法，最后，通過理論分析和實驗仿真對本文的算法與傳統(tǒng)可終止判定算法進(jìn)行了比較。

2 ECA規(guī)則集的EPN模型

2.1 模型設(shè)計

ECA規(guī)則的事件分為原子事件和復(fù)合事件，條件分為原子條件和復(fù)合條件。為簡單起見，本文約定，ECA規(guī)則的復(fù)合事件只能通過“”∧運算符將原子事件或原子事件的“逆事件”復(fù)合起來；復(fù)合條件只能通過“”∧運算把原子條件或原子條件的否定復(fù)合而來。在此約定下，本文提出了一種可有效表示ECA規(guī)則集的擴展Petri網(wǎng)模型——EPN模型。

定義1 描述ECA規(guī)則集的EPN是一個9元組，EPN=(P, T, F, C, E, W, G, CF, M0)。

1) P 是庫所的有限集，P=Pe∪Pt∪Pv∪Pn∪Pc，其中，Pe是事件庫所集，Pt是處于觸發(fā)態(tài)的庫所集，Pv是處于激活態(tài)的庫所集，Pn是動作庫所集，Pc是條件庫所集。Pe、Pt、Pv、Pn和Pc兩兩不相交。

2) T是變遷的有限集，Tt?T是觸發(fā)變遷集，Tv?T是激活變遷集，Tn?T是執(zhí)行變遷集。Tt、Tv和Tn兩兩不相交。

3) F是流關(guān)系的有限集， F = Fi∪ Fo，其中，F(xiàn)i? { (p, t)|p ∈ P , t ∈ T }是 輸 入 弧 集 ， Fo?{(t,p)| p∈ P , t ∈ T }是輸出弧集；Fi=Fn∪Fh∪Ft，F(xiàn)n、Fh和Ft分別是一般弧集(normal arcs)、抑制弧集(inhibitor arcs)和檢測弧集(test arcs)，并且 Fn、Fh和 Ft兩兩不相交。

4) C是顏色的非空有限集；CF： P→CM是顏色映射函數(shù)，其中，CM是C上的多重集(multiset)。

5) E： F→ expression 是弧函數(shù)；G： T→ bool是變遷門函數(shù)(guard function)。

6) W： P→N+是庫所容量函數(shù)，對?p∈P, 都有W(p)∈N+，N+是自然數(shù)集合，表示庫所p的最大容量。

7) M0： P→CM是初始標(biāo)記函數(shù)，對網(wǎng)中庫所標(biāo)記。?p∈P，M(p)表示p的標(biāo)識，p中的token以二元組(p, c)表示，其中，c∈C表示token顏色。

定義2 在EPN中，變遷t 的前集用?t 表示，?t = {p|(p, t)∈F, p∈P}。

1) 若對于?p∈?t，都有 p不包含 token且(p,t)∈Fh，或者p 中至少包含E(p,t)個token，并且(p, t)?Fh，則稱t是激活的(enabled)。

2) 若t 是激活的，且G(t)返回true，則稱t為可發(fā)生的(firable)。

3) 若t為可發(fā)生的，則t發(fā)生后，網(wǎng)中的標(biāo)識由式(1)確定。

帶檢測弧和抑制弧的有色 Petri網(wǎng)在表達(dá)能力上是與傳統(tǒng)有色 Petri網(wǎng)是等價的[16]，因此，檢測弧和抑制弧并沒有降低EPN的分析能力，并且檢測弧和抑制弧使得EPN比標(biāo)準(zhǔn)有色Petri網(wǎng)更為簡潔。

2.2 EPN的描述能力

EPN不僅可以描述復(fù)合事件和復(fù)合條件，而且可以描述 ECA規(guī)則中事件消耗模式(event consumption mode)。

2.2.1 對觸發(fā)變遷的描述

ECA規(guī)則的每個原子事件在EPN中都對應(yīng)一個原子事件庫所。普通原子事件在EPN中對應(yīng)的事件庫所與觸發(fā)變遷之間的弧是普通弧，而原子事件的“逆事件”對應(yīng)的弧則為抑制弧。設(shè)一條ECA規(guī)則r的事件為e1∧e2∧?e3，變遷t是r在EPN中對應(yīng)的觸發(fā)變遷，庫所p是r處于觸發(fā)態(tài)的庫所。圖1是觸發(fā)變遷t發(fā)生過程，圖1(a)是t發(fā)生前EPN狀態(tài)，圖1(b)是t發(fā)生后EPN狀態(tài)。t發(fā)生后，一個token將流入到庫所p，其含義是規(guī)則r被觸發(fā)。

圖1 觸發(fā)變遷的發(fā)生過程

2.2.2 對激活變遷的描述

ECA規(guī)則的每個原子條件在EPN中都對應(yīng)一個條件庫所。普通原子條件所對應(yīng)的條件庫所與規(guī)則的激活變遷之間的弧是檢測弧，而否定形式的原子條件所對應(yīng)的條件庫所與激活變遷之間的弧是抑制弧。設(shè)一條ECA規(guī)則r的條件為c1∧?c2，變遷t為激活變遷，庫所p和p'分別為處于觸發(fā)態(tài)和激活態(tài)的庫所。激活變遷t的發(fā)生過程如圖2所示，其中，圖2(a)是t發(fā)生前的EPN狀態(tài)，圖2(b)是t發(fā)生后的 EPN狀態(tài)。t發(fā)生后，p'中將產(chǎn)生一個token，此時規(guī)則r被激活。

圖2 激活變遷的發(fā)生過程

2.2.3 對執(zhí)行變遷的描述

通常情況下，一條 ECA規(guī)則執(zhí)行后不會產(chǎn)生事件，也不會改變條件，此時該規(guī)則在EPN所對應(yīng)的執(zhí)行過程如圖3所示，其中，庫所p和p'分別為處于激活態(tài)的庫所和動作庫所。

圖3 執(zhí)行變遷的發(fā)生過程

2.2.4 對規(guī)則動作改變條件情形的描述

如果一條ECA規(guī)則r改變原子條件，那么EPN中r對應(yīng)的執(zhí)行變遷t的發(fā)生過程如圖4所示，其中，庫所p和pc分別為處于激活態(tài)的庫所和條件c

對應(yīng)的庫所。

圖4 3種改變條件的情形對應(yīng)的EPN

1) 情形1：使條件c為真

如圖4(a)所示，在網(wǎng)中添加一個動作庫所p'和一個變遷t'，(pc, t')為抑制弧。t發(fā)生后，如果c為真，則t'將不發(fā)生，此時c仍為真；否則t'將發(fā)生，將c改為真。

2) 情形2：使條件c為假

如圖4(b)所示，在網(wǎng)中添加一個動作庫所p'和一個變遷t'，(pc, t')為一般弧。t發(fā)生后，如果c為假，則t'將不發(fā)生，此時c仍為假；否則t'將發(fā)生，將c改為假。

3) 情形3：使條件c取反

如圖4(c)所示，在網(wǎng)中添加一個動作庫所p'和2個變遷t'和t''，(pc, t')和(pc, t'')分別為一般弧和抑制弧。t發(fā)生后，如果c為真，則t'將發(fā)生，將c改為假；否則變遷t''將發(fā)生，將c改為真。

2.2.5 對事件消耗模式的描述

ECA規(guī)則的事件消耗模式包括消耗范圍(記為cs)和消耗時間(記為 ct)2種屬性[17]，其中，消耗范圍表示系統(tǒng)對觸發(fā)事件的處理方式，具有3種取值：不消耗(記為0)、局部消耗(記為1)和全局消耗(記為2)；消耗時間屬性有2種取值：條件評價后(記為0)和規(guī)則動作執(zhí)行后(記為1)。若ct=0，則不考慮條件評價的結(jié)果，而是根據(jù)cs的取值處理觸發(fā)事件；若ct=1，則需考慮規(guī)則條件評價結(jié)果。如果條件評價結(jié)果為假，則不處理觸發(fā)事件；否則，將根據(jù)cs的取值處理觸發(fā)事件。為了在EPN中有效描述事件消耗模式，本文約定，對于一個事件庫所 p，其中的token標(biāo)識(p, c)中c取值為規(guī)則標(biāo)識，含義是該token能夠觸發(fā)規(guī)則標(biāo)識為c的ECA規(guī)則。針對不同的事件消耗模式，EPN的具體結(jié)構(gòu)如下：(設(shè)事件 e是可以觸發(fā)規(guī)則集{rj, rj+1, …, rk}，p是對應(yīng)的事件庫所)

1) 消耗范圍是不消耗(cs=0)

此時，p中有一個標(biāo)記為(p, n)的token，符號n表示 e的事件消耗范圍是不消耗；p到規(guī)則集{rj,rj+1,…, rk}所對應(yīng)的每一個觸發(fā)變遷均有一條輸入弧。圖 5是事件消耗時間為“條件評價后”(ct=0)的EPN結(jié)構(gòu)，t2是激活變遷。設(shè)r的條件為c1∧?c2。pc1和 pc2分別與變遷 t3和 t4連接，其中，( pc1, t2)和( pc2, t4)為檢測弧，( pc1, t3)和( pc2, t2)為抑制弧。r被觸發(fā)后，3個變遷t2、t3和t4中有且僅有一個發(fā)生，此時，庫所p中都將產(chǎn)生一個token，其含義是當(dāng)評估完條件后，觸發(fā)事件e都將重新產(chǎn)生，而不論評估結(jié)果如何。

圖5 觸發(fā)事件的消耗范圍為“不消耗”且ct=0時的EPN

圖 6為事件消耗時間為“執(zhí)行動作后”(ct=1)的EPN，t2和t3分別是激活變遷和執(zhí)行變遷。只有當(dāng)t3發(fā)生時，e才會被重新產(chǎn)生，其含義是在條件的評價結(jié)果為真時，不會被消耗觸發(fā)事件，反之，若條件檢測結(jié)果為假，則消耗觸發(fā)事件。

圖6 觸發(fā)事件的消耗范圍為“不消耗”且ct=1時的EPN

2) 消耗范圍是局部消耗(cs=1)

此時，事件庫所p中有k-j+1個token，標(biāo)記分別為(p, rj), (p, rj+1), …, (p, rk)。庫所 p到{rj,rj+1, …, rk}所對應(yīng)的每個觸發(fā)變遷均有一條輸入弧，且弧上的表達(dá)式為所指向的 ECA規(guī)則標(biāo)識。由于每個token根據(jù)其顏色只觸發(fā)其中一條規(guī)則，因此，局部消耗事件在消耗時間為“條件評價后”與 “執(zhí)行動作后”的EPN結(jié)構(gòu)相同。圖7為局部消耗模式的EPN，設(shè)規(guī)則r1的條件為c1?c2, t2和t3分別是激活變遷和執(zhí)行變遷，不論t2是否發(fā)生，觸發(fā)事件都將被消耗。

3) 消耗范圍為全局消耗(cs=2)

此時，庫所 p中只有一個標(biāo)記為(p, g)的token，符號 g 表示事件消耗范圍是全局消耗；p到{rj, rj+1,…, rk}的每個觸發(fā)變遷均有一條輸入弧。設(shè)e觸發(fā)了2條ECA規(guī)則r1和r2，其中，r1優(yōu)先級較高，r1和r2的條件分別為c1和c2。圖8為事件消耗時間為“條件評價后”(ct=0)的 EPN，t2和 t3分別是 r1和r2的激活變遷。t1發(fā)生后，r1和r2被觸發(fā)。由于(1tp, t3)是抑制弧，故先評價c1。若c1滿足，則消耗2tp中的token，處于觸發(fā)態(tài)r2被改成未觸發(fā)態(tài)。

圖7 觸發(fā)事件的消耗范圍為“局部消耗”的EPN

圖8 觸發(fā)事件的消耗范圍為“全局消耗”且ct=0時的EPN

圖 9為觸發(fā)事件的消耗時間為“執(zhí)行動作后”(ct=1)的EPN。t1發(fā)生后，r1和 r2均被觸發(fā)，此時(1tp, t3)和(1vp, t3)是抑制弧，因此先對r1進(jìn)行條件評價，當(dāng)r1的條件滿足且變遷t4發(fā)生時，r2的狀態(tài)被改變，被重新轉(zhuǎn)為未觸發(fā)狀態(tài)。

圖9 觸發(fā)事件的消耗范圍為“全局消耗”且ct=1時的EPN

2.2.6 對規(guī)則產(chǎn)生事件的描述

在EPN中，如果執(zhí)行變遷產(chǎn)生原子事件e(設(shè)p為e對應(yīng)的事件庫所)，那么：1) 如果e的事件消耗模式為不消耗，則所產(chǎn)生 token的標(biāo)記為(p,n)；2) 如果 e的事件消耗模式為全局消耗，則所產(chǎn)生token的標(biāo)記為(p, g)；3)如果e的事件消耗模式為局部消耗，設(shè)e可觸發(fā)規(guī)則集{rj, rj+1,…, rk}，則將產(chǎn)生k-j+1個token，其標(biāo)記依次為(p, rj), (p,rj+1),…, (p, rk)。

2.3 EPN舉例

例1 一條ECA規(guī)則r 描述如下。

ON e1?e2??e3

IF c1??c2THEN e2??c1

規(guī)則 r 的語義為：當(dāng)原子事件e1和 e2發(fā)生并且e3沒有發(fā)生時，r被觸發(fā)，然后評價r的條件，如果c1成立且c2不成立，則執(zhí)行動作，產(chǎn)生e2并使c1不成立。設(shè)r觸發(fā)事件的消耗模式為局部消耗。圖10是規(guī)則r的EPN的初始狀態(tài)，e1和e2已發(fā)生，e3未發(fā)生，此時觸發(fā)變遷t1是可發(fā)生的。t1發(fā)生后，r被觸發(fā)，庫所pt中產(chǎn)生一個token。由于條件庫所pc1中有 token(條件 c1成立)且?guī)焖?pc2中沒有token(條件c2不成立)，此時激活變遷t2是可發(fā)生的。t2發(fā)生后，r被激活，庫所pv中產(chǎn)生一個token。此時，t3可發(fā)生。t3發(fā)生后，在e3和pn各產(chǎn)生一個token。由于1cp有token，因此變遷t4是可發(fā)生的。t4發(fā)生后，消耗庫所1cp中的token。此時，完成了規(guī)則r 的一次觸發(fā)執(zhí)行過程。

圖10 規(guī)則r的EPN

2.4 ECA規(guī)則集的EPN等價轉(zhuǎn)化

為了利用 EPN中的規(guī)則結(jié)構(gòu)信息分析規(guī)則集的終止性，本文提出了EPN的等價轉(zhuǎn)化算法，該算法將包含復(fù)雜規(guī)則特性(如復(fù)合事件、復(fù)合條件、事件消耗模式、觸發(fā)關(guān)系、活化關(guān)系和墮化關(guān)系等)的ECA規(guī)則集轉(zhuǎn)化為等價的EPN。ECA規(guī)則集EPN的等價轉(zhuǎn)化算法如圖11所示。

3 ECA規(guī)則集的終止性分析

3.1 理論分析

在ECA規(guī)則中，如果存在事件消耗模式為不消耗的事件，那么一旦該事件發(fā)生，該規(guī)則將不可終止。因此本文假設(shè)規(guī)則集中不存在事件消耗模式為不消耗的規(guī)則。設(shè)∑為 ECA規(guī)則集R的EPN表示，L是網(wǎng)∑ 中的一個觸發(fā)環(huán)，L=(r1, r2,…, ri)表示規(guī)則 r1觸發(fā) r2, r2觸發(fā) r3,…,且 ri觸發(fā) r1。

圖11 ECA規(guī)則集EPN的等價轉(zhuǎn)化算法

定義3 設(shè)L是網(wǎng)∑的一個觸發(fā)環(huán)，如果從任意初始標(biāo)識出發(fā)，L中的規(guī)則都將在執(zhí)行有限次后永遠(yuǎn)不會被觸發(fā)，那么稱L為一個假觸發(fā)環(huán)，否則，L為一個真觸發(fā)環(huán)。

定義4 設(shè)L是網(wǎng)∑的一個觸發(fā)環(huán)。對于L中的一條規(guī)則r和一個庫所p，如果規(guī)則r在網(wǎng)∑中對應(yīng)的事件庫所集合、條件庫所集合和動作庫所集合包含p，則稱p屬于觸發(fā)環(huán)L，記p∈L。

定義5 設(shè)L是網(wǎng)∑的一個觸發(fā)環(huán)，如果存在庫所p和p'，滿足p∈∑，p'∈L，并且從庫所p'到庫所p有一條通路，則稱p是觸發(fā)環(huán)L可達(dá)的。

定理1 設(shè)L是網(wǎng)∑中一個觸發(fā)環(huán)，存在一條規(guī)則r∈L，構(gòu)成規(guī)則r的原子事件設(shè)為e，并設(shè)e在∑中對應(yīng)的庫所為p，t為規(guī)則r的觸發(fā)變遷。如果(p,t)為一般弧，滿足要么p的前集為空，要么p不由任何觸發(fā)環(huán)可達(dá)，那么L是一個假觸發(fā)環(huán)。

證明 設(shè)網(wǎng)∑的一個觸發(fā)環(huán)L=(r1, r2, …, ri)且規(guī)則r∈L，e是r的原子事件，p為e對應(yīng)的事件庫所，t為r的觸發(fā)變遷，(p, t)為一般弧，n為∑的初始標(biāo)識下p中所包含token的數(shù)目，n是自然數(shù)。1)如果 p的前集為空，那么∑中任何變遷的發(fā)生只可能消耗p的token，而不會在p中產(chǎn)生token。消耗完所有p中的token以后，規(guī)則r 將不可能被再一次觸發(fā)和執(zhí)行。由于初始狀態(tài)下p中的token的數(shù)目是有限的(數(shù)目為n)，因此，r 最大觸發(fā)次數(shù)不會超過n，在此之后，r 將不能再被觸發(fā)，從而L為一個假觸發(fā)環(huán)。2) 如果p不被任何觸發(fā)環(huán)可達(dá)，此時進(jìn)入p中的token數(shù)目是有限的，不妨設(shè)為m，從而當(dāng)消耗完p中所有token時，r被觸發(fā)執(zhí)行的次數(shù)不會超過n+m。此后規(guī)則r將不能再被觸發(fā)，從而L終止。

因此，觸發(fā)環(huán)L是一個假觸發(fā)環(huán)，命題得證。

推論1 設(shè)L是網(wǎng)∑中一個觸發(fā)環(huán)，一條ECA規(guī)則r∈L，e為r的原子事件，p為e對應(yīng)庫所，t為r對應(yīng)的觸發(fā)變遷，弧(p, t)為一般弧。如果p的前集為空或僅由假觸發(fā)環(huán)可達(dá)，則L是一個假觸發(fā)環(huán)。

定理2 設(shè)L是網(wǎng)∑中一個觸發(fā)環(huán)。如果存在一條ECA規(guī)則r∈L，其原子條件為c，滿足以下3個條件：1) (c, t)是一般弧，其中，t是r的激活變遷；2) c被改為假或取反；3)改變c 的規(guī)則只有一條，設(shè)為r'，且r'∈L，那么L為一個假觸發(fā)環(huán)。

證明 采用反證法。假設(shè)觸發(fā)環(huán)L不是假觸發(fā)環(huán)。此時，從∑中任何狀態(tài)出發(fā)，r' 可以被無限次執(zhí)行。規(guī)則 r'改變了規(guī)則 r的條件 c，使其為假或取反，但是r被激活的前提是條件評估必須為真。由于改變規(guī)則r條件的規(guī)則只能是規(guī)則r'，因此當(dāng)r'執(zhí)行后，導(dǎo)致規(guī)則r的條件評價為假，從而使得r不能被激活和執(zhí)行，從而使得L不能永遠(yuǎn)執(zhí)行下去，與假設(shè)矛盾。命題得證。

定理3 設(shè)L是網(wǎng)∑中一個觸發(fā)環(huán)，如果存在一條ECA規(guī)則r∈L，r的原子條件為c，并且1) (c, t)是抑制弧，其中，t是r的激活變遷；2) c被改為假或取反；3) 改變c的規(guī)則只有一條，設(shè)為r'，且r'∈L，那么L為一個假觸發(fā)環(huán)。

證明 與定理2類似。

定理4 設(shè)ECA規(guī)則集R的等價EPN為∑，如果∑中不存在任何觸發(fā)環(huán)或者所有的觸發(fā)環(huán)都是假觸發(fā)環(huán)，那么，ECA規(guī)則集R是可終止的。

證明 如果網(wǎng)∑中不包含任何觸發(fā)環(huán)，則命題顯然成立。設(shè)L是∑的一個假觸發(fā)環(huán)，那么對于任意ECA規(guī)則r∈L，由定義3可知，r在觸發(fā)有限次后將不能被再次觸發(fā)，導(dǎo)致規(guī)則r是可終止的。由于∑中所有觸發(fā)環(huán)都是假觸發(fā)環(huán)，因此，規(guī)則集 R中的所有假觸發(fā)環(huán)中的規(guī)則都是可終止的，從而R是可終止的。命題得證。

3.2 終止性判定算法

基于ECA規(guī)則集的等價EPN，本文提出了相應(yīng)的終止性判定算法。該算法充分利用EPN所包含的規(guī)則信息，通過化簡EPN來判定規(guī)則集的可終止性。算法具體描述如圖12所示。

圖12 ECA規(guī)則集的可終止性判定算法

本質(zhì)上講，基于圖理論的 ECA規(guī)則集終止性分析方法是通過構(gòu)造規(guī)則集的觸發(fā)關(guān)系矩陣(或活化關(guān)系矩陣等)，并依據(jù)該矩陣元素的可達(dá)性判定原規(guī)則集是否存在環(huán)(回路)。一般地，設(shè)A為規(guī)則集的觸發(fā)關(guān)系矩陣，元素aij=1表示ECA規(guī)則i觸發(fā)ECA規(guī)則j。矩陣M=Ak中的元素mij的值表示從規(guī)則i到規(guī)則j的長度為k的觸發(fā)鏈路條數(shù)，而其對角線上的元素aii不為0則表示存在觸發(fā)環(huán)或回路。在極端情況下，規(guī)則集不存在任何觸發(fā)環(huán)或存在一個包含大部分或所有規(guī)則的觸發(fā)環(huán)時，矩陣的乘法運算需要進(jìn)行到An，這是判定算法的最壞情況。因此，現(xiàn)有基于觸發(fā)圖等圖理論的判定算法的時間復(fù)雜度為O(n4)[8,9,14]，其中，n為ECA規(guī)則條數(shù)。

本文提出的規(guī)則集判定算法不同于傳統(tǒng)基于圖理論的規(guī)則集可終止性判定算法，它基于ECA規(guī)則集的等價EPN，而EPN中包含了ECA規(guī)則的豐富規(guī)則信息，如復(fù)合事件、復(fù)合條件、事件消耗模式等，通過在EPN來判定定理1、定理2和定理 3，從而不斷消除所有能終止的規(guī)則和所有假觸發(fā)環(huán)，達(dá)到化簡 EPN的目的。如果最終EPN的所有元素均被刪除，則表示原ECA規(guī)則集不包含任何觸發(fā)環(huán)或所有的觸發(fā)環(huán)都是假觸發(fā)環(huán)，從而原ECA規(guī)則集是可終止的，否則，原規(guī)則集不可終止。

在算法2中，2)基于定理1和推論1對EPN進(jìn)行化簡，時間復(fù)雜度為O(m2)，其中，m為ECA規(guī)則集中所有不同的原子事件個數(shù)。3)基于定理2和定理3對EPN再次化簡，時間復(fù)雜度為O(kn)，其中，k為規(guī)則中所有原子條件的個數(shù)，n為規(guī)則條數(shù)。通常在ECA規(guī)則集合中，k<

3.3 終止性判定舉例

例2 設(shè)有ECA規(guī)則集R={ r1, r2, r3, r4}，其中，

r1： ON e1?e2IF c1THEN e3

r2： ON e3?e4IF c2THEN e1

r3： ON e4IF c3?c2THEN ?c2?e5

r4： ON e5IF c3THEN e4

ECA規(guī)則r1, r2, r3和r4中各元素的含義與例1中的 ECA規(guī)則相同，設(shè)所有規(guī)則的事件消耗模式為局部消耗。圖13是規(guī)則集R的等價EPN∑。對規(guī)則集R的終止性分析過程如下所述。

圖13 規(guī)則集的EPN

執(zhí)行算法2的2)后，網(wǎng)∑被化簡，如圖14所示。在3)中，由于原子條件c2及改變該條件的唯一一條ECA規(guī)則r3使c2為假，從而定理2成立，進(jìn)而刪除相關(guān)元素后，EPN被再次化簡為只剩下規(guī)則r1。由于flag的取值為true，轉(zhuǎn)至2)，EPN被再次化簡為空，從而得出結(jié)論：規(guī)則集R是可終止的。目前，采用已有方法均不能得出與筆者相同的終止性分析結(jié)論。

圖14 化簡后的EPN

4 實驗分析

針對不同的ECA規(guī)則集和終止性判定算法，本文設(shè)計了相應(yīng)的仿真實驗以驗證各判定算法的正確性和效率。實驗環(huán)境如下：CPU Intel 雙核1.86 GHz，內(nèi)存 1GB，Windows XP專業(yè)版，Microsoft Visual Studio 2005平臺。參與對比的判定算法有3種TG、BK和PN算法，其中，TG(基于觸發(fā)圖的判定)算法是依據(jù)規(guī)則集的觸發(fā)關(guān)系矩陣及其乘法運算計算是否存在回路，BK 算法是 Bostan-Korpeoglu[14]等人的算法，PN是本文所使用的算法。

4.1 實驗1

待測試ECA規(guī)則集R只包含一個觸發(fā)環(huán)L，L= {r1, r2, …, rn}，n為規(guī)則條數(shù)。r1的事件為 e1?e2，rn產(chǎn)生事件e1、事件e2是獨立事件，它不被任何規(guī)則產(chǎn)生。實驗中n取值范圍(100, 1 000)。表1記錄了規(guī)則集在不同算法下的運行時間。結(jié)果表明本文提出算法(PN)的效率最高，且算法PN和BK得出了正確結(jié)論(規(guī)則集是可終止的)，而算法 TG的判定結(jié)果出錯(規(guī)則集不可終止)。

表1 含一個觸發(fā)環(huán)時算法的運行時間(單位：s)

4.2 實驗2

待測試ECA規(guī)則集R含有3個觸發(fā)環(huán)，分別為 L1、L2和 L3，其中，L1=( r1, r2,…, rn/2)，L2=( rn/2+1,rn/2+2,…, rn)和 L3=(rn/4, rn/4+1,…, rn/2, rn/4×3, rn/4×3+1,…,rn)。規(guī)則 r1的事件為 e1?e2，其中，e2不被任何規(guī)則動作產(chǎn)生。表2記錄了規(guī)則集在不同算法下的運行時間，結(jié)果表明本文提出算法(PN)的運行時間仍然最短，并且得出了正確結(jié)論，而TG算法的判定結(jié)果仍然是錯誤的。

表2 含3個觸發(fā)環(huán)時算法的運行時間(單位：s)

4.3 實驗3

隨機生成待測試ECA規(guī)則集R。表3記錄了不同算法的運行時間。所有算法的判定結(jié)果是規(guī)則集保證終止，即規(guī)則集不含任何觸發(fā)環(huán)，但本文算法PN的運行時間仍遠(yuǎn)低于其他算法。

表3 不同算法對隨機生成的規(guī)則集判定的運行時間(單位：s)

5 結(jié)束語

ECA規(guī)則具有復(fù)雜的結(jié)構(gòu)特性，這些結(jié)構(gòu)特性使得 ECA規(guī)則集的可終止性判定十分困難。針對目前 ECA規(guī)則集的終止性判定算法只考慮部分結(jié)構(gòu)特性而導(dǎo)致算法準(zhǔn)確性差的缺點，本文提出了可有效表示ECA規(guī)則集的擴展Petri網(wǎng)模型(EPN)，并在此基礎(chǔ)上綜合分析了 ECA規(guī)則的各種結(jié)構(gòu)特性對終止性的影響，提出了基于EPN的可終止性判定算法。該算法通過化簡EPN來直接刪除ECA規(guī)則間的假觸發(fā)環(huán)，從而提高了判定準(zhǔn)確性，并在一定程度上降低了傳統(tǒng)圖理論判定算法的時間復(fù)雜度。理論分析和實驗結(jié)果表明，本文提出的 ECA規(guī)則集可終止性判定算法具有更高的準(zhǔn)確性和更低的時間復(fù)雜度。

[1] PATON N, DIAZ O. Active database systems[J]. ACM Computing Surveys, 1999, 31(1)：63-103.

[2] 盧捍華, 閔麗娟, 王亞石. 工作流主從實例處理方法及其Petri網(wǎng)建模[J]. 通信學(xué)報, 2010, 31(1)：92-99.LU T H, MIN L J, WANG Y S. Approach to master-slave workflow system and its Petri-net modeling[J]. Journal on Communications,2010, 31(1)：92-99.

[3] 郭迎九, 林闖, 尹浩等. 基于Petri網(wǎng)的數(shù)字媒體分發(fā)協(xié)議的安全性證明[J].電子學(xué)報,2009,37(5)：1031-1036.GUO Y J, LIN C, YIN H, et al. Proof of the security of digital media distributing protocol based on Petri net models[J]. Acta Electronica Sinica, 2009, 37(5)：1031-1036.

[4] AIKEN A, WIDOM J, HELLERSTEIN J M. Behavior of database production rules： termination, confluence, and observable determinism[J]. SIGMOD, 1992, 21(2)：59-68.

[5] BAILEY J, DONG G, RAMAMOHANARAO K. Decidability and undecidability results for the termination problem of active database rules[A]. PODS'98[C]. New York, USA, 1998. 264-273.

[6] MURATA T. Petri nets： properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4)：541-580.

[7] BARALIS E, CERI S, WIDOM J. Better termination analysis for active databases[A]. RIDS '93[C]. Edinburgh, Scotland, 1993.163-179.

[8] BARALIS E, CERI S, PARABOSCHI S. Improved rule analysis by means of triggering and activation graphs[A]. RIDS'95[C]. Greece：Springer-Verlag, 1995. 165-181.

[9] MONTESI D, BAGNATO M, DALLERA C. Termination analysis in active databases[A]. IDEAS'99[C]. Montreal, Canada, 1999. 288-297.

[10] 郝忠孝, 任超, 趙齡強. 含環(huán)觸發(fā)圖對應(yīng)的主動規(guī)則集可終止性分析[J]. 計算機研究與發(fā)展, 2005, 42(12)：2199-2205.HAO Z X, REN C, ZHAO L Q. Termination analysis of active rule based on dependency set[J]. Journal of Computer Research and Development, 2005, 42(12)：2199-2205.

[11] 熊曾剛, 楊揚, 曾明. 基于Petri網(wǎng)的兩階段網(wǎng)格任務(wù)調(diào)度模型與分析[J]. 通信學(xué)報, 2009, 30(8)：69-77.XIONG C G, YANG Y, ZENG M. Research on two-phase grid task scheduling based on Petri nets[J]. Journal on Communications, 2009,30(8)：69-77.

[12] LATIFA B, HAFIDA B. The priority of rules and the termination analysis using Petri nets[J]. The International Arab Journal of Information Technology, 2007, 4(2)：177-183.

[13] MEDINA-MARIN J, PEREZ-LECHUGA G, LI X. ECA rule analysis in a distributed active database[A]. ICCTD'09[C]. Kinabalu, Malaysia,2009.113-116.

[14] BOSTAN-KORPEOGLU B, YAZICI A. A fuzzy Petri net model for intelligent databases[J]. Data & Knowledge Engineering, 2007, 62(2)：219-247.

[15] 張立臣.面向普適計算的主動訪問控制模型研究[D].西安：陜西師范大學(xué),2011.ZHANG L C. Research on Active Access Control Model for Pervasive Computing[D]. Xian： Shaanxi Normal University,2011.

[16] CHRISTENSEN S, HANSEN N. Coloured Petri nets extended with place capacities, test arcs and inhibitor arcs[J]. Lecture Notes in Computer Science, 1993, 691(1)：186-205.

[17] FRATERNALI P, TANCA L. A structured approach for the definition of the semantics of active databases[J]. ACM Trans on Database Systems, 1995, 20(4)：414-471.