Method and apparatus for efficiently implementing read-type procedural attachments in RETE-like pattern matching environment

• US 5,179,633 A
• Filed: 06/29/1990
• Issued: 01/12/1993
• Est. Priority Date: 06/29/1990
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Yerazunis, William S., Kirk, Steven A., Barabash, William
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Downs, Robert W.
• Application Number:
  US07/546,549
• Time in Patent Office: 928 Days
• Field of Search: 364/513, 395/62, 395/64, 395/76
• US Class Current: 706/48
• CPC Class Codes: G06N 5/047 Pattern matching networks; Rete networks
• CPC Class Codes: Y10S 706/906 Process plant

Abstract

A recticular discrimination network utilized in an expert system that permit read procedural attachments on working memory element slots using a gamma memory. The gamma memory is associated with one- or two- input nodes and stores references to the attached WME slot, use of which minimizes computation and interaction among data elements in a RETE-net.

Claims

1. A computer-based discrimination network for evaluating a set of rules, each rule comprising a set of conditions, each condition including at least one data value variable slot used to accept values of data elements input from a working memory to the network for use in the evaluation of the condition to yield a result, the evaluation of the set of conditions occurring in a condition-matching cycle, the network comprising:

(a) a plurality of nodes, each of the nodes representing one of the set of conditions, the plurality of nodes being coupled to one another in a manner to represent the set of rules;

(b) a processor coupled to the plurality of nodes for passing values of data elements from the working memory to the network and evaluating the conditions represented by each node;

(c) at least one live slot being a pre-determined data value variable slot within a pre-determined data value variable slot within a pre-determined condition, the at least one live slot linked to a corresponding procedure and causing the corresponding procedure to execute, the execution causing a new value of a data element to be supplied to the at least one live slot; and

(d) a gamma memory associated with each one of the rules having a condition with a live slot, each gamma memory storing references to the values of the data elements accepted by the set of conditions of each associated one of the rules having a condition with a live slot where a predetermined result is yielded by a pre-determined subset of the conditions.

2. The computer-based discrimination network of claim 1 further comprising:

(a) a first memory containing the values of data elements; and

(b) the processor coupled to the plurality of nodes being coupled to the first memory and arranged to pass the values of said data elements by passing pointers that reference said data elements, said pointers comprising references to memory locations that contain the values of data elements.

3. The computer-based discrimination network of claim 1 further comprising:

(a) a first memory containing values of data elements; and

(b) the processor coupled to the plurality of nodes being coupled to the first memory and arranged to pass actual data elements as tokens, said tokens comprising data elements stored in the first memory.

4. The computer-based discrimination network of claim 1 further comprising at least one subroutine, said subroutine comprising computer program language statements, the statements together representing the conditions of one of the set of rules.

5. The computer-based discrimination network of claim 1 wherein the pre-determined subset of conditions are the conditions of one of the rules, which conditions do not have a live slot.

6. The computer-based discrimination network of claim 5 wherein each condition yields a true/false result.

7. The computer-based discrimination network of claim 6 wherein the pre-determined result is a true result yielded by all the conditions in the pre-determined subset of conditions.

8. The computer-based discrimination network of claim 6 wherein each rule further comprises a firing part, the firing part being a task processed by the processor when each of the set of conditions comprising the rule is evaluated as true.

9. The computer-based discrimination network of claim 8, wherein the processor performs a predetermined conflict resolution scheme such that when more than one set of conditions comprising a rule are evaluated as true, the conflict resolution scheme determines which firing part to execute.

10. The computer-based discrimination network of claim 1 further comprising an alpha memory and a beta memory, the alpha memory associated with a first condition of one of the rules having two conditions, the alpha memory storing references to the data elements accepted by the first condition, the beta memory associated with a second condition of the rule having two conditions, the beta memory storing references to the data elements accepted by the second condition.

11. The computer-based discrimination network of claim 1 wherein the processor modifies the gamma memory of a rule after the new value of the data element is supplied to the at least one live slot of the condition of the rule.

12. The computer-based discrimination network of claim 11 wherein the modification to the gamma memory by the processor includes adding an add sign to the reference of each value of the data elements where the data elements satisfy all the conditions of the rule.

13. The computer-based discrimination network of claim 11 wherein the modification to the gamma memory by the processor includes adding a minus sign to the reference of each value of the data elements where the data elements do not satisfy all the conditions of the rule.

14. The computer-based discrimination network of claim 1 further comprising an update slot associated with each live slot to store a cycle number.

15. The computer-based discrimination network of claim 1 wherein the set of rules are re-evaluated by the processor after all the conditions in the set of conditions are evaluated in the condition-matching cycle.

22. The method of claim 10 wherein more than one variable in one of the conditions of the rule has associated with it a read procedural attachment.

16. A method carried out by a computer processor for evaluating a rule comprising a set of conditions in a network, the conditions comprising variables and operators, the variables corresponding to data values stored in a first memory, a variable in one of the conditions of the rule having associated with it a read procedural attachment, the read procedural attachment comprising a read function to provide a new data value for the variable that has the associated read procedural attachment, the network comprising a plurality of interconnected nodes, each node representing a condition, the plurality of nodes being coupled in such a manner to represent the set of conditions of the rule, the method carried out by the processor comprising the steps of:

(a) presenting a token representative of the data values of the variables of one of the set of conditions to the network;

(b) evaluating the conditions of the rule that comprise variables that do not have the associated read procedural attachment to determine whether the conditions are satisfied by the token;

(c) if the conditions of the rule that comprise variables that do not have the associated read procedural attachment are satisfied by the token, storing the token in a second memory;

(d) if the conditions of the rule that comprise variables that do not have the associated read procedural attachment are satisfied by the token,

(i) evaluating the node having the read procedural attachment on the variable of the condition by performing the read procedural attachment to collect the new data value,

(ii) evaluating the conditions of the rule that comprise the variable that has the associated read procedural attachment using the new data value to determine whether the conditions of the rule are satisfied, and

(iii) modifying the second memory to store the results of the evaluation of the rule.

17. The method of claim 16 wherein the network is arranged to evaluate a plurality of expressions.

18. The method of claim 17 comprising the following further steps of:

(g) performing subsequent acts when the conditions of any one of the plurality of the rules are satisfied;

(h) for all instances where two tokens satisfy all conditions of two rules, performing a conflict resolution analysis comprising a pre-selected conflict resolution scheme to determine which subsequent acts between the two rules to perform first; and

(i) evaluating for each of the two rules where the result of one of such rules is based on a value having been determined by the read procedural attachment, performing the read procedural attachment again to collect the data value updated by the read procedural attachment, and re-evaluate the one rule using the updated value to re-determine whether the conditions of the one rule is satisfied.

19. The method of claim 16 wherein step (a) further comprises the steps of:

(a) storing the values of the variables of one of the set of conditions in a third memory;

(a) presenting the token representative of the values of the variables of one of the set of conditions to the network as a pointer to the location of the value of the variables of the condition in the third memory; and

(a) accessing the values of the variables of the condition using the pointer.

20. The method of claim 16 wherein step (a) further comprises the steps of placing the value of the data element into the token and presenting the token to the network.

21. The method of claim 16 wherein each of the nodes comprises at least one subroutine, said subroutine comprising computer program language statements, said statements being coupled in such a manner to represent the conditions of the rule.

23. The method of claim 16 wherein parts (i) to (iii) of step (d) are also performed if all conditions of the rule comprise variables that have the associated read procedural attachment.

24. A computer-implemented method for updating data when evaluating an expression comprising a set of conditions organized into a network, the conditions each comprising at least one variable slot, in which data is input to evaluate the conditions, the network comprises a plurality of test nodes each representative of one of the set of conditions, each test node being connected to other test nodes in the network, each one of the test nodes having at least one input means for evaluating the condition and an output, all coupled to a memory, the computer-implemented method comprising the steps of:

(a) declaring a variable slot of the condition of a pre-selected one of the test nodes to be attached to a read function that provides an updated data value for the variable;

(b) presenting a token containing data to the input of the pre-selected test node;

(c) invoking the attached read function before evaluating the token against the condition;

(d) determining whether the token satisfies the condition of the pre-selected test node using the updated data value in the variable slot of the condition;

(e) dividing the memory into areas to cumulatively store the result of the determining step for the pre-selected test node, the result indicating if the condition is satisfied or if the condition is not satisfied only because the updated data value fails to satisfy the condition;

(f) passing to other connected test nodes in the network tokens containing data used in evaluating the expression, when the condition of the pre-selected test node has been satisfied;

(g) repeating steps (b)-(f) each time a new token is presented to the input of the pre-selected test node;

(h) re-evaluating the attached read function for each one of the cumulatively stored results to produce a set of re-updated data values; and

(i) repeating steps (d)-(f) using the set of re-updated data values.

25. A computer program in a storage device for use in connection with a computer processor adapted to respond to changes when evaluating an expression comprising a set of conditions in which the evaluation of the expression is based upon values of data elements presented to the computer program, the computer program comprising:

(a) a plurality of interconnected node modules operative in the computer processor, each of the node modules representing one of the conditions of the expression, each one of the plurality of node modules including at least one input to receive data in evaluating the condition, and an output being coupled in such a manner to represent the set of conditions in the expression;

(b) a token passing module operative in the computer processor for passing tokens representative of data elements to the inputs of the node modules;

(c) a read module operative in the computer processor connected to one of the node modules for accessing a data input from a peripheral source and returning a current data element to be used in evaluating the condition of the one node module;

(d) a testing module operative in the computer processor for determining whether one of the tokens input to the one node module satisfies the condition of the one node module that will upon evaluating the condition of the one node invoke the read module before determining whether the input to the one node module satisfies the corresponding condition of the one node module;

(e) a storage module operative in the computer processor for storing in a memory coupled to the computer processor tokens comprising data used in evaluating the condition of the one test node with an indication that the data contained in the token satisfies the condition or the data contained in the token fails the condition only because the current data element, obtained from the read module, does not satisfy the condition; and

(f) a token propagation module operative in the computer processor for propagating a token from the output of the one node, if the condition of the one node is satisfied.

26. The computer program of claim 25 wherein the token passing, read, storage, testing and token propagation modules, each further comprises:

(a) sub-modules operative in the computer processor to accept data elements in the form of pointers comprising location references to peripheral sources;

(b) sub-modules operative in the computer processor to access data elements located in said peripheral sources;

(c) sub-modules operative in the computer processor to store updated information in said peripheral location accessible by the pointers; and

(d) sub-modules operative in the computer processor to propagate the pointers containing the results of the evaluation to subsequent modules.

27. The computer program of claim 25 further comprising a re-evaluation module operative in the computer processor that re-invokes the read module after a pre-determined time period or in a subsequent cycle and invokes the read module and the testing module.

28. The computer program of claim 25 wherein the computer program is arranged to evaluate a plurality of expressions and further comprises a subsequent action module operative in the computer processor to perform a pre-selected set of subsequent actions when each of the conditions of one or more of the expressions are satisfied.

29. A computer-based expert system comprising a plurality of expressions, each expression comprising a set of conditions, the conditions including at least one variable slot wherein the evaluation of each condition is based upon values of data elements input to the variable slots, the expert system comprising:

(a) a first memory having a plurality of data elements stored therein;

(b) a plurality of nodes each representing one of the conditions comprising the expression, the plurality of nodes being coupled to one another in a manner to represent the set of the conditions comprising the expression;

(c) a processor coupled to the first memory and the plurality of nodes to input values of the data elements stored in the first memory to the data value variable slots of the conditions represented by the plurality of nodes and evaluating the expression for each one of the values of data elements input to the data value variable slots of the conditions represented by the nodes;

(d) at least one live slot being a pre-determined variable slot within a pre-determined condition, the at least one live slot linked to a corresponding procedure causing the corresponding procedure to execute, the execution causing a new value of a data element to be supplied to the at least one live slot; and

(e) a second memory associated with each one of the plurality of expressions having a condition with a live slot, each second memory storing references to the values of the data elements input to the variable slots of the conditions of each associated one of the plurality of expressions having a condition with a live slot where a predetermined result is yielded by a pre-determined subset of the conditions;

the processor operating to evaluate each one of the plurality of expressions using the new data value and to store the result of each one of the plurality of expressions and the values used in evaluating the expressions in the second memory.

30. The expert system of claim 29 wherein the system is arranged to pass pointers to memory locations that contain values of data elements, said processor being arranged to access said data values using the pointers.

31. The expert system of claim 29 further comprising;

(a) a subsequent action device to perform a pre-selected set of subsequent actions when all the conditions of one or more expressions are satisfied;

(b) a conflict resolution scheme, said conflict resolution scheme comprising means to determine which of the subsequent actions of each expression to take when all of the conditions of two or more of the expressions are satisfied; and

(c) at least one of the plurality of nodes arranged to execute the corresponding procedure that has been placed upon the live slot, to collect a new data value for that data value variable slot updated by the execution of the corresponding procedure, and to evaluate the condition represented by that node, the conflict resolution scheme further comprising means for re-evaluating the expression using the new data value, means for storing the data used to evaluate the expression and the result of evaluating the expression using the new data value in the second memory, and, before taking the subsequent actions, and means for re-evaluating the expression using the stored values and a further data value obtained by re-executing the corresponding procedure.

32. The expert system according to claim 29 wherein at least one of the plurality of nodes is a node having one data input and one live slot and is arranged to execute the corresponding procedure.

33. The expert system according to claim 29 wherein at least one of the plurality nodes is a node having two data inputs and one live slot and is arranged to execute the corresponding procedure.