The RETE Algorithm
- Production rules can be reorganisaed for efficient pattern matching.
- The RETE algorithm creates a decision tree that combines the patterns in all the rules of the knowledge based.
- Designed by Forgy (CMU) it was first used in OPS5 and is now widely used in other production rules systems
Example
rete-rule-1:
if match(red,green)
and data(X, X)
and data(Y, green)
then ...
rete-rule-2:
if match(X, red)
and data(Colour, X)
and Colour \= green
and data(X, X)
then ...
Pattern Network
Join Network
Once it has been determined which patterns have been matched by facts, comparisons of variable bindings across patterns must be checked to ensure that variables used in more than one pattern have consistent values.
Join network for rete-rule-2
Compiling Rules
- OPS83 compiles rules into machine code.
- XCON (R1) is implemented in this way.
- Compiling turns pattern matching into machine code.
- Combines rules into a decision tree.
Example
a & b | c -> d
a & e -> f
test a
iffalse L1
test b
iftrue L2
test e
iftrue L3
L1: test c
iffalse ......
L2: do d
......
L3: do f
......