Rete Rules Mechanisms
At its most fundamental level, the Rete Algorithm works with a given set of rules which are stored in the Rete’s production memory, and a given set of currently-known facts (objects) that are stored in the Rete’s working memory. Working memory will include facts from the external world and also the current problem solving state of the rete network. The diagram below illustrates the basic flow of data through a Rete-based system.
Prior to rule evaluation, the set of production rules will be compiled and translated into a Rete node network. Some nodes in this network represent the conditions in each of the rules, whilst other nodes in the network represent possible inter-relations between the conditions of each rule.
To begin the evaluation process, the application asserts all known facts into the Rete which causes the Rete Algorithm to stores these facts in working memory. These facts in working memory are known as working memory elements. The assertion of these facts will cause evaluation of rete network nodes that correspond to conditions that are dependant on the asserted facts (that is the USING clause for the rule contains a set of declarations that match a particular subset of the currently asserted facts). If the associated conditions evaluate to true, then a tuple containing the satisfying facts will be propagated to downstream network nodes. If the propagation of a tuple reaches the end of the network (a leaf node) then this indicates that all conditions for a specific production rule have been satisfied. The Rete engine will then place a reference to this rule, along with the final tuple that caused all the rules conditions to be satisfied, in another memory area known as the Agenda.
Strictly speaking, the Agenda is not native component of the Rete algorithm. However, most rules-based systems make use of an Agenda in order to manage the situation when multiple rules concurrently activate. The Agenda maintains a collection of activations, where an activation represents a rule, its actions, and the tuple of facts that caused the rule to activate. Once activations are on the Agenda, the action part of the rule may be executed and the activation is then removed from the Agenda. In the case where the Agenda contains more than a single activation, the Rete engine needs to determine the order in which to perform the actions associated with each activation. This may be further complicated if execution of an action causes new facts to be asserted, which may result in more activations being added to or removed from the Agenda. In this situation, a conflict resolution strategy is used to determine the order of execution when multiple activations are on the Agenda.
It should now be obvious that the sequence of execution of a Rete-based system can be very complex indeed. Additions of facts may result in actions being added to the agenda and executed, which may result in the addition of more facts. Additionally, facts may be retracted or modified at any stage during this process. Any changes to the facts may result in pending activations being removed from the Agenda before they are executed (if their conditions are no longer satisfied). This continual cycle of assertion-matching-execution will end only when there are no remaining activations on the Agenda.