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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.     

基于条件冲突分析的主动规则集汇流性判定方法

主动规则使数据库具备自反应能力,在数据库、知识库和无线传感器网络等领域得到了广泛应用。汇流性分析是保持数据一致性的重要手段,但有效判定汇流性仍是一个难题。现有的方法基于规则可交换性进行判定,没有考虑规则之间是否存在条件冲突而导致它们不可能同时出现在同一个执行序列中;同时基于触发关系的集合分析没有考虑在规则触发序列中的先后时序性。为此,提出了规则的触发序列概念,分析了单个触发序列上的条件冲突和一对无序规则所在的两条触发序列之间的条件冲突,从而提出了更有效的汇流性先决条件及其判定定理,同时给出了新的判定算法的完整描述及其可终止性、正确性证明和复杂度分析。     

Mining Informative Rule Set for Prediction

Mining transaction databases for association rules usually generates a large number of rules, most of which are unnecessary when used for subsequent prediction. In this paper we define a rule set for a given transaction database that is much smaller than the association rule set but makes the same predictions as the association rule set by the confidence priority. We call this rule set informative rule set. The informative rule set is not constrained to particular target items; and it is smaller than the non-redundant association rule set. We characterise relationships between the informative rule set and non-redundant association rule set. We present an algorithm to directly generate the informative rule set without generating all frequent itemsets first that accesses the database less frequently than other direct methods. We show experimentally that the informative rule set is much smaller and can be generated more efficiently than both the association rule set and non-redundant association rule set.     

基于Web数据挖掘的高效关联规则研究

随着网络资源越来越丰富，Web数据挖掘逐渐成为因特网上资源有效利用的研究热点。本文提出通过对因特网上非结构化数据的XML格式进行筛选等处理，然后转化为结构化数据存储在SQL Server数据库中。并在此基础之上利用关联规则发现以生成最小关联规则集来代替完全关联规则集，就可以有效地剪除弱关联规则，大幅度地减少候选频繁项目目集，从而提高规则发现效率。最后，在传统经典算法Apriori基础上，利用弱关联规则的向上关闭特性设计了一个相应的高效算法。     

主动数据库中的时序逻辑

ECA主动规则中的“条件”通常描述主动数据库的当前状态或状态转换,表现为一个或一组查询语句。但是经常还会遇到基于数据库一系列状态演变过程之上的查询要求,这时不能使用平常意义上的条件来表示。文章基于过去时序逻辑,提出了一种说明时序条件的语言,可以对数据库基于时间状态的演变的过程进行监控,从而增强了主动数据库中规则语言的表达能力。     

概念格上规则产生集的算法研究与应用

用传统的规则生成算法产生的关联规则集合相当庞大,其中很多规则可由其它规则导出。使用闭项集可以减少规则的数目,而概念格节点间的泛化和例化关系非常适用于规则的提取。目前几种基于概念格的规则提取算法局限于得到准确支持度、信任度的无冗余规则。提出了一种在概念格上挖掘出能推导出所有满足最小支持度、信任度规则的规则产生集算法,文中称之为组规则产生集算法,减少了规则的规模,提高了挖掘效率,进一步给出了组规则产生集的存储数据结构和根据应用需要用其导出单一后项规则的算法。