Method and apparatus for efficiently implementing read-type procedural attachments in RETE-like pattern matching environment
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
33 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 22)
-
-
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. - View Dependent Claims (17, 18, 19, 20, 21, 23)
-
-
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. - View Dependent Claims (26, 27, 28)
-
-
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. - View Dependent Claims (30, 31, 32, 33)
-
Specification