Effects of Database Size on Rule System Performance: Five Case Studies.

David A. Brant, Timothy Grose, Bernie J. Lofaso, Daniel P. Miranker: Effects of Database Size on Rule System Performance: Five Case Studies. VLDB 1991: 287-296
  author    = {David A. Brant and
               Timothy Grose and
               Bernie J. Lofaso and
               Daniel P. Miranker},
  editor    = {Guy M. Lohman and
               Am\'{\i}lcar Sernadas and
               Rafael Camps},
  title     = {Effects of Database Size on Rule System Performance: Five Case
  booktitle = {17th International Conference on Very Large Data Bases, September
               3-6, 1991, Barcelona, Catalonia, Spain, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1991},
  isbn      = {1-55860-150-3},
  pages     = {287-296},
  ee        = {db/conf/vldb/BrantGLM91.html},
  crossref  = {DBLP:conf/vldb/91},
  bibsource = {DBLP,}


Building practical expert database systems requires an effective inferencing capability over large data sets. Inferencing in this context means repeatedly executing a fixed set of queries, interleaved with update transactions, until a fixed point is reached. The effectiveness of the interferencing mechanism is heavily dependent upon theamount of state space needed and the ability of the underlying algorithms to avoid unnecessary work. Common techniques used in the design of rule-based systems store large amounts of state in order to derive precise query support information that will enable better performance. These techniques were intended for use in main memory on small data sets and are not necessarily suited for a database environment. When confronted with a large database these techniques may experience severe performance problems - severe enough to render them useless. In this paper we examine the effects of database size on live test cases. The use of real programs with real data provides insights that are not to be found through analysis and simulation. We compare two different rule systems, one based on the TREAT match algorithm and the other on LEAPS, a lazy matching algorithm. The results show that state can be a problem in rule systems and that by using lazy matching it is possible to eliminate some state while improving performance.

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

Guy M. Lohman, Amílcar Sernadas, Rafael Camps (Eds.): 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings. Morgan Kaufmann 1991, ISBN 1-55860-150-3


[Bein et al.,1987]
Jonathan Bein, Roger King: MOBY: An Architecture for Distributed Expert Database Systems. VLDB 1987: 13-20 BibTeX
[Blakeley & Martin,1990]
José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263 BibTeX
Donald Cohen: Compiling Complex Database Transition Triggers. SIGMOD Conference 1989: 225-234 BibTeX
[Delcambre & Etheredge,1988]
Lois M. L. Delcambre, James N. Etheredge: The Relational Production Language: A Production Language for Relational Databases. Expert Database Conf. 1988: 333-351 BibTeX
Charles Forgy: Rete: A Fast Algorithm for the Many Patterns/Many Objects Match Problem. Artif. Intell. 19(1): 17-37(1982) BibTeX
[Joobbani & Siewiorek,1986]
[Kiernan et al.,1990]
Gerald Kiernan, Christophe de Maindreville, Eric Simon: Making Deductive Databases a Practical Technology: A Step Forward. SIGMOD Conference 1990: 237-246 BibTeX
[McDermott et al.,1978]
[Miranker et al.,1990 ]
[Miranker & Brant,1990]
Daniel P. Miranker, David A. Brant: An Algorithmic Basis for Integrating Production Systems and Large Databases. ICDE 1990: 353-360 BibTeX
[Oflazer, 1986]
[Raschid et al.,1988]
Louiqa Raschid, Timos K. Sellis, Chih-Chen Lin: Exploiting Concurrency in a DBMS Implementation for Production. DPDS 1988: 34-45 BibTeX
[Srivastava et al.,1990]
Jaideep Srivastava, Kuo-Wei Hwang, Jack S. Eddy Tan: Parallelism in Database Production Systems. ICDE 1990: 121-128 BibTeX
[Tan et al.,1990]
[Wang & Hanson,1990]
Yu-Wang Wang, Eric N. Hanson: A Performance Comparison of the Rete and TREAT Algorithms for Testing Database Rule Conditions. ICDE 1992: 88-97 BibTeX

Referenced by

  1. 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)
  2. Tadashi Ohmori, Mamoru Hoshi: Gaming-Simulations of Multi-Agent Information Systems using Large Databases: The Concept and Database Algorithms. DASFAA 1995: 95-106
  3. Stephen Correl, Daniel P. Miranker: On Isolation, Concurrency, and the Venus Rule Language. CIKM 1995: 281-289
  4. Amy J. Lee, Elke A. Rundensteiner, Spencer Thomas: Physical Map Assembler: An Active Object-Oriented Database for Human Genome Applications. SSDBM 1994: 128-137
  5. David A. Brant, Daniel P. Miranker: Index Support for Rule Activation. SIGMOD Conference 1993: 42-48
  6. Marco Richeldi, Jack Tan: JazzMatch: Fine-Grained Parallel Matching for Large Rule Sets. ICDE 1993: 616-623
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:48 2009