A Predicate Matching Algorithm for Database Rule Systems.

Eric N. Hanson, Moez Chaabouni, Chang-Ho Kim, Yu-Wang Wang: A Predicate Matching Algorithm for Database Rule Systems. SIGMOD Conference 1990: 271-280

@inproceedings{DBLP:conf/sigmod/HansonCKW90,
  author    = {Eric N. Hanson and
               Moez Chaabouni and
               Chang-Ho Kim and
               Yu-Wang Wang},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {A Predicate Matching Algorithm for Database Rule Systems},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {271-280},
  ee        = {http://doi.acm.org/10.1145/93597.98736, db/conf/sigmod/HansonCKW90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Forward-chaining rule systems must test each newly asserted fact against a collection of predicates to find those rules that match the fact. Expert system rule engines use a simple combination of hashing and sequential search for this matching. We introduce an algorithm for finding the matching predicates that is more efficient than the standard algorithm when the number of predicates is large. We focus on equality and inequality predicates on totally ordered domains. This algorithm is well-suited for database rule systems, where predicate-testing speed is critical. A key component of the algorithm is the interval binary search tree (IBS-tree). The IBS-tree is designed to allow efficient retrieval of all intervals (e. g. range predicates) that overlap a point, while allowing dynamic insertion and deletion of intervals. The algorithm could also be used to improve the performance of forward-chaining inference engines for large expert systems applications.

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

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/smod7592 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

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990

, SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library

References

[AL62]: ...
[Bay72]: Rudolf Bayer: Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms. Acta Inf. 1: 290-306(1972)
[BO89]: Virginia E. Barker, Dennis E. O'Connor: Expert Systems for Configuration at Digital: XCON and Beyond. Commun. ACM 32(3): 298-318(1989)
[Col89]: ...
[DBB*88]: Umeshwar Dayal, Barbara T. Blaustein, Alejandro P. Buchmann, Upen S. Chakravarthy, Meichun Hsu, R. Ledin, Dennis R. McCarthy, Arnon Rosenthal, Sunil K. Sarin, Michael J. Carey, Miron Livny, Rajiv Jauhari: The HiPAC Project: Combining Active Databases and Timing Constraints. SIGMOD Record 17(1): 51-70(1988)
[DE88]: Lois M. L. Delcambre, James N. Etheredge: The Relational Production Language: A Production Language for Relational Databases. Expert Database Conf. 1988: 333-351
[For81]: ...
[For82]: Charles Forgy: Rete: A Fast Algorithm for the Many Patterns/Many Objects Match Problem. Artif. Intell. 19(1): 17-37(1982)
[GS78]: Leonidas J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. FOCS 1978: 8-21
[Gut84]: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
[Han89]: Eric N. Hanson: An Initial Report on The Design of Ariel: A DBMS With an Integrated Production Rule System. SIGMOD Record 18(3): 12-19(1989)
[HC89]: ...
[KS89]: ...
[McC85]: Edward M. McCreight: Priority Search Trees. SIAM J. Comput. 14(2): 257-276(1985)
[Mir87]: Daniel P. Miranker: TREAT: A Better Match Algorithm for AI Production System Matching. AAAI 1987: 42-47
[S*79]: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34
[Sam88]: Hanan Samet: Hierarchical Representations of Collections of Small Rectangles. ACM Comput. Surv. 20(4): 271-309(1988)
[Sam90]: Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
[SHP88]: Michael Stonebraker, Eric N. Hanson, Spyros Potamianos: The POSTGRES Rule Manager. IEEE Trans. Software Eng. 14(7): 897-907(1988)
[SLR89]: Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Data Intensive Production Systems: The DIPS Approach. SIGMOD Record 18(3): 52-57(1989)
[SSH86]: Michael Stonebraker, Timos K. Sellis, Eric N. Hanson: An Analysis of Rule Indexing Implementations in Data Base Systems. Expert Database Conf. 1986: 465-476
[Tar83]: ...