ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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
@inproceedings{DBLP:conf/vldb/BrantGLM91,
  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
               Studies},
  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, http://dblp.uni-trier.de}
}

Abstract

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 ...

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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Bein et al.,1987]
Jonathan Bein, Roger King: MOBY: An Architecture for Distributed Expert Database Systems. VLDB 1987: 13-20 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Blakeley & Martin,1990]
José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cohen,1989]
Donald Cohen: Compiling Complex Database Transition Triggers. SIGMOD Conference 1989: 225-234 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Forgy,1981]
...
[Forgy,1982]
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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McDermott et al.,1978]
...
[Miranker,1990]
...
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Oflazer, 1986]
...
[Perlin,1989]
...
[Raschid et al.,1988]
Louiqa Raschid, Timos K. Sellis, Chih-Chen Lin: Exploiting Concurrency in a DBMS Implementation for Production. DPDS 1988: 34-45 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Srivastava et al.,1990]
Jaideep Srivastava, Kuo-Wei Hwang, Jack S. Eddy Tan: Parallelism in Database Production Systems. ICDE 1990: 121-128 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tan et al.,1990]
...
[Wang,1989]
...
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Winston,1984]
...

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

Copyright © Mon Nov 2 21:18:34 2009 by Michael Ley (ley@uni-trier.de)