Unrolling Cycles to Decide Trigger Termination.

Sin Yeung Lee, Tok Wang Ling: Unrolling Cycles to Decide Trigger Termination. VLDB 1999: 483-493

@inproceedings{DBLP:conf/vldb/LeeL99,
  author    = {Sin Yeung Lee and
               Tok Wang Ling},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {Unrolling Cycles to Decide Trigger Termination},
  booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
               Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
               UK},
  publisher = {Morgan Kaufmann},
  year      = {1999},
  isbn      = {1-55860-615-7},
  pages     = {483-493},
  ee        = {db/conf/vldb/LeeL99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Active databases have gained a substantial interest in recent years in enforcing database integrity, however, its current implementations suffer many problems such as running into an infinite loop. While deciding termination is an undecidable task, several works have been proposed to prove termination under certain situations. However, most of these algorithms cannot conclude termination if a cyclic execution actually presents during run-time. This is rather limited. The trigger system can still terminate if these cycles can only be executed a finite number of times. Adopting the trigger graph approach, we propose a method to detect if some cycles can only be executed finitely. We then present a cycle-unrolling algorithm to remove those cycles that can only be executed finitely from a trigger graph. Similarly, we present the concept of finitely-updatable predicate to further improve most existing detection methods. Finally, we conclude with an algorithm to detect if a given trigger system will terminate.

Copyright © 1999 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.): VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents

References

[1]: Alexander Aiken, Jennifer Widom, Joseph M. Hellerstein: Behavior of Database Production Rules: Termination, Confluence, and Observable Determinism. SIGMOD Conference 1992: 59-68
[2]: Elena Baralis, Stefano Ceri, Stefano Paraboschi: Run-time Detection of Non-Terminating Active Rule Systems. DOOD 1995: 38-54
[3]: Elena Baralis, Stefano Ceri, Stefano Paraboschi: Compile-Time and Runtime Analysis of Active Behaviors. IEEE Trans. Knowl. Data Eng. 10(3): 353-370(1998)
[4]: Elena Baralis, Jennifer Widom: An Algebraic Approach to Rule Analysis in Expert Database Systems. VLDB 1994: 475-486
[5]: Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577
[6]: Umeshwar Dayal: Active Database Management Systems. JCDKB 1988: 150-169
[7]: Dennis R. McCarthy, Umeshwar Dayal: The Architecture Of An Active Data Base Management System. SIGMOD Conference 1989: 215-224
[8]: Oscar Díaz, Norman W. Paton, Peter M. D. Gray: Rule Management in Object Oriented Databases: A Uniform Approach. VLDB 1991: 317-326
[9]: Stella Gatziu, Andreas Geppert, Klaus R. Dittrich: Integrating Active Concepts into an Object-Oriented database System. DBPL 1991: 399-415
[10]: Anton P. Karadimce, Susan Darling Urban: Conditional Term Rewriting as a Formal Basis for Active Database Rules. RIDE-ADS 1994: 156-162
[11]: Anton P. Karadimce, Susan Darling Urban: Refined Triggering Graphs: A Logic-Based Approach to Termination Analysis in an Active Object-Oriented Database. ICDE 1996: 384-391
[12]: Tok Wang Ling: The Prolog Not-Predicate and Negation as Failure Rule. New Generation Comput. 8(1): 5-31(1990)
[13]: Sin Yeung Lee, Tok Wang Ling: A Path Removing Technique for Detecting Trigger Termination. EDBT 1998: 341-355
[14]: Michael Stonebraker, Greg Kemnitz: The Postgres Next Generation Database Management System. Commun. ACM 34(10): 78-92(1991)
[15]: Hsiu-yen Tsai, Albert Mo Kim Cheng: Termination Analysis of OPS5 Expert Systems. AAAI 1994: 193-198
[16]: Thomas Weik, Andreas Heuer: An Algorithm for the Analysis of Termination of Large Trigger Sets in an OODBMS. ARTDB 1995: 170-189
[17]: Leonie van der Voort, Arno Siebes: Termination and Confluence of Rule Execution. CIKM 1993: 245-255
[18]: ...