主動規則集的可終止性分析

1主動規則終止性的相關研究主動數據庫嵌入數據庫“eca（事件影響操作）規則庫”，并提前集成數據庫以執行主動服務。與eca規則的結合極大地提高了系統的功能。然而，規則的處理和管理非常復雜：規則反映了任何事件的序列，規則之間相互觸發，規則處理的結果取決于事件的發生和事件的順序。為了解決這些問題，研究人員認識到，規則收集的行為必須滿足終止和流通性。通常，當規則沒有包含任何函數時，規則集將終止。匯流性意味著數據庫的最終狀態不依賴于主動規則的執行順序。主動規則的終止性,總的來說是一個較難判定的問題.最早對主動規則終止性研究的是在1992年Aiken等人的文章中,給出了基于Startbust產生式規則系統的靜態分析理論.1995年又給出了主動規則集所對應的觸發圖無環是保證終止的充分條件.1996年Karadimce等人在AOODB(activeobject-orienteddatabase)環境下,對觸發圖做了改進并應用于受限制的規則模型,同樣未對有環的觸發圖的終止性問題進行研究.文獻在研究規則匯流性問題時指出了規則執行時存在必然順序.文獻中描述了用Meta-rules管理規則間沖突的技術,指出了規則間存在的多種關系.文獻均未涉及規則集的終止性問題.在對規則進行簡單的句法分析知,即使是含環的觸發圖,其對應的規則集也有可能是可終止的.正是基于這一點,我們對此問題進行了研究,給出了一種在觸發圖含環時其對應的規則集是否可終止的判定定理和相應的算法.通過對規則及規則間相互作用的研究,給出了規則之間存在的兩種依賴關系:條件依賴、事件依賴.在此基礎上,構造了規則的執行依賴圖EDG(executiondependencygraph),把規則的執行圖和規則觸發圖TG(triggergraph)進行歸并構造了觸發-依賴圖(T-DG),還給出了依賴傳遞閉包等概念.最終給出了主動規則的終止性判定定理、算法及算法分析.2主動規則eca一個主動數據庫應用可被描述為A=〈DB,EV,R〉,其中,DB為數據庫模式,EV由事件名組成,R為主動規則集.數據庫的狀態族〈DB,EV〉表示為DS,并假設DS在R下是封閉的.一個數據庫狀態是一個二維組S=〈O,E〉,其中,O是一個持久化數據庫對象集,E是一個等待處理事件的多集.在O(E)中的單個對象(事件)表示為O(e).對象形式化定義為Ο=t0:cˉ[l1∶=t1???ln∶=tn],其中,t0是惟一的對象標識(Ο-id)?cˉ是O所屬的類,且li∶=ti(i=1,…,n)為屬性值對,這里li是屬性名,ti是li對應于O的值.可以理解類cˉ有n個屬性l1,…,ln.事件有以下形式:e=d(S0@?S1???Sn)?其中,d為事件名,S0為事件接受者的對象標識(O-id),且S1,…,Sn(n≥0)是事件參數.事件是在數據庫系統運行中的某特定時刻對系統有某種意義的“發生”,每個事件描述系統都維護一個系統支持的基本事件表,基本事件通過使用邏輯操作符和專門的事件描述符連接起來構成復合事件.為了討論方便,限定基本事件為對象狀態事件(objectstateevent):create(objectcreation),一個對象創建后立即發生.delete(objectdeletion),一個對象刪除前立即發生.update,read,access(objectupdate,read,access),在一個對象被修改、讀、通過成員函數訪問之前或者之后立即發生.事件的出現指出數據庫在變化中,而沒有事件表明數據庫到達一個穩定狀態.通常,一個數據庫狀態S=〈O,?〉被稱為靜止的數據庫狀態.任何其他的數據庫狀態S=〈O,E〉,E≠?,被稱為瞬時的數據庫狀態.主動規則描述對象怎樣對事件的發生進行響應,主動規則(ECA)句法如下:r∷ON〈事件表達〉IF〈條件評價〉THEN〈動作執行〉,r為規則名.一個主動數據庫系統通過ECA規則來管理事先指定的事件發生.一旦指定的事件發生了,相關規則的條件部分被檢測,若合格,則規則的動作部分被執行.當規則通過事件監測階段,規則等待的一個或者多個時間發生了,則稱規則被觸發(triggered).當?規?則通過了條件檢測,則稱它是符合執行條件的(eligible).用Actions(r)表示規則r的動作可能執行的操作集,Actions(r)?EV.做如下約定:①規則集的規則數有限;②規則集在給定時間內被有限次觸發;③單一規則動作終止.設R為一個主動數據庫應用的主動規則集,主動規則r∈R,r的執行將轉換數據庫狀態S=〈O,E〉到一個新的數據庫狀態S′=〈O′,E′〉.我們用S→S′來表示S通過應用主動規則r一步變換到S′.如果存在規則r∈R一步轉換S為S′,我們記為S→RS′.如果存在狀態S′有S→S′,則主動規則r被稱為在狀態S下是符合條件的.一個數據庫狀態S沒有主動規則是符合條件的,則稱該數據庫狀態為終態.令S0=〈O0,E0〉∈DS為一個固定的數據庫狀態,一個由S0開始的執行序列是一個數據庫狀態S0,S1,S2,…的序列,其中,Si→RSSi+1(i≥0).如果它有一個有限長度n≥0,且Sn是終態,則稱由S0開始的執行序列終止.如果對每一個數據庫狀態Si∈DS,由Si開始的每一個執行序列都終止,則稱一個主動應用A=〈DB,EV,R〉滿足終止性.3節點系統的模式定義1.觸發圖TG定義如下:令R表示應用A中的主動規則集,D表示應用A中所使用的事件集.一個觸發圖TG=(R,Et)是一個有向圖,其中,R是主動規則集,Et是觸發邊的集合.對任意兩個節點u,v∈R,如果存在一個事件d∈D,u產生事件e=d(…),且v消耗事件e=d(…),即u的執行可能會觸發v的執行,則有一條從u到v的弧(u,v)∈Et.由于主動規則集R的規則數和D中的事件數有限,則應用A的觸發圖TG(A)可以按照定義1構建.無環的TG是對應的規則集可終止的充分條件.定義2.設觸發圖TG=(R,Et),r∈R,則r的觸發傳遞閉包T(r)+滿足如下條件:①r∈T(r)+;②T(r)+=T(r)+∪{u|(u,v)∈Et且v∈T(r)+}.定義3.設觸發圖TG=(R,Et),r∈R,r的觸發傳遞閉包為T(r)+.若存在T(r)+,且S在TG的某個環路中,則稱T(r)+為r的含環觸發傳遞閉包,記做T-L(r)+.通過對規則及規則間相互作用的分析,我們發現規則間在規則執行時存在依賴關系.給定規則集R,規則對u,v∈R,規則u的執行并不直接觸發v,但v的每次執行都依賴于u的先行執行.我們給出2種依賴關系.定義4.設規則u,v∈R,如果u的執行是v的每次條件成立的必要條件,則稱v條件依賴于u.記做CD(u,v).定義5.設規則u,v∈R,如果e=d(…)是觸發v所需的事件,u的執行不產生e=d(…),但u的執行是產生e=d(…)的必要條件,則稱v事件依賴于u.記做ED(u,v).以上2種依賴,對不同的規則系統和數據庫模式情況會有所不同,條件依賴比較明顯,事件依賴相對要復雜些.定義6.設規則集R,執行依賴圖EDG=(R,Ed)是一個有向圖,其中R是規則集,E是依賴邊的集合.對任意兩個節點u,v∈R,如果滿足ED(u,v)或CD(u,v)或同時滿足,則有一條從u到v的弧(u,v)∈Ed,則稱v的執行依賴于u.記做D(u,v).執行依賴具有傳遞依賴性,即若v的執行依賴于u,u的執行依賴于w,則v的執行傳遞依賴于w.定義7.設執行依賴圖EDG=(R,Ed),v∈R,如果D(v)={u|(u,v)∈Ed},則稱D(v)為v的直接依賴集.定義8.設執行依賴圖EDG=(R,Ed),v∈R,v的直接依賴集為D(v),則v的依賴傳遞閉包D(v)+按如下步驟構造:①D(v)+=D(v);②D(v)+=D(v)+∪{r|(r,t)∈Ed且t∈D(v)+}.定義9.設觸發圖TG=(R,Et)和執行依賴圖EDG=(R,Ed),則觸發-依賴圖T-TG=(R,Et-d)是一個由TG和EDG歸并構成的有向多圖,其中R為TG和EDG中的頂點集,Et-d=Ed∪Et.我們給出一個例子來說明各種依賴、觸發圖(TG),執行依賴圖和觸發-依賴圖.例1.本例涉及的對象為O1=X:Cx[p,q];O2=Y:Cy[s,t];O3=Z:Cz[u,v].涉及以下規則集:r1∷ONcreate(X@…)IF…THENread(X@…);r2∷ONread(X@…)IF…THENcreate(Y@…);r3∷ONread(Z@…)IF…THENdelete(Y@…),access(X@…);r4∷ONdelete(Y@…)IF…THENupdate(Z@u=10);r5∷ONupdate(Z@…)IF…THENupdate(X@p=1);r6∷ONaccess(X@…)IFA=Z.u,A=10THENaccess(Z@…),update(Z@u=0);r7∷ONaccess(Z@…)IF…B=X.p,B=1THENread(Z@…),update(X@p=0).為了討論方便,我們僅列出了規則中和討論密切相關的部分.在以下規則中:r4事件依賴于r2,因為delete(Y@…)依賴于create(Y@…);r6條件依賴于r4,因為r6的條件檢測依賴于r4動作的執行;r7條件依賴于r5,因為r7的條件檢測依賴于r5動作的執行.由以上規則可分別得出相應的觸發圖(TG)(見圖1(a))執行依賴圖(EDG)(見圖1(b))和觸發-依賴圖(見圖1(c)).圖中,實線表示觸發邊,虛線表示依賴邊.定義10.設觸發圖TG=(R,Et),Rc={r1,r2,…,rk}為TG圖中一個環路.如果在規則的實際執行過程中,Rc并不是無限循環觸發執行,則稱Rc為非循環執行環路.定義11.設觸發圖TG=(R,Et)和執行依賴圖EDG=(R,Ed),Rc={r1,r2,…,rk}是TG圖中的一個環路,v(v∈R)的直接依賴集為D(v),如果D(Rc)=D(r1)∪D(r2)∪…∪D(rk),ri∈R(i=1,2,…,k)則稱D(Rc)為環路Rc的直接依賴集.定義12.設觸發圖TG=(R,Et),執行依賴圖EDG=(R,Ed)和觸發-依賴圖T=DG=(R,Et-d),v(v∈R)的依賴傳遞閉包為D(v)+,對TG圖中的一條環路Rc={r1,r2…,rk},如果D(Rc)+=D(r1)+∪D(r2)+∪…∪D(rk)+,ri∈R(i=1,2,…,k),則稱D(Rc)+為環路Rc的依賴傳遞閉包.例如,例1中環路{r3,r6,r7}的依賴傳遞閉包為{r2,r4,r5}.定理1.設觸發圖TG=(R,Et),r∈R,則r被無限次執行的必要條件是TG中存在r的含環觸發傳遞閉包T-L(r)+.證明.反證法.假設r被無限次執行,但TG中不存在r的含環觸發傳遞閉包.由定義2、約定①可知T(r)+為一有限集,以T(r)+中的規則為頂點構造有向圖TG(r)=(T(r)+,Er),其中,Er={(u,v)}對任意u,v∈T(r)+且(u,v)∈Et},則TG(r)為TG的一個子圖.由假設和定義3知TG(r)為一有向無環圖,如果r被無限執行,根據約定②③,則TG(r)中存在一條無限的路徑,即T(r)+中有無限個規則,和T(r)+為一有限集相矛盾.證畢.引理1.設觸發圖TG=(R,Et)和TG中的環路Rc={r1,r2,…,rk},如果環路Rc的直接依賴集D(Rc)中存在規則被有限次執行,則環路Rc為非循環執行環路.證明.假設環路Rc的直接依賴集D(Rc)中存在規則r′被有限次執行.由假設和定義11、定義7知r′∈D(Rc)=D(r1)∪D(r2)∪…∪D(rk),則至少存在某一個規則ri∈R(i=1,2,…,k),使r′∈D(ri);不失一般性,令r′∈D(r1),由定義6、定義7知,對執行依賴圖EDG=(R,Ed),(r′,r1)∈Ed且r′和r1滿足ED(r′,r1)或滿足CD(r′,r1)或同時滿足.則由定義4、定義5知r′和r1必具備下列關系之一:①r′的執行是r1每次執行條件評估為真的必要條件;②對于觸發v所需的事件e=d(…),r′的執行不產生e=d(…),但r′的執行是產生e=d(…)的必要條件;③對關系①②同時滿足.根據以上分析,r′和r1無論具備哪一種關系均具有:若r′被有限次執行,則r1只能被有限次執行,故環路Rc={r1,r2,…,rk}只能循環執行有限次.根據定義11知環路Rc為非循環執行環路.證畢.定理2.設觸發-依賴圖T-DG=(R,Et-d),觸發圖TG=(R,Et),執行依賴圖EDG=(R,Ed),Rc={r1,r2,…,rk}為TG圖中的環路,它的依賴傳遞閉包為D(Rc)+.如果對于任意r∈D(Rc)+,在TG圖中不存在規則r的含環觸發傳遞閉包T-L(r)+,則Rc為非循環執行環路.證明.根據定理1知,如果r不屬于TG圖中任何環路或者在TG圖中不存在規則r的含環觸發傳遞閉包T-L(r)+,則規則r只能被有限次執行.因此,環路Rc的直接依賴集D(Rc)中至少存在規則r′只能被有限次執行.由引理1知Rc為非循環執行環路.證畢.通過以上的討論,不難證明以下定理.定理3.如果觸發圖TG=(R,Et)中不存在環路或所有環路均為非循環執行環路,則規則集R終止.4基于駁岸的可終止性算法設計已知觸發圖TG=(R,Et)中所有環路的集合R*c={Rc1,Rc2,…,Rcn}.下面先給出判定觸發圖TG=(R,Et)中環路Rc={r1,r2,…,rk}∈R*c是否為非循環執行環路的算法.算法1.Nc-T(Rc).{非循環執行環路的判定}定理4.該算法是可終止的、正確的.算法的時間復雜度為max{O(|R|2+|Et||R|),O(|Rc|(|R|+|Ed|))}.其中;|R|為主動規則數,|Et|為觸發邊數,|Rc|為環路中的規則數,|Ed|為依賴邊?數.證明.可終止性.該算法中只有for循環,故是可自動終止的.正確性.顯然根據定理2和定義2,3,定義7,8,定義11,12保證了該算法對非循環執行環路的判定是正確的.分析.在該算法中采用十字鏈表作為圖的存儲結構.在步驟①中,R*c中所含有的規則數最多為|R|,則時間復雜度為O(|R|);步驟②中,在對圖EDG從r開始進行逆向深度優先搜索的時間復雜度為O(|R|+|Ed|),環路Rc中的規則數為|Rc|,則在執行步驟②的時間復雜度為O(|Rc|(|R|+|Ed|));步驟③中,在對圖TG從r開始做逆向深度優先搜索的時間復雜度為O(|R|+|Et|),D(Rc)*中最大規則數為|R|,則執行步驟③的時間復雜度為O(|R|2+|Et||R|).故該算法的時間復雜度為max{O(|R|2+|Et||R|),O(|Rc|(|R|+|Ed|))}.證畢.算法2.Termi-T(R).{終止性判定}定理5.算法2是可終止的、正確的.該算法的時間復雜度為max{O(|R|3+|Ed||R|2),O(n2(|R|2