熊中敏，趙夢(mèng)露，黃冬梅

（上海海洋大學(xué)信息學(xué)院，上海201306）

1 引言

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

為了克服已有判定方法的不足，本文提出了觸發(fā)環(huán)的可執(zhí)行序列概念，建立包含可更新變量的條件公式的方法和由此產(chǎn)生的規(guī)則集可終止性判定方法。分析結(jié)果表明，所提出的方法可以發(fā)現(xiàn)現(xiàn)有方法不能發(fā)現(xiàn)的可終止性情形。通過對(duì)主動(dòng)規(guī)則集可終止性理論的研究，可為設(shè)計(jì)具有良好行為特性的主動(dòng)規(guī)則集提供理論依據(jù)，并有助于設(shè)計(jì)并實(shí)現(xiàn)主動(dòng)數(shù)據(jù)庫(kù)系統(tǒng)的輔助分析工具，促進(jìn)主動(dòng)規(guī)則作為一種機(jī)制在其他行業(yè)中得到更多、更充分的應(yīng)用。

2 相關(guān)知識(shí)

2.1 主動(dòng)規(guī)則

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

2.2 規(guī)則執(zhí)行模式

本文采取文獻(xiàn)［9］中的規(guī)則處理過程，如圖1所示。

Figure 1 Process based on rule execution mode圖1 基于規(guī)則執(zhí)行模式的處理過程

2.3 相關(guān)研究分析

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

例1 圖2以O(shè)racle觸發(fā)器方式定義如下的主動(dòng)規(guī)則。

Figure 2 Related active rule set definitions圖2 相關(guān)主動(dòng)規(guī)則集定義

圖3 表示上述規(guī)則集關(guān)聯(lián)的觸發(fā)圖和活化圖，其中虛線表示活化邊，實(shí)線表示觸發(fā)邊。

Figure 3 TG＆AG associated with rule set in Figure 2圖3 與圖2中規(guī)則集關(guān)聯(lián)的TG圖和AG圖

圖3 中一個(gè) TG環(huán)R1｛r1，r2，r3｝和一個(gè) AG環(huán)R′1｛r1，r2，r3｝，R1以執(zhí)行序列r1r2r3r1循環(huán)觸發(fā)執(zhí)行。變量R.B、S.H、S.L、R.C 和R.D 既在R1的規(guī)則動(dòng)作部分又在R1的規(guī)則條件部分，同時(shí)不出現(xiàn)在任何不屬于R1但可由其觸發(fā)可達(dá)的規(guī)則的動(dòng)作部分。不屬于R1但可由其觸發(fā)可達(dá)的規(guī)則不能保證在R1的循環(huán)執(zhí)行中真正運(yùn)行。

（1）建立基于變量R.B的公式。R.B只在r1、r3的動(dòng)作中賦予初值，由于公式中被更新變量應(yīng)基于同一個(gè)初始值變化，所以有公式：δ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更新，出現(xiàn)在r3的條件中。不妨將r3看作R1循環(huán)執(zhí)行的第一個(gè)被觸發(fā)規(guī)則，由于公式中被更新變量應(yīng)基于同一個(gè)初始值變化，即R.D總代表一個(gè)初始值，所以如果R.D初值已被增量＋△L更新，則公式中包含R.D的條件謂詞應(yīng)將比較值以增量－△L更新，從而取得等價(jià)變換。建立的公式為：（R.D＜2－0.5）AND（R.D ＝1），真值為true，是可滿足的。

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

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

3 活化路徑和活化路徑集

為了表達(dá)規(guī)則之間的可無限次維持的活化關(guān)系，文獻(xiàn)［15］提出了活化路徑等概念。

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

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

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

文獻(xiàn) ［7］已經(jīng)證明從R的不可歸約規(guī)則集中移出的規(guī)則必有限次執(zhí)行。在后文中非特別說明，定理中所指的規(guī)則、TG環(huán)和AG環(huán)均包含在一個(gè)不可歸約規(guī)則集中。

推論1［15］一個(gè)觸發(fā)環(huán)RT中任意一個(gè)規(guī)則表示為r，若r總存在一條活化路徑Pa且可由RT觸發(fā)可達(dá)Pa中任一規(guī)則，則RT將具有非終止性；否則，RT必可終止。

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

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

定義4［15］觸發(fā)環(huán)的規(guī)則執(zhí)行序列 RES（Rule Execute Sequence）表示為：當(dāng)觸發(fā)環(huán)中至少一個(gè)規(guī)則被一個(gè)事務(wù)觸發(fā)時(shí)，從r1到rn的循環(huán)執(zhí)行，記作〈〈r1，…，rn〉〉＋，其中每個(gè)元素ri是互不相同的。屬于觸發(fā)環(huán)RT的所有RES，記作RESSet（RT）。

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

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

以下的調(diào)整操作保證RES－Set（RT）中RES相對(duì)于Pa是極小化的。

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

定理1 若規(guī)則r不屬于TG環(huán)RT并且不能為其觸發(fā)可達(dá)，則r不能與RT同步運(yùn)行。

證明 通過反證法證明。假設(shè)r在RT上規(guī)則r′之后得到運(yùn)行，根據(jù)前述的規(guī)則執(zhí)行語(yǔ)義，必有r′觸發(fā)r。根據(jù)定義1可知：r可由RT觸發(fā)可達(dá)，與定理的前提產(chǎn)生矛盾，假設(shè)不成立，定理成立。 □

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

定義7 若變量X出現(xiàn)在TG環(huán)RT的規(guī)則條件部分，但不出現(xiàn)在屬于RT的規(guī)則或不屬于RT但可由其觸發(fā)可達(dá)的規(guī)則的動(dòng)作部分，則稱X為RT的不可更新變量。

定義8 若變量X同時(shí)出現(xiàn)在TG環(huán)RT的規(guī)則條件部分和動(dòng)作部分，但不出現(xiàn)在不屬于RT卻可由其觸發(fā)可達(dá)的規(guī)則的動(dòng)作部分，則稱X為RT的可更新變量。

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

定義9 在TG環(huán)RT中，若規(guī)則r給一個(gè)可更新變量X賦初值，則r稱為X的一個(gè)斷點(diǎn)。

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

根據(jù)定義7，基于不可更新變量X建立的條件公式為TG環(huán)RT中規(guī)則條件部分包含X的謂詞的邏輯組合。詳細(xì)方法見文獻(xiàn)［13，14］。

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

在條件公式中，所有謂詞中同一個(gè)可更新變量都是基于同樣的初始值，初始值由其斷點(diǎn)規(guī)則賦值，如果某個(gè)謂詞中變量已發(fā)生增量＋△X的更新，變量始終看作其初始值，則應(yīng)將比較值以增量－△X更新，并稱這種等價(jià)變換為相對(duì)于斷點(diǎn)規(guī)則的更新投影。

（1）如果觸發(fā)環(huán)RT的可更新變量X在RT的執(zhí)行序列ξ中無斷點(diǎn)，則任選ξ中規(guī)則r為首個(gè)被觸發(fā)規(guī)則，對(duì)其后執(zhí)行規(guī)則中包含X的條件謂詞做相對(duì)于r的更新投影，只能建立一個(gè)公式；

（2）如果觸發(fā)環(huán)RT的可更新變量X在R的執(zhí)行序列ξ中有斷點(diǎn)r，則將r選為首個(gè)被觸發(fā)規(guī)則，對(duì)其后執(zhí)行規(guī)則中包含X的條件謂詞作相對(duì)于r的更新投影，建立一個(gè)公式。

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

算法1 Formula－constructing

輸入：TG環(huán)RT的執(zhí)行序列ξ和RT的可更新變量X；

輸出：條件公式集SC。

Begin

SC：＝?

（1）IF X 在ξ中無斷點(diǎn)規(guī)則

r表示ξ中任一規(guī)則并作為其循環(huán)執(zhí)行的首個(gè)觸發(fā)規(guī)則；P表示r的條件中包含X的一個(gè)謂詞；δ1表示首個(gè)建立的公式；Updated（X）表示在X上已完成的一組更新；δ1：＝P；

IF r的動(dòng)作以＋△X更新X

Updated（X）＝｛－△X｝；

ENDIF

IF r的動(dòng)作以－△X更新X

Updated（X）＝｛＋△X｝；

ENDIF

ENDIF

IF X在ξ中有多個(gè)斷點(diǎn)

r表示X的任意斷點(diǎn)規(guī)則并選作ξ循環(huán)執(zhí)行中首個(gè)觸發(fā)規(guī)則；P表示r的動(dòng)作中賦X 初值的謂詞；

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

ENDIF

（2）r′表示ξ的循環(huán)執(zhí)行中下一個(gè)觸發(fā)規(guī)則；

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

FOR?deltax∈Updated（X）Do

n：＝n＋deltax；

ENDFOR

δ1：＝δ1∧P；

ENDIF

IF r′不為r且不是X 在ξ中的斷點(diǎn)

IF r′的動(dòng)作以＋△X更新X

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

ENDIF

IF r′的動(dòng)作以－△X更新X

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

ENDIF

Goto（2）

ENDIF

IF r′不為r但作為X 在ξ中的斷點(diǎn)

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

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

ENDIF

IF r′即為r／＊ξ完成一次循環(huán)執(zhí)行＊／

δn表示當(dāng)前建立的公式；SC：＝SC∪｛δn｝；

Return（SC）；

ENDIF

END

5 TG環(huán)的可終止性分析

ρ表示TG環(huán)RT的一個(gè)規(guī)則執(zhí)行序列，F(xiàn)ormula（ρ）表示利用算法1和文獻(xiàn)［13，14］中方法分別基于RT的可更新變量和不可更新變量為ρ建立的一組條件公式。

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

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

定義10 在TG環(huán)RT中，若可更新變量X在RT中沒有斷點(diǎn)規(guī)則，則X是RT的可累積更新變量。

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

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

證明 假設(shè)由算法1為RT的執(zhí)行序列ρ建立的基于不可更新變量、可更新變量的所有條件公式都可滿足，并按定理2判斷RT將具有非終止性，可按ρ循環(huán)執(zhí)行。在循環(huán)執(zhí)行到第（k＋1）次時(shí)，經(jīng)過ρ的k次循環(huán)過程中累積的更新后，X改變?yōu)椋╔＋k×Sum（△X））。如果通過算法1建立的公式δ（X＋k×Sum（△X））＝false，則ρ的第（k＋1）次循環(huán)中至少有一個(gè)規(guī)則因?yàn)闂l件無法滿足而不能運(yùn)行，導(dǎo)致ρ必可終止。 □

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

算法2 Refined Termi－test

輸入：R的TG環(huán)集ST；

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

（1）FOR每個(gè)TG環(huán)RT∈ST

Sign：＝false；／／假設(shè)RT不是可終止的

FOR每個(gè)規(guī)則r∈Rules－Set（RT）

flag：＝true；／／假設(shè)r是可終止的

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

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

flag：＝false；／／r可非終止運(yùn)行

ENDIF

ENDIF

IF flag

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

ENDIF

ENDFOR

IF NOT（Sign）

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

ENDIF

ENDFOR

（2）Return（true）；／＊無不可終止TG環(huán)，R可終止運(yùn)行＊／

END

定理4 算法2是正確的、可終止的。其時(shí)間復(fù)雜度為O（m×p2×n），其中m表示觸發(fā)環(huán)的個(gè)數(shù)，p表示規(guī)則集R中的規(guī)則個(gè)數(shù)，n表示活化環(huán)個(gè)數(shù)。

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

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

現(xiàn)有方法在判斷含有自惰化規(guī)則的規(guī)則集可終止性時(shí)存在不足，為此，本文提出了觸發(fā)環(huán)的執(zhí)行序列的概念，從而將觸發(fā)環(huán)和規(guī)則的執(zhí)行語(yǔ)義結(jié)合在一起；并進(jìn)一步提出了觸發(fā)環(huán)執(zhí)行序列上的可更新變量、不可更新變量的概念，給出了建立包含可更新變量的條件公式的方法和由此產(chǎn)生的判斷規(guī)則集可終止性的技巧；同時(shí)，還給出了運(yùn)用該方法的判定定理及其相應(yīng)的算法。

［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）

附中文參考文獻(xiàn)：

［11］ 郝忠孝，熊中敏.計(jì)算主動(dòng)數(shù)據(jù)庫(kù)中不可歸約規(guī)則集的有效算法［J］.計(jì)算機(jī)研究與發(fā)展，2006，43（2）：281－287.

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