Rete Algorithm — Conflict Sets and Resolution
How expert systems match thousands of rules efficiently — alpha nets, beta nets, timestamps, and why specificity beats recency (or vice versa)
The Simplest Explanation
A rule-based expert system has rules like IF Fuel=diesel AND BoM=crankshaft THEN R1 and a working memory (WM) of facts with timestamps (101, 102, …).
Naively, each cycle you'd test every rule against every fact → . Rete (Forgy 1982) compiles rules into a network so WM changes only trickle through affected paths.
- Alpha net: filters single WMEs by condition (e.g.,
CLASS=Fuel,type=diesel) - Beta net: joins WMEs that share a variable binding (e.g., both
^item= same machine) - Conflict set: all fully-matched rule-data tuples ready to fire
Then a conflict resolution strategy picks one tuple to fire.
Alpha = one-fact filter. Beta = multi-fact join (shared variable). Conflict set = Beta outputs that match a rule. Strategy picks the winner.
Network Structure (from Papers)
Example from 26T1 FN (mushroom Rete):
WME → A1: CLASS=Cap → A4: specimen=<n> → A7: surface=SMOOTH → A14: colour=RED → B2 → R3
→ A8: colour=WHITE ──┘
A2: CLASS=Stalk → A5 → A9: root=BULBOUS → B1 → R1
→ A10: br-surface=SCALY ─→ B1
A3: CLASS=Mushroom → A6 → A11: habitat=LEAVES etc → B3 → R4
Timestamps matter: WME 101 is older than 107. Assume WMEs reside at appropriate Alpha nodes; Beta nodes point to WMEs in Alphas.
Step-by-Step: Building the Conflict Set
Given WM:
101. (Fuel ^item machine5 ^type diesel)
102. (Fuel ^item machine2 ^type petrol)
103. (Fuel ^item machine3)
104. (Power ^item machine4 ^lines 1)
105. (BoM ^item machine4 ^part armature)
...
- Route each WME down Alpha: 101 → Fuel+diesel branch, 105 → BoM+armature, etc.
- At each Beta, check shared
^itemequality: does Fuel and BoM refer to same machine?- 101 (^item machine5) + 106 (^item machine3) → different → no join
- 104 (^item machine4) + 105 (^item machine4) → same → joins
- Those that survive all Betas for a rule = one entry in conflict set, e.g.,
R6,104,105.
Conflict Resolution Strategies
Papers test two strategies every year:
| Strategy | Picks... | Intuition | Example Winner |
|---|---|---|---|
| Specificity | Tuple with most conditions (most specific rule) | Prefer detailed knowledge over general | R1,101,107 (3 refs) beats R2,107 (1 ref) |
| Recency | Tuple containing the newest WME (highest timestamp) | Prefer recent data (like stack) | R1,101,107 has max 107 vs R6,104,105 max 105 → R1 wins |
Tie-breakers: within same specificity/recency, papers use label ordering (R1 before R7) or timestamp ordering.
Worked Example: 22T3 FN Q10
WM max timestamp = 107. Conflict set includes: R1,101,107 (max 107), R2,107 (107), R6,104,105 (105), R7,105 (105), R7,106 (106).
- Specificity: Count WMEs per tuple: R1 has 2, R6 has 2, R7 has 1 → R1 and R6 tie → label order picks R1,101,107.
- Recency: Highest timestamp in each tuple: R1=107, R2=107, R7,106=106... R1 and R2 tie on 107 → specificity tie-break again → R1,101,107 (both strategies converge here; not always).
Contrast with 23T1 FN Q6: WM up to 105, conflict set F1-Car,104,107,109 (recency max 109) wins Recency, but Specificity picks Truck,101,102,105 (most conditions) — they diverge!