一种新的判定主动规则集可终止性的方法_第1页
一种新的判定主动规则集可终止性的方法_第2页
一种新的判定主动规则集可终止性的方法_第3页
一种新的判定主动规则集可终止性的方法_第4页
一种新的判定主动规则集可终止性的方法_第5页
已阅读5页,还剩1页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

一种新的判定主动规则集可终止性的方法

由于相互触发行为的相互触发,规则集中规则的无限期执行可能是不可能的。由于对规则集描述的无结构化,规则集的可终止性问题已成为一个难题。现有的研究工作有一定的局限性。在文献中,tg是通过分析触发图(tg)而制定的。然而,由于所见的活动规则并非孤立于无限的状态,而应该与所建规则同时且无限,因此计算的不可归因的规则集可以进一步归因。也就是说,当一个令人困惑的规则集被评估为不完整时,它被认为是一个不完整的规则。文献提出了创建ag地图的技能,并提出了文献提出的方法,但这些规则没有得到满足。在文献中,基于tg和ag图分析的问题解决了这个问题,但由于tg和ag图之间的关系没有考虑,因此没有解决上述问题。在文献中,基于事实的规则集的可最终确定并不考虑规则之间的激活关系,而没有解决上述问题。在计算不可归因规则集时,文献考虑了上述缺陷,但未能直接应用于规则集的可最终确定算法。本文以激活可达、激活路径、盲活动环和盲活动规则为基础,介绍了一种新的动态规则集可最终评价方法,使规则集的静和动态分析更加完善、高效。举一个实例说明文中的思想.例1图1中含有2个TG环R1{r1,r2,r3}、R2{r4,r5,r6}和一个AG环R′1{r1,r2,r4,r3}.触发边用实线表示,活化边用虚线表示,图中表示的规则都是自惰化规则.在所述的规则执行语义下,R1和R2不能同时同步执行.运用文献中的归约算法,不能消除任何一条边,即文献判定此规则集具有不可终止性.当R1中任一规则被系统触发时,r4不能同时被触发.由于不能得到来自r4的活化作用,r3的条件在自惰化后变为假.R1因为r3的可终止执行而终止.此时由于不存在任何一个不可终止TG环,此规则集是可终止的.同样地,若R2中任一规则被系统触发,此规则集也是可终止的,即此规则集总表现出可终止性.文献由于没有考虑活化关系,故不能对该规则集作可终止性判定.文献虽然可以通过不可归约规则集进行正确判定,但需要大量的计算工作.文中的方法将直接对此规则集的可终止性作准确的判定.1规则的积极执行1.1规则学习和执行主动规则的结构遵循event-condition-action范型.event表示规则的触发事件,通常为数据操作事件;condition表示规则条件,常表示为数据库查询语句;action表示规则的执行动作,通常由一组数据更新操作组成.ri和rj分别表示2个规则,考虑如下2种关系:1)若ri的动作中含有rj的触发事件,则称ri可触发rj;2)若ri的动作的执行可能使rj的条件为真,则称ri可活化rj.这2种关系可分别描述为2种有向图,即触发图(TG)和活化图(AG).自惰化规则指其动作的执行使其自身条件为假的一类规则.1.2环策略及过程耦合模式(couplingmode)指定条件部分的评估时刻(E-C耦合)或动作部分的执行时刻(C-A耦合).最流行的模式为立即方式和延迟方式.本文将E-C耦合和C-A耦合均指定为立即方式,即条件在触发事件出现后立即进行评价或动作在条件评估为真后立即执行.环策略(cyclepolicy)描述当条件评估或动作执行过程中有事件发生时系统如何反应.系统通常对耦合模式为立即方式的规则采取递归方式的环策略.在这种情况下,若条件评估或动作执行过程中有事件发生会导致条件评估或动作执行暂时中止,结果使得监控这些事件的规则能尽快地被系统处理.规则评价的调度阶段(scheduling)决定当有多个规则被同时触发时系统如何反应.若调度方式选择为全部有序方式(allsequential),则系统按序激发所有规则实例.本文采用全部有序调度方式.采取的规则处理过程(rulesprocess)如下,当规则被触发时,系统立即评估其条件.若条件可满足,系统将此规则从已触发规则集中消除并立即执行其动作;若条件不满足,采取事件消耗策略(event-consuming),即系统将此规则从已触发规则集中消除.2规则rj活动例2图2表示一个规则集的触发图和活化图,实线表示触发弧,虚线表示活化弧.由于图2中每个规则都处于一个触发环中,并且每次自惰化后均可以再次被活化,文献判定此规则集可能是不可终止的.{r4,r5}是唯一的一个在TG图和AG图中均为环的规则集,根据文献可推断r1和r3应能由{r4,r5}可达.但直接根据文献中关于一个规则由一个规则集可达的概念并不能得出此结论,因为此规则集中不存在这样的2个规则ra和rt,它们均可由{r4,r5}可达,当rj为r1或r3时,使得<ra,rj>∈AG和<rt,rj>∈TG.为克服文献的不足,提出触发可达和活化可达的概念.定义1若规则集R中存在一个规则ri且有<ri,rj>∈TG,则称规则rj可由规则集R直接触发可达;若规则rj可由规则集R直接触发可达,或存在可由R直接触发可达的一个规则rt,使得<rt,rj>∈TG,则称规则rj由R触发可达.例3在图1中,r1可由{r1,r2,r3}直接触发可达,亦即可由{r1,r2,r3}触发可达.定义2若规则集R中存在一个规则ri且有<ri,rj>∈AG,则称规则rj可由规则集R直接活化可达;若规则rj可由规则集R直接活化可达或存在可由R直接活化可达的一个规则ra使得<ra,rj>∈AG,则称规则rj由R活化可达.例4在图1中,r4可由{r1,r2,r3}直接活化可达,r5和r6可由{r1,r2,r3}活化可达.定义3若存在<ri,rj>∈TG,则称规则ri是rj的触发规则;若存在<ri,rj>∈AG,则称规则ri是rj的活化规则.例5在图1中,r1既是r2的触发规则,也是r2的活化规则.定义4在TG图中,形如<r0,…,rn,r0>的路径称之为TG环;在AG图中,形如<r0,…,rn,r0>的路径称之为AG环.例6在图1中,<r1,r2,r3,r1>是一个TG环,<r1,r2,r4,r3,r1>是一个AG环.定理1在AG图中,若规则r不在任何一个AG环中且不被任一个AG环活化可达,则r必有限次执行.若一个规则可活化另一个规则,这种活化关系可以无限次地或有限次地被维持.仅仅知道一个规则能被另一个规则活化是不够的,为了表达规则之间的可无限次维持的活化关系,根据定理1提出了活化路径和活化路径集的概念.定义5若ra是r的一个活化规则,与活化边<ra,r>∈AG相关的活化路径Pa定义如下:1)若ra包含在一个活化环Ra中,则Pa表示为Ra;2)若ra可由一个活化环Ra活化可达且ra∈Ra,则Pa表示为Ra∪p′,p′为具有下述特性的一条路径:①ra可沿p′由Ra活化可达,但p′不含Ra中任一规则;②p′是极小化的,即消除p′上任一规则,则不再具有属性A).例7在例1中,r1,r2,r3,r4和r5的活化路径均表示为AG环R′1{r1,r2,r4,r3},而r6的活化路径为(R′1,r5).定义6一个规则r的活化路径集由它的所有活化路径组成,记作Path-Setact(r).定理2在活化图AG中能无限次地活化r的所有路径必包含在r的活化路径集中.3可停止tg链分析3.1rt不可终止的情形定义7主动规则集R的不可归约规则集是通过运用归约算法(rulereductionalgorithm)处理后得到的一个子集.文献已经证明R中从其不可归约规则集中移出的规则必有限次执行.在后文中非特别说明,定理中所指的规则、TG环和AG环均包含在一个不可归约规则集中.对于一个TG环RT中的规则r,包含在r的活化路径中的规则可能被RT包含,或不在RT中但可由RT触发可达,或既不被RT包含也不能由RT触发可达.这些情形将决定活化路径能否与RT同步执行,进一步影响r能否受到活化作用,从而可决定RT的可终止性.定理3r为一个TG环RT中任意一个规则,若r总存在一条活化路径Pa且Pa中任一规则均被RT包含,则RT将具有非终止性.定理4r为一个TG环RT中任意一个规则,若r总存在一条活化路径Pa且Pa具有如下条件之一,则RT将具有非终止性.1)Pa中任一规则均被RT包含;2)除了含有RT中规则外,Pa中余下规则不被RT包含但可由RT触发可达.定理5r表示不可归约规则集R中TG环RT包含的一个规则,Pa表示r的任意一个活化路径且具有以下属性:除了含有被RT包含或不被RT包含但可由RT触发可达的规则外,Pa中余下规则不能由RT触发可达.则有如下结论:1)Pa中包含的不能由RT触发可达的规则必被R中另一触发环R′T包含或触发可达;2)r′表示R′T中任意一个规则,r′不能由RT触发可达;3)若R′T可终止,则RT必可终止;4)若RT不可终止,则R′T必不可终止;5)若RT总被看作是可终止的,则规则集R的可终止性判定更为准确、有效.根据定理5,将满足定理5条件的TG环RT看作是可终止的.从而得到如下推论:推论1r为一个触发环RT中任意一个规则,若r总存在一条活化路径Pa且Pa中的任一规则可由RT触发可达,则RT将具有非终止性.否则,RT必可终止.3.2禁止活化规则定理6RA表示不可归约规则集R中任意一个AG环.若RA中任一规则可由一个TG环RT触发可达,则RA将具有非终止性.否则,RA必可终止.定义8一个可终止的AG环称之为禁止AG环.例8在例1中,活化环R′1是一个禁止AG环.定理7r为不在任何一个AG环中的任意一个规则.若r可由一个AG环RA活化可达,并且r和RA中任一规则均可由一个TG环RT触发可达,则r可能无限次执行.否则,r必有限次执行.定义9一个只可有限次执行的活化规则称之为禁止活化规则.例9在例1中,r5只可由R′1活化可达且R′1是一个禁止AG环,可推断r5是一个禁止活化规则.定义10一个不含任何禁止AG环和任何禁止活化规则的活化路径称为有效活化路径.定理8r表示一个TG环RT中的任意一个规则.若r总存在一个有效活化路径Pa且Pa中任一规则可由RT触发可达,则RT将具有非终止性.否则,RT必可终止.证明1)若r总存在一个有效活化路径Pa,由定理6、定义8、定理7、定义9可知Pa中AG环和活化规则均可由一个TG环触发可达.A)若此TG环即为RT,则由推论1可知RT具有非终止性;B)若此TG环不为RT,则由推论1可知RT具有可终止性.2)若r不存在任何一个有效活化路径,由定理6、定义8、定理7、定义9可知中r中的任一活化路径P中必存在一个禁止AG环,或一个禁止活化规则.a)若存在一个禁止AG环,由定理6、定义8可知P中必有一个规则(即P中所含禁止AG环中一个规则)不为任何TG环触发可达,即不为RT触发可达;b)若存在一个禁止活化规则,由定理7、定义9可知P中必有一个规则不与任何AG环被同一个TG环触发可达,即不为RT触发可达.由推论1可知在a)和b)情况下RT均具有可终止性.由1)和2)可知结论成立.4基于活化路径的算法实现R表示一个任意的不可归约规则集,同时定义2个集合:ST={RT|RT是R中的一个TG环},SA={RA|RA是R中的一个AG环}.基于定理6~8,本文提出了一个主动规则集可终止性判定算法.TG环RT中所有规则形成集合记作Rules-Set(RT),算法中Rules-Set对其他变量的意义依此类推.算法RefinedTermi-test输入:TG环集ST和AG环集SA输出:若R是可终止的,则输出true;否则,输出false2)For每一个不被任何AG环包含的规则r∈RDo注意算法中计算一个TG环触发可达的规则集时,可选取此触发环上任一规则为起始顶点,按已知的有向图搜索算法遍历TG图,所能访问到的所有规则形成的集合即为所求.类似地可计算一个AG环活化可达的规则集.为突现该算法思想和描述算法的简便,未考虑此步的具体算法实现.判断一个规则能否由一个TG环(或AG环)触发可达(或活化可达),可通过一个元素能否为集合包含的逻辑判断实现,故将此操作看作基本操作.另外,规则r的活化路径集的求法可通过选取r为起始顶点,在有向图AG中采取逆向深度优先搜索方法,每搜索至活化环上某一点,表明得到了一个活化路径.同样,本文未考虑此步的具体算法实现.定理9算法是正确的、可终止的,其时间复杂度为O(m×p×q),m表示TG环的个数,p表示规则个数,q表示R中规则的活化路径的最大个数.证明正确性.由定理6知步骤1)是正确的;由定理7知步骤2)是正确的;由定理8知步骤3)是正确的.即算法是正确的.可终止性.因为不可归约规则集R中TG环个数、AG环个数、主动规则的个数、规则的活化路径个数都是有限的,故算法1可自动终止.时间复杂度分析.很明显算法的时间复杂度由步骤3)决定.最坏情况下每个规则都可由任一触发环触发可达且每个规则都不存在一条有效路径Pa使得Pa中任一规则可由某一触发环包含或触发可达,此时步骤3)中的语句执行的最多次数为(m×p×q).故算法的时间复杂度可表示为O(m×p×q).例10利用算法分析例1.1)R′1中规则r1、r2、r3只能由R1触发可达,而r4只能由R2触发可达,故算法步骤1)判定R′1是禁止AG环.2)因为R′1是规则集中唯一的AG环且是禁止的,r5和r6只能由R′1活化可达,故算法步骤2)判定它们都是禁止活化规则.3)对TG环R1来说,它包含的所有规则都只有一个活化路径R′1.因为R′1是禁止的,所以无任何规则具有有效活化路径,故算法步

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论