Chapter 5. Rule Algorithms

5.1. PHREAK Algorithm

The new PHREAK algorithm is evolved from the RETE algorithm. While RETE is considered eager and data oriented, PHREAK on the other hand follows lazy and goal oriented approach. The RETE algorithm does a lot of work during the insert, update and delete actions in order to find partial matches for all rules. In case of PHREAK, this partial matching of rule is delayed deliberately.

The eagerness of RETE algorithm during rule matching wastes a lot of time in case of large systems as it does result in a rule firing eventually. PHREAK algorithm addresses this issue and therefore is able to handle large data more efficiently.

PHREAK is derived from a number of algorithms including the following LEAPS, RETE/UL and Collection-Oriented Match algorithms.

In addition to the enhancements listed in the Rete00 algorithm, PHREAK algorithm adds the following set of enhancements:

  • Three layers of contextual memory: Node, Segment, and Rule memories.
  • Rule, segment, and node based linking.
  • Lazy (delayed) rule evaluation.
  • Stack-based evaluations with pause and resume.
  • Isolated rule evaluation.
  • Set-oriented propagations.

5.2. Rule Evaluation With PHREAK Algorithm

When the rule engine starts, all the rules are unlinked. At this stage, there is no rule evaluation. The insert, update, and delete actions are queued before entering the beta network. The rule engine uses a simple heuristic—​based on the rule most likely to result in firings—​to calculate and select the next rule for evaluation. This delays the evaluation and firing of the other rules. When a rule has all the right input values populated, it gets linked in—​a goal representing this rule is created and placed into a priority queue, which is ordered by salience. Each queue is associated with an AgendaGroup. The engine only evaluates rules for the active AgendaGroup by inspecting the queue and popping the goal for the rule with the highest salience. This means the work done shifts from the insert, update, delete phase to the fireAllRules phase. Only the rule for which the goal was created is evaluated, and other potential rule evaluations are delayed. While individual rules are evaluated, node sharing is still achieved through the process of segmentation.

Unlike the tuple-oriented RETE, the PHREAK propagation is collection-oriented. For the rule that is being evaluated, the engine accesses the first node and processes all queued insert, update, and delete actions. The results are added to a set, and the set is propagated to the child node. In the child node, all queued insert, update, and delete actions are processed, adding the results to the same set. Once finished, this set is propagated to the next child node and the same process repeats until it reaches the terminal node. This creates a batch process effect, which can provide performance advantages for certain rule constructs.

This linking and unlinking of rules happens through a layered bit mask system, based on network segmentation. When the rule network is built, segments are created for nodes that are shared by the same set of rules. A rule itself is made up from a path of segments. In case a rule does not share any node with any other rule, it becomes a single segment.

A bit-mask offset is assigned to each node in the segment. Furthermore, another bit mask is assigned to each segment in the rule’s path according to these rules:

  • If there is at least one input, the node’s bit is set to the on state.
  • If each node in a segment has its bit set to the on state, the segment’s bit is also set to the on state.
  • If any node’s bit is set to the off state, the segment is also set to the off state.
  • If each segment in the rule’s path is set to the on state, the rule is said to be linked in, and a goal is created to schedule the rule for evaluation.

The same bit-mask technique is used to also track dirty nodes, segments, and rules. This allows for an already linked rule to be scheduled for evaluation if it has been considered dirty since it was last evaluated. This ensures that no rule will ever evaluate partial matches.

As opposed to a single unit of memory in RETE, PHREAK has three levels of memory. This allows for much more contextual understanding during the evaluation of a rule.

PHREAK and Sequential Mode

The sequential mode is supported for the PHREAK algorithm: the modify and update rule statements are now allowed. Any rule that has not yet been evaluated will have access to data modified by the previous rules that used modify or update. This results in a more intuitive behavior of the sequential mode.

For example, consider the following rule:

rule "Rule1"
salience 100
when
   $fact : MyFact( field1 == false )
then
   System.out.println("Rule1 : " + $fact);
   $fact.setField1(true);
   update($fact);
end


rule "Rule2"
salience 95
when
    $fact : MyFact( field1 == true )
then
    System.out.println("Rule2 : " + $fact);
    update($fact);
end

When you insert a MyFact with the value field1==false:

  • The ReteOO algorithm executes only Rule1.
  • The PHREAK algorithm executes both Rule1 and Rule2.

For more information about the sequential mode, see Section 20.1.11.2.1, “Sequential Mode”.

5.3. Rete Algorithm

5.3.1. ReteOO

The Rete implementation used in BRMS is called ReteOO. It is an enhanced and optimized implementation of the Rete algorithm specifically for object-oriented systems. The Rete Algorithm has now been deprecated, and PHREAK is an enhancement of Rete. However, Rete can still be used by developers. This section describes how the Rete Algorithm functions.

Rete Root Node

When using ReteOO, the root node is where all objects enter the network. From there, it immediately goes to the ObjectTypeNode.

Figure 5.1. ReteNode

5944

ObjectTypeNode

The ObjectTypeNode helps to reduce the workload of the rules engine. If there are several objects, the rule engine wastes a lot of cycles trying to evaluate every node against every object. To make things efficient, the ObjectTypeNode is used so that the engine only passes objects to the nodes that match the object’s type. This way, if an application asserts a new Account, it does not propagate to the nodes for the Order object.

In Red Hat JBoss BRMS, an inserted object retrieves a list of valid ObjectTypesNodes through a lookup in a HashMap from the object’s class. If this list does not exist, it scans all the ObjectTypeNodes to find valid matches. It then caches these matched nodes in the list. This enables Red Hat JBoss BRMS to match against any class type that matches with an instanceof check.

AlphaNodes

AlphaNodes are used to evaluate literal conditions. 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.

AlphaNodes are propagated using ObjectTypeNodes.

Hashing

Red Hat JBoss BRMS uses hashing to extend Rete by optimizing the propagation from ObjectTypeNode to AlphaNode. 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 retrieves the correct AlphaNode from the HashMap. This avoids unnecessary literal checks.

When facts enter from one side, you may do a hash lookup returning potentially valid candidates (referred to as indexing). At any point a valid join is found, the Tuple joins with the Object (referred to as a partial match) and then propagates to the next node.

BetaNodes

BetaNodes are used to compare two objects and their fields. The objects may be of the same or different types.

Alpha Memory and Beta Memory

Alpha memory refers to the left input on a BetaNode. In Red Hat JBoss BRMS, this input remembers all incoming objects.

Beta memory is the term used to refer to the right input of a BetaNode. It remembers all incoming tuples.

Lookups with BetaNodes

When facts enter from one side, you can do a hash lookup returning potentially valid candidates (referred to as indexing). If a valid join is found, the Tuple joins with the Object (referred to as a partial match) and then propagates to the next node.

LeftInputNodeAdapters

A LeftInputNodeAdapter takes an Object as an input and propagates a single Object Tuple.

Terminal Nodes

Terminal nodes are used to indicate when a single rule matches all its conditions (that is, the rule has a full match). A rule with an OR conditional disjunctive connective results in a sub-rule generation for each possible logical branch. Because of this, one rule can have multiple terminal nodes.

Node Sharing

Node sharing is used to prevent redundancy. As many rules repeat the same patterns, node sharing allows users to collapse those patterns so that the patterns need not be reevaluated for every single instance.

The following rules share the first pattern but not the last:

rule
when
  Cheese($cheddar : name == "cheddar")
  $person: Person(favouriteCheese == $cheddar)
then
  System.out.println($person.getName() + "likes cheddar");
end
rule
when
  Cheese($cheddar : name == "cheddar")
  $person : Person(favouriteCheese != $cheddar)
then
  System.out.println($person.getName() + " does not like cheddar");
end

The Rete network displayed below denotes that the alpha node is shared but the beta nodes are not. Each beta node has its own TerminalNode.

Figure 5.2. Node Sharing

5954

5.4. Switching Between PHREAK and ReteOO

It is possible to switch between PHREAK and ReteOO either by setting system properties, or in KieBase configuration. PHREAK is the default algorithm in both cases.

Switching to ReteOO requires the drools-reteoo-VERSION.jar file to be available on the class path. To include the file, add the following ReteOO Maven dependency to the pom.xml file in your project:

<dependency>
  <groupId>org.drools</groupId>
  <artifactId>drools-reteoo</artifactId>
  <version>DROOLS_VERSION</version>
</dependency>

For the supported Maven artifact version, see the Supported Component Versions section of the Red Hat JBoss BPM Suite Installation Guide.

Note

If the ReteOO Maven dependency is not specified in the pom.xml file in your project, the BRMS engine uses PHREAK instead and issues a warning.

Switching Between PHREAK and ReteOO in System Properties

To switch between the PHREAK and ReteOO algorithms, edit the drools.ruleEngine system property to contain one the following values:

drools.ruleEngine=phreak
drools.ruleEngine=reteoo

The default value is phreak.

Switching Between PHREAK and ReteOO in KieBaseConfiguration

When creating a KieBase, specify the rule engine algorithm in KieBaseConfiguration. See the following example:

import org.kie.api.KieBase;
import org.kie.api.KieBaseConfiguration;
import org.kie.api.KieServices;
import org.kie.api.runtime.KieContainer;
import org.kie.internal.builder.conf.RuleEngineOption;
...
KieServices kservices = KieServices.Factory.get();
KieBaseConfiguration kconfig = kieServices.Factory.get().newKieBaseConfiguration();

// You can either specify PHREAK (default):
kconfig.setOption(RuleEngineOption.PHREAK);

// or legacy ReteOO:
kconfig.setOption(RuleEngineOption.RETEOO);

// ... and then create a KieBase for the selected algorithm
// (getKieClasspathContainer() is just an example):
KieContainer container = kservices.getKieClasspathContainer();
KieBase kbase = container.newKieBase(kieBaseName, kconfig);

For a list of Maven dependencies, see example Embedded jBPM Engine Dependencies. If you use Red Hat JBoss BRMS, see example Embedded Drools Engine Dependencies.

Additionally, if you want to switch to ReteOO, use the drools-reteoo dependency:

<dependency>
  <groupId>org.drools</groupId>
  <artifactId>drools-reteoo</artifactId>
  <version>6.5.0.Final-redhat-2</version>
</dependency>

For the current Maven artifact version, see chapter Supported Component Versions of the Red Hat JBoss BPM Suite Installation Guide.

Note

Switching to ReteOO requires drools-reteoo-(version).jar to exist on the classpath. If not present, the BRMS Engine reverts back to PHREAK and issues a warning. This applies for switching with KieBaseConfiguration and system properties.