CIS587: The RETE Algorithm

Last Modified:

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:

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

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.

An Example

Here is a very simple example of a Rete. Suppose we are given the rules:

	(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

Efficiency considerations when Writing Rules

 Here we examine how the order of the patters in the left hand side of a rule affects the storage requirements of the Rete algorithm. Other implementations of rule based systems are similarly affected by the order of the variables.

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)	    | f8
We 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.

References

 
    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