What is Rete Algorithm?
The Rete algorithm can be explained as a pattern matching algorithm for implementing rule-based systems. The algorithm was developed to efficiently apply many rules or patterns to many objects, or facts, in a knowledge base. It is used to determine which of the system's rules should fire based on its data store, its facts. The Rete algorithm was designed by Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper.
What is a Rete tree?
The Rete algorithm is an algorithm that organizes its data in a tree-like structure. Each node in the tree represents a test which will get performed against data being added or removed from memory. Each node will have one or two inputs and possibly many outputs. As a new piece of data enters the tree, it is filtered through the tree until it reaches a terminal node. If a terminal node is reached, this means that a new activation record is created with all the data points which caused the rule to be true. Rules in Rete systems work best if you can be as explicit as possible. This means you should write rules that look for very detailed items in a given piece of data. This causes a path in the Rete tree to be traversed in a somewhat determinant manner, which exposes the efficiencies inherent to the Rete algorithm.
How do you create a Rete network?
When large volumes of business rules need to be assessed against facts or data, the constant screening for applicability can be costly — both in terms of evaluation (and re-evaluation) and in terms of ordering the statements properly. This innovative approach for inference allows savings in both areas.
In absence of the Rete algorithm, or derivatives, the traditional approach is to sequence and nest the IF-THEN-ELSE statements of the rules in such a way that you capitalize on the test evaluations — you reuse them as much as possible. When you think about it, it would be akin to creating the leanest decision tree possible, in a graphical form or more likely in straight code. This “sequential” approach breaks (mostly in terms of performance) when rules need to execute as a result of the execution of other rules. This is what we call inference. In a sequential approach, you would have to restart the complete ruleset evaluation after each rule execution (if rules are prioritized) or after a full pass through the ruleset (in absence of prioritization).
However, prioritization might prevent you from reusing test evaluations all together in a sequential approach: if the conditions are not co-located in the logic, then you will likely have to perform those tests multiple times. Systems have become much more sophisticated than they used to be back then, and most BRMS products provide a sequential deployment option which is still pretty good when inference is not needed. The beauty of those products is that you can still manage the rules independently of each other and the sequential engine takes care of optimizing the generated spaghetti code.
How to implement Rete algorithm?
The Rete network is the heart of the Rete algorithm. It is made of nodes that each hold a list of objects that satisfy the associated condition. The original Rete algo worked out of facts but I will simplify the description to refer to objects since all commercial engines have evolved to be object-oriented nowadays.
The Rete network is constructed when you compile a rules project — only once when you start that service (or class for simpler designs) — and then shared across all invocations.
The discrimination tree is the first part of the Rete network. It starts with Alpha nodes that are associated with Classes (in the object-oriented sense). All instances of a given class will be listed in any given Alpha node. The discrimination happens by adding conditions as single nodes attached to the Alpha node or to another parent node.
What are Rete algorithm alternatives?
The Non-Rete algorithm (NRE) is an alternative to the Rete algorithm that consumes less memory than the Rete algo. 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.
What are the differences between Rete and NRE algorithm?
The two main differences between the two algorithms are:
1. 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.
2. 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.
