ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Behavior of Database Production Rules: Termination, Confluence, and Observable Determinism.

Alexander Aiken, Jennifer Widom, Joseph M. Hellerstein: Behavior of Database Production Rules: Termination, Confluence, and Observable Determinism. SIGMOD Conference 1992: 59-68
@inproceedings{DBLP:conf/sigmod/AikenWH92,
  author    = {Alexander Aiken and
               Jennifer Widom and
               Joseph M. Hellerstein},
  editor    = {Michael Stonebraker},
  title     = {Behavior of Database Production Rules: Termination, Confluence,
               and Observable Determinism},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {59-68},
  ee        = {http://doi.acm.org/10.1145/130283.130296, db/conf/sigmod/AikenWH92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Static analysis methods are given for determining whether arbitrary sets of database production rules are (1) guaranteed to terminate; (2) guaranteed to produce a unique final database state; (3) guaranteed to produce a unique stream of observable actions. When the analysis determines that one of these properties is not guaranteed, it isolates the rules responsible for the problem and determines criteria that, if satisfied, guarantee the property. The analysis methods are presented in the context of the Starburst Rule System; they will form the basis of an interactive development environment for Starburst rule programmers.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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

Printed Edition

Michael Stonebraker (Ed.): Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. ACM Press 1992 BibTeX , SIGMOD Record 21(2), June 1992
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1216 KB]

References

[AS91]
Serge Abiteboul, Eric Simon: Fundamental Properties of Deterministic and Nondeterministic Extensions of Datalog. Theor. Comput. Sci. 78(1): 137-158(1991) BibTeX
[AWH92]
...
[BFKM85]
...
[CW90]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577 BibTeX
[GJ91]
Narain H. Gehani, H. V. Jagadish: Ode as an Active Database: Constraints and Triggers. VLDB 1991: 327-336 BibTeX
[Han89]
Eric N. Hanson: An Initial Report on The Design of Ariel: A DBMS With an Integrated Production Rule System. SIGMOD Record 18(3): 12-19(1989) BibTeX
[HCL+90]
Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) BibTeX
[HH91]
...
[Hue80]
Gérard P. Huet: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems. J. ACM 27(4): 797-821(1980) BibTeX
[KU91]
...
[MD89]
Dennis R. McCarthy, Umeshwar Dayal: The Architecture Of An Active Data Base Management System. SIGMOD Conference 1989: 215-224 BibTeX
[Ras90]
Louiqa Raschid: Maintaining Consistency in a Stratified Production System Program. AAAI 1990: 284-289 BibTeX
[SJGP90]
Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290 BibTeX
[WCL91]
Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285 BibTeX
[WF90]
Jennifer Widom, Sheldon J. Finkelstein: Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270 BibTeX
[ZH90]
Yuli Zhou, Meichun Hsu: A Theory for Rule Triggering Systems. EDBT 1990: 407-421 BibTeX

Referenced by

  1. Sin Yeung Lee, Tok Wang Ling: Unrolling Cycles to Decide Trigger Termination. VLDB 1999: 483-493
  2. Blaz Zupan, Albert Mo Kim Cheng: Optimization of Rule-Based Systems Using State Space Graphs. IEEE Trans. Knowl. Data Eng. 10(2): 238-254(1998)
  3. Avigdor Gal, Opher Etzion: A Multiagent Update Process in a Database with Temporal Data Dependencies and Schema Versioning. IEEE Trans. Knowl. Data Eng. 10(1): 21-37(1998)
  4. James Bailey, Guozhu Dong, Kotagiri Ramamohanarao: Decidability and Undecidability Results for the Termination Problem of Active Database Rules. PODS 1998: 264-273
  5. Sin Yeung Lee, Tok Wang Ling: A Path Removing Technique for Detecting Trigger Termination. EDBT 1998: 341-355
  6. Oscar Díaz, Arturo Jaime: EXACT: An Extensible Approach to Active Object-Oriented Databases. VLDB J. 6(4): 282-295(1997)
  7. Luigi Palopoli, Riccardo Torlone: Generalized Production Rules as a Basis for Integrating Active and Deductive Databases. IEEE Trans. Knowl. Data Eng. 9(6): 848-862(1997)
  8. James Bailey, Lobel Crnogorac, Kotagiri Ramamohanarao, Harald Søndergaard: Abstract Interpretation of Active Rules and its Use in Termination Analysis. ICDT 1997: 188-202
  9. Anca Vaduva, Stella Gatziu, Klaus R. Dittrich: Graphical Tools for Rule Development in the Active DBMS SAMOS. ICDE 1997: 587
  10. C. K. Kim, Janusz R. Getta: Concurrency Control in Active Database Systems with Prioritised Rules. ADBIS 1997: 29-34
  11. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Modularization Techniques for Active Rules Design. ACM Trans. Database Syst. 21(1): 1-29(1996)
  12. Jennifer Widom: The Starburst Active Database Rule System. IEEE Trans. Knowl. Data Eng. 8(4): 583-595(1996)
  13. 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
  14. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
    Contents
  15. Weidong Chen: Query Evaluation in Deductive Databases with Alternating Fixpoint Semantics. ACM Trans. Database Syst. 20(3): 239-287(1995)
  16. Alexander Aiken, Joseph M. Hellerstein, Jennifer Widom: Static Analysis Techniques for Predicting the Behavior of Active Database Rules. ACM Trans. Database Syst. 20(1): 3-41(1995)
  17. Jeng-Rung Chen, Albert Mo Kim Cheng: Response Time Analysis of EQL Real-Time Rule-Based Systems. IEEE Trans. Knowl. Data Eng. 7(1): 26-43(1995)
  18. Tor Didriksen, César A. Galindo-Legaria, Eirik Dahle: Database De-Centralization - A Practical Approach. VLDB 1995: 654-665
  19. Philippe Picouet, Victor Vianu: Semantics and Expressiveness Issues in Active Databases. PODS 1995: 126-138
  20. Danilo Montesi, Riccardo Torlone: A Rewriting Technique for the Analysis and the Optimization of Active Databases. ICDT 1995: 238-251
  21. Danilo Montesi, Riccardo Torlone: A Transaction Transformation Approach to Active Rule Processing. ICDE 1995: 109-116
  22. Alejandro P. Buchmann, Jürgen Zimmermann, José A. Blakeley, David L. Wells: Building an Integrated Active OODBMS: Requirements, Architecture, and Design Decisions. ICDE 1995: 117-128
  23. Danilo Montesi, Riccardo Torlone: A Framework for the Specification of Active Rule Language Semantics. DBPL 1995: 4
  24. Stefano Ceri, Piero Fraternali, Stefano Paraboschi, Letizia Tanca: Automatic Generation of Production Rules for Integrity Maintenance. ACM Trans. Database Syst. 19(3): 367-422(1994)
  25. Christine Collet, Thierry Coupaye, T. Svensen: NAOS - Efficient and Modular Reactive Capabilities in an Object-Oriented Database System. VLDB 1994: 132-143
  26. Elena Baralis, Jennifer Widom: An Algebraic Approach to Rule Analysis in Expert Database Systems. VLDB 1994: 475-486
  27. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Declarative Specification of Constraint Maintenance. ER 1994: 205-222
  28. Stefano Ceri, Jennifer Widom: Managing Semantic Heterogeneity with Production Rules and Persistent Queues. VLDB 1993: 108-119
  29. Christian Laasch, Marc H. Scholl: Deterministic Semantics of Set-Oriented Update Sequences. ICDE 1993: 4-13
  30. Anton P. Karadimce, Susan Darling Urban: A Framework for Declarative Updates and Constraint Maintenance in Object-Oriented Databases. ICDE 1993: 391-398
  31. Jing P. Yoon: Database Updates Using Active Rules: A Unified Approach for Consistency Maintenance. DASFAA 1993: 271-278
  32. Jennifer Widom: The Starburst Rule System: Language Design, Implementation, and Applications. IEEE Data Eng. Bull. 15(1-4): 15-18(1992)
  33. Suzanne W. Dietrich, Susan Darling Urban, John V. Harrison, Anton P. Karadimce: A DOOD RANCH at ASU: Integrating Active, Deductive and Object-Oriented Databases. IEEE Data Eng. Bull. 15(1-4): 40-43(1992)
  34. Stefano Ceri, Piero Fraternali, Stefano Paraboschi, Letizia Tanca: Constraint Enforcement Through Production Rules: Putting Active Databases at Work. IEEE Data Eng. Bull. 15(1-4): 10-14(1992)
  35. Stefano Ceri: A Declarative Approach to Active Databases. ICDE 1992: 452-456
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:09 2009