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

Active rules termination determination based on enhanced conditional formula

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

Termination decision in active database becomes a focus for many researchers. Existing methods based on triggering and activation graphs do not consider whether all rules in a triggering cycle can be executed at the same execution sequence. Existing methods based on logical formula, where only those non-updatahle or finitely updatable variables can be represented, cannot conclude termination if a rule set contains only those cycles that can be executed in a finite number of times. To solve this prob- lem, the concept of the execution sequence of a triggering cycle and the method to construct an enhanced formula including updatable variables are proposed. Many termination cases that cannot be determined by previous methods can be detected by the proposed solution, whose correctness and termination are proved.