View Full Document

15 views

Unformatted text preview:

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 Refined Triggering Graph Method SUSAN D URBAN s urban asu edu MICHAEL K TSCHUDI SUZANNE W DIETRICH AND ANTON P KARADIMCE Department of Computer Science and Engineering Arizona State University Tempe AZ 85287 5406 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 whether 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 a sample application is also addressed Keywords 1 active rules termination analysis triggering graph satisfiable trigger conditions Introduction Research in the area of active database systems has demonstrated that it is not easy to develop a set of rules for an active database application Even a small set of rules inadvertently may contain cycles of rule firings Rules can be analyzed manually but this is a tedious process 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 the difficulty of the problem the use of termination analysis tools can be quite helpful to active database developers in highlighting any potential cycles in an active rule set and in eliminating inessential cycles from a triggering graph As described in Karadimce and Urban 1991 inessential cycles are those cycles that structurally appear in a triggering graph but semantically are incapable of demonstrating cyclic behavior In the past few years several techniques have been developed to support termination analysis of active database rules These techniques range from the conservative construction of basic triggering graphs showing how the action of one rule relates to the event of another rule 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 One such semantic approach is the refined triggering graph method RTG Karadimce and Urban 1996 Karadimce 1997 The RTG method studies the contents of active rules 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 whether 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 the basic triggering graph can be removed thus refining the triggering graph One can continue the refinement until no cycles remain in the graph or until the remaining cycles of the graph cannot be eliminated In the former case termination is assured In the latter case the refined triggering graph can serve other termination analysis methods such as the static 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 Urban et al 1997 In particular the RTG method applied to CDOL defines the use of triggering formulae within three different levels of termination analysis where each level of analysis provides an increasing degree of semantic analysis of rule connectivity Triggering formulae are based on concepts borrowed from constraint logic programming In particular triggering formulae in the RTG method use the order sorted algebraic definition of CDOL to test for the satisfiability of constraint conditions that are formed by a sequence of rules within a triggering graph Simplification rules are applied to CDOL rule conditions within triggering formulae some of which transform rule conditions into a more efficient form for data retrieval and some of which help to identify unsatisfiable triggering relationships between rules The primary objective of the research described in this paper has been to implement and evaluate the RTG method Tschudi 1997 Tschudi et al 1997 The goal of the implementation aspect of the research was to 1 demonstrate the feasibility and utility of triggering formulae to support the satisfiability analysis of rule connectivity and 2 extend the original theoretical definition of the RTG approach with practical implementation considerations In particular the implementation described in this paper incorporates rule processing semantics such as immediate and deferred coupling modes rule priorities and before after triggering events into the implementation of the RTG method The implementation also integrates constrained resolution techniques from constraint logic programming Burckert 1991 and the use of constraint simplification rules with the satisfiability algorithm of Rosenkrantz and Hunt 1980 to provide a more complete approach to testing for the 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 the details of the work concerning satisfiability rules the satisfiability algorithm and our


Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Active Rule Termination Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Active Rule Termination Analysis and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?