RETE Engines Must Forward and Backward Chain?!

Posted on 03/06/10 16 Comments

In a new development for me, I recently learned that one of the criteria for a “RETE-based rules-engine” to actually be classified as “RETE” is that the software must perform both forward and backward chaining. A well respected rules professional just informed me:

If [the rules-engine] is just forward chaining it’s not RETE because the scalability with respect to rule count and dataset size won’t be the same. [For example] with Drools 2.0, more than 100 rules the performance starts to drop off exponentially. The same is true of dataset size.

I think this means that I should go back and revise my past slide presentations where I categorized a “RETE” rules-engine that only performs forward chaining as a “RETE” engine, based on what I was told by the developers. Yikes!

If anyone has any references on this, or links to any blog posts or documentation on this, please post. Thanks!

Share and Enjoy:
  • Print
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks

16 Comments

  1. Zbigniew Jerzak says:
    Saturday, March 6, 2010 at 10:38am

    RETE algorithm, when originally developed by Dr Charles Forgy was performing only the forward chaining. Obviously, backward chaining has a potential to bring a significant performance boost, but that does not mean that forward chaining only engines are not RETE-based. RETE algorithm is a way to structure rules and facts in memory, with forward chaining being the basic version of reasoning using that structure and backward chaining the extended one (BTW – Dr Forgy never published his backward chaining version of RETE algorithm).

  2. Tim Bass says:
    Saturday, March 6, 2010 at 11:00am

    Hi Zbiniew,

    Thanks for commenting. Your reply matches my prior understanding and my blurbs in my older presentations; which also matches what is written in Wikipedia (whatever that is worth, LOL).

    However, there seems to be some valid concern that when a rules-engine only forward chains, it does not exhibit “true RETE” performance. Someone recently pointed out to me the following:

    Drools2 was only forward chaining for several critical reasons.

    1. There wasn’t any alpha memories in the alpha nodes.
    2. The join order was arbitrary, which goes against RETE.
    3. The conflict resolution in Drools 2 wasn’t right.
    4. The scalability dropped dramatically as rule count increased, which
    true RETE engines do not exhibit.

    … it seems there is a gap between the short descriptions, marketing blurbs and the actually technical details of the inner workings, which are not easy to comprehend.

    Can someone help me understand this better?

  3. Peter Lin says:
    Saturday, March 6, 2010 at 3:27pm

    Correction on the RETE. I doesn’t have to do forward and backward chaining. Many do like ART, Haley and JESS. Each engine uses a different approach to support backward chaining. I’ve written about this before. What distinguishes RETE from a simple forward chaining is defined by.

    1. alpha memories in the alpha node. this helps with retract and modify. without it, performance has a huge impact. For “read” only use cases that never retract or modify facts, it’s not an issue. Strict RETE should have alpha memories.

    2. the join order is based on the sequence of the conditional elements defined in the rule. If the rule engine doesn’t do that and produces arbitrary joins, it’s not RETE. Easiest way is to look at the discrimination network the rule engine creates.

    3. the conflict resolution insures the correct rule fires. To fully explain conflict resolution would be a 30 page paper, so it’s not possible to tackle in a comment.

    4. finally, the proof is in the pudding. A real RETE rule engine should see no performance drop as the rule count goes from 1-1000. If it doesn’t, it’s not RETE.

    For those that want to learn more, I would suggest downloading JESS and look at the RETE network it produces. Any rule engine that doesn’t produce a similar discrimination network isn’t RETE in my book.

    The other common mistake with implementing RETE is doing a search across all the facts every single time for each rule. One example of this is Ruleby. When I explained the difference, they fixed the issue and rewrote their core. That resulted in a huge performance boost. The reason the alpha nodes need alpha memory is to reduce repeated searches. Hope that explains it.

    peter

  4. Tim Bass says:
    Saturday, March 6, 2010 at 4:41pm

    Hi Peter,

    Thanks for those references. I will take a look when I have a lot of extra time!

    Do you have any comment on this Nov 2006 presentation?

    Rete, Rete II, Rete III & Rete in TIBCO BusinessEvents

    http://www.slideshare.net/TimBassCEP/ss-presentation-716373

    Do I need to change it? Or is your “public” position officially “No Comment” ?

    Should I revise it? If so, what should be changed?

    Yours, Tim

  5. Peter Lin says:
    Saturday, March 6, 2010 at 4:58pm

    My bias opinion. Rete II and III are fundamentally the same from an algorithm perspective. What makes it different is the implementation is more efficient. I classify II and III or ReteOO as marketing terms. These differences come from techniques like hashed memories, lazy evaluation, late binding and writing really efficient code.

  6. Tim Bass says:
    Saturday, March 6, 2010 at 5:16pm

    Hi Peter,

    I agree. Anyway, as I recall, that presentation was not designed to be technical and was more “marketing-oriented” anyway.

    Anyway, I can’t revise it, really, since I am “long gone” from TIBCO… I may just take it down since it is really “non technical” and not designed to be either.

    Thanks for your feedback.

  7. Charles Young says:
    Sunday, March 7, 2010 at 12:09am

    And to clarify further on backward chaning, a common misunderstanding (I know because I used to assume this at one time) is that forward chaining is synonymous to the match-resolve-act cycle and therefore backward chaining must somehow use some different cycle. This is not the case, which is why, although backward chaining is not ‘required’ by Rete, Rete engines can be, and sometimes are, built to perform backward chaining. Indeed, at a deeper level, backward chaining is a natural approach for production systems. Grammar-driven parser generators are an example of a type of production system which in essence perform backward reasoning. Paul Hayley suggested, some years ago, that an automated approach to ‘full’ backward chaining (i.e., automatically instrumenting rule sets to perform backward chaining wherever possible) will generally yield a performance benefit in most common scenarios, and I think he is probably correct, although it would take some proper research to really establish this beyond doubt.

  8. Peter Lin says:
    Sunday, March 7, 2010 at 3:08am

    Here is the link to Paul Haley’s paper from 20 yrs back.

    http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/

    Haley rule engine implemented this approach, so oracle has it now.

  9. Peter Lin says:
    Sunday, March 7, 2010 at 3:35am

    Not to confuse things, but there’s a third way to chain rules, which I’ve been researching for many years now. I call it bi-directional chaining. It’s bi-directional in the sense that if the data is available, it works in normal forward chaining mode. If the data isn’t in the working memory, the engine gets it and asserts it. By “get it” I mean it attempts to deduce it by looking at the rules and working memory. If it needs to, it will query external data source and assert the data. The reason for this is it reduces the need to generate subgoals and manage them. That’s the theory anyways, I still haven’t had time to work it through completely.

  10. is Tim Bass says:
    Sunday, March 7, 2010 at 9:45am

    I think it is interesting that a number of people have devoted much of their professional lives to optimizing rule-based approaches, especially to inferencing.

    When I worked with TIBCO BE, I never considered BE an inferencing engine, because it was not really a “detection engine” as much as a “scheduling engine”. For this reason, I always viewed BE as a type of “core controller” that would be used to schedule complex transactions (which it does very well).

    For me, a forward-chaining event-driven rules-processing IDE such as BE was an excellent Blackboard Controller, scheduling and directing the work of many intelligent agents.

    So, when I worked on these types of projects before, I considered CEP a larger, more complete architecture, that required numerous components to detection complex events and situations.

    The primary reason I placed BE at the center of the BB architecture as the “BB Controller” function was based on the US DOD JDL architecture that is used to process complex events and sensor data.

    It make no sense to me to reinvent the wheel, and the JDL is a very good, mature, and quite proven functional architecture for this type of processing.

    Unfortunately, I have noticed that TIBCO has (seemingly) dropped this approach, and simplified their marketing material to a version of CEP that looks like a rules-engine; so they have (seemingly) collapsed the vision to match their product v. showing the product as a part of a larger architectural construct.

    This is one key problem when vendors are defining the space v. outside experts; i.e. the folks who spent years defining the JDL for the DOD. The JDL is a large scale distribution processing vision that can be applied to a very large class of complex problems.

    Reducing the vision to what fits a rules-engine is a bit like burning all the books in a library that are not about rules.

    Maybe one issue is that that rule-processing, like RETE, is such a fascinating area, that folks who work deep in that area do not really have the time or energy to go deep into other areas?

  11. Peter Lin says:
    Sunday, March 7, 2010 at 3:19pm

    I spend most of my free time reading, researching and experimenting with pattern matching algorithms, temporal logic, production rule engines and AI. From my bias perspective, it’s a full time job, so it’s really really difficult to master all these related areas at the same time. Just looking at fuzzy logic, natural language parsing and statistical filters, it would take atleast a decade to master each one. To obtain sufficient experience and depth across multiple disciplines requires decades of dedicated study. I think it’s safe to say to nobody today has achieved that level of experience and depth. The best thing we can hope for is collaboration between the most experience people and hope it will move the state of art forward.

  12. Tim Bass says:
    Sunday, March 7, 2010 at 3:32pm

    Hello Peter,

    I have seen some strong cross-discipline expertise in the multi-sensor data fusion field, supporting US DOD, where folks seems to collaborate with best-of-breed tools to solve complex multi-agent, multi-discipline architecture, but even then, there does exist professional bias.

    However, in the commercial space where the dialog is most driven by commercial vendors, cross-discipline expertise is rare. Most people are pressured to be sales people, not objective system architects recommending various best-of-breed systems and engineering them to work together.

    Perhaps we are on the verge of a renaissance in this area as cloud-oriented computing services become more mainstream?

    Maybe we should draft a new charter for an organization of people who are not vendor sales driven, not “my company wants me to do this and that driven…” and are truly a federation of objective cross-discipline system architects without conflicts of interest?

  13. Peter Lin says:
    Sunday, March 7, 2010 at 4:23pm

    My bias perspective, there is a need for vendor free collaboration. There’s always going to be vendor driven associations, but having vendor free group provides balance. A safe place where end users can speak freely and not have vendors get all militant.

  14. Tim Bass says:
    Sunday, March 7, 2010 at 4:33pm

    Yes, it is wrong for vendors to call themselves “CEP Engines’ or “RETE compliant” and other terms without any oversight. In addition, the oversight should be conflict-of-interest free, completely. This means no software vendors, no analysts who receive money from vendors (Gartner et al), no people serving on boards of companies (or advisers or consultants to those software companies) in the same domain.

    Hence, before you can all your software “RETE” you must open the kimono (no licensing muzzle orders) to an independent group of people. The entire software industry is, for the most part, “marketing fraud”, without oversight and controls, but pregnant with conflicts-of-interest, undisclosed relationships, etc.

    Of course, there needs to be a well written charter for that organization, with a set of guiding principles, etc. that defines the organization before it seeks membership.

  15. Tim Bass says:
    Sunday, March 7, 2010 at 4:48pm

    Note: I don’t think a professional association like we are referring to must be 100% “vendor free”; they can have narrowly defined associate roles that do not drive charter, serve in leadership positions, etc. All relationships must be disclosed, etc.

    For example, Gartner receives consulting” or “seminar” money from the same vendors they are evaluating for their “magic carpet ride”…. !! Vendors wine them and dine them very well. The entire industry is full of “corrupt” practices accepted as the “standard order of business”.

    The same is true for all these web sites and trade rags with “writers” and “bloggers” blogging for money, undisclosed, third party press releases… .the entire industry needs to be reformed, in my biased opinion.