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

An Efficient Algorithm for Computing an Irreducible Rule Set in Active Database

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

Termination decision in active database is an important problem and becomes a focus for many researchers. Several works suggest proving termination by using triggering and activation graphs at compile-time, and computing an irreducible rule set is the key technique. But due to the various conservativeness of the existing approachesl the irreducible rule set computed by them can be reduced again. This defect impairs not only the correctness of termination decision at compile-time but also the efficiency of run-time rule analysis. In this paper, the characteristic of nontermination for an activation rule is analyzed in detail and such concepts as activation path, inhibited activation cycle and inhibited activation rule are proposed. Based on these concepts, an efficient algorithm for computing an irreducible rule set is presented, which can make the irreducible rule set, computed by the existing approaches, to be reduced again.