Journal of Intelligent Information Systems 12, 27–60 (1999)c° 1999 Kluwer Academic Publishers. Manufactured in The Netherlands.Active Rule Termination Analysis:An Implementation and Evaluation of the RefinedTriggering Graph Method∗SUSAN D. URBAN [email protected] K. TSCHUDI, SUZANNE W. DIETRICH AND ANTON P. KARADIMCEDepartment of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287-5406Abstract. This paper describes the implementation of the Refined Triggering Graph (RTG) method for activerule termination analysis and provides an evaluation of the approach based on the application of the method to asample active application. TheRTG method has been defined in the context of an active-deductive, object-orienteddatabase language known as CDOL (Comprehensive, Declarative, Object Language). The RTG method studiesthe contents of rule pairs and rule cycles in a triggering graph and tests for: (1) the successful unification of onerule’s action with another rule’s triggering event, and (2) the satisfiability of active rule conditions, asking whetherit 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 connectingthe two rules in a basic triggering graph can be removed, thus refining the triggering graph. An important aspectin the implementation of the method is the development of a satisfiability algorithm for CDOL conditions. Thispaper presents the tool that was developed based on the RTG method, describing how techniques from constraintlogic programming are integrated with other techniques for testing the satisfiability of rule triggering conditions.The effectiveness of the approach within the context of a sample application is also addressed.Keywords: active rules, termination analysis, triggering graph, satisfiable trigger conditions1. IntroductionResearchinthe area ofactivedatabasesystems hasdemonstratedthat it isnoteasy todevelopa set of rules for an active database application. Even a small set of rules inadvertentlymay contain cycles of rule firings. Rules can be analyzed manually, but this is a tediousprocess with plenty of room for error. Automated termination analysis, on the other hand,cannot always guarantee that a given set of rules will terminate in all cases. Despite thedifficulty of the problem, the use of termination analysis tools can be quite helpful toactive database developers in highlighting any potential cycles in an active rule set andin eliminating inessential cycles from a triggering graph. As described in (Karadimce andUrban, 1991), inessential cycles are those cycles that structurally appear in a triggeringgraph, but semantically are incapable of demonstrating cyclic behavior.In the past few years, several techniques have been developed to support terminationanalysisof activedatabase rules. These techniquesrange from the conservativeconstructionof basic triggering graphs, showing how the action of one rule relates to the event of anotherrule (e.g., Aiken, et al., 1992), to more semantic methods that examine the conditions of∗This research was sponsored by NSF Grant No. IRI-9410983.28 URBAN ET AL.rules (e.g., Baralis et al., 1994, 1995a). Onesuch semantic approach is the refined triggeringgraph method (RTG) (Karadimce and Urban, 1996; Karadimce, 1997). The RTG methodstudies the contents of active rules and tests for: (1) the successful unification of one rule’saction with another rule’s triggering event, and (2) the satisfiability of active rule conditions,asking whether it is possible for the condition of a triggered rule to evaluate to true inthe context of the triggering rule’s condition. If the analysis can provably demonstratethat one rule cannot trigger another rule, the directed vector connecting the two rulesin the basic triggering graph can be removed, thus refining the triggering graph. One cancontinue the refinement until no cycles remain in the graph or until the remaining cyclesof the graph cannot be eliminated. In the former case, termination is assured. In the lattercase, the refined triggering graph can serve other termination analysis methods, such as thestatic and run-time termination analysis tools described in (Baralis, et al., 1995a, 1995b).The RTG method was defined in the context of CDOL (Comprehensive, Declarative,Object Language), the active, deductive, object-oriented language described in (Urbanet al., 1997). In particular, the RTG method applied to CDOL defines the use of triggeringformulae within three different levels of termination analysis, where each level of analysisprovidesan increasing degree of semantic analysis of rule connectivity. Triggering formulaearebased onconcepts borrowedfromconstraint logic programming. In particular, triggeringformulae in the RTG method use the order-sorted, algebraic definition of CDOL to test forthe satisfiability of constraint conditions that are formed by a sequence of rules within atriggering graph. Simplification rules are applied to CDOL rule conditions within triggeringformulae, some of which transform rule conditions into a more efficient form for dataretrieval and some of which help to identify unsatisfiable triggering relationships betweenrules.The primary objective of the research described in this paper has been to implementand evaluate the RTG method (Tschudi, 1997; Tschudi et al., 1997). The goal of the im-plementation aspect of the research was to: (1) demonstrate the feasibility and utility oftriggering formulae to support the satisfiability analysis of rule connectivity, and (2) ex-tend the original, theoretical definition of the RTG approach with practical implementationconsiderations. In particular, the implementation described in this paper incorporates ruleprocessing semantics, such as immediate and deferred coupling modes, rule priorities, andbefore/after triggering events into the implementation of the RTG method. The implemen-tation also integrates constrained resolution techniques from constraint logic programming(Burckert, 1991) and the use of constraint simplification rules with the satisfiability algo-rithm of Rosenkrantz and Hunt (1980) to provide a more complete approach to testing forthe satisfiability of rule triggering relationships. Whereas the work in (Tschudi et al., 1997)provides a high-level overview of our results, this paper elaborates on