The Misunderstood Decision Table

Dietrich Kappe, Tuesday, June 13, 2006 @ 9:00 am

Pity the poor Decision Table. It and its close relative, the Decision Tree, are much maligned in the world of Business Rules Engines. They are slow, awkward, unattractive, unsuitable for all but the most primitive and useless of problems. Clearly RETE is superior, for it allows you to throw your facts and rules into a cauldron and magically and instantly come up with results. Only losers use decision tables.

Of course this view is far from the truth and relies on both a misunderstanding of what problem the RETE algorithm tries to solve and a straw man decision table implementation. First to the question of what problem the RETE algorithm tries to solve. From Forgy's original paper:

A pattern matcher can avoid iterating over the elements in working memory by storing information between cycles. The step that can require iteration is determining whether a given pattern matches any of the working memory elements. The simplest interpreters determine this by comparing the pattern to the elements one by one. The iteration can be avoided by storing, with each pattern, a list of the elements that it matches. The lists are updated when working memory changes. When an element enters working memory, the interpreter finds all the patterns that match it and adds it to their lists. When an element leaves working memory, the interpreter again finds all the patterns that match it and deletes it from their lists.

Since pattern matchers using the Rete algorithm save this kind of information, they never have to examine working memory.

To summarize, if you want to match (or unmatch) new rules when the facts change, you don't want to reevaluate the whole shootin' match. The RETE algorithm does this efficiently. But what if you don't need to match rules when the facts change? In that case, all this saving of information may be just a bunch of overhead.

Next to the question of the straw man: when most writers discuss the decision table, they describe a n-dimensional table with discrete and finite dimensions and cells that contain "actions." They also tend to imply a certain execution algorithm, as this article does:

The decision table is a very familiar decisioning structure. Price
lists, bus , and train schedules are often represented as a table and
function very similarly to a decision table. For example, given your
current location (input parameter 1) and where you want to go ( input
parameter 2), the table will tell you when the train will arrive (your
outcome). At a most basic level, two different parameters are
represented along the axis of the table in columns and rows. The
intersections of the two axes constitute the decision point for the
given combination of parameter values.

While the author doesn't explicitly say that this is how the implementation and execution of a decision table should proceed -- look up an entry in a multidimensional table -- it is implied. This gives the decision table short shrift. Just like the production system is an invention of the 1970's for which efficient algorithms were developed in the 1980's and 1990's, just so the decision table and tree are inventions of the 1950's for which efficient algorithms were developed in the 1960's and 1970's. These efficient algorithms don't look anything like the naive table look up.

Most of the efficient algorithms involve turning the "extended" decision table, which has multiple discrete values in a dimension, into a simple decision table, which has just true-false values in its dimensions. Then this simple decision table is typically converted into a different problem space which has more efficient solution algorithms. Depending on whether the goal is to optimize average or worst case execution time or memory consumption, the solution might involve converting the table into a decision tree.

Last, while decision tables and trees are typically used on an analytical level in current business rules practice -- business analysts decomposing a problem into a table or tree of actions -- IF-THEN rules can actually be converted into simple decision tables directly. When the efficient decision table algorithms are combined with other techniques like rule chaining, the result can be rather zippy systems for situations where inferencing is not necessary or the numbers of rules and facts are small.

I hope I've convinced you of the decision table's continued viability. The next time someone scoffs at the decision table, please say a kind word in its defense.

business rules

Comments: 3 so far

• Leave a comment
• Comment feed for this post
• TrackBack URL

1. 

   Dietrich
   Could not agree more - the representation of business rules can and should be somewhat independent of how they execute. For some rulesets decision tables or decision trees make great metaphors for understanding the rules.
   BTW there are posts on this topic on the RealRules blog at http://www.realrules.info/?q=node/25 and on the Artemis Alliance blog at http://aai-rules.blogspot.com/2006/03/decision-tables-and-trees.html.

   Comment by James Taylor, Tuesday, June 13, 2006 @ 12:22 pm

2. 

   There’s actually a rather simple way of using a RETE engine with a decision table (aka spreadsheet) style interface. The primary cost in cases where facts are not modified is storing the alpha memories and beta memories in RETE. Depending on the use case, turning off either alpha or beta memory would greatly improve memory usage and performance. for example, in Sumatra users can turn off alpha memory.

   In some cases, one can use LEAPS algorithm if the rules fit nicely into a decision table structure. JRules has sequential evaluation, which is basically LEAPS. The real benefit of decision tables in my mind is lower learning curve for users. Whether the use case fits decision table is a different story.

   Drool3 has some support for spreadsheet and it compiles the rules to RETE, so it’s straight forward.

   my bias 2 cents.

   Comment by Peter Lin, Thursday, June 15, 2006 @ 12:36 pm

3. 

   Dietrich,

   I see several authors have now joined the decision table debate since my article. The concept frequently mentioned here is my supposed coupling between the algorithm and the table representation. I guess for the particular article, the algorithm itself used by a vendor was not my focus. I was more trying to illustrate various useful ways of representing business rules and cared less about what the actual algorithm did. From a business user’s perspective the simplicity of representation and organization is really the important part. I am glad however this thread has been picked up and dicussed to, in the end, benefit our audience.

   Comment by Krzysztof Karski, Friday, June 16, 2006 @ 2:05 pm

Leave a comment