The Rete algorithm works wonderfully in language systems such as Lisp where pertinent attributes about objects are directly asserted to the rules engine. In an object-oriented language, such as C++ or Java, and entire graph of objects can be reachable from a single named root object. Expressing highly complex relationships between entities using Cambridge-prefix notation may require many separate assertions. In an OO language, the single root object is all that should be asserted, since attributes and relationships can be extracted using normal language constructs.
Bob McWhirter of The Werken Company adapted Forgy's original Rete algorithm to object-oriented constructs, creating the Rete-OO algorithm. As with Rete, there are 1/1 nodes and 2/1 nodes. Unlike Rete, there are nodes that exist simply to extract reachable attributes and add columns to passing tuples. Rete always constructs the condition 1/1 nodes toward the root of the tree leaving the bottom portion to be comprised of purely aggregating 2/1 join nodes. Rete-OO must interleave both 1/1 and 2/1 nodes.
Tuple set #1:
| type | person | sister | cat | dog |
|---|---|---|---|---|
| person | rebecca | jeannie | zoomie | null |
| person | jeannie | rebecca | null | zoomie |
Tuple set #2:
| type | person | sister | cat | dog |
|---|---|---|---|---|
| person | rebecca | jeannie | zoomie | null |
| person | jeannie | rebecca | null | toby |
For the same Example Tuple Sets, as in Rete, the conditions could be expressed in terms of object-oriented language boolean and assignment expressions. The choice of Java as the expression language is purely arbitrary.
- (0) Person personOne, personTwo
- (1) personOne.hasSister(personTwo)
- (3) petName = personOne.getCat().getName()
- (3) petName = personTwo.getDog().getName()
Rete-OO adds the concept of root object declaration, where the root objects of the condition are declared with a name and type. The object's type maps directly to the tuple type in Rete. The root object name has no direct mapping in Rete and causes the addition of a parameter node in Rete-OO. Boolean expressions in Rete-OO conditions are equivalent to Rete's condition patterns against attributes. The assignment expressions map to place-holder variables in Forgy's algorithm.
The types of nodes used in Rete-OO graph construction are listed here. Those that are new or different from Rete are denoted with a '*'.
- Object type
- Object type nodes differentiate objects by filtering on their defined type.
- Parameter*
- Parameter nodes create a tuple with a single entry binding the object to the name.
- Condition
- Condition nodes simply tests a tuple against an a boolean expression.
- Extraction*
- Extraction nodes extract new attributes, create new columns on tuples, and store the results.
- Join
- Join nodes connect the output arcs from two other nodes and allows consistent tuples to be merged and passed through.
- Terminal
- Terminal nodes fire to indicate a successful match for the rule.
The resulting Rete-OO graph is constructed in a different manner than the equivalent Rete graph, due to the addition and rearrangement of some nodes.
