RetePlus algorithm
RetePlus is a rule execution mode based on the Rete algorithm. It relies on a working memory and agenda, and supports negative patterns, object notification, and logical objects.
RetePlus is the Decision Server extension based on the Rete algorithm. In RetePlus mode, rule execution uses an environment based on a working memory and agenda.
Additional information on RetePlus operation is given in the sections:
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, each rule engine in Decision Server is paired with a working memory. The working memory contains all the objects contained in the associated IlrContext 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.
To manage and inspect the working memory, you can use the following methods:
-
IlrContext#insert(java.lang.Object)
-
IlrContext#retract(java.lang.Object)
-
IlrContext#update(java.lang.Object)
-
IlrContext#updateContext()
-
IlrContext#enumerateObjects()
-
IlrContext#getObjects(java.lang.Class,%20boolean)>
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 #JqoSdk2m__rule_instances.
To manage the agenda, you can use the following methods:
-
IlrContext#isAgendaNotEmpty()
-
IlrContext#getFirstInstance()
-
IlrContext#enumerateInstances()
The agenda stores rule instances that are eligible to be run. 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:-
cure
-
incrementAge
You can replace the
update
statement in theincrementAge
rule with anupdate refresh
statement:rule incrementAge { when { p: Person(!sick; age < 50); } then { p.age += 1; update refresh p; }
If the object
Person(18,true)
is inserted in the working memory, theupdate refresh
statement produces the following execution trace:-
cure
-
incrementAge
-
incrementAge
-
incrementAge
-
...
-
incrementAge
Until the condition
age < 50
is false.
-
- Priority
-
The rule priority is the second criterion that is taken into account to decide at which position a rule instance should be placed in the agenda.
- 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 by 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:
-
init
rule: Because the objectangel
was inserted from the application, theinit
rule is the only rule that can be run. It inserts the objectsclown
and then the objectdascyllus
into the working memory. The most recent object is thereforedascyllus
. -
first
rule: This rule is run before thesecond
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. -
second
rule: This rule is run before thethird
rule. The second and the third rules have the same priority, but the objectdascyllus
is more recent than the objectclown
. -
third
rule: This rule is run before thelast
rule. Although the objectdascyllus
is more recent thanclown
, thethird
rule has a higher priority than thelast
rule. -
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:
Rule | Rule | Rule | Rule |
---|---|---|---|
rule1(A,C) | rule1(A,D) | rule1(B,C) | rule1(B,D) |
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
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 equals "history"; number > 300);
}
then {
?c.updateNumbering(); // This call modifies ?c
update ?c;
}
};
If you do not use modify
,
you must use the update
primitive to inform Decision Server that
objects have been modified. Forgetting to notify Decision Server of
modifications leads to inconsistent states.
Attribute modification
The modify
statement
lets you modify the values of the attributes of objects in the working
memory.
Here is an example:
rule ModifyLecturer {
when {
?c: Course(department equals "History"; lecturer equals "Tanner");
}
then {
modify ?c {lecturer = "Chen"};
}
};
Network operation
The RetePlus network can minimize the number of rules and conditions:
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.
A not
condition
returns true for a simple condition if the working memory does not
contain any object that can match the condition.
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, nameda1
anda2
. -
The B class has three attributes, named
b1
,b2
, andb3
. -
The
C
class has a single attribute, namedc1
.
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 performs 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
andb3
gives rise to a node composed of two pairs of tokens, and the test between attributesb2
andc1
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.