主动规则集的可终止性分析

主动规则集的可终止性分析

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