基于触发路径的主动规则集终止性分析

为满足用户对网络服务的个性化、定制化和主动化需求,主动规则成为解决这些问题的关键技术.研究了在网络环境下基于规则的复杂应用中,大量规则集同时触发所带来的规则终止性问题,提出的分析方法确保主动规则能够有效运行,以提供更加灵活的主动服务.讨论了以静态分析方法为主的主动规则终止性分析相关工作,随后给出问题描述和相关形式化定义.分析了基于关联图的终止性分析方法的保守性,引入触发路径和有限触发环概念,提出了基于触发路径的两种终止情形分析方法,提高了规则集终止性分析的准确性,采用两阶段分析算法保证了分析效率.与相关分析方法的实验比较说明,文中方法能够更准确高效地检测主动规则集的终止性,并适应基于主动规则的其它应用.     

支持复合事件的主动规则的可终止性分析

ＥＣＡ规则系统已经成为主动数据库提供主动服务的通用机制．规则集合的可终止性是规则行为分析的一个重要问题．文中给出了ＥＣＡ规则系统的形式化描述，并着重讨论了复合事件机制对可终止性问题的影响．文中结合规则实例给出了分析规则终止性的静态判定算法，这一算法可作为主动规则分析工具的理论基础．     

关联图与主动规则集的终止性分析

终止性反映了主动数据库系统良好的行为特性.目前有关主动规则集终止性分析的主要依据是触发图和活化图,其分析结果是保守的.为表达一个规则的动作可能使另一规则的条件为假的事实,引入了惰化图(deactivationgraph),并与触发图和活化图相结合,定义了更为一般的关联图(relationshipgraph).同时,给出了基于关联图的主动规则集终止性静态分析算法,提高了终止性判定的准确性.     

主动规则可终止性的动态分析方法

判定主动规则集合的执行情况是相当困难的,尤其是在主动规则支持复合事件时,提出了一种利用确定型多带图灵机对主动数据库进行动态分析的模型,归结出主动规则可终止的充分必要条件,并进一步提出了利用动态分析模型进行主动规则可终止性判定的算法,该模型易于实现,能有效描述规则集合的动态特性,可以作为分析主动规则集合行为的理论基础,还可以用于对主动规则的辅助设计和验证。     

XML中的主动规则及其可终止性分析

主动XML系统一般采用触发器,即“事件-条件-动作”(ECA)规则来提供主动行为。本文提出了一种新的事件监测机制,在XML系统中引入‘主动节点’,即把规则也融入节点,各节点上的ECA规则只需在节点修改时被激活并进行检查,提高了动作的执行效率,增强了系统的实时性。本文结合规则实例给出了分析规则终止性的静态判定算法,引入触发图、活化图、修改后的触发图、触发环等概念,对触发图中的简单触发环进行转换,产生一个对应于触发环的循环语句,对触发环中每一个被修改的节点产生一个递归等式。展开递归等式检验它的可满足性可以用来分析规则集的可终止性。这一算法提高了可终止性判定的精确性,降低了复杂度。     

基于增强条件公式的主动规则集可终止性判定

主动规则集的可终止性判定是一个研究热点问题,现有的基于触发图和活化图的方法没有考虑触发环所有所属规则能否在同一次执行中执行;现有的条件公式判定方法只能包含不可更新或有限次更新变量,当主动规则集只包含可有限次循环执行的触发环时,现有方法不能准确判定它是可终止的。为此,提出了触发环的执行序列的概念和建立包含可更新变量的增强条件公式的方法,新的判定方法将触发环和执行语义有机地结合在一起,较现有方法可以发现更多的可终止性情形,同时给出了新算法的可终止性和正确性证明。     

基于增强条件公式的主动规则集可终止性判定

主动规则集的可终止性判定是一个研究热点问题,现有的基于触发图和活化图的方法没有考虑触发环所有所属规则能否在同一次执行中执行;现有的条件公式判定方法只能包含不可更新或有限次更新变量,当主动规则集只包含可有限次循环执行的触发环时,现有方法不能准确判定它是可终止的。为此,提出了触发环的执行序列的概念和建立包含可更新变量的增强条件公式的方法,新的判定方法将触发环和执行语义有机地结合在一起,较现有方法可以发现更多的可终止性情形,同时给出了新算法的可终止性和正确性证明。     

基于活化路径和条件公式的主动规则集可终止性判定方法

支持主动规则机制已经成为现代数据库系统的一个重要特征.主动规则集的可终止性判定是主动数据库中一个核心问题之一,利用触发图和活化图的方法来判定可终止性都存在不同的保守性.为此,提出了为有效活化路径建立条件公式的思想,在此基础上给出了一个新的判定主动规则集可终止性的方法.分析的结果表明,提出的方法较现有方法可以发现更多的可终止性情形,最后给出了相应的算法及其可终止性、正确性证明.     

基于约束的主动规则终止性分析

终止性是主动规则所需的最重要的一个性质,但规则的终止性检查通常是不可判定的.已有的静态分析方法非常保守,SQL3标准也没有提供保证终止的机制,所以商业数据库限制规则级联触发的最大次数确保终止.由于规则可看成数据库状态转换器,而约束能够表示所有可能的数据库状态,基于约束表示的数据库状态及约束求解,模拟规则处理,可得到更精确的终止性结论.     

主动数据库中基于图的规则的指称语义研究

1 引言主动数据库的主动特性一般使用E-C-A(Event-Condi-tion-Action)规则模型描述。我们用CA规则表示ECA规则模型中的Condition和Action部分,ECA规则语言的语义可描述为:事件E的发生可触发CA规则的执行,该CA规则的执行又可导致其它事件的发生,进而触发其它CA规则的执行,形成触发规则集。主动规则源于人工智能的知识表示的产生式系统(OPS5),许多主动数据库规则系统的执行语义均源于OPS5产生式规则语言的recognize-act cycle算法(如图     

Active Rule Termination Analysis: An Implementation and Evaluation of the Refined Triggering Graph Method

This paper describes the implementation of the Refined Triggering Graph (RTG) method for active rule termination analysis and provides an evaluation of the approach based on the application of the method to a sample active application. The RTG method has been defined in the context of an active-deductive, object-oriented database language known as CDOL (Comprehensive, Declarative, Object Language). The RTG method studies the contents of rule pairs and rule cycles in a triggering graph and tests for: (1) the successful unification of one rule's action with another rule's triggering event, and (2) the satisfiability of active rule conditions, asking whether it is possible for the condition of a triggered rule to evaluate to true in the context of the triggering rule's condition. If the analysis can provably demonstrate that one rule cannot trigger another rule, the directed vector connecting the two rules in a basic triggering graph can be removed, thus refining the triggering graph. An important aspect in the implementation of the method is the development of a satisfiability algorithm for CDOL conditions. This paper presents the tool that was developed based on the RTG method, describing how techniques from constraint logic programming are integrated with other techniques for testing the satisfiability of rule triggering conditions. The effectiveness of the approach within the context of a sample application is also addressed.     

基于主动数据库的工作流管理系统

高端工作流管理系统在应用中与数据库的频繁连接和数据交换成为其性能的瓶颈。该文提出一种新的基于主动数据库技术和ECA规则理论实现工作流管理系统的方法,探讨了基于主动数据库实现工作流管理系统的参考模型,与传统工作流参考模型的比较证明了该参考模型的合理性与可行性。     

PEARD: A Prototype Environment for Active Rule Debugging

This research has investigated dynamic, execution-based rule analysis through the development of a Prototype Environment for Active Rule Debugging, called PEARD. PEARD simulates the execution of active database rules, supporting the Event-Condition-Action rule paradigm. Rule definition is flexible, where changes to rules can be applied immediately during a debugging session without recompiling the system. A breakpoint debugging tool allows breakpoints to be set so that the state of variables may be inspected and changed anytime a breakpoint is reached during rule execution. A rule visualization tool displays the rule triggering process in graph form, supporting different visualization granularities to help the user to understand rule execution. Color coding is also used as part of the visualization tool to help the user see where the different parts of an ECA rule are executed due to deferred coupling modes. Users can examine different parts of the rule graph display to inspect the state of a transaction at different rule execution points. Other debugging features include a means for detecting potential cycles in rule execution and a utility to examine different rule execution paths from the same point in the rule triggering process. Our experience with PEARD has helped to identify some of the useful functional components of an active rule debugging tool and to identify research directions for future active rule development environments.This research was partially supported by NSF Grant No. IRI-9410993.     

Abstract Interpretation for Termination Analysis in Functional Active Databases

An active database consists of a traditional database supplemented by a set of Event-Condition-Action (ECA) rules. One of the key questions for active database designers is that of termination of the ECA rules. The behaviour of the ECA rules may be obscure and their semantics is often not specified formally. Consequently, developing termination analysis algorithms and proving their correctness is a challenging task. In this paper we address this problem for functional active databases by adopting an abstract interpretation approach. By functional active databases we mean active databases whose transaction execution semantics have been expressed in a purely functional language. Although we demonstrate our techniques for a specific active DBMS which supports a functional database programming language interface, these techniques are directly applicable to other active DBMSs whose execution semantics have been specified using a functional or a denotational approach.     

计算主动数据库中不可归约规则集的有效算法

主动数据库中规则集的可终止性判定是一个重要问题,已经成为一个研究热点.有些研究工作提出了在编译阶段运用触发图和活化图的方法解决这个问题,其中的一个关键技术就是计算主动规则集的不可归约规则集.现有的计算方法由于具有一定保守性,使得计算出的不可归约规则集仍可进一步地归约,这无疑将影响到规则集的可终止性判定的准确性和运行阶段规则分析的效率.经过深入分析活化规则可无限执行的特点,提出了活化路径等概念.基于这些概念,提出了一个计算主动规则集的不可归约规则集的有效算法,使现有方法求得的不可归约规则集得到进一步的归约.     

主动数据库技术在控制系统规则库方面的应用研究

讨论并分析了建立水下无人潜器(AUV)自主运动控制规则库的必要性和重要性及可行性。指出主动机制是主动数据库的一个重要功能．采用事件一条件一动作的规则来实现其主动功能。就控制系统的事件．动作特点提出控制规则数据库设计方案。解决了自主控制系统中控制规则单一的瓶颈问题。最后．对主动控制规则库的实现技术进行了讨论并提出了相应的解决方案。