This chapter describes the existing Rete algorithm used by the Rules Engine and introduces a Non-Rete algorithm.
This chapter includes the following sections:
The Rete algorithm was invented by Charles Forgy and was the subject of his 1979 PhD thesis. It was conceived for use with the expert systems of the time and was based on the observation that the facts in the rule engine's working memory change slowly over time through a series of inference cycles. Much of its power is derived from a trade off of increased memory use for improved performance.
Caching previous rule condition evaluation results avoids the re-evaluation of all rule conditions when a small change is made to working memory. Many business rules use cases do not fit this usage profile and thus do not benefit from the use of a Rete algorithm while incurring the overhead of the algorithm's memory consumption characteristics.
The Non-Rete algorithm (NRE) is an alternative to the Rete algorithm that consumes less memory than the Rete algorithm. For many business rules use cases it will also result in improved performance. The core of NRE algorithm is a new rule condition evaluation approach. The majority of the rules engine is unmodified and shared across the Rete and NRE algorithms. The externally defined semantics of the existing Rete algorithm are preserved by the NRE algorithm. Here are some key points about the new algorithm:
Simpler internal rule representation.
Byte code generated for rule tests, rule actions, and user defined functions.
More efficient modify operation.
Rule conditions not evaluated until the containing ruleset is on the top of the stack. After initial evaluation, re-evaluation occurs on fact operations as needed.
Ability to avoid unnecessary re-evaluation when rulesets are only present on the ruleset stack once during rule execution.
The two main differences between the two algorithms are:
Rule condition evaluation:
In the Rete algorithm, rule conditions are evaluated when fact operations occur (assert, modify, retract).
In the Non-Rete algorithm, rule conditions are evaluated for the first time when the ruleset is on the top of the stack, then on fact operations after that.
Rule firing order. There are cases where the rule firing order is not defined, for example when a single fact activates multiple rules at the same time and the priorities are identical. In these cases, the order in which the rule activations fire may be different.
Note:
It is possible that an existing set of rules has an implicit dependency on the order in which the rules fire with the Rete algorithm even though that order may not be defined. The order may be different with the Non-Rete algorithm, which may expose a latent bug in the rules as authored.
The selection of the algorithm to be used must be done when a RuleSession or RuleSessionPool is created.
For backwards compatibility, the default is the Rete algorithm. The key for the algorithm configuration parameter is RuleSession.CFG_ALGORITHM and the two values are:
RuleSession.ALGORITHM_RETE
RuleSession.ALGORITHM_NRE
Also, there is a configuration parameter: RuleSession.CFG_ALLOW_ERROR_SUPPRESSION
It is common that multiple rulesets are executed during a rule execution. It is also common that each ruleset is pushed onto the ruleset stack once and after rules in that ruleset have completed firing, it is not pushed onto the stack again during that rule execution. With the Non-Rete algorithm, additional performance gain can be realized for these cases by specifying that the rulesets will only appear on the stack once. This setting can be set and queried with the RL built in functions:
function setRulesetsOnStackOnce(boolean bv) returns boolean
function isRulesetsOnStackOnce() returns boolean