Rule Engines: RETE and Alternatives

The famous RETE algorithm was invented by Dr. Charles Forgy more than 30 years ago and it still remains the foundation for most implementations of inferential rule engines.  Recently Carole-Ann asked the question: why after all these years there were no practical alternatives to RETE?

Of course, there are many non-inferential (sequential) rule engines that simply rely on explicitly specified sequencing of rules and rule sets. Sequential engines are quite successful because in many practical applications manual rules sequencing is a sufficient (and frequently preferred) mode. However, until recently real inferential rule engines were based on RETE only.  Why?

I addressed this question in my presentation at RulesFest-2011 – see also Carole-Ann’s comments.  My answer was simple: because there were no needs for alternatives – RETE is the best for execution of inferential rules in this, commonly used, setting:

However, the latest decision management approaches deal with situations when:

  • There are no rule languages at all (e.g. DMN decision tables)
  • There are no assumptions about a particular rule ordering within rule sets or between rule sets (e.g. TDM)
  • Business users who create rules-based decision models have no idea about a working memory and fact assertion/retraction.

These requirements bring real-world incentives for new implementations of inferential (non-sequential) rule engines.  One of them just became publicly available.

The new OpenRules Release 6.2.0 includes an advanced Rule Solver that in particular provides an inferential rule engine. To the best of my knowledge, it is the first alternative to RETE-based engines.  Rule Solver utilizes the power of Constraint Programming (CP) and is based on the standard JSR-331 that allows users to switch between different underlying constraint solvers without any changes in their decision models. Thus, now we have two architectural routes for inferential decision modeling and execution:

Different decision management systems may execute declarative decision models in two alternative ways:

  1. Using a RETE-based rule engine
  2. Using a constraint-based rule engine.

Rule Solver User Manual contains examples of Excel-based decision models that do not use any rule language and utilize classic decision tables. The same decision model may be executed by either standard OpenRules sequential engine or by Rule Solver. Contrary to the sequential engine, Rule Solver automatically resolves rule ordering problems inside one decision table and between multiple decision tables.

Rule Solver automatically validates if Excel-based decision models contain conflicts and points to possible inconsistencies in business rules. Especially valuable is its ability to diagnose conflicts between rules defined in different decision tables; frequently is very difficult or even impossible to find such conflicts manually. Additionally, Rule Solver can infer decisions even in situations when business rules only partially define a problem – it essentially minimizes the total number of rules needed to model the decision problem.

Rule Solver helps users to define and solve complex constraint satisfaction problems that are usually out of reach for traditional rule engines (including RETE-based).  You may look at examples of scheduling and resource allocation problems in my previous post.

While this is only an initial implementation, Rule Solver is already capable to address many real-world decision management problems. You may download Rule Solver as a part of the complete OpenRules installation from http://openrules.com/download.htm and try it for your own problems. Your comments and suggestions are very welcome.

Advertisements

About jacobfeldman

CTO at www.openrules.com http://www.linkedin.com/in/jacobfeldmanopenrules
This entry was posted in Constraint Programming, Decision Management, Optimization, Rule Engines and tagged , , . Bookmark the permalink.

One Response to Rule Engines: RETE and Alternatives

  1. Carole-Ann says:

    Hey Jacob, nice post! That brings back tons of memories of the Rules vs. Optimization days…

    I find fascinating how some use cases sound very intuitive — like scheduling telephone installations, rules can be used to figure out how what needs to happen and a solver can optimize the resources (engineers or technicians) that perform the non-automated tasks. But some other use cases are quite tricky. Each technology can bring value, so the choice is not so clear cut.

    My experience is that Solvers really shine when there are lots of constraints that make only very few paths (out of the many) actual solutions. The more dead-ends, the more effective the solver will be.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s