Termination analysis of active rules modular sets

ABSTRACT

This paper presents an algorithm for static termination analysis of active rules in a context of modular design. Several recent works have suggested proving termination by using the concept of triggering graph. We propose here an original approach, based on these works, and that allows to guarantee the termination of a set of rules, conceived by several designers, even when none of the designers knows the set of the active rules. We introduce the notions of private event and of public event, and we refine the notion of triggering graph (by enclosing also events in graphs). We replace then the notion of cycle (which is no more relevant in a context of modular design) by the notion of maximal private path preceding a rule. By means of these tools, we show that it is possible to prove termination of active rules modular sets.

REFERENCES

• 1: Alexander Aiken , Jennifer Widom , Joseph M. Hellerstein, Behavior of database production rules: termination, confluence, and observable determinism, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.59-68, June 02-05, 1992, San Diego, California, United States
• 2: James Bailey , Guozhu Dong , Kotagiri Ramamohanarao, Decidability and undecidability results for the termination problem of active database rules, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.264-273, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275517]
• 3: Elena Baralis , Stefano Ceri , Stefano Paraboschi, Improving Rule Analysis by Means of Triggering and Activation Graphs, Proceedings of the Second International Workshop on Rules in Database Systems, p.165-181, September 25-27, 1995
• 4: Elena Baralis , Stefano Ceri , Stefano Paraboschi, Modularization techniques for active rules design, ACM Transactions on Database Systems (TODS), v.21 n.1, p.1-29, March 1996 [doi>10.1145/227604.227605]
• 5: Elena Baralis , Jennifer Widom, An Algebraic Approach to Rule Analysis in Expert Database Systems, Proceedings of the 20th International Conference on Very Large Data Bases, p.475-486, September 12-15, 1994
• 6: Stefano Ceri , Jennifer Widom, Deriving production rules for constraint maintenance, Proceedings of the sixteenth international conference on Very large databases, p.566-577, September 1990, Brisbane, Australia
• 7: U. Dayal , A. P. Buchmann , D. R. McCarthy, Rules are objects too: A knowledge model for an active, object-oriented databasesystem, Lecture notes in computer science on Advances in object-oriented database systems, p.129-143, September 1988, Bad Mu:9Ainster am Stein-Edernburg, Germany
• 8: Anton P. Karadimce , Susan Darling Urban, Refined Triggering Graphs: A Logic-Based Approach to Termination Analysis in an Active Object-Oriented Database, Proceedings of the Twelfth International Conference on Data Engineering, p.384-391, February 26-March 01, 1996
• 9: Sin Yeung Lee , Tok Wang Ling, Refined Termination Decision in Active Databases, Proceedings of the 8th International Conference on Database and Expert Systems Applications, p.182-191, September 01-05, 1997
• 10: Sin Yeung Lee , Tok Wang Ling, A Path Removing Technique for Detecting Trigger Termination, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.341-355, March 23-27, 1998
• 11: Sin Yeung Lee , Tok Wang Ling, Unrolling Cycles to Decide Trigger Termination, Proceedings of the 25th International Conference on Very Large Data Bases, p.483-493, September 07-10, 1999
• 12: Michael K. Tschudi , Susan Darling Urban , Suzanne W. Dietrich , Anton P. Karadimce, An Implenentation and Evaluation of the Refined Triggering Graph Method for Active Rule Termination Analysis, Proceedings of the Third International Workshop on Rules in Database Systems, p.133-148, June 26-28, 1997
• 13: T. Weik, A. Heuer. An Algorithm for the Analysis of Termination of Large Trigger Sets in an OODBMS. In Proc. Int' I Workshop on Active and ReaFime Databases. Skoevde, Sweden, 1995.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Algorithms, Design, Verification

Keywords:
active database systems, static analysis, termination