Thursday, June 01, 2006

What is a Rule Engine

Drools is a Rule Engine but it is more correctly classified as a Production Rule System. The term "Production Rule" originates from formal grammer - where it is described as "an abstract structure that describes a formal language precisely, i.e., a set of rules that mathematically delineates a (usually infinite) set of finite-length strings over a (usually finite) alphabet". Production Rules is a Rule Based approach to implementing an Expert System and is considered "applied artificial intilligence".

The term Rule Engine is quite ambiguous in that it can be any system that uses rules, in any form, that can be applied to data to produce outcomes; which includes simple systems like form validation and dynamic expression engines: "How to Build a Business Rules Engine (2004)" by Malcolm Chisholm exemplifies this ambiguity. The book is actually about how to build and alter a database schema to hold validation rules which it then shows how to generate VB code from those validation rules to validate data entry - while a very valid and useful topic for some, it caused quite a suprise to this author, unaware at the time in the subtleties of Rules Engines differences, who was hoping to find some hidden secrets to help improve the Drools engine. jBPM uses expressions and delegates in its Decision nodes; which controls the transitions in a Workflow. At each node it evaluates a rule that dicates the transition to undertake - this is also a Rule Engine. While a Production Rule System is a kind of Rule Engine and also Expert System, the validation and expression evaluation Rule Engines mention previously are not Expert Systems.

A Production Rule System is turing complete with a focus on knowledge representation to expression propositional and first order logic in a concise, non ambigious and declarative manner. The brain of a Production Rules System is an Inference Engine that is able to scale to a large number of rules and facts; the engine is able to schedule many rules that are elegible for execution at the same time through the use of a "conflict resolution" strategy. There are two methods of execution for Rule-Based Systems - Forward Chaining and Backward Chaining; systems that implement both are called Hybrid Production Rule Systems. Understanding these two modes of operation are key to understanding why a Production Rule System is different.

Forward Chaining is 'data-driven' and thus reactionary - facts are asserted into the working memory which results in rules firing - we start with a fact, it propagates and we end with multiple elegible Rules which are scheduled for execution. Drools is a forward chaining engine. Backward Chaining is 'goal-driven', we start with a conclusion which the engine tries to satisfy. If it can't it searches for conclusions, 'sub goals', that help satisfy an unknown part fo the current goal - it continues this process until either the initial conclusion is proven or there are no more sub goals. Prolog is an example of a Backward Chaining engine; Drools will adding support for Backward Chaining in its next major release.

The Rete algorithm by Charles Forgy is a popular approach to Forward Chaining, Leaps is another approach. Drools has implementations for both Rete and Leaps. The Drools Rete implementation is called ReteOO signifying that Drools has an enhanced and optimised implementation of the Rete algorithm for Object Oriented systems. Other Rete based engines also have marketing terms for their proprietary enhancements to Rete, like RetePlus and Rete III. It is important to understand that names like Rete III are purely marketing where, unlike the original published Rete Algorithm, no details of implementation are published; thus asking a question like "Does Drools implement Rete III?" is nonsensical. The most common enhancements are covered in "Production Matching for Large Learning Systems (Rete/UL)" (1995) by Robert B. Doorenbos

Business Rule Management Systems build value on top of an Rule Engine providing systems for rule management, deployment, collaboration, analysis and end user tools for business users. Further to this the Business Rules Approach is a fast evolving and popular methodology helping to formalise the role of Rule Engines in the enterprise.

For more information read the following two chapters from the manual:
Introduction and Background
Knowledge Representation

Post Comment

1 comment:

  1. Nice to see you blogging, thanks for differentiating between BREs and BRMSs (something I still haven't forgiven Gartner for failing to do).
    I also have tried to differentiate between the two and have some other Business Rules FAQs on my blog.