Drools - Rete

Rete
[Charles Forgy] created the original Rete algorithm around 1982 as part of his DARPA-funded research. Compared to many previous production-matching algorithms, Rete was very advanced. Even today, there have been few improvements to it in the general case. Variations on Rete, such as TREAT, may have different performance characteristics depending on the environment. Some perform better with large rule sets but small numbers of objects, while other perform well for steady-state environments, but react poorly to numerous successive changes in the data.
Commercial vendors typically have optimized their implementations of the Rete algorithm, along with providing add-ons. An algorithm does not a product make.
A Rete network is a graph through which data flows. Originally, data was specified using Cambridge-prefix tuples since Lisp-like languages were in style for logic programming. The tuples were used to express attributes about objects. For example, tuples may be used to express a person‘s name and her pets. The tuples are dropped into the Rete network, and those that reach the far end cause the firing of a rule. The original production-matching was based upon matches against tuple patterns.
Rete Animation
The Rete network is comprise of two types of nodes:
1-input/1-output nodes The 1/1 nodes are constrictive nodes that only allow matching tuples to flow through. Any tuples that do not match are discarded by the node.
2-input/1-output nodes The 2/1 nodes simply connect the output arcs from two other nodes (either 1/1 nodes or 2/1 nodes) merging tuples from both the left and right incoming arcs into a single tuple on the outgoing arc. Maintains a memory of tuples for matching against future facts.
A forest of 1/1 nodes acts as the entry-point into the entire Rete network for any incoming tuple. The network-entry nodes filter tuples purely by their type. Tuples about dogs and tuples about cats may each have a different type and may be differentiated from each other by the 1/1 network-entry nodes.
Each condition of a rule is merely a pattern for a particular tuple type. The condition describes the attributes that a tuple must have and acts as a filter. Each condition is transformed into a 1/1 node that only allows tuples matching the specified attributes to pass. An attribute value may be specified as a variable and implies that the variable must hold the same value in all occurrences. The 1/1 filter nodes are attached to the network downstream from the 1/1 entrynode that differentiates their tuple type.
Consider a condition such as ‘For any person who has a dog that has the same name as that person‘s sister‘s cat, then...‘ This could be expressed with the condition patterns of:
(1) ( person name=person? sister=sister? )(2) ( person name=person? dog=petName? )(3) ( person name=sister? cat=petName? )
Condition #1 models the sister relationship so that the rule only applies to two people who are sisters. The person? and sister? tokens are variables that must be consistent across any set of tuples that match this rule.
Conditions #2 and #3 serve two roles. The dog and cat attributes share the same petName? variable and serve to identify two people who have a cat and a dog with the same name. They each contain a name attribute with either the variable person? or sister? which ties the last two conditions back to the first two.

A Rete Network.
typepersonsistercatdog
tuple set # 1
personrebeccajeanniezoomienull
personjeannierebeccanullzoomie
tuple set #2
personrebeccajeanniezoomienull
personjeannierebeccanulltoby
Example Tuple Sets
If two sets of tuples, see Example Tuple Sets, were asserted against the rule, tuple set #1 would cause a firing of the rule, where tuple set #2 would not. In both cases, the two tuples would pass node condition(1), as the nodes simply associate the person? and sister? variables with the appropriate values from each tuple.
The join(1) node would allow both tuples to merge and propagate past it in both the first and second case. Additionally, for both cases, the rebecca tuple would pass node condition(2) and the jeannie tuple would pass node condition(3).
The join(2) node is where the two cases differ. In the first case, nodes condition(2) and condition(3) have each associated the value of ‘zoomie‘ to the petName? variable. In the second case, the two nodes has assigned different values to the variable. The join(2) node only allows those tuples that have consistent associations with all variables to pass.
While it may be simple to create a rules engine that allows specification of business logic in a format that is comfortable to business analysts, the matching of the rules may still be problematic without a good algorithm.
The rules engine must be made aware of its environment, typically through a process called fact assertion. Fact assertion consists of the program asserting facts into a rules session, orWorking Memory.
Whenever a fact is asserted, retracted or modified within theWorking Memory, many rules may become candidates for firing, or may have become invalidated. A simplistic approach is to reevaluate all rules against the entirety of the working memory. This method is guaranteed to be correct but will also certainly be sub-optimal. Any individual fact modification only affects a small number of conditions in a small number of rules.
Variations of the Rete algorithm allow the rules engine to maintain a memory of the results of partial rule matches across time. Reevaluation of each condition is no longer necessary, as the engine knows which conditions might possibly change for each fact, and only those must be reevaluated.
_xyz