To be concrete about what we mean by "facts", "patterns", and "rules", here are some examples of facts:
(has-goal obj-17 simplify) ;; The goal of obj-17 is simplify (expression obj-17 0 * 13) ;; The expression obj-17 is "0 * 13" (expression obj-21 4 + 6) ;; The expression obj-21 is "4 + 6" (is-a horse comet) ;; Comet is a horse (is-a-parent-of comet prancer) ;; Comet is a parent of Prancer
(has-goal ?X simplify) (expression ?y 0 ?op ?a2) (is-a-parent-of ?u ?v)
and of rules:
(R1 (has-goal ?x simplify) (expression ?x 0 + ?y) ==>....) (R2 (has-goal ?x simplify) (expression ?x 0 * ?y) ==>....) (R3 (is-a horse ?x) (is-a-parent-of ?x ?y) (is fast ?Y) ==>....)
Thus facts are variable-free tuples, patterns are tuples with some variables, and rules have as left-hand sides lists of patterns.
The Rete Algorithm
The Rete algorithm uses a rooted acyclic directed graph, the Rete, where
the nodes, with the exception of the root,
represent patterns, and paths from the root to the leaves represent
left-hand sides of rules. At each node is stored
information about the facts satisfied
by the patterns of the nodes in the paths from the root up to
and including this node.
This information is a relation representing the possible values of the
variables occurring in the patterns in the path.
The Rete algorithm keeps up to date the information associated with the nodes in the graph. When a fact is added or removed from working memory, a token representing that fact and operation is entered at the root of the graph and propagated to its leaves modifying as appropriate the information associated with the nodes. When a fact is modified, say, the age of John is changed from 20 to 21, this is expressed as a deletion of the old fact (the age of John is 20) and the addition of a new fact (the age of John is 21). We will consider only additions of facts.
The Rete consists of the root node, of one-input pattern nodes, and of two input join nodes.
The root node has as successors one-input "kind" nodes, one for each possible kind of fact (the kind of a fact is its first component). When a token arrives to the root a copy of that token is sent to each "kind" node where a SELECT operation is carried out that selects only the tokens of its kind.
Then for each rule and each of its patterns we create a one input alpha node. Each "kind" node is connected to all the alpha nodes of its kind and delivers to them copies of the tokens it receives. To each alpha node is associated a relation, the Alpha Memory, whose columns are named by the variables appearing in the node's pattern. For example, if the pattern for the node is (is-a-parent-of ?x ?y) then the relation has columns named X and Y. When a token arrives to the alpha node a PROJECT operation extracts from the token tuple's the components that match the variables of the pattern. The resulting tuple is added to the alpha memory of the node.
Then, for each rule Ri, if Ai,1 Ai,2 ... Ai,n are in order the alpha nodes of the rule, we construct two-input nodes, called Beta Nodes, Bi,2 Bi,3 ... Bi,n where
Bi,2 has its left input from Ai,1 and its right input from Ai,2 Bi,j, for j greater than 2, has its left input from Bi,j-1 and its right input from Ai,j
At each beta node Bi,j we store a relation, the Beta Memory, which is the JOIN of the relations associated to its left and right input, joined on the columns named by variables that occur in both relations. For example if the left input relation and right input relations are:
X Y X Z ========= ========= ann 4 ann tom sam 22 ann sue tom jane then the resulting beta memory relation is X Y Z ================= ann 4 tom ann 4 sue
Finally the last beta node of each rule is connected to a new alpha node where a PROJECT operation takes place to select all and only the variables that occur on the right-hand side of the rule.
Here is a very simple example of a Rete. Suppose we are given the
(R1 (has-goal ?x simplify) (expression ?x 0 + ?y) ==>....) (R2 (has-goal ?x simplify) (expression ?x 0 * ?y) ==>....) and the following facts: (has-goal e1 simplicity) (expression e1 0 + 3) (has-goal e2 simplicity) (expression e2 0 + 5) (has-goal e3 simplicity) (expression e3 0 * 2) Then the Rete is +----------+ | ENTRANCE | +----------+ x / | \ = / | \ e1 / | \ y e2 +----------+ +------------+ +------------+ = e3 | HAS-GOAL | |EXPRESSION *| |EXPRESSION +| 3 +----------+ +------------+ +------------+ 5 \ / | \ / y | \ / = | \ / 2 | \ / | x y +--------+ +--------+ x y === | | | | === e3 2 +--------+ +--------+ e1 3 | | e2 5 | | R2 R1
Assume that our working memory contains the facts:
FACT | NAME OF THE FACT ================================== (find-match a c e g)| f1 (item a) | f2 (item b) | f3 (item c) | f4 (item d) | f5 (item e) | f6 (item f) | f7 (item g) | f8We compare the behavior of two equivalent rules:
RULE 1: RULE 2: (find-match ?x ?y ?z ?w) (item ?x) (item ?x) (item ?y) (item ?y) (item ?z) (item ?z) (item ?w) (item ?w) (find-match ?x ?y ?z ?w) =========> ... ==========> ...In both Rule 1 and 2 we have five alpha nodes and 4 beta nodes.
Here is the storage for the nodes for Rule 1:
NODE | PATTERN |MEMORY ===================================================== a1 | (find-match ?x ?y ?z ?w)| f1 a2 | (item ?x) | f2 f3 f4 f5 f6 f7 f8 a3 | (item ?y) | f2 f3 f4 f5 f6 f7 f8 a4 | (item ?z) | f2 f3 f4 f5 f6 f7 f8 a5 | (item ?w) | f2 f3 f4 f5 f6 f7 f8 b1 | a1 & a2 | f1 b2 | b1 & a3 | f1 b3 | b2 & a4 | f1 b4 | b3 & a5 | f1 In total we have 1+7+7+7+7+1+1+1+1 = 33 elements.Here is the storage for the nodes for Rule 2:
NODE | PATTERN |MEMORY ===================================================== a1 | (item ?x) | f2 f3 f4 f5 f6 f7 f8 a2 | (item ?y) | f2 f3 f4 f5 f6 f7 f8 a3 | (item ?z) | f2 f3 f4 f5 f6 f7 f8 a4 | (item ?w) | f2 f3 f4 f5 f6 f7 f8 a5 | (find-match ?x ?y ?Z ?W)| f1 b1 | a1 & a2 | [f2 f2] [f2 f3] .. [f8 f8] b2 | b1 & a3 | [f2 f2 f2] ... [f8 f8 f8] b3 | b2 & a4 | [f2 f2 f2 f2] ... [f8 f8 f8 f8] b4 | b3 & a5 | f1 In total we have 7+7+7+7+1+7*7+7*7*7+7*7*7*7+1 = 2823 elements.One can examine similarly the effect that different styles of rule writing have on efficiency. For example, we can examine if it is better to write that use few rules each with many patterns, or more rules each with fewer patterns.
Forgy, C.L.: Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem Artificial Intelligence, 19(1982) 17-37 Winston,P.H.: Artificial Intelligence, Third Edition Addison-Wesley, 1992 Pages 119-161 Giarratano,J., Riley,G.: Expert Systems: Principles and Programming PWS Publishing Co., 1994 Pages 513-545