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.