含环触发图对应的主动规则集可终止性分析

主动规则集的可终止性是主动数据库规则集的三大重要特征之一．主动规则集可否保证终止将直接影响到系统的应用．由于主动规则间存在依赖关系,通过对依赖关系的分析,给出了规则的触发传递闭包、依赖传递闭包等概念．以此为基础,提出了用规则触发-依赖图（T—DG）方法来分析主动规则集的终止性．特别讨论了判定含环的触发图（TG）对应的主动规则集是否保证终止的方法,给出了相应的判定算法、算法证明及分析．     

含有非独立型触发环的主动规则集归约算法研究

可终止性判定问题是主动数据库的一个核心问题。现有的研究工作提出了运用触发图和活化图的方法解决这个问题，其中的一个关键技术就是利用归约算法对主动规则集进行归约。已有的计算方法对一些可归约规则无法识别。本文提出了独立型触发环、非独立型触发环、活化路径、禁止活化环、禁止活化规则等概念。基于这些概念，提出了一个新的归约算法，从而可识别出更多的可归约规则。     

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

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

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

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

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

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

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

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

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

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

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

在对XML数据模型主动机制研究的基础上，结合规则实例提出了一种新的分析规则终止性的静态判定算法。此算法基于触发环的概念，首先对触发环中每一个被修改的节点产生一个递归等式，然后通过展开递归等式并检验其可满足性，就可以分析规则集的可终止性，这样不仅可以得到更高的精确度及更小的复杂度，而且可以得到有效的判定主动规则可终止性的条件。     

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

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

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

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

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.     

基于赋权多段图的Web服务动态选取机制

针对Web服务组合中动态优化选取问题,设计了支持Web服务组合的Web服务评价模型和一个三层结构组织模型.在充分考虑Web服务之间的接口匹配问题的基础上,提出了一个基于赋权多段图最长路径选择策略的Web服务全局优化选取方法,并提出了动态规划、线性规划以及遗传算法进行Web服务动态优化选取.基于赋权多段图的Web服务优化选取方法,有效解决了Web服务组合中Web服务的接口匹配问题,使Web服务的选取更加准确.     

空间数据库主动规则并发行为控制研究

网络环境下空间信息大规模应用中常常有大量的用户规则同时触发，这带来了规则并发行为的控制和效率问题．目前大多数方法难以满足大量用户同时操作时的频繁动态更新，因此提出标注事件图分析模型及并发规则集终止性分析算法，通过实例说明算法的有效性和通用性．在并发索引结构Rlink树基础上，提出一种支持空间数据库主动规则频繁更新的混合索引结构HRlink树及改进的自底向上更新算法IBUU．实验仿真表明，采用IBUU算法的HRlink树频繁更新性能大大高于Rlink树．     

基于可信计算的Web服务调用关键路径研究

随着Web服务数目的增长,企业SAP（Systems Applications and Products in data processing）系统完成一次Web服务调用的响应时间开销越来越大,并且所调用的服务有部分是不可信的,严重束缚了服务请求的执行效率和调用质量。引入可信计算,即诚信度概念,结合工程学中的关键路径概念,创新性地提出一种基于诚信度算法的Web服务调用关键路径确定方法。针对服务注册中心提供的满足用户需求的Web服务,用诚信度算法对其进行计算,把诚信度值低于用户期望值的那部分Web服务排除在外;把可信Web服务调用过程抽象成用带权有向无环图表示的AOE（Activity On Edge）网图,使用关键路径确定算法,在图中找到一条服务调用关键路径。在关键路径上的所有服务都是关键服务,通过SAP系统客户端使用缓冲管理、业务代理等设计模式,减少关键服务的调用时间,来提高关键路径的工效,缩短服务调用响应周期,进而提高服务调用的整体执行效率和质量。通过实际系统开发,验证该算法的可行性和有效性。本系统已在某集团所属全部企业运行,降低了企业的运营成本,提高了工作效率,受到用户的满意度好评。     

基于领域本体的Web服务动态组合

随着Web环境下服务数量的快速增长,如何自动地根据服务请求,进行服务的动态组合成为一个迫切需要解决的问题,该文提出了一种基于领域本体的服务动态组合方法,该方法利用领域本体及其推理能力,生成一个优化的服务组合图,然后基于该图给出了一个高效的服务组合算法．与已有的方法相比,该文的方法综合考虑了服务语义、服务组合的质量和服务组合的效率等因素,可以自动地根据服务请求实现服务的动态组合．同时保证了服务组合的效率和质量．     

一种Agent数据库系统框架及其规则并行算法

面向对象方法描述的对象是被动的,与主动机制存在矛盾,不能很好地定义分布式主动数据库中对象的功能和特性.分布式主动数据库中的主动规则还带来了终止性、合流性的问题.首先分析面向对象方法的局限性,将Agent技术、分布式数据库、主动数据库相结合,给出一种面向Agent的分布式主动数据库系统框架.然后在这个框架基础上,提出扩展事件规则图方法和改进的Coffman-Graham规则并行算法,并分析它们的性能.分析结果表明,前者在一定程度上解决了数据库系统的终止性问题,后者在保持合流性的基础上提高了规则并行处理效率.这个框架对研究Agent技术在分布式主动数据库中的应用有一定的启示.