基于自依賴規(guī)則分析的主動規(guī)則終止性研究＊

陸惠玲，周 濤

（寧夏醫(yī)科大學(xué)理學(xué)院，寧夏 銀川750004）

1 引言

在主動數(shù)據(jù)庫的研究中，主動規(guī)則是主動數(shù)據(jù)庫的核心。主動數(shù)據(jù)庫通過引入人工智能的知識控制理論檢測數(shù)據(jù)庫中的事件，當(dāng)待檢測事件發(fā)生后數(shù)據(jù)庫會自動完成一系列的數(shù)據(jù)庫操作，無須人為干涉。規(guī)則庫是主動數(shù)據(jù)庫的核心部分，是實現(xiàn)主動功能的基礎(chǔ)［1，2］。規(guī)則主要由三部分組成：事件、條件、動作，包含有這些組件的規(guī)則稱為事件—條件—動作ECA（Event Condition Action）規(guī)則，即在某一事件發(fā)生時引發(fā)數(shù)據(jù)庫管理系統(tǒng)去檢測數(shù)據(jù)庫當(dāng)前狀態(tài)，看是否滿足設(shè)定的條件，如果條件滿足，便觸發(fā)規(guī)定動作的執(zhí)行。從規(guī)則的形式可以看出，一條規(guī)則的事件部分可以是另外一條規(guī)則的動作部分的子集，也就是說，一條規(guī)則的動作的執(zhí)行同時也就意味著另外一條規(guī)則的事件的發(fā)生；同樣，一條規(guī)則的條件部分依賴于對于當(dāng)前數(shù)據(jù)庫狀態(tài)的查詢，它的動作部分同時也在改變著當(dāng)前數(shù)據(jù)庫的狀態(tài)，因而也就有可能使得另外一條原本條件為假的規(guī)則的條件部分變?yōu)檎婊蛘呒?。從上述分析可以看出，在一個規(guī)則庫中，不同的規(guī)則的不同部分之間存在著影響和依賴。歸納起來，主動行為的復(fù)雜性主要體現(xiàn)在終止性和行為一致性方面［1，3，4］。由于規(guī)則的條件和動作執(zhí)行結(jié)果依賴于它被處理時的數(shù)據(jù)庫狀態(tài)，無法僅僅根據(jù)規(guī)則的定義精確地判定對一組規(guī)則的處理必定是不可終止的或行為是不一致的。對于一個規(guī)則集合R，到目前為止能夠判定規(guī)則終止性、匯流性的算法已經(jīng)有很多，但從理論角度來講都是不完備的。這也正是制約主動數(shù)據(jù)庫發(fā)展的一個重要瓶頸。

文獻［1］首先介紹了觸發(fā)圖的概念，在文獻［5］中徹底闡述了這個概念：這樣的一個圖的建立依賴于規(guī)則的語法分析；圖中的節(jié)點是規(guī)則，兩條規(guī)則r1、r2通過一條從r1到r2的邊連接（如果r1的動作包含規(guī)則r2的觸發(fā)事件）。在這樣一個圖中環(huán)的存在意味著一種風(fēng)險—規(guī)則集的非終止性。規(guī)則集合中如果不存在環(huán)就保證了規(guī)則集的終止性。然而該分析中沒有考慮到規(guī)則的條件部分的惰化。因此，文獻［1，6～9］從不同角度提出了規(guī)則終止性判斷算法，整體來看就是考慮到了規(guī)則條件部分的惰化或者是一條路徑上全部條件的惰化；文獻［10］提出了一種方法來解開這個觸發(fā)環(huán)，并考慮了一條路徑上的所有條件都得到滿足的情況；文獻［11］精簡了觸發(fā)圖，其中使用了partial和total邊，這主要是考慮到了復(fù)合事件的影響。但是，主動規(guī)則的終止性問題仍然沒有得到較好的解決，在主動規(guī)則的終止性分析方面的主要成績就是提出了觸發(fā)圖以及在這方面的一些研究。

本文針對規(guī)則終止性問題展開討論，通過分析觸發(fā)邊、活化邊、惰化邊三種邊的觸發(fā)時序關(guān)系，構(gòu)造了條件斷言函數(shù)來描述活化邊和惰化邊對ECA規(guī)則中條件的影響，最后給出了觸發(fā)邊、活化邊和惰化邊的組合時序?qū)σ?guī)則的具體觸發(fā)情況；在此基礎(chǔ)上進一步完善了Barakis R提出的不可歸約規(guī)則集中的自依賴規(guī)則判定算法，對其中的能夠形成環(huán)狀結(jié)構(gòu)的自觸發(fā)規(guī)則給出了全面的討論，提出了一種新的自依賴規(guī)則判定算法。該算法可以找到在不可歸約集中由自觸發(fā)規(guī)則引發(fā)的不終止性導(dǎo)致的一種環(huán)狀觸發(fā)，通過把自觸發(fā)規(guī)則單獨處理來打斷這個環(huán)從而使規(guī)則集終止，有效提高了規(guī)則不終止性問題的判斷能力。

2 基本概念

觸發(fā)圖TG（Triggering Graph）、觸發(fā)邊TE（Triggering Edge）、活 化 圖 AG （Activation Graph）、活化邊AE（Activation Edge）、惰化圖DG（Deactivation Graph）和惰化邊 DE（Deactivation Edge）是主動規(guī)則ECA分析的主要手段，其概念參見文獻［1，11，12］。在惰化圖中，大多數(shù)惰化邊都是自惰化的，當(dāng)然也有例外，特別是一個不包含條件成分的規(guī)則都是自惰化的?；罨吅投杌叢粫瑫r存在，即如果（Vri，Vrj）∈AE，則（Vri，Vrj）?DE，反之亦然。在觸發(fā)圖中，文獻［13］證明了觸發(fā)環(huán)是規(guī)則非終止性的必要條件，如果TG中沒有環(huán)，則規(guī)則執(zhí)行必然終止。僅考慮TG圖，相當(dāng)于假定觸發(fā)時條件為真，動作必然執(zhí)行，TG環(huán)意味著非終止。引入AG圖，觸發(fā)環(huán)中沒有到達活化邊的規(guī)則在被觸發(fā)時條件為假，動作不會執(zhí)行，TG環(huán)未必導(dǎo)致非終止。進一步，引入DG圖后，根據(jù)活化邊與惰化邊之間的相對次序，TG環(huán)中只含有到達活化邊和惰化邊規(guī)則在被觸發(fā)時條件仍然可能為假，動作不會執(zhí)行，仍可能判定終止。以下分析是基于TG、AG和DG的。

定義1 活化環(huán)：令A(yù)G＝（VR，AE）為一活化圖，若有規(guī)則r1，r2，…，rk∈R，（r1，r2）∈AE，（r2，r3）∈AE，…，（rk，r1）∈AE，則稱ρ＝（r1，r2，…rk）為一活化環(huán)。觸發(fā)環(huán)是觸發(fā)圖中的環(huán)，活化環(huán)是活化圖中的環(huán)。

定義2 條件斷言函數(shù)Asseveration（G，r）：把關(guān)聯(lián)圖G中的活化邊和惰化邊對ECA規(guī)則r中條件的影響通過構(gòu)造斷言函數(shù)來表達。規(guī)定斷言函數(shù)的返回值有True、False兩個：如果規(guī)則r先被惰化，然后被活化（也就是說惰化邊先到、活化邊后到），那么條件斷言函數(shù)的返回值為True；如果規(guī)則r先被活化，然后被惰化（也就是說活化邊先到、惰化邊后到），那么條件斷言函數(shù)的返回值為False。還有兩種特殊情況，一種就是只有一條活化邊到達的情況，那么函數(shù)的返回值肯定為True；另外一種就是只有惰化邊到達的情況，那么函數(shù)的返回值肯定為False。

為了在后面的算法中能夠清晰地表達這種復(fù)雜的關(guān)系，仍然區(qū)分活化和惰化規(guī)則r的規(guī)則，稱對規(guī)則r發(fā)出活化邊的規(guī)則為條件斷言函數(shù)的活化前件，稱對規(guī)則r發(fā)出惰化邊的規(guī)則為條件斷言函數(shù)的惰化前件；可以簡稱為規(guī)則r的活化前件和惰化前件，而規(guī)則r稱之為條件斷言函數(shù)的后件。

可以用二叉樹的形式來描述關(guān)聯(lián)圖中規(guī)則r與它的觸發(fā)邊、條件斷言函數(shù)Asseveration（G，r）之間的關(guān)系。在二叉樹中，節(jié)點代表規(guī)則，節(jié)點的左孩子代表它的事件依賴規(guī)則節(jié)點，節(jié)點的右孩子代表它的條件依賴（或逆條件依賴）規(guī)則節(jié)點，虛線表示條件斷言函數(shù)，規(guī)則r1是規(guī)則r3的條件斷言前件；實線表示觸發(fā)邊。如在圖1中，r3條件依賴（或逆條件依賴）于r1，r2事件依賴于r1。

Figure 1 Binary－tree representation of association graph圖1 關(guān)聯(lián)圖的二叉樹表示

圖1的鄰接矩陣形式如圖2所示。關(guān)聯(lián)圖中的規(guī)則數(shù)目決定鄰接矩陣的規(guī)模，如果規(guī)則ri與規(guī)則rj之間存在觸發(fā)邊，則G［i，j］＝1；如果規(guī)則ri與規(guī)則rj之間存在活化邊，則G［i，j］＝－1；如果規(guī)則ri與規(guī)則rj之間存在惰化邊，則G［i，j］＝0。如果規(guī)則ri與規(guī)則rj之間不存在任何關(guān)系G［i，j］＝ ∞ 。

Figure 2 Storage structure of adjacency matrix 圖2 鄰接矩陣的存儲結(jié)構(gòu)

定義3 關(guān)聯(lián)圖（Association Graph）：令R 為任意規(guī)則集，TG（VR，TE）為觸發(fā)圖，AG（VA，AE）為活化圖，DG（VD，DE）為惰化圖，則G＝（VR，E）為關(guān)聯(lián)圖，其中E＝AE∪TE∪DE。

考慮規(guī)則ri的執(zhí)行可能使規(guī)則rk的條件為真，規(guī)則rj的執(zhí)行可能使規(guī)則rh的條件為假。在適當(dāng)條件下，觸發(fā)環(huán)和活化環(huán)未必導(dǎo)致規(guī)則集合呈現(xiàn)非終止性行為。在圖3所示的例子中，按照文獻［13］所述的算法，這個圖是不可能規(guī)約的，判定為非終止的。若規(guī)則r3的執(zhí)行使得規(guī)則r1的條件為假，則非終止性情況就會發(fā)生變化。在圖3所示的例子中，加入惰化邊（r3，r1）后得到圖4，然后就可以很容易地判定它的終止性了。

Figure 3 Non－termination analysis based on TGgraph and AGgraph圖3 基于TG圖和AG圖非終止性分析

Figure 4 Termination analysis based on association graph圖4 基于關(guān)聯(lián)圖的終止性分析

定義4 合格規(guī)則：設(shè)任意一條規(guī)則r∈R，如果該規(guī)則的條件部分為真，并且其所等待的事件已經(jīng)發(fā)生，其發(fā)生的時刻不能早于條件為真的時刻，那么稱這樣的規(guī)則為合格規(guī)則。

關(guān)于這個概念要進行一些特別的說明，在一個關(guān)聯(lián)圖中存在三種依賴關(guān)系：事件依賴、條件依賴、條件逆依賴，它們分別與關(guān)聯(lián)圖中的三種邊相對應(yīng)，即觸發(fā)邊TE、AE、DE?；罨c惰化的結(jié)果是使某條規(guī)則的條件為真或者為假，它們執(zhí)行的結(jié)果可以在一段時間內(nèi)有效，而觸發(fā)行為卻是瞬間的，其結(jié)果不能暫時保留，即對于一條ECA主動規(guī)則r，當(dāng)事件發(fā)生時，如果條件C不晚于E被觸發(fā)的時刻為真（也就是說這條規(guī)則的條件斷言函數(shù)的返回值為真），那么規(guī)則r就是合格的。從另外一個角度來講就是條件斷言必須早于觸發(fā)，這樣的觸發(fā)才有可能是有效觸發(fā)，否則為無效觸發(fā)。

定義5 自依賴規(guī)則：所謂自依賴規(guī)則，是指當(dāng)一條規(guī)則r被系統(tǒng)調(diào)度執(zhí)行以后，它的條件部分自動置為假，它的動作又觸發(fā)和活化了規(guī)則庫中的其它規(guī)則，從而產(chǎn)生了鏈鎖反應(yīng)。而經(jīng)過了由于規(guī)則r的執(zhí)行所導(dǎo)致的一系列的規(guī)則執(zhí)行以后，r又成為可以被系統(tǒng)調(diào)度執(zhí)行的合格規(guī)則（觸發(fā)事件發(fā)生，規(guī)則r的條件斷言函數(shù)返回值為真），稱規(guī)則r為自依賴規(guī)則。

這個概念是文獻［14］首先提出來的，并且在該文中給出了一個算法來判斷在不可歸約規(guī)則集中的自依賴規(guī)則。文獻［14］指出，在規(guī)則不含優(yōu)先級的情況下，多個被觸發(fā)的規(guī)則的執(zhí)行次序隨意確定，其中必有呈現(xiàn)非終止性的排列，因而不可歸約集會呈現(xiàn)非終止性行為；在規(guī)則包含優(yōu)先級的情況下，多個被觸發(fā)規(guī)則的執(zhí)行次序由被觸發(fā)規(guī)則的優(yōu)先級確定，其排序次序唯一，如果該次序不導(dǎo)致終止行為的發(fā)生，則規(guī)則集仍然呈現(xiàn)終止行為。文獻［4，20］給出進一步的討論，如果歸約以后規(guī)則集為空，說明該關(guān)聯(lián)圖中不存在環(huán)，這肯定是終止的。但是，這里需要說的是，上述結(jié)論不能推出如果關(guān)聯(lián)圖中存在環(huán)就一定不終止。換句話說，就是到目前為止能知道的是如果規(guī)則集終止就必須無環(huán)，但存在環(huán)未必不終止。經(jīng)過歸約以后的不可規(guī)約規(guī)則集就變成了許多個”環(huán)狀”的規(guī)則集，分析這樣的規(guī)則集的終止性是富有挑戰(zhàn)性的一項工作。本文就是在這種情況下，在借鑒文獻［14，15］的相關(guān)思想的基礎(chǔ)上，對其中能夠形成環(huán)狀結(jié)構(gòu)的自觸發(fā)規(guī)則給出了詳細的討論，并通過一個算法找出了在不可歸約集中的一種環(huán)，它是由自觸發(fā)規(guī)則引發(fā)的不終止性。解決的辦法就是把自觸發(fā)規(guī)則單獨處理以便打斷這個環(huán)從而使規(guī)則集終止。顯然這對規(guī)則的終止性分析有十分積極的意義。

3 自依賴規(guī)則的判定算法

3.1 自依賴規(guī)則的判定算法

在分析之前首先分析觸發(fā)邊、活化邊、惰化邊三種邊的關(guān)系，以及它們的時序關(guān)系，前兩種邊代表的是可能，即如果某條規(guī)則被活化或觸發(fā)，它有可能執(zhí)行；惰化邊代表肯定，即如果某條規(guī)則被惰化，那么這條規(guī)則肯定不能被執(zhí)行。三種邊的到達組合時序?qū)σ?guī)則r的觸發(fā)影響，表1和表2給出了詳細的說明。

Table 1 Combinatorial sequential relationship of two types of edges表1 有兩種類型的邊的組合時序關(guān)系

Table 2 Combinatorial sequential relationship of three types of edges表2 有三種類型的邊的組合時序關(guān)系

說明：AE→TE表示AE的到達不晚于TE；把真正有意義的規(guī)則用加黑方式表示，并且在旁邊加了＊。

規(guī)則r的條件斷言活化前件、條件斷言的惰化前件可能都不止一個，本文認為不管有幾條活化邊或者惰化邊射入規(guī)則r，只要符合上面的幾條時序關(guān)系，就與一條活化邊或一條惰化邊的效果是一樣的，因此這里只考慮累計的效果。由于引入了條件斷言函數(shù)，每次用條件斷言函數(shù)來判斷某條規(guī)則活化和惰化情況，而無須對有多條活化邊或惰化邊與只有一條活化邊或惰化邊的情況進行區(qū)分，這樣惰化和活化被統(tǒng)一在了一個概念中，簡化了終止性的分析。如果條件斷言函數(shù)返回值為True，并且條件斷言函數(shù)的執(zhí)行早于觸發(fā)邊的到達，那么這條規(guī)則就可以被觸發(fā)；如果條件斷言函數(shù)返回值為False，并且條件斷言函數(shù)的執(zhí)行早于觸發(fā)邊的到達，那么在這種情況下，規(guī)則不能被觸發(fā)，活化邊是無效活化；如果條件斷言函數(shù)返回值為False，并且條件斷言函數(shù)的執(zhí)行晚于觸發(fā)邊的到達，那么這條規(guī)則肯定不能被觸發(fā)，也稱為無效活化。當(dāng)然如果只有活化邊到達，則返回值肯定為真；如果只有惰化邊到達，則返回值肯定為假。

3.2 算法基礎(chǔ)

定理1 如果規(guī)則r是規(guī)則庫中的一個自依賴規(guī)則，那么規(guī)則r必然在關(guān)聯(lián)圖中的一個觸發(fā)環(huán)上［11］。

定義6 規(guī)則間的距離Dist（ri，rj）：在一個觸發(fā)環(huán)中，兩條規(guī)則ri與rj的距離是指在觸發(fā)環(huán)中，ri到rj之間的弧的個數(shù)。

定義7 A（r）函數(shù)：r是關(guān)聯(lián)圖中的一個規(guī)則節(jié)點，函數(shù)的返回值是關(guān)聯(lián)圖中規(guī)則r的條件斷言函數(shù)的活化前件ri（在條件斷言函數(shù)的返回值為真的情況下），也就是說在關(guān)聯(lián)圖中存在著從ri到r的活化邊。如果在關(guān)聯(lián)圖中，規(guī)則r沒有條件斷言函數(shù)活化前件，則返回值為0。

定義8 T（r）函數(shù)：r是關(guān)聯(lián)圖中的一個規(guī)則節(jié)點，函數(shù)的返回值是關(guān)聯(lián)圖中r的觸發(fā)節(jié)點rj，也就是說在關(guān)聯(lián)圖中存在著從rj到r的觸發(fā)邊。如果在關(guān)聯(lián)圖中，r沒有觸發(fā)節(jié)點，則返回值為0。

定義9 在一個關(guān)聯(lián)圖中，一個規(guī)則節(jié)點r調(diào)用A（r）函數(shù)或者T（r）函數(shù)，如果返回值為0，那么規(guī)則r不是自依賴規(guī)則。

定義10 一條規(guī)則r的反向觸發(fā)活化閉包記作r＊，定義如下：

（1）r0＝｛r｝；

（2）rn＝ ｛A（rn－1），T（rn－1）｝；

（3）r＊＝∪n≥0rn；

定義11 在關(guān)聯(lián)圖G中，如果規(guī)則ri是規(guī)則rj的條件斷言函數(shù)的活化前件，并且規(guī)則rj的條件斷言函數(shù)Asservation（G，rj）的返回值為真，那么，ri稱作rj的直接活化節(jié)點，而ri的反向觸發(fā)活化閉包中的所有規(guī)則節(jié)點，則稱作規(guī)則rj的間接活化節(jié)點。

定義12 設(shè)r是一個觸發(fā)環(huán)中的節(jié)點，如果r被調(diào)度執(zhí)行以后不會被再次調(diào)度執(zhí)行，稱規(guī)則r是觸發(fā)環(huán)中的一個斷點。

定義13 規(guī)則r的直接或者間接活化節(jié)點調(diào)用函數(shù)T或者函數(shù)A，如果它的返回值為0，那么規(guī)則r不是自依賴規(guī)則。

定義14 將一條規(guī)則節(jié)點r的活化節(jié)點作為一棵二叉樹的根節(jié)點，調(diào)用函數(shù)A，得到的規(guī)則節(jié)點ri作為r的右孩子節(jié)點，調(diào)用函數(shù)T，得到的規(guī)則節(jié)點rj作為r的左孩子節(jié)點，然后再對規(guī)則節(jié)點ri和rj調(diào)用函數(shù)T和A，得到的規(guī)則節(jié)點分別作為ri和rj的左孩子節(jié)點和右孩子節(jié)點，如此遞歸進行，從而形成了一棵二叉樹，稱這個過程為二叉樹的形成過程。

定義15 在二叉樹的形成過程中，作為具有同一父節(jié)點的兄弟節(jié)點，規(guī)定右孩子為活化節(jié)點，左孩子為觸發(fā)節(jié)點，即右孩子對父節(jié)點起活化作用，稱為間接活化節(jié)點的活化節(jié)點（根據(jù)二叉樹形成的定義，二叉樹的根節(jié)點是一個規(guī)則節(jié)點的直接活化節(jié)點，所以二叉樹中的活化節(jié)點稱作間接活化節(jié)點的活化節(jié)點），左孩子對父節(jié)點起到了觸發(fā)作用，稱為間接活化節(jié)點的觸發(fā)節(jié)點。

定義16 在一棵二叉樹中，節(jié)點e的路徑長度是指從根節(jié)點到e之間的弧的個數(shù)。

定義17 在一棵以r1為根節(jié)點的二叉樹T0（V0，E0，S0）中，令 T1（V1，E1，S1）為r1的左子樹，在對T1進行中序遍歷的過程中訪問的最后一個節(jié)點，稱作二叉樹T0的左關(guān)鍵節(jié)點。

在圖5中，T0的左關(guān)鍵節(jié)點是r5，因為對r的左子樹的中序遍歷的訪問次序是：r4，r2，r5，其中r5是訪問的最后一個規(guī)則節(jié)點。

Figure 5 Key nodes graph圖5 關(guān)鍵節(jié)點圖

定義18 在一棵以r為根節(jié)點的二叉樹T0（V0，E0，S0）中，令 T2（V2，E2，S2）為r1的右子樹，在對T2進行中序遍歷的過程中訪問的最后一個節(jié)點，稱作二叉樹T0的右關(guān)鍵節(jié)點，稱作二叉樹T0的右關(guān)鍵節(jié)點。

在圖5中T0的右關(guān)鍵節(jié)點是r3，因為對r的右子樹的中序遍歷的訪問次序是r6，r3，其中r3是訪問的最后一個規(guī)則節(jié)點。

定理2 如果一個觸發(fā)環(huán)C上的規(guī)則節(jié)點r是自依賴規(guī)則，那么在對r的條件斷言活化前件ri遞歸調(diào)用函數(shù)A和函數(shù)T所形成的二叉樹中，必然會形成這樣一棵二叉樹，該二叉樹的所有葉節(jié)點都落在觸發(fā)環(huán)C上［16］。

定理3 在對一個關(guān)聯(lián)圖中的規(guī)則節(jié)點r遞歸調(diào)用函數(shù)A和函數(shù)T形成二叉樹的過程中，如果新繁衍的葉節(jié)點是其祖先節(jié)點，則規(guī)則r不是自依賴規(guī)則［14］。

定理4 在觸發(fā)環(huán)中的一條規(guī)則的條件斷言函數(shù)的活化前件r對函數(shù)A和T的調(diào)用所形成的二叉樹中，有兩個具有同一父節(jié)點的兄弟節(jié)點ri、rj，若它們都是觸發(fā)環(huán)中的節(jié)點且｜ri（或rj）的路徑長度｜－｜觸發(fā)環(huán)中rj（或rj）距r的距離｜≥0，則規(guī)則r不是自依賴規(guī)則［16］。

推論1 在由于對觸發(fā)環(huán)中的規(guī)則r的函數(shù)A和T的遞歸調(diào)用所形成的二叉樹中，有兩個具有同一父節(jié)點的兄弟節(jié)點ri，rj。若它們都是觸發(fā)環(huán)中的節(jié)點，且｜ri（或rj）的路徑長度｜－｜觸發(fā)環(huán)中rj到r的距離｜＜0，則規(guī)則r有可能不是觸發(fā)環(huán)中的斷點。

圖6描述了一種簡單的符合定理4的例子，下面來考察一下規(guī)則r1是否為自依賴規(guī)則?？梢钥吹剑?guī)則r1由規(guī)則r9活化，即規(guī)則r9是規(guī)則r1條件斷言活化前件，r2和r3是兄弟，它們既是二叉樹中的節(jié)點，也是觸發(fā)圖中的節(jié)點。r1的執(zhí)行導(dǎo)致了r2的執(zhí)行，r2觸發(fā)r3，r3活化r7，而r3的執(zhí)行觸發(fā)了r7與r4，此時，r4、r7同時合格，｜二叉樹中r2的路徑長度（為2）｜＜｜觸發(fā)環(huán)中r3到r1的距離（為3）｜；r7和r8是兄弟，r7剛才已經(jīng)分析過了，它不影響r1是否為自觸發(fā)規(guī)則的判斷，r8被r3活化，r3的路徑長度為3，r8被規(guī)則r6觸發(fā)，r6到r1的距離為1，即｜二叉樹中r3的路徑長度（為3）｜＞｜觸發(fā)環(huán)中r6到r1的距離（為1）｜，在生成樹中只要有一對具有相同父節(jié)點的節(jié)點滿足條件，那么規(guī)則r1就可以斷定不是自依賴規(guī)則。

Figure 6 Relationship I between distance and path length圖6 路徑長度與距離的關(guān)系Ⅰ

在前面的敘述中其實已經(jīng)說明了推論1的內(nèi)容，雖然｜二叉樹中r2的路徑長度（為2）｜＜｜觸發(fā)環(huán)中r3到r1的距離（為3）｜，但規(guī)則r1并不是自依賴規(guī)則，其原因在于在這棵生成二叉樹中，并不是所有的具有相同根節(jié)點的節(jié)點都滿足這一點，只要存在這么一對節(jié)點，都會導(dǎo)致節(jié)點r1不是自依賴規(guī)則。我們給出的定理4恰好就是基于這個假設(shè)的。

圖7就是推論1的另外一種情況，對規(guī)則r1遞歸調(diào)用函數(shù)A和T得到一顆生成二叉樹，可以看到，這棵二叉樹中r2和r3具有同一個父節(jié)點r6，r2的路徑長度為2，r3到r1的距離為3，規(guī)則r6是這棵二叉樹中唯一的非終端節(jié)點，在這種情況下，規(guī)則r1就是自依賴規(guī)則。

定理5 對觸發(fā)環(huán)中的節(jié)點r遞歸調(diào)用函數(shù)A和T得到的二叉樹，葉節(jié)點都落在觸發(fā)環(huán)上，在二叉樹中，如果存在使同一個節(jié)點合格的左右子樹的深度之差大于（觸發(fā)環(huán)中）左子樹最深葉節(jié)點與右子樹中最深葉節(jié)點兩者的距離，則規(guī)則r不是自依賴規(guī)則。

Figure 7 Relationship II between distance and path length圖7 路徑長度與距離的關(guān)系Ⅱ

證明 設(shè)二叉樹中規(guī)則r的左右子樹深度之差（｜左子樹深度－右子樹深度｜）為m，r的左子樹葉節(jié)點的最右邊的節(jié)點為rp（即r的左孩子中距根節(jié)點最遠的節(jié)點），r的右子樹葉節(jié)點的最右邊的節(jié)點為rq（即r的右孩子中距根節(jié)點最遠的節(jié)點），若使r合格的左右子樹的深度之差＞（觸發(fā)環(huán)中）左子樹中最遠的節(jié)點與右子樹中最遠的節(jié)點兩者的距離＞0，則意味著觸發(fā)環(huán)中r執(zhí)行以后，右子樹的rq首先合格，rq執(zhí)行以后，觸發(fā)環(huán)中rq節(jié)點的下一個節(jié)點rl合格，同時，二叉樹中rq的父節(jié)點合格。根據(jù)拓撲關(guān)系，必須在rq的父節(jié)點和rl執(zhí)行完畢之后才會考慮其它節(jié)點，又由于rq、rp的距離小于r的左右子樹深度之差，所以r會在被激活之前被觸發(fā)，因此規(guī)則r不會合格，進而可以推導(dǎo)出規(guī)則r不是自依賴規(guī)則。以上證明的是在觸發(fā)環(huán)上rq＜Trp時的情況，而對于rp＜Trq時情況的證明與此類似。

證畢。

圖8就是用來說明這種情況的，在觸發(fā)環(huán)中，對r1遞歸調(diào)用函數(shù)A和函數(shù)T形成下面的結(jié)構(gòu)，可見形成的二叉樹其右子樹比左子樹深2，即｜deep（r5）－deep（r4）｜＝2，而在觸發(fā)環(huán)中，dist（r4，r5）＝1，這說明當(dāng)規(guī)則r1合格以后，在所有到達觸發(fā)環(huán)的葉子規(guī)則中r4首先合格而被執(zhí)行，r5在觸發(fā)環(huán)中的距離（為2）肯定小于r4在二叉樹中的路徑長度（為4），所以規(guī)則r1肯定先被觸發(fā)，后被活化，根據(jù)表1可知，這種觸發(fā)屬于無效觸發(fā)。

所以規(guī)則r1不是自依賴規(guī)則。

3.3 自依賴規(guī)則判定算法

3.3.1 算法思路

下面給出判定一條規(guī)則是否是自依賴規(guī)則的算法思路：其實就是前面已經(jīng)通過定義、定理的形式給出了各種不是自依賴規(guī)則的情況和是自依賴規(guī)則的情況，這里的算法思路就是前面內(nèi)容的總結(jié)。

Figure 8 Relationship between depth differences of binary tree and distance of triggering ring圖8 二叉樹中的深度差與觸發(fā)環(huán)中的距離的關(guān)系示意圖

總體來說判斷觸發(fā)環(huán)中的一條規(guī)則r是否是自依賴規(guī)則可以分為三個階段：

（1）在二叉樹的形成過程中。

①在遞歸調(diào)用函數(shù)A和T形成二叉樹的過程中，新繁衍生成的節(jié)點如果已經(jīng)在前面生成，根據(jù)定理3，可知這里的二叉樹中出現(xiàn)環(huán)狀結(jié)構(gòu)，則可以判定規(guī)則r不是自依賴規(guī)則。否則，規(guī)則r也不一定就是自依賴規(guī)則。

②在遞歸調(diào)用函數(shù)A和T形成二叉樹的過程中，如果已經(jīng)繁衍了n步，但還沒有繁衍結(jié)束，根據(jù)定理6，可以判定規(guī)則r不是自依賴規(guī)則。否則，規(guī)則r也不一定就是自依賴規(guī)則。

（2）在二叉樹生成后。

①如果生成二叉樹的葉子節(jié)點不全落在觸發(fā)環(huán)上，根據(jù)定理2可知該規(guī)則也不是自觸發(fā)規(guī)則。

②逐一考察二叉樹中的每一個非終端節(jié)點，如果其左、右子樹的深度差大于其觸發(fā)環(huán)中的距離，根據(jù)定理5，可以判定它不是自依賴規(guī)則。

③逐一考察二叉樹中的每一個非終端節(jié)點，比較其左、右葉子節(jié)點的路徑長度和距離。

如果右葉子節(jié)點的路徑長度（活化）＜左葉子節(jié)點的距離，根據(jù)定理4判定規(guī)則r為自依賴規(guī)則。

如果右葉子節(jié)點的路徑長度（活化）＞左葉子節(jié)點的距離，這僅僅是判定規(guī)則r是自依賴規(guī)則的必要條件，如果二叉樹中的所有非終端節(jié)點全部滿足這個條件，那么這個條件就變成了充分條件。根據(jù)推論4判定規(guī)則r為自依賴規(guī)則。否則，不是自依賴規(guī)則。

（3）其它情況。

如果一個觸發(fā)環(huán)中已經(jīng)判定其中一條規(guī)則已經(jīng)是自依賴規(guī)則，根據(jù)定理7，可以判定觸發(fā)環(huán)中的所有規(guī)則都是自依賴規(guī)則；反之也成立。

3.3.2 算法實現(xiàn)

算法1 自依賴規(guī)則的判定算法

輸入 規(guī)則r、關(guān)聯(lián)圖（用鄰接矩陣作為存儲結(jié)構(gòu)）

輸出 如果規(guī)則r是自依賴規(guī)則，返回值是True，否則返回False。

步驟

（1）歸約規(guī)則集

G＝CreatGraph（）；／／利用初始規(guī)則集構(gòu)造一個關(guān)聯(lián)圖

R＝basic＿reduce（G）；／／對初始關(guān)聯(lián)圖進行歸約

if R＝?then｛printf（“這個規(guī)則集是可歸約的，是可以終止的”）；

return（True）；／／不存在自依賴規(guī)則｝；

else｛G＝CreatGraph（）；／＊然后利用歸約以后的規(guī)則集再構(gòu)造關(guān)聯(lián)圖＊／轉(zhuǎn)步驟（2）；｝

（2）找到關(guān)聯(lián)圖G中的所有包含規(guī)則r的觸發(fā)環(huán)

for i＝1 to｜R｜／＊｜R｜為歸約以后規(guī)則集合中規(guī)則的

數(shù)目＊／

｛找第i個節(jié)點的所在的環(huán)，把找到的環(huán)添加到集合

Ui中，這里找到的環(huán)可能不止一個，｜Ui｜就表示集

合中的元素數(shù)目。｝

（3）生成二叉樹并判定

num＝1；／／num用來統(tǒng)計繁衍的步數(shù)

for i＝1to｜R｜｛／＊分別用來判斷每一條規(guī)則是不是

自依賴規(guī)則＊／

flag＝true；

for j＝i to｜Ui｜｛

num＝1；／／num用來統(tǒng)計繁衍的步數(shù)

U′i＝?；／／繁衍生成的節(jié)點集合

r′i＝ A（ri）；r′j＝ T（ri）；

while（r′i?Uior r′j?Ui）｛／＊當(dāng)繁衍節(jié)點落到觸發(fā)環(huán)則終止循環(huán)＊／

if r′i?U′ior r′j?U′ithen ｛flag＝False；return（False）；｝

else｛／＊把繁衍生成的節(jié)點添加到集合U′i中，并構(gòu)造邏輯上的二叉樹；＊／

num＝num＋1；

if num＞｜R｜｛flag＝False；return（False）；｝｝｝；

／／對生成的二叉樹進行判定

if U′i＝?then return（False）；

else

for i＝1to｜U′i｜

if length（leftchild（ri））＜length（rightchild

（rj））｛falg＝False；return（False）；｝

／＊length函數(shù)用來計算節(jié)點的二叉樹中節(jié)點的路徑長度＊／

if｜length（r′i）－length（r′j）｜＞｜distance（r′i）－distance（r′j）｜ then ｛flag ＝ False；return（False）；｝

／＊r′i，r′j在 while循環(huán)結(jié)束以后保存的是剛才生成的二叉樹的終端節(jié)點＊／

／＊distance函數(shù)用來計算二叉樹終端節(jié)點在觸發(fā)環(huán)中的距離＊／

if flag＝True break；／＊如果在當(dāng)前正在判定的觸發(fā)環(huán)中有一條規(guī)則是自依賴規(guī)則，則無需判定剩下的規(guī)則了，其它的全是自依賴規(guī)則＊／｝

4 結(jié)束語

ECA規(guī)則終止性問題是主動數(shù)據(jù)庫中一個關(guān)鍵問題，在不可歸約規(guī)則集中，如果歸約以后規(guī)則集為空，說明該關(guān)聯(lián)圖中不存在環(huán)，這肯定是終止的。但是，上述結(jié)論不能推出如果關(guān)聯(lián)圖中存在環(huán)就一定不終止。換句話說，就是到目前為止能知道的是規(guī)則集如果想終止就必須無環(huán)，但存在環(huán)未必不終止。經(jīng)過歸約以后的不可規(guī)約規(guī)則集就變成了許多個”環(huán)狀”的規(guī)則集，分析這樣的規(guī)則集的終止性是富有挑戰(zhàn)性的一項工作。本文就是在這樣的一種情況下，在借鑒文獻［14，15］相關(guān)思想的基礎(chǔ)上，對其中的能夠形成環(huán)狀結(jié)構(gòu)的自觸發(fā)規(guī)則給出了詳細的討論，并通過一個算法找出了在不可歸約集中的一種環(huán)，它是由自觸發(fā)規(guī)則引發(fā)的不終止性。解決的辦法就是把自觸發(fā)規(guī)則單獨處理以便打斷這個環(huán)從而使規(guī)則集終止。顯然這對規(guī)則的終止性分析是有十分積極意義的。

［1］ Baralis E，Widom J.An algebraic approach to rule analysis in expert database systems［C］∥Proc of the 20th International Conference on Very Large Data Bases，1994：475－486.

［2］ Hao Zhong－xiao.Theory of active database［M］.Beijing：Science Press，2009.（in Chinese）

［3］ Xiong Zhong－min，Hao Zhong－xiao.Determination of termination for a rule set based on conditional formula［J］.Journal of Harbin Institute of Technology，2009，41（5）：221－225.（in Chinese）

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

［5］ Vanduva A，Gatziu S，Dittrich K R.Investigating termina－tion in active database systems with expressive rule languages［C］∥Proc of International Workshop on Rule in Database Systems，1997：149－164.

［6］ Lee S Y，Ling T W.A path removing technique for detecting trigger termination［C］∥Proc of International Conference on Extend Database Technology（EDBT），1998：341－355.

［7］ Lee S Y，Ling T W.Unrolling cycle to decide trigger termination［C］∥Proc of the 25th VLDB Conference，1999：483－493.

［8］ Aiken A，Widom J，Hellerstein J M.Behavior of database production rules：Termination，confluence and observable determinism［C］∥Proc of the ACM SIGMOD International Conference on Management of Data，1992：59－68.

［9］ Lee S Y，Ling T W.Refined termination decision in active databse［C］∥Proc of International Conference on Database and Expert Systems Application（DEXA），1997：182－191.

［10］ Bailey J，Dong G，Ramamohanarao K.Deciability and undecidability result for the termination problem of active databases［C］∥Proc of the 17th ACM SIGMOD－SIGACT－SIGART Symposium on Principles of Database Systems，1998：264－273.

［11］ Wang Rui－xiang.Dependency problem of active database［D］.Qiqihar：Qiqihar University，2003.（in Chinese）

［12］ Yan Wei－min.Data structure［M］.Beijing：Tsinghua University Press，1999.（in Chinese）

［13］ Baralis E，Ceri S，Monteleone G，et al.An intelligent database system application：The design of EMS［C］∥Applications of Database LNCS，1994：172－189.

［14］ Barakis R，Ceri S，Paraboschi S.Improved rule analysis by means of triggering and activation graph［C］∥Rules in Database Systems，Lecture Note in Computer Science，1995：165－181.

［15］ Zuo Wan－li，Liu Ju－h(huán)ong，Liu Shu－fen.Relationship graph and termination analysis for active rules set［J］.Journal of Software，2001，12（2）：276－282.

［16］ Zhou Tao.Active rules design and analysis of active database in object－oriented database［D］.Qiqihar：Qiqihar University，2004.（in Chinese）

［17］ Karamimce A P，Urban S D.Refined triggering graph：A logic－based approach to termination analysis in an active object－oriented database［C］∥Proc of the 12th International Conference on Data Engineering（ICDE），1996：384－391.

［18］ Baralis E，Ceri S，Paraboschi S.Improved rule analysis by means of triggering and activation graph［C］∥Proc of International Workshop Rules in Database Systems（RIDS），1995，985：163－181.

［19］ Aiken A，Hellerstein J M，Widom J.Static analysis techniques for predicting the behaviour of active database rules［J］.ACM TODS，1995，20（1）：3－41.

附中文參考文獻：

［2］ 郝忠孝.主動數(shù)據(jù)庫理論基礎(chǔ)［M］.北京：科學(xué)出版社，2009.

［3］ 熊中敏，郝忠孝.基于條件公式的主動規(guī)則集可終止性判定［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2009，41（5）：221－225.

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

［11］ 王瑞祥.主動數(shù)據(jù)庫中的依賴問題［D］.齊齊哈爾：齊齊哈爾大學(xué)，2003.

［12］ 嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)［M］.北京：清華大學(xué)出版社，1999.

［16］ 周濤，面向?qū)ο蟮闹鲃訑?shù)據(jù)庫中主動規(guī)則的設(shè)計和分析［D］.齊齊哈爾：齊齊哈爾大學(xué)，2004.