Technique for compilation of knowledge bases

• US 4,924,408 A
• Filed: 08/19/1988
• Issued: 05/08/1990
• Est. Priority Date: 08/19/1988
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Highland, Frederic D.
• Primary Examiner(s): MACDONALD, ALLEN R
• Application Number:
  US07/234,268
• Time in Patent Office: 627 Days
• Field of Search: 364/513, 364/300, 364/200, 364/900
• US Class Current: 706/60
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06N 5/042 Backward inferencing
• CPC Class Codes: G06N 5/047 Pattern matching networks; Rete networks

Abstract

A method is disclosed for converting both a knowledge base and an inferencing technique into compilable program code forming a knowledge based system. The method is based on determining what actions an interpretitive inference engine would take with the specific knowledge base and generating only the program code needed to perform these actions. These method eliminates the overhead of interpreting a representation of the knowledge base and significantly improves performance of the system. The method is applicable to both forward and backward chaining reasoning strategies and does not modify or restrict the functional capabilities of the knowledge based system.

Claims

1. A method of converting both a knowledge base and an inferencing technique into compilable program code forming a knowledge based system, said knowledge base including rules and data items, said rules being arranged in a network of nodes and links between such nodes, said nodes representing tests, logical operators, actions and data items, said network being in a form convenient for interpretive inferencing, said method comprising the steps of:

(a) partitioning said network into a plurality of sub-networks;

(b) labelling each node within each respective sub-network with a unique identifier;

(c) generating a segment of compilable, procedural, program code for inferencing which is equivalent to each respective sub-network when combined with said inferencing technique, said identifiers locating the respective code for each node within each respective sub-network, said inferencing code comprising a node sub-segment that implements the function of each node in said respective sub-network based on the rules specified in said knowledge base and that conditionally invokes other sub-segments using said identifiers, and a control sub-segment which provides access to each node sub-segment using said identifiers and provides for repeated execution of each node sub-segment as necessary; and

(d) generating for each data item a segment of compilable procedural, program code for the distribution of such data item which invokes the appropriate program inferencing code by means of said identifiers when such data item is modified during execution of the knowledge based system.

2. The method defined in claim 1, further comprising the initial step of:

forming said network from said knowledge base.

3. The method defined in claim 1, wherein step (a) includes the step of selecting rule trees in said network as the respective sub-networks, with each rule tree'"'"'s action, which is the root of the rule tree, becoming the start of the respective sub-network.

4. The method defined in claim 1, wherein step (a) includes the step of selecting nodes in said network as the respective sub-networks such that the references to nodes outside said sub-networks are minimized.

5. The method defined in claim 1, wherein step (b) includes the step of depth-first traversing each sub-network, starting at the end of such sub-network, and labelling each node in such sub-network sequentially.

6. The method defined in claim 5, wherein said nodes in each sub-network are labeled sequentially in consecutive order.

7. The method defined in claim 6, wherein said nodes of each sub-network are labeled sequentially in consecutive order starting with the number "1".

8. The method defined in claim 1, wherein step (c) includes the step of depth-first traversing each sub-network and generating a segment of compilable, procedural, program code for inferencing which is equivalent to such sub-network, said inferencing code comprising (1) a prologue consisting of initialization, while and case statements, (2) a case part for each node that implements the function of that node based on the rules specified in the knowledge base and conditional statements to reset the identifier to the next node to be evaluated, and (3) an epilogue comprising said control sub-segment.

9. The method defined in claim 8, wherein node subsegments that are referenced by the program code for other sub-networks contain calls to the referencing rule procedures that pass the identifier for the reference point and any data associated therewith.

10. The method defined in claim 8, wherein node sub-segments contain calls to utility software to implement functions whose logic is not derived from said knowledge base.

11. The method defined in claim 1, wherein step (c) includes the step of generating a segment of inferencing code which includes calls to said distribution code for propagation of updated data items.

12. The method defined in claim 1, wherein step (d) includes the step of generating said distribution code consisting of a prologue sub-segment, a subsegment to call each rule procedure which references the data item, and an epilogue sub-segment.

13. The method defined in claim 12, wherein said call sub-segment passes the identifier for the test node to be executed by the inferencing code.