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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

References

[Bein et al.,1987]: Jonathan Bein, Roger King: MOBY: An Architecture for Distributed Expert Database Systems. VLDB 1987: 13-20
[Blakeley & Martin,1990]: José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263
[Cohen,1989]: Donald Cohen: Compiling Complex Database Transition Triggers. SIGMOD Conference 1989: 225-234
[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
[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)
[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
[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
[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
[Srivastava et al.,1990]: Jaideep Srivastava, Kuo-Wei Hwang, Jack S. Eddy Tan: Parallelism in Database Production Systems. ICDE 1990: 121-128
[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
[Winston,1984]: ...