Pattern match reduction in the relational production language
James N. Etheredge, Lois Delcambre · 1989
Production system languages have become a popular tool for the development of viable expert systems in a wide variety of application domains. The success of these languages has stimulated research relating to production system technology. One such area of interest is the extension of the data storage and access capabilities of production systems in order to accommodate larger knowledge bases. A second area of interest is the application of production system inferencing capabilities to the vast amount of data/knowledge currently stored in conventional databases. The research presented here combines the inferencing capabilities of a production language with the data storage and management capabilities of a relational DBMS. The Relational Production Language, RPL, uses a main-memory resident relational database (MMDB) as its working memory. The left hand side of a production rule in RPL issues a relational query against the MMDB. Each tuple in the answer set returned by the query represents an instantiation of the rule and is added to the conflict set. When a rule fires, the relational update operations specified on the right hand side of the rule modify the MMDB. Important research topics associated with the RPL paradigm include the effects of set-valued instantiations, the self-controlling potential of the RPL paradigm, the introduction of parallel firing for both rules and instantiations of rules, and system performance and evaluation metrics. The focus of this dissertation is the design of an efficient interpreter for RPL. In order to provide acceptable performance, the interpreter design must minimize the pattern matching necessary to generate the conflict set on each interpreter cycle. The maintenance of complete state information by the interpreter (as in the Rete algorithm) is impractical in the RPL environment due to the size and volatility of working memory. The reissuance of queries when a relatively small number of tuples have been modified is obviously inefficient. The research presented here defines appropriate structures and algorithms to improve the efficiency of the RPL interpreter. These algorithms are tested via the execution and subsequent analysis of test programs run on a simulator developed to emulate the RPL paradigm, the RPL paradigm utilizing the optimization algorithms, and the Rete algorithm commonly used to implement production system languages.