Shocking – Forrester Produces Shody Work

Dietrich Kappe, Tuesday, March 28, 2006 @ 11:30 am

woolfel gets bent out of shape about an abstract by Forrester that states that InRule uses RETE for it's .NET based BRE when, in fact, they talk about a decision table based approach:

There's a slight chance that InRule is using Microsoft's BRE engine, but I would
think MS would require someone licensing the engine to state that fact clearly.
Since the InRule website doesn't, I suspect InRule doesn't use MS BRE and isn't
RETE.

From my conversations with the InRule guys, it seems that InRule is a hybrid that started out as decision table based but has started to incorporate RETE. That may seem to be a franken-engine, but isn't actually so far fetched when you think about the algorithms. I'm pretty certain that Microsoft's BRE has nothing to do with it, since I believe InRule predates the MS BRE.

Anyhow, I can't get quite as worked up about RETE vs anything else as woolfel can. Most real world applications of rule engines end up being so small in terms of numbers of rules and facts that the advantage of the RETE algorithm doesn't really show up. This is sort of like quicksort vs insertion sort. Yes, quicksort is O(n log n), and insertion sort is O(n^2), but insertion sort is just faster on average for small n.

BTW, does anyone know the the worst case time and space complexity for RETE? I've been able to locate a paper on the average case complexity for RETE, but nothing for the worst case.

Related posts:

1. Vendor Highlights
2. Explaining RETE
3. The Misunderstood Decision Table
4. Exaggerated Claims and the Importance of Hands-on Evaluation
5. The New Blaze is Finally True to its Name

Comments (3)

business rules engines

Comments: 3 so far

• Leave a comment
• Comment feed for this post

1. 

   Thanks for posting a comment on my rant about Forrester. For worse case complexity, Manners benchmark with several hundred guests should give you a pretty good idea. There’s a lot of debate about the value of manners benchmark, but it is still one of the best tests for measuring worse case performance.

   The RETE-UL paper by Doorenbos provides quite a bit of data for machine learning cases. There’s also dozens of paper on ACM-Queue Portal on RETE, TREAT, and LEAPS.

   In practice, a rule powered application should avoid cross-product pattern and use it when the case clearly calls for it.

   In terms of “adding RETE” to a decision table/decision tree engine, it’s not really feasible. One could add memory to a decision table engine, but that is far from being RETE. I have plenty of entries in my blog that explain at the lowest level what RETE means and different approaches for implementing the algorithm.

   The RETE-UL paper also provides detailed description and explanation of why RETE works so well and where it totally fails. The RETE-UL paper is very good and much better than my random rants.

   peter lin

   Comment by Peter Lin, Wednesday, March 29, 2006 @ 5:19 pm

2. 

   I’ve been thinking about your statement “From my conversations with the InRule guys, it seems that InRule is a hybrid that started out as decision table based but has started to incorporate RETE” the last few days and thought I’d share some random rants.

   Before I jump into the details, I’d like make a disclaimer. I have no clue about the design or implement of InRule engine, pretty much this comment is 100% guess work.

   Looking at the history of constraint engines, and rule engines, there’s a couple of different ways to implement a decision table driven rule engine. The easiest technique is to compile the table into 1 rule per row and evaluate the rules sequentially. Doing that generally is rather slow and far from optimal. Many decision table driven engines I am aware of prioritize the rules by inspecting the conditions. Depending on the rules, a decision table engine might place the most restrictive rules at the front. Another approach is to sequence the rules based on “specificity” of the rules. For relatively static use cases, one can also use static analysis to flatten the evaluation and aggressively hash the conditions.

   The question I ask myself is this. “if I have a decision table driven engine, how can I migrate over to RETE?”

   The first step is to use RETE to compile the rules and identify common conditions and share them. In other words, if I have 2 rules
   Rule1
   if account == “123″
   then give discount

   Rule2
   if account == “123″
   then restrict discount to 10%

   The first condition of both rules are common, so it doesn’t make sense to re-evaluate it for multiple rules. Now, one can add a memory, such that the engine does something like
   if object hasn’t been evaluated
   then evaluate
   else go to next condition

   So in that sense, the engine is borrowing ideas from RETE, but using this approach, the engine will not scale like RETE or come close. As the dataset increases or ruleset grows to thousands or even tens of thousands, evaluation time will grow rapidly. I’ve seen systems built this way and they run into scalability issues very quickly.

   Now say I’m not satisfied with just adding memory to common conditions and decide that rather than iterating over the rules, I want to evaluate based on the objects. This is how RETE works. When an object enters the rule engine, it enters the objectTypeNode for that class and propogates through the network. At this point, the engine looks nothing like a sequential approach. It’s actually quite simple to compile a decision table into RETE rules. Drools3 provides support for that. Not many people are aware of this, but back in the 90’s some people embedded CLIPS inside MS Excel. I forget who did that, but it has been done several times over the last 15 years.

   Corticon likewise uses a excel approach and compiles the rules to backward chaining network. To call a rule engine “hybrid” should be used with caution. For example JRules powers their sequential evaluation approach using a hybrid approach. In the case of JRules, their engine provides the ability to run in forward chaining or sequential. I don’t know the exact design of how they achieve this, but I have a decent guess on how it can be done easily. I blogged about it a few weeks back.

   Comment by Peter Lin, Friday, March 31, 2006 @ 9:30 am

3. 

   Actually, there’s an interesting wrinkle on hybrid rule engines.

   In the Internet Business Logic system, the engine switches automatically between back- and forward-chaining. It typically does this several times to get a particular result.

   The outcome is that rules take on a more declarative meaning than if you wanted to read them as one-way only.

   The system that does this is online at reengineeringllc.com, and shared use is free.

   Thanks in advance for coments.

   Comment by Adrian Walker, Saturday, April 22, 2006 @ 2:19 pm

Leave a comment