RetePlus algorithm

Working memory and the agenda

Under the RetePlus execution mode, the rule engine functions with Working memory and an Agenda, adding Rule instances for execution when conditions are met.

Working memory

Under the RetePlus execution mode, a rule engine in Decision Server is paired with a working memory. The working memory contains all the objects contained in the associated Engine object. You can modify the working memory by adding a statement in the action part of a rule or by using the Application Programming Interface (API). Thus, the rule engine is aware of the objects that are in the working memory and any objects that are linked to them. The rule engine can use only objects that are accessible from the working memory.

Agenda

The agenda is where Decision Server stores the rules whose patterns are all matched. Any rule that enters the agenda is said to be instantiated, it becomes a rule instance, see Rule instances.

The agenda stores rule instances that are eligible to be rund. If the agenda is empty, execution has no effect. Rule instances placed in the agenda are said to be eligible. Often, in the agenda, several rules are eligible. Consequently, the rule engine has to have some way of deciding which particular rule in the agenda should be run.

In the agenda, rule instances are ordered according to three criteria that determine which rule should be run first. Additional execution control is offered with the implementation of more complex features, see Object notifications.

Refraction

A rule instance that has been run cannot be reinserted into the agenda if no new fact has occurred, that is, if none of the objects matched by the rule are modified, or if no new object is matched by the rule.

The refraction principle enforces that only one rule instance is created for a given tuple. Because the data unit for an engine cycle is the working memory, the engine can easily record all the possible tuples and check that there is only one rule instance for each tuple.

For example consider the following ruleset:

class Person {
  Person(int age, boolean sick);
  boolean sick;
  int age;
}

rule incrementAge {
when {
  p: Person(!sick; age < 50);
} then {
  p.age += 1;
  update p;
}

rule cure {
when {
  p: Person(sick);
} then {
  p.sick = false;
  update p;
}

If the object Person(18,true) is inserted in the working memory, the refraction principle produces the following execution trace:

1. cure
2. incrementAge

You can add the repeatable property in the incrementAge rule:

rule incrementAge {
 property com.ibm.rules.engine.repeatable=true;
when {
  p: Person(!sick; age < 50);
} then {
  p.age += 1;
}

If the object Person(18,true) is inserted in the working memory, the repeatable property produces the following execution trace:

1. cure
2. incrementAge
3. incrementAge
4. incrementAge
5. ...
6. incrementAge

   Until the condition age < 50 is false.

Repeatable rules

To break the refraction principle, you can use the Boolean rule property com.ibm.rules.engine.repeatable. In the decision engine, you must use this property to mark the sets of rules that you want to be repeatable.

• When a rule is not repeatable, the refraction principle prevents a rule instance from being posted again to the agenda.
• When a rule is repeatable, it can be inserted again as a rule instance in the agenda if a modification occurs against its condition objects.

Recency

If two rule instances have the same priority, the rule that matches the most recent object (the most recently inserted, modified, or retracted object) is run first.

Priority and recency are used to resolve conflicts when several rule instances are candidates for execution at the same time. If, after using all specified conflict resolution methods, several rule instances remain candidates, then the engine uses internal metarules; this assures that the same sequence of rule executing is always followed, given the same conditions.

Example of rule executing order

The following technical rule example shows you the order in which rules are run:

rule init {
   when {
      angel();
   }
   then {
      insert clown();
      insert dascyllus();
   }
};
rule last {
   priority = -100;
   when {
      dascyllus();
   }
   then {
      System.out.println("last");
   }
};
rule first {
   priority = 100;
   when {
      angel();
      clown();
      dascyllus();
   }
   then {
      System.out.println("first");
   }
};
rule second {
   priority = 0;
   when {
      angel();
      dascyllus();
      clown();
   }
   then {
      System.out.println("second");
   }
};
rule third {
   priority = 0;
   when {
      angel();
      clown();
      dascyllus();
   }
   then {
      System.out.println("third");
   }
};

Suppose that the object angel has been inserted from the application using the API, and therefore has been inserted into the working memory, and that we run all the rules that can be run.

Here is the order in which the rules are run:

1. init rule: Because the object angel was inserted from the application, the init rule is the only rule that can be run. It inserts the objects clown and then the object dascyllus into the working memory. The most recent object is therefore dascyllus.

2. first rule: This rule is run before the second rule. The most recent object matched by these two rules is the same. However, the first object has a higher priority than the second, which determines their execution order.

3. second rule: This rule is run before the third rule. The second and the third rules have the same priority, but the object dascyllus is more recent than the object clown.

4. third rule: This rule is run before the last rule. Although the object dascyllus is more recent than clown, the third rule has a higher priority than the last rule.

5. last rule.

Rule instances

A rule instance is added to the agenda when objects in the working memory satisfy the condition part of that rule.

Let us consider the following technical rule:

rule rule1 {
   when {
      Fish(color == green; type == shark);
      Fish(type == trigger);
   }
   then {...}
};

The following rule instances will be put into the agenda:

In this example, you can see that a rule instance is a dynamic concept: the rule instance is produced by any combination of objects in the working memory that match the patterns specified in the rule. In contrast, a rule is a static concept.

Negative patterns

Standard rule conditions might be described as existential, in the sense that they could be matched by one or several objects that actually happen to exist. In the RetePlus execution mode there is a complementary concept known as negative patterns. To express the nonexistence of a particular object in the working memory, we place the not keyword before the condition of the object, as shown here:

not Fish(type==eel);

This negative pattern gives rise to a successful match because there is no object that matches the corresponding positive pattern:

Fish(type==eel);

Conversely, this negative pattern:

not Fish(type==angel);

does not give rise to a successful match for the simple reason that there is an object that matches the corresponding positive pattern:

Fish(type==angel);

Object notifications

With the RetePlus execution mode, you have statements to control individual operations:

• Object insertion
• Object retraction
• Object update
• #concept_cfl_nsj_hkb__attribute_modification

Object insertion

The insert statement lets you create a new object and insert it into the working memory. This keyword is followed by the name of the class and the values of the attributes of the object to be created.

Here is an example that involves the creation of a new Course object whose department and number attributes take the values History and 324, respectively:

insert Course(History,324);

There are two possibilities for the way that an insert operation is processed:

• The object is already in the working memory. In this case, the insert operation is equivalent to an update.

• The object is not in the working memory. In this case, the object is inserted into the working memory and the insert daemon of the corresponding class and its superclasses, if any, is called, and the agenda is updated.

Object retraction

The retract statement lets you remove from the working memory an object that is bound to a rule variable.

In the following example, the retract primitive removes the object bound to the ?c variable:

rule RemoveCourse {
   when {
      ?c: Course(department == History; number == 254);
   }
   then {
      retract ?c;
   }
};

The retract daemon of the corresponding class, if any, is called, and the agenda is updated accordingly. Retracting an object from the working memory might cause a logical object to lose one or several of its justifications.

Object update

When an object is modified by Java™, the modifications are not seen by Decision Server. This means that data maintained by Decision Server will not be consistent with the new contents of the modified object.

To avoid inconsistencies, the update statement should be called for such an object. This statement allows Decision Server to update its internal structures according to the new contents of the modified object.

In the following rule, the first action modifies the number attribute. The update primitive is then called to inform Decision Server that the object has been modified.

rule NumberingUpdate {
   when {
      ?c: Course(department == "history"; number > 300);
   }
   then {
      ?c.updateNumbering(); // This call modifies ?c 
      update ?c;
   }
};

Network operation

The RetePlus network can minimize the number of rules and conditions:

• RetePlus network operation
• Example of a RetePlus network
• RetePlus network structure
• Object addition
• Object removal

RetePlus network operation

The RetePlus network indexes rules so as to minimize the number of rules and conditions that need to be evaluated whenever the working memory is changed. The network minimizes the number of evaluations by sharing tests between rules and propagating changes incrementally. When all the tests have been completed, the network designates a rule.

In most cases, executing a rule modifies the working memory. Objects in the working memory referenced by these rules can be inserted, removed, and modified. The network processes the changes inferred by the execution of the rule and produces a new set of rules to be executed.

When a change occurs in the working memory, two things can happen, depending on the nature of the change:

• If there is an insertion of an object into the working memory (positive), the rule can be executed.

• If there is a removal of an object from the working memory (negative), the rule must be removed from the agenda. The agenda is the place where the current set of rules to be executed is maintained.

This process continues cyclically until there are no further rule instances left in the agenda.

Example of a RetePlus network

To illustrate our description of a RetePlus network, we shall make use of a trivial filter rule, written in the rule language that refers to classes named A, B, and C:

rule filter {
   when {
      A (a1==3; ?x:a2);
      B (b1==2; ?y:b2; b3==?x);
      C (c1==?y);
   }
   then {
      System.out.println("filter");
   }
}

The class attributes are the following:

• The A class has two attributes, named a1 and a2.

• The B class has three attributes, named b1, b2, and b3.

• The C class has a single attribute, named c1.

Assume that the working memory contains the following objects:

A( a1=3 a2=10 )
B( b1=2 b2=4 b3=10 )
B( b1=2 b2=7 b3=10 )
C( c1=4 )

RetePlus network structure

A RetePlus network can be represented as a graph composed of three zones:

Discrimination tree

A discrimination tree is a pattern-matching process that does tests. These tests are represented by diamond shapes at the top of the network. The tests concern the classes of objects and the values of their attributes. Input to this tree consists of tokens representing each of the current objects in the working memory.

When the pattern deals with only one object and its attributes, it is said to be a discrimination test. When it is a combination, it is called a join; these appear in the lower part of the graph.

Alpha nodes

An alpha node is formed at the next level of the network, for each token that passes the tests of the discrimination tree. Each node is composed of one or several tokens, represented by round-cornered rectangles (there are three alpha nodes in the figure). One alpha node contains two B-class tokens. The other two nodes contain only one class token each—A-class and C-class tokens, respectively.

Tests and tuples

The third zone of the network matches tokens of several classes of objects. The resulting nodes are known as tuples, which will be made up of several tokens. The equality test between attributes a2 and b3 gives rise to a node composed of two pairs of tokens, and the test between attributes b2 and c1 then filters out a triplet of tokens. In a RetePlus network, we often refer to tuples of this kind as join nodes.

Object addition

To demonstrate further this idea of the RetePlus network, suppose an extra object is inserted into the working memory. The added object is of the C class, and the value of its c1 attribute is 7.

C( c1=7 )

At this stage, when all the tests of the nodes are carried out, only the third test C (c1==?y); (class of object = C) is satisfied. The tests of the child nodes continue as the token descends through the network.

Here, there is no child node in the discrimination tree. For that reason, the object is stored directly in the alpha node.

When the token reaches the second join node B (b1==2; ?y:b2; b3==?x), the test is carried out between each B object of the pairs stored next to the memory of the join node and the C object contained in the token that just arrived at the join node. The test is satisfied for the B object of the second pair. We can therefore proceed and create a triplet formed by the second pair and the object in the token.

By forming this triplet we have, in fact, descended all the way through the network, and a new instance of the filter rule can be executed.

Object removal

Suppose that we now remove the object that we just added to the working memory.

The progress of the token through the discrimination tree is the same as in the case of object addition, but the arrival of the negative token in the alpha node causes the removal of the object contained in the token.

When the token arrives at the second join node, all the triplets that contain the object in the token are removed and the token continues its progression through the network.

As in the object addition example, the rule node is reached. The instance of the filter rule whose objects satisfy the conditions corresponding to the objects in the token are removed from the agenda.