Active Rule Termination Analysis: An Implementation and Evaluation of the
Refined Triggering Graph Method
Susan D. Urban, Michael K. Tschudi, Suzanne W. Dietrich,
Anton P. Karadimce
Department of Computer Science and Engineering
Arizona State University
Tempe, AZ 85287-5406
602-965-2874
{s.urban}@asu.edu
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 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 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, 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 the sample application is also
addressed.
This research was supported by NSF grant no. IRI-9109195 and NSF grant no.
IRI-9410993.