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}
}
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
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
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 
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]
- ...
- [3]
- Elena Baralis, Stefano Ceri, Jennifer Widom:
Better Termination Analysis for Active Databases.
Rules in Database Systems 1993: 163-179
- [4]
- Elena Baralis, Jennifer Widom:
Using Delta Relations to Optimize Condition Evaluation in Active Databases.
Rules in Database Systems 1995: 292-308
- [5]
- ...
- [6]
- David A. Brant, Daniel P. Miranker:
Index Support for Rule Activation.
SIGMOD Conference 1993: 42-48
- [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)
- [9]
- Stefano Ceri, Georg Gottlob, Letizia Tanca:
Logic Programming and Databases.
Springer 1990, ISBN 3-540-51728-6
- [10]
- Stefano Ceri, Jennifer Widom:
Deriving Production Rules for Constraint Maintainance.
VLDB 1990: 566-577
- [11]
- Lois M. L. Delcambre, James N. Etheredge:
The Relational Production Language: A Production Language for Relational Databases.
Expert Database Conf. 1988: 333-351
- [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)
- [13]
- Douglas N. Gordin, Alexander J. Pasik:
Set-Oriented Constructs: From Rete Rule Bases to Database Systems.
SIGMOD Conference 1991: 60-67
- [14]
- Eric N. Hanson:
Rule Condition Testing and Action Execution in Ariel.
SIGMOD Conference 1992: 49-58
- [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
- [18]
- Alon Y. Levy, Yehoshua Sagiv:
Queries Independent of Updates.
VLDB 1993: 171-181
- [19]
- Xiaolei Qian, Gio Wiederhold:
Incremental Recomputation of Active Relational Expressions.
IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991)
- [20]
- Arnon Rosenthal, Sharma Chakravarthy, Barbara T. Blaustein, José A. Blakeley:
Situation Monitoring for Active Databases.
VLDB 1989: 455-464
- [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
- [22]
- Eric Simon, Jerry Kiernan, Christophe de Maindreville:
Implementing High Level Active Rules on Top of a Relational DBMS.
VLDB 1992: 315-326
- [23]
- Arie Tzvieli:
On the Coupling of a Production System Shell and a DBMS.
JCDKB 1988: 291-309
- [24-1]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
Contents - [24-2]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - [25]
- Leonie van der Voort, Arno Siebes:
Termination and Confluence of Rule Execution.
CIKM 1993: 245-255
- [26]
- Yuli Zhou, Meichun Hsu:
A Theory for Rule Triggering Systems.
EDBT 1990: 407-421
Referenced by
- 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)
- Sin Yeung Lee, Tok Wang Ling:
Unrolling Cycles to Decide Trigger Termination.
VLDB 1999: 483-493
- Yahia Rabih:
Formalisation and Analysis of Dynamic Behaviour in Object-Oriented Systems.
ADBIS (Short Papers) 1999: 163-170
- Elena Baralis, Stefano Ceri, Stefano Paraboschi:
Compile-Time and Runtime Analysis of Active Behaviors.
IEEE Trans. Knowl. Data Eng. 10(3): 353-370(1998)
- James Bailey, Guozhu Dong, Kotagiri Ramamohanarao:
Decidability and Undecidability Results for the Termination Problem of Active Database Rules.
PODS 1998: 264-273
- James Bailey, Lobel Crnogorac, Kotagiri Ramamohanarao, Harald Søndergaard:
Abstract Interpretation of Active Rules and its Use in Termination Analysis.
ICDT 1997: 188-202
- Elena Baralis, Stefano Ceri, Stefano Paraboschi:
Modularization Techniques for Active Rules Design.
ACM Trans. Database Syst. 21(1): 1-29(1996)
- Jennifer Widom, Stefano Ceri (Eds.):
Active Database Systems: Triggers and Rules For Advanced Database Processing.
Morgan Kaufmann 1996, ISBN 1-55860-304-2
Contents - 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)
- H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz:
View Maintenance Issues for the Chronicle Data Model.
PODS 1995: 113-124
- Stephen Correl, Daniel P. Miranker:
On Isolation, Concurrency, and the Venus Rule Language.
CIKM 1995: 281-289
- Elena Baralis, Stefano Ceri, Stefano Paraboschi:
Declarative Specification of Constraint Maintenance.
ER 1994: 205-222
Last update Fri May 25 08:45:31 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
