dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases.

Françoise Fabret, Mireille Régnier, Eric Simon: An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases. VLDB 1993: 455-466
@inproceedings{DBLP:conf/vldb/FabretRS93,
  author    = {Fran\c{c}oise Fabret and
               Mireille R{\'e}gnier and
               Eric Simon},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {An Adaptive Algorithm for Incremental Evaluation of Production
               Rules in Databases},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {455-466},
  ee        = {db/conf/vldb/FabretRS93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Several incremental algorithms have been proposed to evaluate database production rule programs. They all derive from existing incremental algorithms, like RETE and TREAT, developed for rule-based systems in the framework of Artificial Intelligence. In this paper, we address a specific but crucial problem that arises with theseincremental algorithms: how much data should be profitably materialized and maintained in order to speed-up program evaluation? We show that the answer exposes to a well known tradeoff. Our major contribution is to propose an adaptive algorithm that takes as input a program of rules and returns for each rule, the set of most profitable relational expressions that should be maintained in order to obtain a good compromise. A notable feature of our algorithm is that it works for both set-oriented and instance-oriented rules. We compare our algorithms with existing incremental algorithms for database production rule programs.

Copyright © 1993 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 ...

Printed Edition

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BCL89]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BFKM85]
...
[Bry89]
François Bry: Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited. SIGMOD Conference 1989: 193-204 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DE88]
Lois M. L. Delcambre, James N. Etheredge: The Relational Production Language: A Production Language for Relational Databases. Expert Database Conf. 1988: 333-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[For82]
Charles Forgy: Rete: A Fast Algorithm for the Many Patterns/Many Objects Match Problem. Artif. Intell. 19(1): 17-37(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Han92]
Eric N. Hanson: Rule Condition Testing and Action Execution in Ariel. SIGMOD Conference 1992: 49-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HW92]
...
[KdMS90]
Gerald Kiernan, Christophe de Maindreville, Eric Simon: Making Deductive Databases a Practical Technology: A Step Forward. SIGMOD Conference 1990: 237-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mir87]
Daniel P. Miranker: TREAT: A Better Match Algorithm for AI Production System Matching. AAAI 1987: 42-47 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Pai83]
Robert Paige: Transformational Programming - Applications to Algorithms and Systems. POPL 1983: 73-87 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PK82]
Robert Paige, Shaye Koenig: Finite Differencing of Computable Expressions. ACM Trans. Program. Lang. Syst. 4(3): 402-454(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SJGP90]
Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SKdM92]
Eric Simon, Jerry Kiernan, Christophe de Maindreville: Implementing High Level Active Rules on Top of a Relational DBMS. VLDB 1992: 315-326 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SLR88]
Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms. SIGMOD Conference 1988: 404-412 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SZ91]
Arie Segev, J. Leon Zhao: Data Management for Large Rule Systems. VLDB 1991: 297-307 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WCL91]
Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. François Llirbat, Françoise Fabret, Eric Simon: Eliminating Costly Redundant Computations from SQL Trigger Executions. SIGMOD Conference 1997: 428-439
  2. Wilburt Labio, Dallan Quass, Brad Adelberg: Physical Database Design for Data Warehouses. ICDE 1997: 277-288
  3. Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conference 1996: 447-458
  4. Martin Sköld, Tore Risch: Using Partial Differencing for Efficient Monitoring of Deferred Complex Rule Conditions. ICDE 1996: 392-401
  5. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
    Contents

Last update Fri Sep 14 17:38:16 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page