主動規(guī)則集的可終止性分析

主動規(guī)則集的可終止性分析

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