Rete Algorithm

Rete algorithm is well described in the Drools Expert User Guide.

The latin word "rete" means "net" or "network".
The Rete algorithm can be broken into 2 parts: rule compilation and run-time execution.

The compilation algorithm describes how the Rules in the Production Memory are processed to generate an efficient discrimination network. In non-technical terms, a discrimination network is used to filter data as it propagates through the network.

The nodes at the top of the network would have many matches, and as we go down the network, there would be fewer matches. At the very bottom of the network are the terminal nodes. Dr. Forgy described 4 basic nodes: root, 1-input, 2-input and terminal.

The root node is where all objects enter the network. From there, it immediately goes to the ObjectTypeNode. The purpose of the ObjectTypeNode is to make sure the engine doesn't do more work than it needs to.

For example, say we have 2 objects: Account and Order. If the rule engine tried to evaluate every single node against every object, it would waste a lot of cycles. To make things efficient, the engine should only pass the object to the nodes that match the object type. The easiest way to do this is to create an ObjectTypeNode and have all 1-input and 2-input nodes descend from it. This way, if an application asserts a new Account, it won't propagate to the nodes for the Order object.

Rete algorithm

In Drools when an object is asserted it retrieves a list of valid ObjectTypesNodes via a lookup in a HashMap from the object's Class; if this list doesn't exist it scans all the ObjectTypeNodes finding valid matches which it caches in the list.

This enables Drools to match against any Class type that matches with an instanceof check.

ObjectTypeNodes can propagate to AlphaNodes, LeftInputAdapterNodes and BetaNodes.
AlphaNodes are used to evaluate literal conditions. Although the 1982 paper only covers equality conditions, many RETE implementations support other operations.

Was it clear so far?

For example, Account.name == "Mr Trout" is a literal condition. When a rule has multiple literal conditions for a single object type, they are linked together. This means that if an application asserts an Account object, it must first satisfy the first literal condition before it can proceed to the next AlphaNode.

Drools extends Rete by optimizing the propagation from ObjectTypeNode to AlphaNode using hashing. Each time an AlphaNode is added to an ObjectTypeNode it adds the literal value as a key to the HashMap with the AlphaNode as the value. When a new instance enters the ObjectType node, rather than propagating to each AlphaNode, it can instead retrieve the correct AlphaNode from the HashMap,thereby avoiding unnecessary literal checks.

Rete algorithm is built-in the Rules Engine as major part of Drools.

Drools team expands this algorithm and plans to add more flavors of inference.

There is a plan to add ontology query which can benefit from existing knowledge domains presented as ontology graphs.
Find more about adding a semantic flavor (ontology) to rules in the IT of the Future, Part 2, Transition to Semantic Cloud.

We discussed so far straight logical algorithms for computers. But people�s thinking process includes different types of logic which sometimes can be more productive.
These are: imperfect reasoning (fuzzy logic, certainty factors), belief systems, temporal reasoning, correlation, association and more�

References:

1. Drools Expert User Guide
2. http://ITofTheFuture.com - Part 2, Transition to Semantic Cloud (Workflow Components and Rules)

Assignments
1. Answer QnAs
2. Create another QnA related to the subject and email to jeff.zhuk@javaschool.com

Rete-algorithm