The RETE Algorithm

Neal A.  Fishman
Neal A. Fishman Enterprise Architect, Equifax Read Author Bio || Read All Articles by Neal A. Fishman

 

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...

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:


citations icon
Neal A. Fishman , "The RETE Algorithm" Business Rules Journal Vol. 1, No. 10, (Oct. 2000)
URL: http://www.brcommunity.com/a2000/b042.html

About our Contributor:


Neal  A. Fishman
Neal A. Fishman Enterprise Architect, Equifax

Neal A. Fishman is an Enterprise Architect with Equifax. He has 20 years of experience in Data Processing. He is heavily involved in the architecture, design, and performance tuning of databases in multi-tier heterogeneous web, client/server, data sharing and data warehousing environments.

He serves as a member of the Business Rules Group, and is a former member of the IEEE IDEF1X (IDEFobject) Standards Committee. He is an ExperNet expert for Giga and a Practicing Member of the World Wide Institute of Software Architects. He is certified by IBM as a developer and DBA in DB2 UDB, and is
currently a board member of the Atlanta Chapter of DAMA.

He has delivered presentations in North America, Australia, and Europe. He has been published in Database Programming & Design, SQL Server Professional, DM Review magazine, and The DataToKnowledge Newsletter. He serves as Technology Review Editor for BRCommunity.com.

Read All Articles by Neal A. Fishman
Subscribe to the eBRJ Newsletter
In The Spotlight
 Ronald G. Ross
 Jim  Sinur

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.