陸惠玲，周 濤

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

1 引言

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

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

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

2 基本概念

觸發(fā)圖TG（Triggering Graph）、觸發(fā)邊TE（Triggering Edge）、活 化 圖 AG （Activation Graph）、活化邊AE（Activation Edge）、惰化圖DG（Deactivation Graph）和惰化邊 DE（Deactivation Edge）是主動(dòng)規(guī)則ECA分析的主要手段，其概念參見(jiàn)文獻(xiàn)［1，11，12］。在惰化圖中，大多數(shù)惰化邊都是自惰化的，當(dāng)然也有例外，特別是一個(gè)不包含條件成分的規(guī)則都是自惰化的。活化邊和惰化邊不會(huì)同時(shí)存在，即如果（Vri，Vrj）∈AE，則（Vri，Vrj）?DE，反之亦然。在觸發(fā)圖中，文獻(xiàn)［13］證明了觸發(fā)環(huán)是規(guī)則非終止性的必要條件，如果TG中沒(méi)有環(huán)，則規(guī)則執(zhí)行必然終止。僅考慮TG圖，相當(dāng)于假定觸發(fā)時(shí)條件為真，動(dòng)作必然執(zhí)行，TG環(huán)意味著非終止。引入AG圖，觸發(fā)環(huán)中沒(méi)有到達(dá)活化邊的規(guī)則在被觸發(fā)時(shí)條件為假，動(dòng)作不會(huì)執(zhí)行，TG環(huán)未必導(dǎo)致非終止。進(jìn)一步，引入DG圖后，根據(jù)活化邊與惰化邊之間的相對(duì)次序，TG環(huán)中只含有到達(dá)活化邊和惰化邊規(guī)則在被觸發(fā)時(shí)條件仍然可能為假，動(dòng)作不會(huì)執(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中的活化邊和惰化邊對(duì)ECA規(guī)則r中條件的影響通過(guò)構(gòu)造斷言函數(shù)來(lái)表達(dá)。規(guī)定斷言函數(shù)的返回值有True、False兩個(gè)：如果規(guī)則r先被惰化，然后被活化（也就是說(shuō)惰化邊先到、活化邊后到），那么條件斷言函數(shù)的返回值為True；如果規(guī)則r先被活化，然后被惰化（也就是說(shuō)活化邊先到、惰化邊后到），那么條件斷言函數(shù)的返回值為False。還有兩種特殊情況，一種就是只有一條活化邊到達(dá)的情況，那么函數(shù)的返回值肯定為True；另外一種就是只有惰化邊到達(dá)的情況，那么函數(shù)的返回值肯定為False。

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

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

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

圖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 鄰接矩陣的存儲(chǔ)結(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所示的例子中，按照文獻(xiàn)［13］所述的算法，這個(gè)圖是不可能規(guī)約的，判定為非終止的。若規(guī)則r3的執(zhí)行使得規(guī)則r1的條件為假，則非終止性情況就會(huì)發(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ā)生的時(shí)刻不能早于條件為真的時(shí)刻，那么稱這樣的規(guī)則為合格規(guī)則。

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

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

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

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

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

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

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

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

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

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

3.2 算法基礎(chǔ)

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

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

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

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

定義9 在一個(gè)關(guān)聯(lián)圖中，一個(gè)規(guī)則節(jié)點(diǎn)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é)點(diǎn)，而ri的反向觸發(fā)活化閉包中的所有規(guī)則節(jié)點(diǎn)，則稱作規(guī)則rj的間接活化節(jié)點(diǎn)。

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

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

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

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

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

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

在圖5中，T0的左關(guān)鍵節(jié)點(diǎn)是r5，因?yàn)閷?duì)r的左子樹(shù)的中序遍歷的訪問(wèn)次序是：r4，r2，r5，其中r5是訪問(wèn)的最后一個(gè)規(guī)則節(jié)點(diǎn)。

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

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

在圖5中T0的右關(guān)鍵節(jié)點(diǎn)是r3，因?yàn)閷?duì)r的右子樹(shù)的中序遍歷的訪問(wèn)次序是r6，r3，其中r3是訪問(wèn)的最后一個(gè)規(guī)則節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

證畢。

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

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

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

3.3.1 算法思路

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

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

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

（1）在二叉樹(shù)的形成過(guò)程中。

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

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

（2）在二叉樹(shù)生成后。

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

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

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

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

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

（3）其它情況。

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

3.3.2 算法實(shí)現(xiàn)

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

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

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

步驟

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

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

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

if R＝?then｛printf（“這個(gè)規(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個(gè)節(jié)點(diǎn)的所在的環(huán)，把找到的環(huán)添加到集合

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

合中的元素?cái)?shù)目。｝

（3）生成二叉樹(shù)并判定

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

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

自依賴規(guī)則＊／

flag＝true；

for j＝i to｜Ui｜｛

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

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

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

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

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

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

num＝num＋1；

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

／／對(duì)生成的二叉樹(shù)進(jìn)行判定

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ù)用來(lái)計(jì)算節(jié)點(diǎn)的二叉樹(shù)中節(jié)點(diǎn)的路徑長(zhǎng)度＊／

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é)束以后保存的是剛才生成的二叉樹(shù)的終端節(jié)點(diǎn)＊／

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

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

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

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

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

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

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

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

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

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

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