This project investigates techniques that allow programs written in the Production System (PS) paradigm to reason correctly and efficiently with large databases located on secondary storage. A class of stratified PS programs are identified. For this class of programs, an operational semantics and a model theoretic semantics are developed. The correct semantics ensure that a stratified PS program will correspond to a consistent theory, the execution of the program will not produce incorrect, inconsistent answers and execution of the program will terminate. Implementation techniques for stratified PS programs using relational data structures and relational queries are developed as well as strategies for the concurrent execution of productions in stratified PS programs. The results of this research will provide a foundation for expert systems, written as stratified PS programs, to reason correctly and efficiently with data in relational databases.
