AI Search · Exam notes

Rete Nets: Conflict Set, Specificity, Recency

One Rete comprehension per paper, three sub-questions on one network: which rule-data tuples match? which fires under specificity? which fires under recency? One chain answers all: locate every WME in the alpha net, keep only the tuples whose shared variables agree, then count tests for specificity and compare timestamps for recency.

Points 1 and 2 are the rules. Point 3 applies them to the vehicle network. Point 4 has three small drills to solve with a pen.

1. Vocabulary in one table

TermMeaning
WMEOne fact: (class, attribute values), plus a timestamp (its sequence number, here 101 to 109). Higher number = more recent.
RuleLHS patterns (conditions on WMEs) arrow RHS action (the classification). A rule fires only if every LHS pattern matches.
Alpha nodeTests one WME at a time: class name, then one attribute test. A WME sits in every alpha node whose test it passes.
Beta nodeJoin: checks variable consistency. Here each beta demands one shared variable \(\langle v \rangle\) (the vin) be equal across its WMEs.
Conflict setAll rule-data tuples with every pattern matched. First-cycle question: build this set, then resolve it.
SpecificityMost tests fires first. Count tests from the top of the net down to the rule node. Most alpha tests wins.
RecencyHighest timestamp fires first. For each tuple take the max WME timestamp, then take the max over tuples.

Conventions used on this page: ties break by label order (A1, A2, ..., B1, ...). A negated test is written ¬X (the question text writes it as ~X). This network has no negated tests; drill D2 shows how one works.

2. The three checks

  1. Match (conflict set). For each candidate tuple check four things: class name, each attribute condition (\(\ge 700\), \(\le 500\), \(= 1\), slick vs regular), the shared variable \(\langle v \rangle\) binds the same vin in every WME, and every negative pattern is absent. One failure kills the tuple. A WME with hp 400 passes both \(\ge 300\) and \(\le 500\), so it can fill two alpha slots at once.
  2. Specificity. Count alpha tests on each firing rule's path: 3 per pattern chain (class, vin, attribute test). Highest count fires first.
  3. Recency. Max timestamp inside each tuple wins. Compare 109 vs 108 vs 105, not the number of WMEs.

3. Worked example: vehicle network, Q68 to Q70

3a. The network as tables (solve from this, then check the animation)

Alpha chainTestsWMEs that stop here
A1, A5, A9Wheel; vin = \(\langle v \rangle\); tyre = slick109 (C3, slick)
A1, A5, A10Wheel; vin = \(\langle v \rangle\); tyre = regular108 (B2, regular)
A2, A6, A11Passenger; vin = \(\langle v \rangle\); limit = 1104 (C3)
A2, A6, A12Passenger; vin = \(\langle v \rangle\); limit = 2102 (A1), 103 (B2)
A3, A7, A13Power; vin = \(\langle v \rangle\); hp \(\ge\) 700106 (B2, 800), 107 (C3, 900)
A3, A7, A14Power; vin = \(\langle v \rangle\); hp \(\ge\) 300105 (A1, 400), 106, 107
A3, A7, A15Power; vin = \(\langle v \rangle\); hp \(\le\) 500105 (A1, 400) only
A4, A8, A16Cargo; vin = \(\langle v \rangle\); bed = \(\langle x \rangle\)101 (A1, flat)
Rule (via beta)Needs (same vin \(\langle v \rangle\))Patterns
F1-Car via B1A9 + A11 + A133
Luxury-Car via B2A10 + A12 + A133
Truck via B3A12 + A14 + A15 + A164
WMEFactAlpha nodes reached
101(Cargo vin A1 bed flat)A4, A8, A16
102(Passenger vin A1 limit 2)A2, A6, A12
103(Passenger vin B2 limit 2)A2, A6, A12
104(Passenger vin C3 limit 1)A2, A6, A11
105(Power vin A1 hp 400)A3, A7, A14, A15
106(Power vin B2 hp 800)A3, A7, A13, A14
107(Power vin C3 hp 900)A3, A7, A13, A14
108(Wheel vin B2 tyre regular)A1, A5, A10
109(Wheel vin C3 tyre slick)A1, A5, A9

Read one alpha chain top to bottom as one pattern: class, then vin, then the attribute test. A WME slides down every chain whose tests it passes and stops where a test fails. Cover the animation. Locate all nine WMEs, test the four candidate tuples at the betas, then pick by tests and by timestamps.

3b. Animation: the whole net from step 0, progress marked on it

Step 0 | | grey = empty, black = WME located or join checked (tags list resident WMEs, betas show the surviving vin), outline = current step, thick border = fires first under the active strategy

Why this step

Tracker

3c. The three questions

A Rete net classifies machines. Alpha nodes test class, vin, then one attribute. Beta nodes B1, B2, B3 each require the vin \(\langle v \rangle\) to be equal across their inputs and feed rules F1-Car, Luxury-Car, Truck. WMEs in timestamp order:

101 (Cargo vin A1 bed flat). 102 (Passenger vin A1 limit 2). 103 (Passenger vin B2 limit 2). 104 (Passenger vin C3 limit 1). 105 (Power vin A1 hp 400). 106 (Power vin B2 hp 800). 107 (Power vin C3 hp 900). 108 (Wheel vin B2 tyre regular). 109 (Wheel vin C3 tyre slick).

  1. Which rule-data tuples are in the conflict set? Candidates: (F1-Car,104,107,109), (Luxury-Car,103,106,108), (Truck,101,102,105), (Truck,101,103,106).
  2. Under specificity, which tuple fires in the first round?
  3. Under recency, which tuple fires in the first round?

3d. Answers first, then the working

Conflict set: (F1-Car,104,107,109), (Luxury-Car,103,106,108), (Truck,101,102,105). Specificity fires (Truck,101,102,105). Recency fires (F1-Car,104,107,109).

CandidateBetaVerdict
(F1-Car,104,107,109)B1, vin C3A9 = {109}, A11 = {104}, A13 has 107. All C3. IN.
(Luxury-Car,103,106,108)B2, vin B2A10 = {108}, A12 has 103, A13 has 106. All B2. IN.
(Truck,101,102,105)B3, vin A1A15 holds only 105, forcing A1. 105 fills A14 and A15 at once. IN.
(Truck,101,103,106)B3, split vin103 is B2 vs 101 is A1, and 106 (800) fails A15. OUT.
  1. B1 (F1-Car) needs A9, A11, A13 with one vin. A9 has only 109 (C3). A11 has only 104 (C3). A13 has 106 (B2) and 107 (C3). Only vin C3 works: (F1-Car,104,107,109) is in.
  2. B2 (Luxury-Car) needs A10, A12, A13 with one vin. A10 has only 108 (B2). A12 has 102 (A1), 103 (B2). A13 has 106 (B2), 107 (C3). Only vin B2 works: (Luxury-Car,103,106,108) is in.
  3. B3 (Truck) needs A12, A14, A15, A16 with one vin. A15 holds only 105, so vin must be A1. Then A12 must be 102, A14 can be 105 (400 passes both \(\ge\) 300 and \(\le\) 500), A16 is 101. So (Truck,101,102,105) is in. The rival (Truck,101,103,106) fails twice: 103 is vin B2 against 101 vin A1, and 106 (hp 800) fails A15 (\(\le\) 500). Out.
  4. Specificity: count alpha tests. F1-Car: 3 + 3 + 3 = 9. Luxury-Car: 3 + 3 + 3 = 9. Truck: 3 + 3 + 3 + 3 = 12 (four patterns). Highest count fires: (Truck,101,102,105). Counting each beta join as one more test (10, 10, 13) keeps the same winner.
  5. Recency: max timestamp per tuple. F1-Car: max(104,107,109) = 109. Luxury-Car: max(103,106,108) = 108. Truck: max(101,102,105) = 105. Highest fires: (F1-Car,104,107,109).

4. Practice: three small drills

Solve each with a pen before opening the answer. Each drill is self contained.

Drill D1: variable consistency trap

Rule R: (Wheel vin \(\langle v \rangle\)) + (Power vin \(\langle v \rangle\), hp \(\ge\) 700). WMEs: 201 (Wheel vin X), 202 (Power vin X hp 800), 203 (Power vin Y hp 900). Q: which tuples are in the conflict set: (R,201,202), (R,201,203)?

Step 0

Why this step

Tracker

Answer D1

(R,201,202) only. (R,201,203) matches class and attribute tests but binds \(\langle v \rangle\) to X and Y at once, so the beta join rejects it.

Drill D2: negative pattern

Rule R: (Power hp \(\ge\) 700) + ¬(Wheel tyre slick), i.e. no slick-wheel WME may exist. Case A WMEs: 201 (Power hp 800), 202 (Wheel tyre regular). Case B adds 203 (Wheel tyre slick). Q: is R in the conflict set in each case?

Step 0

Why this step

Tracker

Answer D2

Case A: in, via (R,201). Case B: out. The positive pattern still matches, but the negative pattern ¬(Wheel tyre slick) is violated by 203, so the whole rule is blocked.

Drill D3: specificity and recency disagree

Tuples in the conflict set: (Ra,209) with 2 tests, max timestamp 209; (Rb,201,202) with 5 tests, max timestamp 202. Q: which fires under specificity? which under recency?

Step 0

Why this step

Tracker

Answer D3

Specificity fires (Rb,201,202) (5 tests beat 2). Recency fires (Ra,209) (209 beats 202). The two strategies can pick different winners; read which one the sub-question asks for.

5. Exam checklist (write this on the rough sheet)

  1. List every WME under each alpha test it passes. One WME can sit in two sibling alphas (105 sits in A14 and A15).
  2. For each candidate tuple, check class, each attribute, then the shared vin at the beta. One mismatch kills it.
  3. Check negative patterns last: the forbidden WME must be absent everywhere, not just in the tuple.
  4. All patterns of a rule must match. Count patterns per rule before resolving.
  5. Specificity: count alpha tests from the top of the net to each firing rule. Highest count fires.
  6. Recency: max timestamp inside each tuple, then max across tuples. Ties break by label order.