分享
CIS587: The RETE AlgorithmLast Modified:
The Rete Algorithm [References] is intended to improve the speed of forwardchained 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: (hasgoal obj17 simplify) ;; The goal of obj17 is simplify (expression obj17 0 * 13) ;; The expression obj17 is "0 * 13" (expression obj21 4 + 6) ;; The expression obj21 is "4 + 6" (isa horse comet) ;; Comet is a horse (isaparentof comet prancer) ;; Comet is a parent of Prancer of patterns: (hasgoal ?X simplify) (expression ?y 0 ?op ?a2) (isaparentof ?u ?v) and of rules: (R1 (hasgoal ?x simplify) (expression ?x 0 + ?y) ==>....) (R2 (hasgoal ?x simplify) (expression ?x 0 * ?y) ==>....) (R3 (isa horse ?x) (isaparentof ?x ?y) (is fast ?Y) ==>....) Thus facts are variablefree tuples, patterns are tuples with some variables, and rules have as lefthand sides lists of patterns. The Rete AlgorithmThe 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 lefthand 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 oneinput pattern nodes, and of two input join nodes. The root node has as successors oneinput "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 (isaparentof ?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 twoinput 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,j1 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 righthand side of the rule. An ExampleHere is a very simple example of a Rete. Suppose we are given the rules:(R1 (hasgoal ?x simplify) (expression ?x 0 + ?y) ==>....) (R2 (hasgoal ?x simplify) (expression ?x 0 * ?y) ==>....) and the following facts: (hasgoal e1 simplicity) (expression e1 0 + 3) (hasgoal e2 simplicity) (expression e2 0 + 5) (hasgoal e3 simplicity) (expression e3 0 * 2) Then the Rete is ++  ENTRANCE  ++ x /  \ = /  e1 /  \ y e2 ++ ++ ++ = e3  HASGOAL  EXPRESSION * EXPRESSION + 3 ++ ++ ++ 5 \ /  \ / y  \ / =  \ / 2  \ /  x y ++ ++ x y ===     === e3 2 ++ ++ e1 3   e2 5   R2 R1 Efficiency considerations when Writing RulesHere 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 ================================== (findmatch 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: (findmatch ?x ?y ?z ?w) (item ?x) (item ?x) (item ?y) (item ?y) (item ?z) (item ?z) (item ?w) (item ?w) (findmatch ?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  (findmatch ?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  (findmatch ?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. ReferencesForgy, C.L.: Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem Artificial Intelligence, 19(1982) 1737 Winston,P.H.: Artificial Intelligence, Third Edition AddisonWesley, 1992 Pages 119161 Giarratano,J., Riley,G.: Expert Systems: Principles and Programming PWS Publishing Co., 1994 Pages 513545 ingargiola@cis.temple.edu 
