基于增強條件公式的主動規則集可終止性判定＊

熊中敏，趙夢露，黃冬梅

（上海海洋大學信息學院，上海201306）

1 引言

由于集成有主動規則的數據庫系統具有自動反應的功能，主動規則在SQL Server、Oracle、DB2和Informix等重要的商業數據庫系統中得到了運用。主動規則近年來吸引了較多的關注，已經應用到許多新領域中：例如 XML 文檔［1，2］、RDF［3］、語義網絡［4］和傳感器數據庫［5］等等。遵循 Event－Condition－Action范型的主動規則之間的相互觸發可導致整個規則集的無限次執行［6，7］，規則集的可終止性的判定成為一個難題［8］。為了限制觸發器級聯執行的深度，現有商業數據庫系統采用門檻值的方法，比如Oracle定義該值為32。但是，定義合適的門檻值比較困難，定義過小，將誤判可終止的規則集為不可終止，導致放棄已執行的正確結果；定義過大，真正的不可終止規則集被系統終止時已經循環執行多次，既浪費系統資源又使系統性能惡化。

為了克服已有判定方法的不足，本文提出了觸發環的可執行序列概念，建立包含可更新變量的條件公式的方法和由此產生的規則集可終止性判定方法。分析結果表明，所提出的方法可以發現現有方法不能發現的可終止性情形。通過對主動規則集可終止性理論的研究，可為設計具有良好行為特性的主動規則集提供理論依據，并有助于設計并實現主動數據庫系統的輔助分析工具，促進主動規則作為一種機制在其他行業中得到更多、更充分的應用。

2 相關知識

2.1 主動規則

主動規則常表示為 E－C－A 范型［7］，分別代表規則的觸發事件、規則條件、規則的執行動作。ra和rb分別表示兩個規則：（1）若ra的觸發事件包含在rb的動作中，則稱rb可觸發ra；（2）若執行rb的動作可使ra的條件成立，則稱rb可活化ra。這兩種關系形成兩種有向圖：觸發圖（TG）和活化圖（AG）。執行規則動作后因使自身條件不成立而無法再執行的規則稱為自惰化規則。以上內容詳見文獻［7］。

2.2 規則執行模式

本文采取文獻［9］中的規則處理過程，如圖1所示。

Figure 1 Process based on rule execution mode圖1 基于規則執行模式的處理過程

2.3 相關研究分析

本文研究主動規則集在編譯階段的可終止性判定問題，該研究當前主要分為兩類：基于觸發圖和活化圖的方法和基于條件公式的方法。已有的研究工作都存在一定的局限。文獻［10］通過分析主動規則集的語法建立觸發圖進行判定；文獻［7］利用活化圖進行判定，建立活化圖的代數方法由文獻［11］提出；本文的前期研究文獻［12］根據規則的立即執行語義，提出觸發環中規則同步執行的思想并用來建立不可歸約規則集。雖然文獻［12］將規則集分析細化到觸發環分析，但這類方法都沒有考慮觸發環所有所屬規則能否在同一次執行中執行，只是考慮單個規則在規則集或觸發環的運行當中能否無限次執行。基于規則集或觸發環建立條件公式的判定方法克服了這一缺陷。文獻［10］提出移出邊的方法，根據兩個規則的條件建立條件公式；文獻［13，14］提出移出路徑的思想，考慮一個觸發序列上所有規則條件建立更強的條件公式；本文前期工作文獻［15］根據規則的立即執行語義，提出建立活化路徑的條件公式進行判斷的方法，能更大程度地解決包含有自惰化規則［7］的規則集的可終止性判定問題。但是，這類方法具有以下不足：（1）條件公式中只包含不可更新變量或有限次更新變量，而有限次更新變量的判定是一個NP問題［14］；（2）如果規則集只包含有限次執行的觸發環，不能有效判斷其終止性。下面通過一個實例說明上述已有判定方法的不足。

例1 圖2以Oracle觸發器方式定義如下的主動規則。

Figure 2 Related active rule set definitions圖2 相關主動規則集定義

圖3 表示上述規則集關聯的觸發圖和活化圖，其中虛線表示活化邊，實線表示觸發邊。

Figure 3 TG＆AG associated with rule set in Figure 2圖3 與圖2中規則集關聯的TG圖和AG圖

圖3 中一個 TG環R1｛r1，r2，r3｝和一個 AG環R′1｛r1，r2，r3｝，R1以執行序列r1r2r3r1循環觸發執行。變量R.B、S.H、S.L、R.C 和R.D 既在R1的規則動作部分又在R1的規則條件部分，同時不出現在任何不屬于R1但可由其觸發可達的規則的動作部分。不屬于R1但可由其觸發可達的規則不能保證在R1的循環執行中真正運行。

（1）建立基于變量R.B的公式。R.B只在r1、r3的動作中賦予初值，由于公式中被更新變量應基于同一個初始值變化，所以有公式：δ1＝（R.B＝0），δ2＝（R.B ＝1）∧（R.B ＝1）＝ （R.B ＝1）。它們的真值為true，是可滿足的。

（2）與變量R.B類似，建立基于變量S.H、R.C的公式：ξ1＝（S.H ＝1），ξ2＝（S.H ＝0），ξ3＝（R.C ＝1），ξ4＝（R.C ＝0）。它們的真值為true，是可滿足的。

（3）建立基于變量R.D的公式。R.D被r3賦予初值，被r2更新，出現在r3的條件中。不妨將r3看作R1循環執行的第一個被觸發規則，由于公式中被更新變量應基于同一個初始值變化，即R.D總代表一個初始值，所以如果R.D初值已被增量＋△L更新，則公式中包含R.D的條件謂詞應將比較值以增量－△L更新，從而取得等價變換。建立的公式為：（R.D＜2－0.5）AND（R.D ＝1），真值為true，是可滿足的。

（4）建立基于變量S.L的公式。R1中沒有規則賦予S.L初值，S.L被r1更新，出現在r2的條件中。一旦r1再次作為被觸發規則，R1完成一次循環執行，可建立以下公式：σ＝ （S.L ＝S.L ＋1）AND（S.L＜2）＝ （（S.L ＋1）＜2））。盡管當r4賦S.L初值0且σ＝true，R1可循環執行一次，但當R1循環執行到第三次，即S.L＝0，K＝2，使得σ＝ （（S.L＋K×1）＜2）＝false，導致r3不能真正被執行，R1必可終止。

圖2中存在觸發環，文獻［6，10］不能判斷此規則集可終止；利用文獻［7，12］中的方法分析，只有r4從圖2中移出，它們不能判斷此規則集可終止；規則集中的變量都是可更新的，沒有不可更新變量和有限次更新變量被文獻［10，13～15］中的方法發現，它們不能判斷此規則集可終止。

3 活化路徑和活化路徑集

為了表達規則之間的可無限次維持的活化關系，文獻［15］提出了活化路徑等概念。

定義1［15］若規則ri∈規則集R且有〈ri，rj〉∈TG，則稱rj可由R直接觸發可達；若rj可由R直接觸發可達或存在規則rt可由R直接觸發可達使得〈rt，rj〉∈TG，則稱rj由R 觸發可達。

定義2［15］若規則ri∈規則集R且有〈ri，rj〉∈AG，則稱規則rj可由R直接活化可達；若rj可由R直接活化可達或存在規則ra可由R直接活化可達使得〈ra，rj〉∈AG，則稱rj由R 活化可達。

定義3［15］r的一個活化規則表示為ra，與ra相關的r的活化路徑Pa定義如下：（1）若ra∈一個活化環Ra，則Pa表示為Ra；（2）若ra?一個活化環Ra但可由Ra活化可達，則Pa表示為Ra∪p′，p′滿足下述特性：①ra可沿p′由Ra活化可達，但p′?Ra中任一規則；②p′是極小化的，即p′上任一規則被消除，則屬性①就不滿足。

文獻 ［7］已經證明從R的不可歸約規則集中移出的規則必有限次執行。在后文中非特別說明，定理中所指的規則、TG環和AG環均包含在一個不可歸約規則集中。

推論1［15］一個觸發環RT中任意一個規則表示為r，若r總存在一條活化路徑Pa且可由RT觸發可達Pa中任一規則，則RT將具有非終止性；否則，RT必可終止。

4 基于活化路徑建立條件公式

推論1沒有考慮活化路徑中的規則是否可以同時執行，其判斷具有保守性。

定義4［15］觸發環的規則執行序列 RES（Rule Execute Sequence）表示為：當觸發環中至少一個規則被一個事務觸發時，從r1到rn的循環執行，記作〈〈r1，…，rn〉〉＋，其中每個元素ri是互不相同的。屬于觸發環RT的所有RES，記作RESSet（RT）。

例2 在圖3中，TG環R1｛r1，r2，r3｝具有兩個RES：RES1＝〈〈r1，r2，r3〉〉＋，RES2＝〈〈r1，r2，r4，r3〉〉＋，RES－Set（R1）＝｛RES1，RES2｝。

定義5 規則r∈TG環RT且Pa為r的一條活化路徑，δ為RT的一條執行序列，若滿足特性：（1）δ包含Pa；（2）任一規則移出δ，則屬性（1）不成立或RT上有一個規則不能被觸發。則稱δ相對于Pa是極小化的。

以下的調整操作保證RES－Set（RT）中RES相對于Pa是極小化的。

定義6 TG環RT的一條RES表示為δ，RT上一個規則的活化路徑表示為Pa，定義操作Curtail（δ，RT，Pa）如下：若在δ上子序列P 滿足如下性質：（1）P的起點A?RT但A∈Pa；（2）P 的終點B∈RT；（3）r表示P 上除了起點A 和終點B之外的點，則r?RT且r?Pa。則起點A和終點B保留在P上，余下的點裁剪掉。

定理1 若規則r不屬于TG環RT并且不能為其觸發可達，則r不能與RT同步運行。

證明 通過反證法證明。假設r在RT上規則r′之后得到運行，根據前述的規則執行語義，必有r′觸發r。根據定義1可知：r可由RT觸發可達，與定理的前提產生矛盾，假設不成立，定理成立。 □

若r不屬于RT但可由其觸發可達，不能保證r能和RT同步執行，為判斷RT的終止性建立的條件公式中的變量不應被r的動作更新；否則，無法明確評估此變量在RT的循環執行中的更新變化。根據定理1，提出以下定義。

定義7 若變量X出現在TG環RT的規則條件部分，但不出現在屬于RT的規則或不屬于RT但可由其觸發可達的規則的動作部分，則稱X為RT的不可更新變量。

定義8 若變量X同時出現在TG環RT的規則條件部分和動作部分，但不出現在不屬于RT卻可由其觸發可達的規則的動作部分，則稱X為RT的可更新變量。

由于公式中可更新變量應基于同一個初始值變化，而變量常常多次賦初值，故提出以下定義。

定義9 在TG環RT中，若規則r給一個可更新變量X賦初值，則r稱為X的一個斷點。

4.1 基于不可更新變量建立條件公式

根據定義7，基于不可更新變量X建立的條件公式為TG環RT中規則條件部分包含X的謂詞的邏輯組合。詳細方法見文獻［13，14］。

4.2 基于可更新變量建立條件公式

在條件公式中，所有謂詞中同一個可更新變量都是基于同樣的初始值，初始值由其斷點規則賦值，如果某個謂詞中變量已發生增量＋△X的更新，變量始終看作其初始值，則應將比較值以增量－△X更新，并稱這種等價變換為相對于斷點規則的更新投影。

（1）如果觸發環RT的可更新變量X在RT的執行序列ξ中無斷點，則任選ξ中規則r為首個被觸發規則，對其后執行規則中包含X的條件謂詞做相對于r的更新投影，只能建立一個公式；

（2）如果觸發環RT的可更新變量X在R的執行序列ξ中有斷點r，則將r選為首個被觸發規則，對其后執行規則中包含X的條件謂詞作相對于r的更新投影，建立一個公式。

基于可更新變量建立條件公式的算法如算法1所示。

算法1 Formula－constructing

輸入：TG環RT的執行序列ξ和RT的可更新變量X；

輸出：條件公式集SC。

Begin

SC：＝?

（1）IF X 在ξ中無斷點規則

r表示ξ中任一規則并作為其循環執行的首個觸發規則；P表示r的條件中包含X的一個謂詞；δ1表示首個建立的公式；Updated（X）表示在X上已完成的一組更新；δ1：＝P；

IF r的動作以＋△X更新X

Updated（X）＝｛－△X｝；

ENDIF

IF r的動作以－△X更新X

Updated（X）＝｛＋△X｝；

ENDIF

ENDIF

IF X在ξ中有多個斷點

r表示X的任意斷點規則并選作ξ循環執行中首個觸發規則；P表示r的動作中賦X 初值的謂詞；

δ1：＝ P；Updated（X）＝?；

ENDIF

（2）r′表示ξ的循環執行中下一個觸發規則；

IF r′的條件中有形如X compare n 的謂詞P／＊compare表示 “＞，＜”等比較符，n表示常數＊／

FOR?deltax∈Updated（X）Do

n：＝n＋deltax；

ENDFOR

δ1：＝δ1∧P；

ENDIF

IF r′不為r且不是X 在ξ中的斷點

IF r′的動作以＋△X更新X

Updated（X）＝Updated（X）∪｛－△X｝；

ENDIF

IF r′的動作以－△X更新X

Updated（X）＝Updated（X）∪｛＋△X｝；

ENDIF

Goto（2）

ENDIF

IF r′不為r但作為X 在ξ中的斷點

SC：＝SC∪｛δ1｝；P′ 表示r′的動作中賦X 初值的謂詞；

δ2：＝ P′；Updated（X）＝?；Goto（2）

ENDIF

IF r′即為r／＊ξ完成一次循環執行＊／

δn表示當前建立的公式；SC：＝SC∪｛δn｝；

Return（SC）；

ENDIF

END

5 TG環的可終止性分析

ρ表示TG環RT的一個規則執行序列，Formula（ρ）表示利用算法1和文獻［13，14］中方法分別基于RT的可更新變量和不可更新變量為ρ建立的一組條件公式。

定理2 r表示一個TG環RT中的任意一個規則，若r總存在一個有效活化路徑Pa且Pa中任一規則可由RT觸發可達，同時RT滿足如下性質：若?ρ∈RES－Set（RT），滿足Rules－Set（ρ）?Rules－Set（Pa）且?δ∈Formula（Curtail（ρ，RT，Pa）），有δ≠false，則RT將具有非終止性；否則，RT必可終止。

證明 由定義5、定義6可知：對RES－Set（RT）中任意執行序列ρ，若都存在一個條件公式σ∈Formula（Curtail（ρ，RT，Pa）），有σ＝false，則RT或Pa上必有一個規則不能在ρ的循環中運行。這導致RT上必有一個規則因條件不滿足或自惰化規則r的條件不能被Pa再次活化而不能真正運行，從而導致執行序列ρ不能循環運行而終止，即RT必可終止。反之，因為條件公式都能滿足，Pa上所有規則和r都能被RT的一個執行序列ρ包含并與其同步循環執行，并且r能夠在自惰化后被Pa活化，即ρ可循環運行，故RT將具有非終止性。 □

定義10 在TG環RT中，若可更新變量X在RT中沒有斷點規則，則X是RT的可累積更新變量。

如果X是RT的可累積更新變量，通過算法1只能為其建立一個條件公式，Sum（△X）表示RT按某一執行序列循環執行過程中對X產生的所有更新累積后的凈效果。

定理3 X表示TG環RT的可累積更新變量，δ（X）表示通過算法1為RT的執行序列ρ建立的一個基于X 的條件公式，δ（X＋k×Sum（△X））表示當ρ循環執行k次，X產生可累積更新后δ（X）的表現形式。如果δ（X＋k×Sum（△X））＝false，則ρ必可終止。

證明 假設由算法1為RT的執行序列ρ建立的基于不可更新變量、可更新變量的所有條件公式都可滿足，并按定理2判斷RT將具有非終止性，可按ρ循環執行。在循環執行到第（k＋1）次時，經過ρ的k次循環過程中累積的更新后，X改變為（X＋k×Sum（△X））。如果通過算法1建立的公式δ（X＋k×Sum（△X））＝false，則ρ的第（k＋1）次循環中至少有一個規則因為條件無法滿足而不能運行，導致ρ必可終止。 □

設R表示任意不可歸約規則集，ST＝｛RT｜RT為R中的TG環｝。TG環的可終止性分析算法如算法2所示。

算法2 Refined Termi－test

輸入：R的TG環集ST；

輸出： 如果判斷可終止，返回true；否則，返回false。Begin

（1）FOR每個TG環RT∈ST

Sign：＝false；／／假設RT不是可終止的

FOR每個規則r∈Rules－Set（RT）

flag：＝true；／／假設r是可終止的

IF（?Pa∈Path－Setact（r）滿足Pa是活化路徑且?r′∈Rules－Set（Pa），r′由RT觸發可達）

IF（?ρa∈RES－Set（RT）滿足ρ包含Pa且有：?δ∈Formula（Curtail（ρ，RT，Pa）），δ≠false，同時RT不存在當ρ完成K 次循環后滿足δ（X＋k×Sum（△X））＝false的可累積更新變量X）

flag：＝false；／／r可非終止運行

ENDIF

ENDIF

IF flag

Sign：＝true；break；／／RT是可終止的

ENDIF

ENDFOR

IF NOT（Sign）

Return（false）；／／R不是可終止的

ENDIF

ENDFOR

（2）Return（true）；／＊無不可終止TG環，R可終止運行＊／

END

定理4 算法2是正確的、可終止的。其時間復雜度為O（m×p2×n），其中m表示觸發環的個數，p表示規則集R中的規則個數，n表示活化環個數。

證明 定理2、定理3保證了算法的正確性；因為不可歸約規則集R中TG環個數、一個TG環的RES個數、AG環個數、主動規則的個數、規則的活化路徑個數、一個TG環中不可更新變量和可更新變量的個數都是有限的，故算法2可自動終止。很明顯，算法的時間復雜度由觸發環RT的可終止性判定決定，即決定是否存在flag＝false。在最壞情況下m個觸發環都需要被檢驗；每個觸發環所包含的規則個數Rules－Set（RT）不超過規則集R中的規則個數p；在最壞情況下每個規則都能由任何活化環活化可達，p個規則可以最多有（p×n）個活化路徑，將每個活化路徑中規則的觸發可達判定和與之相關的條件公式的檢測看作是基本操作，則最內層的For語句最多可執行基本操作 （m×p×（p×n））次。故算法的時間復雜度為O（m×p2×n）。 □

6 結束語

現有方法在判斷含有自惰化規則的規則集可終止性時存在不足，為此，本文提出了觸發環的執行序列的概念，從而將觸發環和規則的執行語義結合在一起；并進一步提出了觸發環執行序列上的可更新變量、不可更新變量的概念，給出了建立包含可更新變量的條件公式的方法和由此產生的判斷規則集可終止性的技巧；同時，還給出了運用該方法的判定定理及其相應的算法。

［1］ Bonifati A，Ceri S，Paraboschi S.Active rules for XML：A new paradigm for e－services［J］.VLDB Journal，2001，10（1）：39－47.

［2］ Bailey J，Poulovassilis A，Wood P T.An event－condition－action language for XML［C］∥Proc of WWW’02，2002：486－495.

［3］ Papamarkos G，Poulovassilis A，Wood P T.RDFTL：An event－condition－action language for RDF［C］∥Proc of the 3rd Web Dynamics Workshop at WWW’04，2004：223－248.

［4］ Papamarkos G，Poulovassilis A，Wood P T.Event－conditionaction rule language for the semantic web［C］∥Proc of Workshop on Semantic Web and Databases，2003：855－864.［5］ Zoumboulakis M，Roussos G，Poulovassilis A.Active rules for sensor databases［C］∥Proc of the 30th VLDB Conference，2004：98－103.

［6］ Aiken A，Hellerstein J，Widom J.Static analysis techniques for predicting the behavior of database production rules［J］.ACM Transactions on Database Systems，1995，20（1）：3－41.

［7］ Baralis E，Ceri S，Paraboschi S.Compile－time and runtime analysis of active behaviors［J］.IEEE Transactions on Knowledge and Data Engineering，1998，10（3）：353－370.

［8］ Bailey J，Dong Guo－zhu，Ramamohanarao K.On the decidability of the termination problem of active database system［J］.Theoretical Computer Science，2004，311 （1－3）：389－437.

［9］ Paton N W，Diaz O.Active database system［J］.ACM Computing Surveys，1999，31（1）：63－103.

［10］ Karadimce A P，Urban S D.Refined triggering graph：A logic－based approach to termination analysis in an active object－oriented database［C］∥Proc of International Conference on Data Engineering（ICDE），1996：1.

［11］ Baralis E，Widom J.An algebraic approach to static analysis of active database rules［J］.ACM Transactions on Database Systems，2000，25（3）：269－332.

［12］ Hao Zhong－xiao，Xiong Zhong－min.An efficient algorithm about computing an irreducible rule set in active database［J］.Journal of Computer Research and Development，2006，43（2）：281－287.（in Chinese）

［13］ Lee S Y，Ling T W.Refined termination decision in active databases［C］∥Proc of International Conference on Database and Expert Systems Applications，1997：182－191.

［14］ Lee S Y，Ling T W.A path removing technique for detecting trigger termination［C］∥Proc of International Conference on Extended Database Technology，1998：1.

［15］ Xiong Zhong－min，Hao Zhong－xiao.An approach to termination decision for a rule set based on activation path and conditional formula［J］.Journal of Computer Research and Development，2006，43（5）：901－907.（in Chinese）

附中文參考文獻：

［11］ 郝忠孝，熊中敏.計算主動數據庫中不可歸約規則集的有效算法［J］.計算機研究與發展，2006，43（2）：281－287.

［15］ 熊中敏，郝忠孝.基于活化路徑和條件公式的主動規則集可終止性判定方法［J］.計算機研究與發展，2006，43（5）：901－907.