On
the Performance of Lazy Matching in Production Systems
Daniel P. Miranker, David A. Brant, Bernie Lofaso and David Gadbois
Proceedings of the 8th National Conference on Artificial Intelligence
AAAI Press / The MIT Press, 1990, Pages 685-692
Abstract
Production systems are an established method for encoding knowledge in an expert systems. The semantics of production system languages and the concomitant algorithms for their evaluation, RETE and TREAT, enuerate the set of rule instantiations and then apply a strategy that selects a single instantiation for firing. Often rule instantations are calculated and never fired. In a sense, the time and space required to eagerly compute these unfired instantiations is wasted. This paper presents preliminary results about a new match technique, lazy matching. The lazy match algoirthm folds the selection strategy into the search for instantiations, such that only one instantiation is computed per cycle. The algorithm improves the worst-case aysmptotic space complexity of incremental matching. Moreover, emperical and analytic resulst demonstrate that lazy matching can substantially improve the execution time of production system programs.
full-text.pdf
An Algorithmic Basis for Integrating Production Systems and Large Databases
Daniel P. Miranker, David A. Brant
ICDE 1990: 353-360
@inproceedings{DBLP:conf/icde/MirankerB90,
author = {Daniel P. Miranker and
David A. Brant},
title = {An Algorithmic Basis for Integrating Production Systems and Large
Databases},
booktitle = {Proceedings of the Sixth International Conference on Data Engineering,
February 5-9, 1990, Los Angeles, California, USA},
publisher = {IEEE Computer Society},
year = {1990},
isbn = {0-8186-2025-0},
pages = {353-360},
ee = {db/conf/icde/MirankerB90.html},
crossref = {DBLP:conf/icde/90},
bibsource = {DBLP, http://dblp.uni-trier.de}
}