Checking a Knowledge-Based System for Consistency and Completeness

  • Tin A. Nguyen
  • Walton A. Perkins
  • Thomas J. Laffey
  • Deanne Pecora


We describe a computer program that implements an algorithm to verify the consistency and completeness of knowledge bases built for the Lockheed expert system (LES) shell. The algorithms described here are not specific to this particular shell and can be applied to many rule-based systems. The computer program, which we call CHECK, combines logical principles as well as specific information about the knowledge representation formalism of LES. The program checks both goal-driven and data-driven rules. CHECK identifies inconsistencies in the knowledge base by looking for redundant rules, conflicting rules, subsumed rules, unnecessary IF conditions, and circular rule chains. Checking for completeness is done by looking for unreferenced attribute values, illegal attribute values, dead-end IF conditions, dead-end goals and unreachable conclusions. These conditions can be used to suggest missing rules and gaps in the knowledge base. The program also generates a chart that shows the dependencies among the rules. CHECK can help the knowledge engineer detect many programming errors even before the knowledge base testing phase. It also helps detect gaps in the knowledge base testing phase. It also helps detect gaps in the knowledge base that the knowledge engineer and the expert have overlooked. A wide variety of knowledge bases have been analyzed using CHECK.