（计算机应用技术专业论文）主动规则的终止性分析.pdf

哈尔滨理工大学工学硕士学位论文 主动规则的终止性分析 摘要 主动数据痒扩展了传统数据席的鼓动功能，弓 爰形魏“事 孛，条件一动 作”的主动规则( 称为e c a 规则) 来表达主动行为。事件部分指定事件序 列；条件部分提供数据库查询；动作部分通常出一个或多个修改或查询构 成。定义良好的娥刚集必须保证靛则之间的耱互触发不会无限循环下去，即 规则是可终止的。终止性反映了主动数据库系统良好的行为特性。 对主动规剩终止僚分援已有静态和动态方法，其中静态方法使用较多， 静态方法是在编译时问内检测主动规则执行的潜在非终止性。静态方法中又 包括图方法和代数分析方法，其中基于图的规则终止性分车厅主要包括触发 蹋、激活图和惰化圈以及基于触发鬻和激活图的觌翔缩减算法。本文分羽介 绍了这几种方法，并给出相应的算法、定理及其证明。 针对已有图分柝方法的局限蛙，本文介绍一萃申主动数据库规则终止性分 析的一种新方法，此方法借助于演化图分析事务与触发器之间的关系。为了 研究规则终止性和模拟规则执行又考虑到触发器信息和事务更新。提出算法 来检验规癸| | 终止性。采用演亿图来模拟规剩静态处理过程弗考虑弱激活图和 惰化图，演化图比传统的分析图提供了更细化的分析方法。给出相应算法并 证明其正确性，并证明该方法对各种规则语言都是实塌的鼹此可用于几种数 据库系统中。 最后本文提出一种分析主动规则集的终止性的模型：在演绎数据库领域 中可判定这个特性然后将其扩展传递到主动e c a 规煲习中，瓣此绘出了主动 规则终止性判定的充分条件。因为套主动规则集的计算依赖于特定系统的 特征，所以终止性分析必须考虑主动规则豹语义。我们将一套规则从已存在 系统的任意形式转换成内部形式；然后，我们将主动规舞i 泽成逻辑语句，考 虑到系统的执行语义，转换为演绎规则中已知终止性的主动过程。 关键词主动数据库；终止性；演绎数据库；事务 墼尘鎏堡三釜兰三：璧i ：兰堡尘兰 t e r m i n a t l 0 na n a l y s i so fa c t i v er u l e s a b s t r a c t a c t i v ed a t a b a s e se x t e n dt h ef u n c t i o n a l i t yo ft r a d i t i o n a l ( p a s s i v e ) d a t a b a s e s t h e yg e n e r a l l yu s ee v e n t - - c o n d i t i o n - a c t i o n ( e c a ) r u l et oe x p r e s st h e i ra c t i v e b e h a v i o u r t h ee v e n tp a r t ，w h i c h s p e c i f i e s al i s to fe v e n t s ，t h ec o n d i t i o n p a r t ，w h i c hi s aq u e r yo nt h ed a t a b a s e ，a n dt h ea c t i o n p a r t ，w h i c hg e n e r a l l y c o n s i s t so fo n eo rm o r eu p d a t e so rq u e r i e so nt h e d a t a b a s e a ni m p o r t a n ti s s u ei n d e s i g n i n gas e to fr u l e si st og e n e r a t er u l e sf o rw h i c hi ti sp o s s i b l et og u a r a n t e e r u l e sc a nn o t t r i g g e r e a c ho t h e r i n f i n i t e l y ，i e ，t h e e x e c u t i o ni s t e r m i n a t e t e r m i n a t i o nr e f l e c t sd e s i r a b l eb e h a v i o rp r o p e r t yo fa c t i v ed a t a b a s e s y s t e r n s t h e r ea r es e v e r a ls t a t i ca n dd y n a m i ca p p r o a c h e sf o ra c t i v er u l e st e r m i n a t i o n a n a l y s i s w ec o n s i d e ro n l ys t a t i cm e t h o d st h a ta tc o m p i l et i m ed e t e c tp o t e n t i a l n o n - t e r m i n a t i n ga c t i v er u l e se x e c u t i o n 。t h es t a t i ca p p r o a c h e si n c l u d eg r a p ha n d a l g e b r a i ca p p r o a c h ，a n dg r a p h i n c l u d e s t r i g g e r i n gg r a p h ，a c t i v a t i o n g r a p h ，d e a c t i v a t i o ng r a p ha n dr u l e r e d u c t i o nm e t h o db a s e do nt r i g g e r i n ga n d a c t i v a t i o ng r a p h s i nt h i sp a p e r ，w ei n t r o d u c et h e s ea p p r o a c h e sr e s p e c t i v e l ya n d p r e s e n ta l g o r i t h ma n dt h e o r e m w h i c h p r o v e dt ob ec o r r e c t i no r d e rt oo v e r c o m el i m i t a t i o no fg r a p ht e r m i n a t i o na n a l y s i sm o t h o d ，an e w m e t h o df o rr u l et e r m i n a t i o na n a l y s i sw i t h i na c t i v ed a t a b a s e si si n t r o d u c e d t h i s m e t h o da n a l y z e sh o wu s e rt r a n s a c t i o ni n f o r m a t i o na n ds t r u c t u r e sc a na f f e c t a c t i v er u l ee x e c u t i o nt e r m i n a t i o n t h ea l g o r i t h mf o rt e s t i n gr u l et e r m i n a t i o ni s p r e s e n t e d a n dp r o v e dt ob ec o r r e c t i nt h i s p a p e rt r i g g e r si n f o r m a t i o na n d t r a n s a c t i o nu p d a t e sa r ec o n s i d e r e di no r d e rt o s t u d yr u l e st e r m i n a t i o na n d s i m u l a t ee x e c u t i o n w ep r e s e n tt h ea l g o r i t h mf o rt e s t i n gr u l et e r m i n a t i o n t h e p r o p o s e da p p r o a c ht u r n so u tt ob ep r a c t i c a la n dg e n e r a lw i t hr e s p e c tt ov a r i o u s r u l e sl a n g u a g e sa n dt h u si tm a yb ea p p l i e dt om a n yd a t a b a s es y s t e m s f i n a l l y ，w eh a v ep r e s e n t e dam o d e lf o rt h ea n a l y s i so ft e r m i n a t i o no fas e to f a c t i v er u l e s ：t h ek n o w nr e s u l t sa b o u tt h e s ep r o p e r t i e si nt h ef i e l do fd e d u c t i v e d a t a b a s e sw i t ht h e i re x t e n s i o n sa r et r a n s f e r r e dt ot h ea c t i v ee c ar u l e s s ot h a t s u f f i c i e n tc o n d i t i o n sf o rt h e a c t i v er u l e st ot e r m i n a t ea r ep r o v i d e d s i n c et h e i i 星兰篓耋三奎兰兰兰堡圭兰堡建兰 c o m p u t a t i o no f as e to fa c t i v er u l e sd e p e n d so nt h ef e a t u r e so ft h es p e c i f i cs y s t e m ， t h ea n a l y s i so ft h ep r o p e r t i e so ft e r m i n a t i o nm u s tt a k ei n t oa c c o u n tt h es e m a n t i c s o ft h ea c t i v er u l e s i nt h i sp a p e r ，w et r a n s l a t eas e to fr u l e sf r o ma n yo ft h e e x i s t i n gs y s t e m si n t oa ni n t e r n a lf o r m a t ；t h e n ，w et r a n s l a t et h ea c t i v er u l e si n t o l o g i c a lc l a u s e s ，t a k i n gi n t o a c c o u n tt h e s y s t e m se x e c u t i o ns e m a n t i c s ，a n d t r a n s f e rt ot h ea c t i v e p r o c e s s k n o w ns i m p l er e s u l t sa b o u tt e r m i n a t i o na n d d e t e r m i n i s ma v a i l a b l ei nt h el i t e r a t u r ef o rd e d u c t i v er u l e s k e y w o r d sa e t i v ed a t a b a s e s ；t e r m i n a t i o n ；d e d u c t i v ed a t a b a s e s ；t r a n s a c t i o n - l i t 哈尔滨理工大学硕士学位论文原创性声明 本人郑黧声明：此处所提交的硕士学位论文主动规则终止性分析，是本 人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究工作所取得 的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究 成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方式注明。本 声明的法律结果将完全由本人承担。 作者签名 杨鹈 日期：2 伽占年弓月j 日 哈尔滨理工大学硕士学位论文使用授权书 主动规划终止性分析系本人在哈尔滨瑗工大学攻读硕士学位期间在导j l i | i 指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所有，本论文 的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨壤工大学关于保 存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子版本，允 许论文被套阅和借阅。本人授权哈尔演理工大学可以采掰影印、缩印或其饨复制 手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密躺，在年解密后适用授权书。 不保密日。 ( 请在以上相应方框内打4 ) 作嚣签名： 韧冷矽 日期：秭年琴月目 导，币签名：槲 日期：酲年，, yd 日 哈尔滨理t 大学t 学硕学位论文 1 1 课题背景 第1 章绪论 关于主动数据库【l l ( a d b ，a c t i v ed a t a b a s e ) 的研究，开始于2 0 世纪8 0 年代中 期，特别是进入9 0 年代以来，越来越受到人们的普遍关注和重视，已成为现代 数据库研究的重要领域和热点。主动数据库是相对于传统数据库而言的，它能 主动监视当i ； 尚不存在的、所希望的未来状态的出现，一旦这种状态出现，它 会按照人们预先定义的规则，执行一系列的数据操作。因而。主动数据库不仅 像传统的数据库一样存储数据，还存储了控制知识；不仅能处理过去和当前的 数据，而且还能处理关于未来的数据操作 在过去的几年中，对于主动数据库的研究集中在非传统应用的需求上，而 传统的数据库管理系统不能满足有些应用需求，如：网络管理、空中交通控 制、计算机集成制造( c i m ) 、以及工程设计等，它们要求( 作为其应用语义的 一部分) 不断地监视数据库状态的变化，并能启动相应的动作而不需要用户或 应用程序的介入。对这些应用来说，事件的监测和动作执行的时自j 有特殊要 求，还有当需要的执行动作在预设的时间内无法执行时，采取替代( 或应急) 方案的能力，对很多上述的系统同等重要。例如，在制造环境下，如果工件的 行程在特定的时b j 内无法完成，作为应急措施，流水线就得停下或减速。 在传统的数据库管理系统中，除了能主动地做一些数据的一致性和完整性 检查之外，不再有其它的主动性设施。近年来，一些商品化的数据库管理系 统，例如s q ls e r v e r 、o r a c l e 和s y b a s e 等数据库系统，都陆续引进了触发器的概 念，主动数据库技术正从实验室的研究向商品化软件开发方向发展，随着人工 智能技术的发展和面向对象设计的理念逐步深入，数据库的主动性功能正在各 种应用中发挥越来越大的作用。 主动数据库的研究中，规则作为主动数据库的核心，是主动数据库的关键 部分，最容易引起人们的注意。主动数据库之所以是主动，关键是它引入了人 工智能的知识控制，也就是为什么一个待监测的事件发生后会有一系列的数据 库操作，并且这些操作是系统自动完成的，而无须人为的干涉。所以从某种意 义上说，主动规则的研究状况直接关系着主动数据库的进展，加大对它的研究 投入可以在很大程度上促进主动数据库的研究与发展，加快主动数据库在现实 哈尔滨理t 大学t 学硕+ 学位轮文 中的应用，更好地适应实际需求，从而为经济和科技的发展做出贡献，因此， 主动规则的研究是极为重要的。而主动规则动作执行引发的事件会触发其它规 则或触发相同的规则，规则间的相互触发可能出现永久不终止的情况，从而导 致系统失败。因此系统应该保证规则的执行是可终止的。终止性反映了主动数 据库系统良好的行为特性。对主动规则的终止性分析能够帮助设计者及时发现 非终止的规则并设计出合理的规则。如何判定主动规则集的可终止性是影响主 动数据库应用的实际问题之一。 目前对主动规则终止性分析已经进行了很多研究，但离完善、实用还有一 段距离。对主动数据库规则终止性分析进行研究，解决其中的难点问题，提出 一套较好的解决方法，将会更准确的预测一个规则集合的执行规律，提高规则 处理的功能、性能和效率，进而在很大程度上促进主动数据库的研究发展，加 快主动数据库在现实中的应用，适应相应应用的需求，为经济和科技发展做出 贡献。 本研究课题是黑龙江省自然科学基金项目( f 0 0 0 6 ) 中的部分研究课题。 1 2 本课题的国内外研究现状 终止性是指主动数据库中规则动作执行引发的事件会触发其它规则或触发 相同的规则，规则日j 的相互触发可能出现永久不终止的情况，从而导致系统失 败。因此系统应该保证规则的执行是可终止的。终止性反映了主动数据库系统 良好的行为特性。 自从建立主动数据库理论以来，对主动规则终止性分析技术的研究就一直 进行着。目前对于主动规则的终止性分析主要有两大类，第一大类为静态分析 方法 2 - s l ；第二大类为动态分析方法1 6 1 。其中目前静态分析方法占主导地位。在 静态分析方法中又可分为图方法叫1 和代数方法【3 】。其中图方法中包括触发图， 激活图和惰性图。 如何判定主动规则集的可终止性是影响主动数据库应用的实际问题之一。 在主动数据库规则分析中，主动规则可终止性是一个较难判定的问题。1 9 9 2 年 最早对主动规则终止性进行研究的a a i k e n m 等人在中给出了基于s t a r t b u s t 产生 式规则系统的静态分析理论，提出的触发图，在触发图中，每一个结点表示规 则集中的一个规则，两结点问的有向弧表示一个规则的动作可能触发另一个规 则的事件的发生，从而触发此规则。若触发图中无环，则此规则集是可以终止 的。1 9 9 4 年b a r a l i s 和w i d o m l 3 l 提出的激活图，在激活图中，同样每一个结点表 哈尔演理t 大学t 学够卜学位论文 示规则集中的一条规则，只是两结点之间的有向弧表示一个规则的动作能够使 另一个规则的条件变为真。同触发图一样，若激活图中无环，则此规则集是可 以终止的。1 9 9 5 年只给出了主动规则集所对应的触发图无环是保证可终止性 的充分条件，但不是必要条件。b a r , i sc ta 1 1 7 1 将二者相结合提出规则缩减方 法。在此方法中，构造触发图和激活图，检测图中每个结点是否进入触发弧或 激活弧，如果没有则除去该结点的相应输出弧，循环检测每个结点，直到没有 可除去的弧为止，如果所有的弧都可以除去，则表示规则集是可以终止的。 1 9 9 6 年a k a r a d i m c e l 8 】等在a o o d b 环境下，对触发图作了改进并应用受限制规 则模型，同样未对有环的触发图进行研究。1 9 9 9 年a n d r e wd i n n l 9 1 等人引入了激 活图与触发图联合判定规则集的终止性问题，也没有考虑触发图中有环时，对 应的规则集运行如果仅被执行有限次，那么这个规则集可能是可终止的。1 9 9 9 年s i n y e u n gl e e 1 0 l 等人提出了活化公式的概念，并给出了计算活化公式的算 法，它没有考虑到在规则执行过程中，一个规则的动作可能会对另一规则的条 件产生影响，因此运用活化公式判定触发图有环时，将无限执行下去，对应的 规则集是不可终止的，很可能在执行的过程中一个规则的动作改变了另一规则 的条件，破坏了循环条件，从而使循环仅执行有限次，其对应的规则集可能终 止。 国内对主动数据库规则终止性的研究也取得了一些进展，不但在理论上提 出了一些算法l 1 4 1 ，并且完成了主动规则终止性分析方法的实现，如 s d a o o d b 。5 l 是中科院计算所1 9 9 7 年研制的一个面向对象的主动数据库系 统，其中就包含了主动舰则终止性分析的算法。 但目前对主动规则终止性分析技术的研究还不完善，各种方法都有其局限 性，还未能提供一种通用性强、能很好适应各种主动规则语言的规则终止性分 析方法。其方法所应用的原型系统离大范围的实际应用还有一段很长的距离， 因此需要对主动规则终止性分析方法进行进一步的研究，提高其功能、性能及 通用性。 1 3 本文概要 本文的主要研究安排如下： 第一章绪论，指出本课题研究在理论和实际应用方面的意义、国内外研究 的现状和研究采取的方法。 啥尔滨理丁大学t 学硕十学伊论文 第二章主动数据库及主动规则概述，介绍主动数据库的系统模型、体系结 构、实现途径和典型的主动数据库系统。 第三章基于图的主动规则终止性分析，给出基于触发图、激活图、惰化图 的规则终止性分析方法，并给出相应算法。 第四章基于事务的规则终止性分析，给出一种规则终止性分析的新方法， 此方法检测规则之间的三种关系包括触发关系、激活关系和惰化关系，主要研 究用户事务的信息和结构如何影响规则终止性。这种方法简单易懂并可灵活地 应用在目| j 各种主动数据库语占中。 第五章带有规则优先级的规则终止性分析，给出生成规则优先级的算法， 并用使用算法来进行规则终止性分析。 哈尔滨理t 大学t 学醪十学位论文 2 1 引言 第2 章主动数据库及主动规则概述 主动数据库是现代数据库技术的一个崭新的发展分支，数据库技术和人工 智能结合的新技术，主动数据库( a c t i v e d a t a b a s e ) 能够主动对事件作出反应。它 支持事件条件动作( e v e n t c o n d i t i o n - a c t i o n ) 规则，通过事件监视器监视如数据 库事务、时间事件、外部信号等事件的发生，执行规定的动作，使得数据库能 够提供主动服务的功能。 在一些现代应用中，如过程控制、网络管理、办公工作流控制、空中交通 管制等，都有一个共同的特点，即数据库不仅存储数据，还要存储控制规则及 过程，这些系统中存在着许多主动性的需求，要求数据库具有各种监视和报警 功能，能主动处理异常情况，具有自动恢复功能。有两种方法：一种是应用程 序必须频繁的发出询问，这种方法的结果依赖于查询的频繁度，事件的类型， 发生的频率等许多参数，因而效果不好，而且浪费了大量的系统资源。另一种 方法是应用程序在每次变更后就检验监视状态或条件，但这种方法破坏了软件 的模块性，不利于应用开发，又将定义事件的条件，表示查询，进行条件评价 等负担部留给了程序员，加重了程序开发人员的工作量。主动数据库则能提供 既保持软件的模块性和便于应用开发，没有频繁查询所带来的资源浪费，又能 及时准确地对被监视情形作出响应的有效机构。在主动数据库中，系统要能自 动监视数据库的状态及变迁，当相关事件发生和条件满足时，能自动而适时地 触发相应的动作。 主动数据库满足了人们实践中的多样性需求。随着计算机应用范围的不断 扩大和深入，数据库在各种领域中起着越来越重要的作用，从基本的数据存 储，到状态监控、安全监控、故障监控，再到军事或民用部门的协同和工作， 以及各种管理信息系统( m i s ) 和决策支持系统( d s s ) ，人们对系统中数据库主动 性功能要求也越来越高，随着技术的进步，主动数据库也将和其它新一代数据 库技术一样得到更大的发展。 主动数据库技术是目前数据库技术中的一个活跃领域，近年的研究已经取 得了很多的成果，但是，作为一个正在发展的领域，许多概念还未形成统一标 准，很多技术问题尚待进一步研究解决。 哈尔游理t 大学t 学够十学9 论文 2 2 主动数据库概述 2 1 1 主动数据库的系统模型 一个主动数据库系统( a d b s ) 功能由一个传统数据库系统( d b s ) 和一个事件 驱动的知识库( e b ) v _ 2 及相应的事件探测器( e m ) 组成，用公式表示是： a d b s = d b s + e b 十e m 其中： d b s 是一个传统的数据库系统，用来存储数据和对数据进行维护和运用。 事件库e b 是一组由事件驱动的知识的集合，每一项知识表示在相应的事 件发生时，如何来主动的执行其中包含的由用户预先设定的动作。 e m 是一个随时监控e b 中的事件是否已经发生的探测模块，一旦探测到某 事件已经发生时就主动地触发系统，按e b 中指明的相应知识执行其中预先设 定的动作。 主动数据库的主动性主要是通过规则机制实现的，常采用事件驱动的e c a 规则模型，即事件条件动作( e c a ) 规则。事件驱动的“事件条件动件”的一 般形式为： w h e n i f t h e n w h e r e e n d e c a 规则由事件、条件、动作三部分组成。上述事件驱动的“事件条件 动作”规则的语义是：当e c a 规则规定的事件发生时，计算机就主动触发执行 i f - t h e n 规则，即当条件满足时执行相应的动作，约束项规定执行规则动作的 约束条件，并且接着逐个检查下一个i f t h e n 规则，直到执行完为止。 2 1 2 主动数据库系统体系结构 综合研究和实际系统开发中的经验，人们提出了用以实现主动数据库系统 抽象模型的主动规则体系结构。图2 1 给出主动系统体系结构卧“。其中方框代 表主要过程，椭圆代表数据存储。 哈尔泞理t 大学t 学母i 卜学位论文 图2 1 主动数据库系统体系结构图 f i g 2 1a b s t r a c ta c t i v er u l es y s t e ma r c i n t e c t u r e 主动数据库管理系统的体系结构应该具有高度的模块性和灵活性，其主要 部件如下； 1 事件监测器确定规则所关心的事件是否发生。原子事件由数据库或外 部源通报。复合通报是指原始事件加上从历史记录中获得的已发生事件的信 息。 2 条件评估器评估与被监测事件相关联的规则的条件部分。在只支持条 件一动作规则的系统中，虽然没有监测事件的明确语句，但是，在实现上也必 须监测原子事件。 3 调度器比较当前被触发规则与先前被触发规则，修改冲突集，触发被 调度为立即处理的规则。 4 查询执行器执行数据库查询或者动作。为了支持监视数据库的演化， 要求不但能够访问数据库当i ； 状态，而且也要能够访问数据库历史状态。 由于目前大部分主动数据库是在传统的数据库管理系统或面向对象数据库 管理系统上研制的，其体系结构大多是扩充数据库管理系统的事务管理部分、 执行 哈尔演理t 大学t 学卿i 十学伊论文 对象管理部件以支持知识模型和执行模型。此外，另增加事件监测部件、条件 评估部件及规则管理部件。 2 1 3 主动数据库系统实现的途径 主动数据库系统可有几种实现途径， 1 改造的途径最简单的实现方案就是在原有数据库管理系统的基础上 进行改造。为此只需在原有数据库管理系统之上增建一个经常有机会运行的事 件监测器即可。此时，事件规则库是统一的一个库，由用户预先设置好，在应 用程序运行的同时，由事件监视器来监视事件的发生，并根据库中所示自动执 行相应的动作。 2 嵌入主动程序设计语言的途径一般的方法是把一般程序设计语占改造 成一种主动的程序设计语占，然后按传统方法把数据库操作嵌入在其中执行。 这种途径已由主动程序设计语言将事件规则库分成块，分布在各个过程或对象 ( 当采用面向对象范式时) 中，运行效率可望大大提高。 3 重新设计主动数据库程序设计语言的途径重新设计主动数据库程序设 计语言将数据管理和操作与应用程序彻底融合在一起，自然也是一条可取的途 径。这就彻底地解决了所谓“阻抗不匹配”问题。 一般来说。第一种途径是一种最简单的途径，但效率较差；第二种途径是 一种折中方案，改造的工作量适中，除了在两种语占的接口部分可能损失一定 的效率之外，运行效率较好；第三种途径是一种最彻底的途径，运行效率较 高，但实现的难度和工作流较大，因此要根据具体情况对以上三种途径进行选 择。 2 1 4 典型的主动数据库系统 迄今为止，国际上已经提出的几种主动数据库系统，主要有以下几个： h i p a c ，s t a r b u r s t ，c h i m e r a ，p o s t g r e s ，a r i e l ，s q l 3 。 这些主动数据库系统的原型中，对规则的定义，时间的表示，符合事件的 检测，终止性分析，规则优化等做了很多工作。在主动数据库系统中，不仅需 要定义e c a 规则，规则相对应事件的检测算法，规则库的管理，而且要给出 一个高效合理的规则执行模型。以下对各个主动数据库系统进行简要的介绍： 1 h i p a c 哈尔滨理t 大学t 学硕十学位论文 h i p a c 1 n - i - 程是由u m e s h w a rd a y a l ，d e n n i sr m c c a r t h y 等人于1 9 8 7 年开 发的，是面向对象主动数据库的先驱。在h i p a c 中，采用了e c a 规则，它被 看作一类对象。 h i p a c 的系统执行模型采用扩展了的嵌套事务执行模型。由于在事件和条 件评价之间以及条件评价和动作执行之间可以指定各种耦合模式，使得用户在 定义规则的反应行为时有很大的灵活性 2 s t a r b u r s t s t a r b u r s t 是m ma l m a d e n 研究中心在1 9 8 4 1 9 9 2 年由j e n n i f e rw i d o m 等人 开发的系统。s t a r b u r s t 系统是第一个清楚的定义了面向集合的语义的主动数据 库系统。在s t a r b u r s t 中，舰则的事件、条件和动作都以类似s q l 的语法来表 示，其规则定义的一般形式如下【1 8 l ： c r e a t er u l en a m eo nt a b l e w h e nt r i g g e r i n g o p e r a t i o n s 【i fc o n d i t i o n 】 t h e na c t i o n l i s t 【p r e c e d e sr u l e l i s t 】 【f o l l o w sr u l e l i s t l 其中n a m e 指定规则的名字；w h e n 从句指定规则何时被触发；i f 从句指定 规则触发后需要判定的条件；t h e n 从句指定规则的动作列表。 p r e c e d e s 和f o l l o w s 从句足可选的，用来指定规则之日j 的优先顺序，若一个 规则r 1 在它的p r e c e d e s 从句中指定了规则r 2 ，则意味着当r l ，r 2 同时触发 时，r l 必须在r 2 之i ； 进行条件评价和执行动作。f o l l o w s 语句则相反。优先顺 序的指定不允许出现环。 3 c h i m e r a c h i m e r a 是由b o n n 大学r a i n e rm a n t h e y 在1 9 9 2 - - 1 9 9 6 年间主持开发 i d e at 程时设计的系统。c h i n l c r a 是一个面向对象的主动数据库系统，它的 规则也采用了e c a 的形式【2 0 1 。 c h i m e r a 中的事件只允许内部事件( i n t e r n a le v e n t s ) ，即对数据库的查询或更 新事件，如c r e a t e ，m o d i f y ，d e l e t e ，g e n e r a l i z e ，s p e c i a l i z e ，s e l e c t 等等。一个 规则可以是指定目标的( t a r g e t e d ) 或未指定目标的( n n t a r g e t e d ) 。所谓指定目标的 规则是指，若规则的指定目标是某个类型( c l a s s ) ，则只有与该类型相关的事件 才能作为触发规则，否则任何类型的事件都能触发规则。 哈尔滨理- 大学t 学妒卜学位论文 4 p o s t g r c s p o s t g r e s 2 ”系统是加利福尼亚大学伯克利分校在1 9 8 6 - - 1 9 9 4 年开发的主动 数据库系统，由m i c h a e ls t o n e b r a k e r 主持开发。p o s t g r e s 系统可以看作是一个 对象关系数据库，它是对关系模型的扩展。p o s t g r e s t 2 2 1 【2 3 1 使用p o s t q u e l 查询 语言。 p o s t g r e s 的规则定义不是采用通常的e c a 模式。在p o s t g r e s 中，有三个特 殊的修饰符( m o d i f i c r ) 可以附加在p o s t q u e l 命令之前，若一个p o s t q u e l 命令被附加了a l w a y s 、r e f u s e 或o n e - t i m e 修饰符，则该命令就成为一个规 则。 5 a r i e l 系统 佛罗垦达大学e r i cn h a n s o n 等人设计开发了a r i e l 系统。a r i e l 也是一个 扩展了关系模型的主动数据库系统1 2 4 i ，它的查询语占是p o s t q u e l 查询语占 的子集，并在此基础上加入了规则定义语言。a r i e l 的规则定义形式如下： d e f i n er u l er u l e - n a m e 【p r i o r i t yp n o d t y - v a l u e 】 o ne v e n t 】 i fc o n d i t i o n t h e na c t i o n 方括号内的部分表示在定义规则时该部分可以省略。规贝t j g ( r u l e n 锄e ) 必 须是唯一的。p f i o f i t y 从句用来指定规则的优先级；o n 从句指定触发规则的事 件：i f 从句是规则触发后需要判定的条件；t h e n 从句指定规则的动作部分。 6 s q l 3 s q l 3 标准2 5 1 不是一个具体的主动数据库管理系统。但在s q l 3 标准中支 持主动规则，而一般的商用关系数据库管理系统都遵循s q l 3 杯准。在s q l 3 标准中，规则被称为触发器( t r i g g e r ) 。触发器由四部分组成：隶属表、触发操 作、触发条件和触发动作。创建触发器的语法【1 4 1 如下； ：= c r e a r et r i g g e r o n 【r e f e r e n c i n g 】 哈尔滨理t 大学t 学硕+ 学位论文 ：= b e f o r e a f t e r ：= i n s e r t d e l e t e i u p d a t e o f 】 ：= ：= 0 l d 【a s 】 i n e w 【a s 】 i o l dt a b l e 【a s 】 l n e w _ t a b l e 【a s 】 ：= f o re a c h r o w i s t a t e m e n t 】 】 ：= w h e n ：_ 旧e g i na t o m i c e n d 触发器名必须足唯一的。规则的隶属表必须是一个基本表。规则的触发操 作只能是i n s e r t ，d e l e t e 或u p d a t e 语句。触发器条件可以是任意复杂的 s q l 谓词判定，谓词判定可以包括子查询，用户定义的函数等。触发器条件可 以省略，当省略触发器条件时，意味着其条件为w h e n ( t r u e ) 。触发器的动 作部分是一个b e g i n e n d 语句块，在块中可以包含任意的s q l 语句。 2 3 主动规则终止性概述 传统的数据库系统是被动的，只有当用户或应用程序响应时数据库才执行 相应命令。主动数据库系统提供主动服务功能，能自动监视数据库的状态及其 变迁，当相关事件发生且条件满足时自动而实时地执行相应的动作。为实现主 动服务，主动数据库采取主动规则机制。主动规则一般使用e c a 规则模型描 述，当系统检测到规则事件e 发生时，就在特定的时刻检查规则的条件c ，如 果条件满足，则执行相应的动作a 支持主动规则的数据库称为主动数据库。 由于一个规则动作的执行可能导致数据变化并因而触发其他规则，定义良好的 哈尔演理 大学t 学修十学世论文 规则集必须保证规则之间的相互触发不会无限地进行下去，即规则处理过程终 止。然而，由于规则库中的规则是在不同时刻由不同用户定义的，主动数据库 中规则集的行为很难预测，对任意数据库状态的改变，规则处理都可能会发 生；一些规则被触发，被触发规则的执行会触发其他的规则，也可能同一个规 则被触发多次，当规则数量较多时，人工保证其终止性是困难的，甚至是不可 能的，因此规则集终止性分析方法的研究是必不可少的，终止性反映了主动数 据库系统良好的行为特性。 一个主动规则库必须具备终止性，终止性是指无论数据库处于怎样的状态 及有怎样的初始执行规则集，规则库中规则的执行必终止。几乎在所有的规则 处理算法中，无论是递归或迭代，顺序还是并发，都有不终止的危险。如果规 则的动作执行部分能产生触发其自身或其它规则的事件，那么规则的触发将有 无限进行下去的可能。有以下办法来处理终止性问题： 非终止性作为一种可能被接受，由规则的设计者保证这种情况不发生，这 类似于处理程序语言中的非终止性问题。 以系统参数的形式给出一个固定的上限，规定在一次规则处理中最多可以 处理的规则数目。当达到这个上限时，规则处理非正常终止。 对规则集的语法限制进行加强，确保规则的处理总是终止。最简单的方法 是禁止规则之间的互相触发：一个复杂一点的办法是允许规则之间的触发，但 是不允许出现环路；另一个更精密复杂的办法是允许出现环路，只要能保证每 一个环路中的某个规则的条件最终会变为假。 2 4 本章小结 本章介绍了主动数据库系统模型、主动数据库系统体系结构、主动数据库 系统实现途径和几个典型的主动数据库系统以及主动规则的终止性。 哈尔滨理 大学工学硕卜学位论文 3 1 引言 第3 章基于图的规则终止性分析 由于一个规则动作的执行可能导致数据变化并因而触发其它规则，定义良 好的规则集必须保证规则之间的相互触发不会无限地进行下去，即规则处理过 程终止。然而，由于规则库中的规则是在不同时刻由不同用户定义的，当其数 量较多时，人工保证其终止性是困难的，甚至是不可能的，静态分析工具成为 a d b m s 不可缺少的辅助成分，其中图方法使用较多。目前，主动规则集终止 性分析主要依据触发图( t r i g g e r i n gg r a p h ) ，激活图f a c t i v a t i o ng r a p h ) 和惰化图 ( d e a c t i v a t i o ng r a p h ) 以及基于触发图和激活图的规则缩减方法( r u l er e d u c t i o n m e t h o db a s e do nt r i g g e r i n ga n da c t i v a t i o ng r a p h s ) 。 3 2 基于触发图和激活图的终止性分析 3 2 1 定义 引用文献【4 】的定义，令r = r l ，r 2 ，r n 表示一个被分析的s t a r b u r s t t t l 规 则集。规则分析在一个确定的规则集上被执行，当规则集变化时，规则分析必 须被重复进行。让p 表示r 中规则上的用户自定义的优先权排序集( 由它们的 p r e c e d e s 和f o l l o w s 从句说明) 。p = 啪，r k r l ， ，其中r , r j 表示规则r t 比规 则r j 优先级高。让t = t l ，t 2 ，k ) 表示数据库模式中的表，c = c j ， t k c i 表示t 中表的列。最后让0 表示数据库修改操作集：o = l t e t uf i t e t u i t c c ，其中 i ，伊表示对表t 的插入， d ，伊 表示从表t 中删除元组， 表示对衰t 的列c 的更新。为了便于后面的 讨论，引入如下一些记号： t r i g g e r e d b y ( r ) 为触发规则r 的0 中的操作的集合 p e r f o r m s ( r ) 为由规则r 中的动作执行的0 中的数据库修改操作 t r i g g e r s ( r ) 为所有能被规则r 的动作触发的规则r ( 可能包括规则r 本 身) 。t r i g g e r s ( r ) = r e r i p e r f o r m s ( r ) n t r i g g e r e d - b y ( r7 ) a u s e s ( r ) 为所有在规则r 的条件被判定或动作中的数据修改操作执行时可 哈尔泞理t 大学t 学顾卜学位论文 能引用到的c 中所有的列。 c a n u n t r i g g c r ( o7 ) 为所有由于0 (