Paper Info
Title
A predicate matching algorithm for database rule systems
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.
Year
DOI
Venue
1990
10.1145/93605.98736
SIGMOD Conference
Keywords
Field
DocType
expert system rule engine,sequential search,matching predicate,large expert systems application,standard algorithm,dynamic insertion,database rule system,forward-chaining rule system,predicate matching algorithm,interval binary search tree,efficient retrieval,expert system,binary search tree,total order
Data mining,Standard algorithms,Computer science,Expert system,Algorithm,Hash function,Inference engine,Predicate (grammar),Linear search,Database,Binary search tree,Blossom algorithm
Conference
Volume
Issue
ISSN
19
2
0163-5808
ISBN
Citations 
PageRank 
0-89791-365-5
76
39.63
References 
Authors
13
4
Name
Order
Citations
PageRank
Eric N. Hanson1917376.11
Moez Chaabouni28140.77
Chang Ho Kim39442.60
Yu-Wang Wang411660.82