Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms.

Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms. SIGMOD Conference 1988: 404-412
  author    = {Timos K. Sellis and
               Chih-Chen Lin and
               Louiqa Raschid},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {Implementing Large Production Systems in a DBMS Environment:
               Concepts and Algorithms},
  booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
               Management of Data, Chicago, Illinois, June 1-3, 1988},
  publisher = {ACM Press},
  year      = {1988},
  pages     = {404-412},
  ee        = {, db/conf/sigmod/SellisLR88.html},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP,}


It has been widely recognized that many future database applications, including engineering processes, manufacturing and communications, will require some kind of rule based reasoning. In this paper we study methods for storing and manipulating large rule bases using relational database management systems. First, we provide a matching algorithm which can be used to efficiently identify applicable rules. The second contribution of this paper, is our proposal for concurrent execution strategies which surpass, in terms of performance, the sequential OPS5 execution algorithm. The proposed method is fully parallelizable, which makes its use even more attractive, as it can be used in parallel computing environments.

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

Haran Boral, Per-Åke Larson (Eds.): Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988 BibTeX , SIGMOD Record 17(2), June 1988

Online Edition: ACM Digital Library


François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. VLDB 1986: 457-466 BibTeX
Peter Buneman, Eric K. Clemons: Efficient Monitoring Relational Databases. ACM Trans. Database Syst. 4(3): 368-382(1979) BibTeX
Upen S. Chakravarthy, Jack Minker: Multiple Query Processing in Deductive Databases using Query Graphs. VLDB 1986: 384-391 BibTeX
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
Charles Forgy: Rete: A Fast Algorithm for the Many Patterns/Many Objects Match Problem. Artif. Intell. 19(1): 17-37(1982) BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Frederick Hayes-Roth: Rule-Based Systems. Commun. ACM 28(9): 921-932(1985) BibTeX
Daniel P. Miranker: Performance Estimates for the DADO Machine: A Comparison of Treat and Rete. FGCS 1984: 449-457 BibTeX
Jooseok Park, Arie Segev: Using Common Subexpressions to Optimize Multiple Queries. ICDE 1988: 311-319 BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX
Michael Stonebraker, Timos K. Sellis, Eric N. Hanson: An Analysis of Rule Indexing Implementations in Data Base Systems. Expert Database Conf. 1986: 465-476 BibTeX
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX

Referenced by

  1. Eric N. Hanson, Chris Carnes, Lan Huang, Mohan Konyala, Lloyd Noronha, Sashi Parthasarathy, J. B. Park, Albert Vernon: Scalable Trigger Processing. ICDE 1999: 266-275
  2. 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)
  3. Louiqa Raschid, Jorge Lobo: Semantics for Update Rule Programs and Implementations in a Relational Database Management System. ACM Trans. Database Syst. 21(4): 526-571(1996)
  4. Jennifer Widom: The Starburst Active Database Rule System. IEEE Trans. Knowl. Data Eng. 8(4): 583-595(1996)
  5. H. V. Jagadish, Alberto O. Mendelzon, Inderpal Singh Mumick: Managing Rule Conflicts in an Active Database. PODS 1996: 192-201
  6. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
  7. Wen-Chi Hou, Zhongyang Zhang: Enhancing Database Correctness: a Statistical Approach. SIGMOD Conference 1995: 223-232
  8. Elena Baralis, Jennifer Widom: An Algebraic Approach to Rule Analysis in Expert Database Systems. VLDB 1994: 475-486
  9. Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Coupling Production Systems and Database Systems: A Homogeneous Approach. IEEE Trans. Knowl. Data Eng. 5(2): 240-256(1993)
  10. Françoise Fabret, Mireille Régnier, Eric Simon: An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases. VLDB 1993: 455-466
  11. Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
  12. Alexander J. Pasik: A Source-to-Source Transformation for Increasing Rule-Based System Parallelism. IEEE Trans. Knowl. Data Eng. 4(4): 336-343(1992)
  13. Françoise Fabret, Mireille Régnier, Eric Simon: Optimizing Incremental Computation of Datalog Programs with Non-deterministic Semantics. ICDT 1992: 155-170
  14. Ing-Miin Hsu, Mukesh Singhal, Ming T. Liu: Distributed Rule Processing in Active Databases. ICDE 1992: 106-113
  15. Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285
  16. Ulf Schreier, Hamid Pirahesh, Rakesh Agrawal, C. Mohan: Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS. VLDB 1991: 469-478
  17. Narain H. Gehani, H. V. Jagadish: Ode as an Active Database: Constraints and Triggers. VLDB 1991: 327-336
  18. Rakesh Agrawal, Roberta Cochrane, Bruce G. Lindsay: On Maintaining Priorities in a Production Rule System. VLDB 1991: 479-487
  19. Douglas N. Gordin, Alexander J. Pasik: Set-Oriented Constructs: From Rete Rule Bases to Database Systems. SIGMOD Conference 1991: 60-67
  20. Arie Segev, J. Leon Zhao: Evaluation of Rule Processing Strategies In Expert Databases. ICDE 1991: 404-412
  21. Jennifer Widom, Sheldon J. Finkelstein: Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270
  22. Jaideep Srivastava, Kuo-Wei Hwang, Jack S. Eddy Tan: Parallelism in Database Production Systems. ICDE 1990: 121-128
  23. Zvi M. Kedem, Alexander Tuzhilin: Relational Database Behavior: Utilizing Relational Discrete Event Systems and Models. PODS 1989: 336-346
  24. Alexander Tuzhilin, Zvi M. Kedem: Querying and Controlling the Future Behaviour of Complex Objects. ICDE 1989: 434-442
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:55 2009