The RETE Algorithm
Rete is latin for "Net."
Rete was the first rule-handling algorithm to enable rule-based systems to deal efficiently with large numbers of rules. Dr. Charles L. Forgy, who is now the Chief Scientist at Production Systems Technology (www.pst.com) in Pittsburgh, PA, developed it at Carnegie-Mellon University. It has become the de facto industry standard, and it is used in many high performance rule-based systems.
Dr. Forgy, also developed the second generation algorithm called Rete II, which significantly enhanced the original Rete Algorithm. Rete II makes rule-based systems better able to deal with large amounts of data and with rapidly changing data.
Dr. Forgy’s original paper was published in Artificial Intelligence. The reference is:
Forgy, C., Rete: A Fast Algorithm for the Many Pattern/Many ObjectPattern Match Problem., Artificial Intelligence, 19, pp. 17-37. 1982.
Rete can be described as a compilation algorithm that transforms a rule set in a tree of interrelated nodes. The internal nodes represent tests appearing in the left hand sides (conditions) of the rules, and the leaves of the tree represent the right hand sides of the rules (actions.) Rete allows sharing tests among rules, and stores information about the object in memory that partially satisfies one or more rule conditions. Rete is used to implement event driven programming more than backward chaining, and is especially fast to react when new information is added to the network.
In this example of the Rete algorithm from ILOGs web site, it demonstrates how to keep track of objects that partially match the rules so that an agenda can be updated quickly.
(defrule StopHeating maximum ?r: (Reactor phase = Gathering) ?h: (HeatingSystem on = ?r) (Sensor on = ?h value > 180) -> (assert (Alarm on = ?r nature = StopHeating)) )
This rule says that for a reactor during the gathering phase (of the final product), if the heating system is on, and the temperature sensor shows a value above 180 degrees, an alarm will go off to stop the heating system. This rule is triggered on three objects: a reactor, a heating system and a sensor.
Whenever three objects satisfy the rule conditions, the rule is fired. For this rule, the Rete algorithm keeps the objects that partially match the rule conditions. The algorithm keeps all the pairs (Reactor, HeatingSystem) that meet the first two conditions. These pairs are waiting for the third condition to be satisfied in order to fire the rule. During the assertion or the modification of a sensor, this rule becomes firable. The assertion or modification of another object of another class does not trigger this rule.
There are a number of good articles on the web that describe the Rete Algorithm. Here are the links...
- http://www.informatik.fh-luebeck.de/~ki/Jess/docs/rete.html
- http://www.pst.com/rete.htm
- http://www.haley.com/3032762912377874/ReteAlgorithm.html
- http://www.haley.com/3032762912377874/ProductionSystems.html
- http://www.ilog.co.jp/html/products/infrastructure/rules_wp4.htm
If you’re using Rete for your Business Rule Application let us know, we can publish your story on the BRCommunity web site. Or if you know of some other web resources for the Rete algorithm drop me a line at: nfishman@brsolutions.com
# # #
Standard citation for this article:
About our Contributor:
Online Interactive Training Series
In response to a great many requests, Business Rule Solutions now offers at-a-distance learning options. No travel, no backlogs, no hassles. Same great instructors, but with schedules, content and pricing designed to meet the special needs of busy professionals.