A Predicate Matching Algorithm for Database Rule Systems

Summary: Proposes an efficient predicate-matching algorithm for large database rule systems, outperforming hashing/sequential search on predicates in ordered domains. IBS-tree enables fast retrieval of overlapping intervals with dynamic insert/delete, boosting forward-chaining performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2553
Venue: SIGMOD
Year: 1990
Pagerank: 8.5034389e-05
Overall Rank: 2,495 | 82.89%
DOI: 10.1145/93597.98736

Incoming Non-self Citations Over Time

Authors

1. Eric N. Hanson (United States Air Force; Wright State University)
2. Moez Chaabouna (Wright State University)
3. Chang-Ho Kim (Wright State University)
4. Yu-Wang Wang (Wright State University)

BibTeX Citation

@inproceedings{hanson_sigmod90,
        title = {{A Predicate Matching Algorithm for Database Rule Systems}},
        author = {Hanson, Eric N. and Chaabouna, Moez and Kim, Chang-Ho and Wang, Yu-Wang},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.98736},
        url = {https://dl.acm.org/doi/10.1145/93597.98736},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
576	Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS	1991	VLDB	0.00016238156
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
1,590	Implementing Set-Oriented Production Rules as an Extension to Starburst	1991	VLDB	0.00010257581
2,009	Rule Condition Testing and Action Execution in Ariel	1992	SIGMOD	9.3096289e-05
2,530	Incremental Evaluation of Rules and its Relationship to Parallelism	1991	SIGMOD	8.458663e-05
6,016	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	6.0082425e-05
7,852	Indexing and Selecting Hierarchical Business Logic	2015	VLDB	5.5313703e-05
8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.409313e-05
10,017	Continuous Query Processing in Data Streams Using Duality of Data and Queries	2006	SIGMOD	5.1758281e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	619	Reasoning about Record Matching Rules	2009	VLDB
2	1,560	Example-driven Design of Efficient Record Matching Queries	2007	VLDB
3	8,226	Data Management for Large Rule Systems	1991	VLDB
4	7,852	Indexing and Selecting Hierarchical Business Logic	2015	VLDB
5	5,074	An Algebraic Approach to Rule Analysis in Expert Database Systems	1994	VLDB
6	12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB
7	6,364	An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases	1993	VLDB
8	13,112	Effects of Database Size on Rule System Performance: Five Case Studies	1991	VLDB
9	13,199	Adaptive Predicate Managers in Database Systems	1986	VLDB
10	113	Interval Hierarchies And Their Application To Predicate Files	1977	SIGMOD