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

Abstract

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, as well as complete 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 if 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, together with the satisfiability algorithm. The effectiveness of the approach within the context of the sample application is also addressed.


*This research is supported by NSF Grant No. IRI-9410983.
Copyright © 1997, Arizona State University. All rights reserved.