Browse Theses

The Relational Production Language, RPL, is a rule language where both the condition and action part of a rule is expressed in a relational language. This makes RPL a natural choice for expert database systems. One serious challenge presented by RPL concerns performance. In this research, the performance of the RPL interpreter is directly addressed in three main ways.

First, the use of a main memory database to support both the materialized views and the query processing is explored. In this research, a new MMDBS called USL is presented and formally evaluated. By using a simple uniform storage structure for intermediate and base relations without indices, the USL MMDBS easily supports materialized query results to facilitate the generation of the conflict set. Within the RPL framework, the storage required for a USL database is only 5% to 10% of the other proposed MMDBSs. And, although the USL MMDBS uses minimum space, it provides several orders of magnitude improvement for sort, join, and set operations, compared to other MMDBSs.

Second, the two most time-consuming aspects of the production system interpreter, i.e., the match process and termination detection, are addressed by the use of algorithms developed and proven correct in this research called the PMR/TD algorithms. PMR/TD enhances the performance of PMR, a technique based on view materialization proposed as an alternative to the Rete algorithm, by using more efficient formulas and including the termination detection algorithm as a part of the match process. PMR/TD termination detection comes as a part of conflict set maintenance at no extra cost using a technique similar to refraction.

The final part, is the development of the detailed design of an efficient interpreter for the RPL production language. In order to improve the performance of the interpreter, a tight integration of the two research components described above (USL MMDBS and PMR/TD) is presented. Finally, three techniques are presented, i.e., algebraic transformation, PMR/TD selection, and index selection, to optimize the execution of the RPL interpreter.