Rule validation in object-oriented knowledge bases
Ping Kun Tony Wu, Stanley Y. W. Su, Nabil N. Kamel · 1994
A knowledge-based system, such as an expert system or a deductive database system, is a deduction system which consists of a finite body of knowledge and an inference engine. Such a system has the capabilities of storing and processing data and knowledge rules, and performing logical deductions. In real-world applications, a knowledge base can contain a large number of rules which pose problems in terms of their consistency and efficiency. Thus, some automatic knowledge base validation and refinement procedures are necessary for building a reliable and efficient knowledge-based system. This research aims to develop methodologies, theories, and techniques for validating and refining a knowledge base. We first propose to use the object-oriented approach to represent knowledge. An object calculus, a formalism based on first-order logic, has been developed for the knowledge representation and for providing a theoretical foundation for the rule validation research. Then, we develop a unified framework for rule validation (i.e., the detection of inconsistencies) and rule refinement (i.e., the improvement of efficiency). This framework utilizes theories and techniques introduced in mathematical logic and mechanical theorem proving. In particular, we formally define the concept of rule base inconsistency and show its relationship with the concept of unsatisfiability in formal logic. We also define the completeness of a rule validation algorithm and show that our rule validation method is complete in the sense that it can not only identify all the input facts causing the system to deduce contradictions but also determine the specific subset of rules involved in the deductions of the contradictions. In addition, we formally define rule base redundancies in general. The rule refinement procedure can detect redundancies and circular chains in a rule base. Its completeness is defined and proved in this work. Finally, we implement (in Prolog) a rule validation and refinement system to verify the theories and to evaluate the techniques. For achieving better system efficiency, we use two techniques in the implementation: the unified framework for both rule validation and rule refinement, and the reversed subsumption deletion strategy. The performance evaluation shows that combining these two techniques can significantly improve the system performance.