Rulebase Conflict Resolution

In the book (rather old now) "Pattern Directed Inference Systems" D.A. Waterman and F. Hayes-Roth made the comment in the "Overview" part that, "Linear growth in computation time with the size of the data base (sic) or the the number of production rules is avoided by only considering data in the active part of memory when rules are applied and by associating with each node a list of rules that reference the node. When the node is activated the associated rules are selected for consideration. Thus the number of rules being tested against memory at an time depends on the number of currently active nodes rather than the size of the production system."

John McDermott and Charles Forgy continue this line of thought on page 177 with a section called "Production System Conflict Resolution Strategies" where they explain how a good CR strategy supports the rulebase interpreter by processing the rules in a manner such that only certain ones are selected. This is an excellent example of using meta-rules. In this short, article-length section they discuss CR, sensitivity, stability, special case rules, recency rules, evaluation, etc.

Although they don't discus this in detail in the limited space made available to them, most vendors seem to feel that there are two major approaches in selecting the next rule - width or breadth. Not true. The major approach should be either LEX - Lexigraphical (as in ILOG JRules) or Means Ends Analysis, MEA - as in OPSJ and others. MEA is basically an extended and enhanced version of LEX. The first example of using the Rete Algorithm (OPS) the inventors used LEX but in later versions this was improved with MEA. There is a good discussion of MEA and LEX in the book by Cooper and Wogrin in their book "Rule-Based (sic) Programming With OPS5." This is something more for vendors than for programmers unless you are using a rulebase that allows you to select your own method of CR.

Without a good CR approach, you will find that the engine spends way too much time thrashing around. Once the Agenda Table is built, depending on the CR, then selecting the next rule is a piece of cake for the engine. In addition to CR there are a lot of other topics that we, the rulebase community should be considering and I'll put all of that in another post later.

SDG
Yaakov