RETE

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.

Example

When a fact is modified, say, the age of Ram is changed from 20 to 21, this is expressed as a deletion of the old fact (the age of Ram is 20) and the addition of a new fact (the age of Ram is 21).

The Rete Algorithm s intended to improve the speed of forward-chained rule systems by limiting the effort required to recomputed 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.

The Rete consists of:-

· Root node

· Of one input-pattern nodes

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