ACM SIGMOD Anthology VLDB dblp.uni-trier.de

An Algebraic Approach to Rule Analysis in Expert Database Systems.

Elena Baralis, Jennifer Widom: An Algebraic Approach to Rule Analysis in Expert Database Systems. VLDB 1994: 475-486
@inproceedings{DBLP:conf/vldb/BaralisW94,
  author    = {Elena Baralis and
               Jennifer Widom},
  editor    = {Jorge B. Bocca and
               Matthias Jarke and
               Carlo Zaniolo},
  title     = {An Algebraic Approach to Rule Analysis in Expert Database Systems},
  booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
               Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
  publisher = {Morgan Kaufmann},
  year      = {1994},
  isbn      = {1-55860-153-8},
  pages     = {475-486},
  ee        = {db/conf/vldb/vldb94-475.html},
  crossref  = {DBLP:conf/vldb/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Expert database systems extend the functionality of conventional database systems by providing a facility for creating and automatically executing Condition-Action rules. While Condition-Action rules in database systems are very powerful, they also can be very difficult to program, due to the unstructured and unpredictable nature of rule processing. We provide methods for static analysis of Condition-Action rules; our methods determine whether a given rule set is guaranteed to terminate, and whether rule execution is confluent (has a guaranteed unique final state). Our methods are based on previous methods for analyzing rules in active database systems. We improve considerably on the previous methods by providing analysis criteria that are much less conservative: our methods often determine that a rule set will terminate or is confluent when previous methods could not. Our improved analysis is based on a "propagation" algorithm, which uses a formal approach based on an extended relational algebra to accurately determine when the action of one rule can affect the condition of another. Our algebraic approach yields methods that are applicable to a broad class of expert database rule languages.

Copyright © 1994 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.): VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile. Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX

References

[1]
Alexander Aiken, Jennifer Widom, Joseph M. Hellerstein: Behavior of Database Production Rules: Termination, Confluence, and Observable Determinism. SIGMOD Conference 1992: 59-68 BibTeX
[2]
...
[3]
Elena Baralis, Stefano Ceri, Jennifer Widom: Better Termination Analysis for Active Databases. Rules in Database Systems 1993: 163-179 BibTeX
[4]
Elena Baralis, Jennifer Widom: Using Delta Relations to Optimize Condition Evaluation in Active Databases. Rules in Database Systems 1995: 292-308 BibTeX
[5]
...
[6]
David A. Brant, Daniel P. Miranker: Index Support for Rule Activation. SIGMOD Conference 1993: 42-48 BibTeX
[7]
...
[8]
Stefano Ceri, Georg Gottlob: Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries. IEEE Trans. Software Eng. 11(4): 324-345(1985) BibTeX
[9]
Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6
BibTeX
[10]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577 BibTeX
[11]
Lois M. L. Delcambre, James N. Etheredge: The Relational Production Language: A Production Language for Relational Databases. Expert Database Conf. 1988: 333-351 BibTeX
[12]
Hasanat M. Dewan, David Ohsie, Salvatore J. Stolfo, Ouri Wolfson, Sushil Da Silva: Incremental Database Rule Processing In PARADISER. J. Intell. Inf. Syst. 1(2): 177-209(1992) BibTeX
[13]
Douglas N. Gordin, Alexander J. Pasik: Set-Oriented Constructs: From Rete Rule Bases to Database Systems. SIGMOD Conference 1991: 60-67 BibTeX
[14]
Eric N. Hanson: Rule Condition Testing and Action Execution in Ariel. SIGMOD Conference 1992: 49-58 BibTeX
[15]
...
[16]
...
[17]
Anton P. Karadimce, Susan Darling Urban: Conditional Term Rewriting as a Formal Basis for Active Database Rules. RIDE-ADS 1994: 156-162 BibTeX
[18]
Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181 BibTeX
[19]
Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991) BibTeX
[20]
Arnon Rosenthal, Sharma Chakravarthy, Barbara T. Blaustein, José A. Blakeley: Situation Monitoring for Active Databases. VLDB 1989: 455-464 BibTeX
[21]
Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms. SIGMOD Conference 1988: 404-412 BibTeX
[22]
Eric Simon, Jerry Kiernan, Christophe de Maindreville: Implementing High Level Active Rules on Top of a Relational DBMS. VLDB 1992: 315-326 BibTeX
[23]
Arie Tzvieli: On the Coupling of a Production System Shell and a DBMS. JCDKB 1988: 291-309 BibTeX
[24-1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[24-2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[25]
Leonie van der Voort, Arno Siebes: Termination and Confluence of Rule Execution. CIKM 1993: 245-255 BibTeX
[26]
Yuli Zhou, Meichun Hsu: A Theory for Rule Triggering Systems. EDBT 1990: 407-421 BibTeX

Referenced by

  1. Fabio Casati, Stefano Ceri, Stefano Paraboschi, Giuseppe Pozzi: Specification and Implementation of Exceptions in Workflow Management Systems. ACM Trans. Database Syst. 24(3): 405-451(1999)
  2. Sin Yeung Lee, Tok Wang Ling: Unrolling Cycles to Decide Trigger Termination. VLDB 1999: 483-493
  3. Yahia Rabih: Formalisation and Analysis of Dynamic Behaviour in Object-Oriented Systems. ADBIS (Short Papers) 1999: 163-170
  4. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Compile-Time and Runtime Analysis of Active Behaviors. IEEE Trans. Knowl. Data Eng. 10(3): 353-370(1998)
  5. James Bailey, Guozhu Dong, Kotagiri Ramamohanarao: Decidability and Undecidability Results for the Termination Problem of Active Database Rules. PODS 1998: 264-273
  6. James Bailey, Lobel Crnogorac, Kotagiri Ramamohanarao, Harald Søndergaard: Abstract Interpretation of Active Rules and its Use in Termination Analysis. ICDT 1997: 188-202
  7. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Modularization Techniques for Active Rules Design. ACM Trans. Database Syst. 21(1): 1-29(1996)
  8. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
    Contents
  9. 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)
  10. H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz: View Maintenance Issues for the Chronicle Data Model. PODS 1995: 113-124
  11. Stephen Correl, Daniel P. Miranker: On Isolation, Concurrency, and the Venus Rule Language. CIKM 1995: 281-289
  12. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Declarative Specification of Constraint Maintenance. ER 1994: 205-222
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 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:46:03 2009