Editing Rete algorithm (section)

== Description ==
The Rete algorithm provides a generalized logical description of an implementation of functionality responsible for matching data [[tuple]]s ("facts") against productions ("[[Rule of inference|rules]]") in a pattern-matching production system (a category of [[rule engine]]).   A production consists of one or more conditions and a set of actions that may be undertaken for each complete set of facts that match the conditions.   Conditions test fact [[Attribute (computing)|attributes]], including fact type specifiers/identifiers.   The Rete algorithm exhibits the following major characteristics:

*	It reduces or eliminates certain types of redundancy through the use of node sharing.
*	It stores partial matches when performing [[Logical conjunction|joins]] between different fact types.   This, in turn, allows production systems to avoid complete re-evaluation of all facts each time changes are made to the production system's working memory.   Instead, the production system needs only to evaluate the changes (deltas) to working memory.
*	It allows for efficient removal of memory elements when facts are retracted from working memory.
The Rete algorithm is widely used to implement matching functionality within pattern-matching engines that exploit a match-resolve-act cycle to support [[forward chaining]] and [[Inference|inferencing]].
*       It provides a means for many–many matching, an important feature when many or all possible solutions in a search network must be found.

Retes are [[directed acyclic graph]]s that represent higher-level rule sets.   They are generally represented at run-time using a network of in-memory objects.   These networks match rule conditions (patterns) to facts (relational data tuples).  Rete networks act as a type of relational query processor, performing [[Projection (relational algebra)|projections]], [[Selection (relational algebra)|selections]] and joins conditionally on arbitrary numbers of data tuples.

Productions (rules) are typically captured and defined by [[Business analyst|analysts]] and [[Software developer|developers]] using some high-level rules language.     They are collected into rule sets that are then translated, often at run time, into an executable Rete.

When facts are "asserted" to working memory, the engine creates ''working memory elements'' (WMEs) for each fact.   Facts are [[tuple]]s, and may therefore contain an arbitrary number of data items.   Each WME may hold an entire tuple, or, alternatively, each fact may be represented by a set of WMEs where each WME contains a fixed-length tuple.   In this case, tuples are typically triplets (3-tuples).

Each WME enters the Rete network at a single root node.  The root node passes each WME on to its child nodes, and each WME may then be propagated through the network, possibly being stored in intermediate memories, until it arrives at a terminal node.

=== Alpha network ===
The "left" (''alpha'') side of the node graph forms a discrimination network responsible for selecting individual WMEs based on simple conditional tests that match WME attributes against constant values.  Nodes in the discrimination network may also perform tests that compare two or more attributes of the same WME.  If a WME is successfully matched against the conditions represented by one node, it is passed to the next node.   In most engines, the immediate child nodes of the root node are used to test the entity identifier or fact type of each WME.   Hence, all the WMEs that represent the same [[wikt:entity|entity]] type typically traverse a given branch of nodes in the discrimination network.

Within the discrimination network, each branch of alpha nodes (also called 1-input nodes) terminates at a memory, called an ''alpha memory''. These memories store collections of WMEs that match each condition in each node in a given node branch.   WMEs that fail to match at least one condition in a branch are not materialised within the corresponding alpha memory.   Alpha node branches may fork in order to minimise condition redundancy.

=== Beta network ===
The "right" (''beta'') side of the graph chiefly performs joins between different WMEs. It is optional, and is only included if required. It consists of 2-input nodes where each node has a "left" and a "right" input. Each beta node sends its output to a ''beta memory''.

In descriptions of Rete, it is common to refer to token passing within the beta network. In this article, however, we will describe data propagation in terms of WME lists, rather than tokens, in recognition of different implementation options and the underlying purpose and use of tokens. As any one WME list passes through the beta network, new WMEs may be added to it, and the list may be stored in beta memories. A WME list in a beta memory represents a partial match for the conditions in a given production.

WME lists that reach the end of a branch of beta nodes represent a complete match for a single production, and are passed to terminal nodes. These nodes are sometimes called ''p-nodes'', where "p" stands for ''production''. Each terminal node represents a single production, and each WME list that arrives at a terminal node represents a complete set of matching WMEs for the conditions in that production. For each WME list it receives, a production node will "activate" a new production instance on the "agenda". Agendas are typically implemented as [[Priority queue|prioritised queues]].

Beta nodes typically perform joins between WME lists stored in beta memories and individual WMEs stored in alpha memories.   Each beta node is associated with two input memories.    An alpha memory holds WM and performs "right" activations on the beta node each time it stores a new WME.    A beta memory holds WME lists and performs "left" activations on the beta node each time it stores a new WME list.  When a join node is right-activated, it compares one or more attributes of the newly stored WME from its input alpha memory against given attributes of specific WMEs in each WME list contained in the input beta memory.   When a join node is left-activated it traverses a single newly stored WME list in the beta memory, retrieving specific attribute values of given WMEs.   It compares these values with attribute values of each WME in the alpha memory.

Each beta node outputs WME lists that are either stored in a beta memory or sent directly to a terminal node.   WME lists are stored in beta memories whenever the engine will perform additional left activations on subsequent beta nodes.

Logically, a beta node at the head of a branch of beta nodes is a special case because it takes no input from any beta memory higher in the network.  Different engines handle this issue in different ways. Some engines use specialised adapter nodes to connect alpha memories to the left input of beta nodes. Other engines allow beta nodes to take input directly from two alpha memories, treating one as a "left" input and the other as a "right" input.   In both cases, "head" beta nodes take their input from two alpha memories.

In order to eliminate node redundancies, any one alpha or beta memory may be used to perform activations on multiple beta nodes.   As well as join nodes, the beta network may contain additional node types, some of which are described below.   If a Rete contains no beta network, alpha nodes feed tokens, each containing a single WME, directly to p-nodes.   In this case, there may be no need to store WMEs in alpha memories.

=== Conflict resolution ===
During any one match-resolve-act cycle, the engine will find all possible matches for the facts currently asserted to working memory.   Once all the current matches have been found, and corresponding production instances have been activated on the agenda, the engine determines an order in which the production instances may be "fired".    This is termed ''conflict resolution'', and the list of activated production instances is termed the ''conflict set''.  The order may be based on rule priority (''salience''), rule order, the time at which facts contained in each instance were asserted to the working memory, the complexity of each production, or some other criteria.   Many engines allow rule developers to select between different conflict resolution strategies or to chain a selection of multiple strategies.

Conflict resolution is not defined as part of the Rete algorithm, but is used alongside the algorithm.    Some specialised production systems do not perform conflict resolution.

=== Production execution===
Having performed conflict resolution, the engine now "fires" the first production instance, executing a list of actions associated with the production. The actions act on the data represented by the production instance's WME list.

By default, the engine will continue to fire each production instance in order until all production instances have been fired.   Each production instance will fire only once, at most, during any one match-resolve-act cycle.   This characteristic  is termed ''refraction''.   However, the sequence of production instance firings may be interrupted at any stage by performing changes to the working memory.   Rule actions can contain instructions to assert or retract WMEs from the working memory of the engine. Each time any single production instance performs one or more such changes, the engine immediately enters a new match-resolve-act cycle.   This includes "updates" to WMEs currently in the working memory.   Updates are represented by retracting and then re-asserting the WME.   The engine undertakes matching of the changed data which, in turn, may result in changes to the list of production instances on the agenda.  Hence, after the actions for any one specific production instance have been executed, previously activated instances may have been de-activated and removed from the agenda, and new instances may have been activated.

As part of the new match-resolve-act cycle, the engine performs conflict resolution on the agenda and then executes the current first instance.  The engine continues to fire production instances, and to enter new match-resolve-act cycles, until no further production instances exist on the agenda.  At this point the rule engine is deemed to have completed its work, and halts.

Some engines support advanced refraction strategies in which certain production instances executed in a previous cycle are not re-executed in the new cycle, even though they may still exist on the agenda.

It is possible for the engine to enter into never-ending loops in which the agenda never reaches the empty state.   For this reason, most engines support explicit "halt" verbs that can be invoked from production action lists.  They may also provide automatic [[cycle detection|loop detection]] in which never-ending loops are automatically halted after a given number of iterations.   Some engines support a model in which, instead of halting when the agenda is empty, the engine enters a wait state until new facts are asserted externally.

As for conflict resolution, the firing of activated production instances is not a feature of the Rete algorithm.   However, it is a central feature of engines that use Rete networks. Some of the optimisations offered by Rete networks are only useful in scenarios where the engine performs multiple match-resolve-act cycles.

=== Existential and universal quantifications ===
Conditional tests are most commonly used to perform selections and joins on individual tuples.   However, by implementing additional beta node types, it is possible for Rete networks to perform [[Quantification (logic)|quantification]]s.    [[Existential quantification]] involves testing for the existence of at least one set of matching WMEs in working memory.   [[Universal quantification]] involves testing that an entire set of WMEs in working memory meets a given condition.    A variation of universal quantification might test that a given number of WMEs, drawn from a set of WMEs, meets given criteria.   This might be in terms of testing for either an exact number or a minimum number of matches.

Quantification is not universally implemented in Rete engines, and, where it is supported, several variations exist.   A variant of existential quantification referred to as ''negation'' is widely, though not universally, supported, and is described in seminal documents.   Existentially negated conditions and conjunctions involve the use of specialised beta nodes that test for non-existence of matching WMEs or sets of WMEs.   These nodes propagate WME lists only when no match is found.   The exact implementation of negation varies.   In one approach,  the node maintains a simple count on each WME list it receives from its left input.   The count specifies the number of matches found with WMEs received from the right input.   The node only propagates WME lists whose count is zero.   In another approach, the node maintains an additional memory on each WME list received from the left input.   These memories are a form of beta memory, and store WME lists for each match with WMEs received on the right input.   If a WME list does not have any WME lists in its memory, it is propagated down the network.   In this approach, negation nodes generally activate further beta nodes directly, rather than storing their output in an additional beta memory.   Negation nodes provide a form of '[[negation as failure]]'.

When changes are made to working memory, a WME list that previously matched no WMEs may now match newly asserted WMEs.   In this case, the propagated WME list and all its extended copies need to be retracted from beta memories further down the network.   The second approach described above is often used to support efficient mechanisms for removal of WME lists.   When WME lists are removed, any corresponding production instances are de-activated and removed from the agenda.

Existential quantification can be performed by combining two negation beta nodes.   This represents the semantics of [[double negation]] (e.g., "If NOT NOT any matching WMEs, then...").   This is a common approach taken by several production systems.

=== Memory indexing ===
The Rete algorithm does not mandate any specific approach to indexing the working memory.   However, most modern production systems provide indexing mechanisms.   In some cases, only beta memories are indexed, whilst in others, indexing is used for both alpha and beta memories.   A good indexing strategy is a major factor in deciding the overall performance of a production system, especially when executing rule sets that result in highly combinatorial pattern matching (i.e., intensive use of beta join nodes), or, for some engines, when executing rules sets that perform a significant number of WME retractions during multiple match-resolve-act cycles.   Memories are often implemented using combinations of hash tables, and hash values are used to perform conditional joins on subsets of WME lists and WMEs, rather than on the entire contents of memories.   This, in turn, often significantly reduces the number of evaluations performed by the Rete network.

=== Removal of WMEs and WME lists ===
When a WME is retracted from working memory, it must be removed from every alpha memory in which it is stored.   In addition, WME lists that contain the WME must be removed from beta memories, and activated production instances for these WME lists must be de-activated and removed from the agenda.   Several implementation variations exist, including tree-based and rematch-based removal.   Memory indexing may be used in some cases to optimise removal.

=== Handling ORed conditions ===
When defining productions in a rule set, it is common to allow conditions to be grouped using an OR [[Logical connective|connective]]. In many production systems, this is handled by interpreting a single production containing multiple ORed patterns as the equivalent of multiple productions.   The resulting Rete network contains sets of terminal nodes which, together, represent single productions.   This approach disallows any form of short-circuiting of the ORed conditions.    It can also, in some cases, lead to duplicate production instances being activated on the agenda where the same set of WMEs match multiple internal productions.   Some engines provide agenda de-duplication in order to handle this issue.

=== Diagram ===
The following diagram illustrates the basic Rete topology, and shows the associations between different node types and memories.

[[Image:Rete.svg|thumb|500px|Illustrates the basic Rete.]]

* Most implementations use type nodes to perform the first level of selection on tuple working memory elements.   Type nodes can be considered as specialized select nodes.   They discriminate between different tuple relation types.
* The diagram does not illustrate the use of specialized nodes types such as negated conjunction nodes.   Some engines implement several different node specialisations in order to extend functionality and maximise optimisation.
* The diagram provides a logical view of the Rete.   Implementations may differ in physical detail.   In particular, the diagram shows dummy inputs providing right activations at the head of beta node branches.  Engines may implement other approaches, such as adapters that allow alpha memories to perform right activations directly.
* The diagram does not illustrate all node-sharing possibilities.

For a more detailed and complete description of the Rete algorithm, see chapter 2 of Production Matching for Large Learning Systems by Robert Doorenbos (see link below).