The Rete Algorithm [References] is intended to improve the speed of forward-chained rule systems by limiting the effort required to recompute the conflict set after a rule is fired. Its drawback is that it has high memory space requirements. It takes advantage of two empirical observations:

*Temporal Redundancy*: The firing of a rule usually changes only a few facts, and only a few rules are affected by each of those changes.*Structural Similarity*: The same pattern often appears in the left-hand side of more than one rule.

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

of patterns:

(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 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.

(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

*ingargiola@cis.temple.edu*