How the Rete Algorithm Works

Rete Algorithm Demystified: Part 2

In part 1 of this blog series, I covered the Rete Algorithm origin and its name. Now as promised, I am going to explain how it works. The Rete Algorithm is one of several decision engine algorithms used in modern rule engines such as Sparkling Logic SMARTS™. See our recent blog post on Decision Engine Performance to learn more about decision performance and the decision engines that drive today’s automated decisions. Explaining how the Rete algorithm works can get technical, so I’ll do my best to keep things simple yet interesting enough for the techies. I hope I will reach that goal. And without further ado, let me introduce the Rete algorithm!

The Big Idea

Traditionally, before the Rete algorithm and its derivatives existed, you had to check each rule statement against each object (or fact) to see if it should fire before moving to the next rule statement. In order to cut time, you would need to order and nest the IF-THEN-ELSE rule statements efficiently. When you think about it, you’re trying to create the leanest decision tree possible in code form. Fortunately, systems have become much more sophisticated. Most BRMS products enable you to manage the rules independently of each other while providing a sequential deployment option that takes care of optimizing the generated spaghetti code.

However, this “sequential” approach breaks down (mostly in terms of performance) when rules are dependent on the outcomes of other rules. These type of rules are called inference rules. When you get to an inference rule, you would essentially have to restart the evaluation process. And, depending how you prioritized the rules, you may have to run the same check multiple times. In other words, assessing large volumes of business rules with multiple dependencies is very time-consuming. To solve this problem, Dr. Charles Forgy came up with a brilliant idea: decouple rule evaluation from execution sequencing. Let’s explore how.

Airline Example

For illustration, I’ll use a simple set of rules that we are mostly familiar with: calculating airline rewards. Members can redeem miles for flight upgrades, hotel or rental car discounts, gift cards, etc. I will leave it up to the creative minds of the airline marketers to come up with them. The below decision service is responsible for processing a member’s activity:

1. IF reward miles for last year OR current year > 25k and <= 100k, THEN status = Silver.
2. IF reward miles for last year OR current year > 100k, THEN status = Gold.
3. IF flight miles < 500, THEN reward 500 miles.
4. IF flight miles >= 500, THEN reward flight miles.
5. IF category is business OR first (class), THEN reward 50% bonus miles.
6. IF status is Silver AND airline is not partner, THEN reward 20% bonus miles.
7. IF status is Gold AND airline is not partner, THEN reward 100% bonus miles.
8. IF member signed up for 3-flights-for-5k-in-March AND number of return flights in March 2011 >= 3, THEN reward 5k additional miles.
9. IF status becomes Gold, THEN reward 8 upgrade certificates.

While this example does not use a lot of inferences, I’ve included enough to illustrate my point. Let’s say a member starts out with 99k miles and goes on a business class 750-mile flight. If you run the rules through a sequential rules engine, he would be start out as Silver (based on rule #1). Then, he would receive 750 miles for the flight (rule #4) and then another 375 miles for flying business class (rule #5). But that would put him over 100k miles, which makes rule #1 no longer applicable to him. Therefore, you would need to start over from the beginning. With 100,125 points, he’s now Gold (based on rule #2). Then, he would receive another 750 bonus miles for being Gold (rule #7) and receive 8 upgrade certificates (rule #9).

The Rete Network is the Heart of the Rete Algorithm

However, if you run the rules through an inference rules engine (based on the Rete algorithm), the engine will assess all the applicable rules, fire the first applicable rule, propagate the changes, and fire again. It works by reconstructing the rules as a Rete network, a map of nodes and connections that indicate which objects (or facts) satisfy which condition and what action to take. Note, the original Rete algorithm worked with facts, but since all commercial engines have evolved to be object-oriented, I will use objects in my illustration. The Rete network is only constructed once, when you initiate a rules service. Once constructed, it is shared across all invocations.

Constructing the Rete Network: Classes

The first part of the Rete network is a discrimination tree. The alpha nodes contain the classes (in the object-oriented sense). Using our airline example, the classes would be the Account (of the member) and the Flight (that the member most recently took). So, I’ve created 2 alpha nodes, one for Account and one for Flight.

Constructing the Rete Network: Objects

Discrimination happens by adding each object as an individual node connected to the alpha node or another parent node. Objects related to Account and Flight would include the following:

• Account
  • status is Gold
  • status is Silver
  • reward miles for last year or current year > 25k and <= 100k
  • reward miles for last year or current year > 100k
  • signed up for “3-flights-for-5k-in-March” promotion
    • number of flights in March >= 3
• Flight
  • miles >= 500
  • miles < 500
  • airline is not a partner
  • airline is a partner
  • category is business
  • category is first

Note, I did not include all the objects but you should get the gist. Each path from top to bottom represents a complete set of conditions THAT APPLY TO A GIVEN CLASS OF OBJECTS.

Constructing the Rete Network: Joints

Next, you would add any connections across classes. For example, rule #6 connects Gold status with a non-partner flight and rule #7 connects Silver status with a non-partner flight. We call these connections “joints” as conditions from each branch will need to be verified. As a side note, you should start to see why combining many objects into a single rule will hurt performance. The more you can discriminate in the beginning, the faster your performance.

Constructing the Rete Network: All Paths Lead to Actions

The path eventually ends with the action part of the rules. The content of the actions is irrelevant for the Rete network. In fact, you could label each action by the rule name (for clarity, I displayed the actual actions). Now you can reconstitute every rule by following every path. Note, every connection between nodes is an “AND” statement. ORs are typically not natively supported. So if you add a rule that offers the same 15% bonus to Silver or Gold members traveling to Hawaii, you can achieve “OR” by connecting both Gold and Silver nodes to that promotion node. In essence, you’re “duplicating” the rules by dividing that rule into 2 separate rules, one for Silver members and another for Gold.

Fortunately this kind of duplication doesn’t really impact performance or maintenance as the Rete algorithm handles duplication efficiently. In addition, when you add this new Hawaii promo, you do not need to create (or duplicate) the Silver status or Gold status nodes. That check is already there and can be reused, regardless the order in which the rules execute. This reuse leads to significant time savings the more promos you add (the number of rules increase).

Real-Time vs Batch Processing

Now let’s look at what happens at runtime when you invoke that rules service with customer data. Your system design will dictate how you process your transactions. Real-time processing occurs when you run your rules on-demand, one transaction at a time. Batch processing occurs when your run your rules on many transactions at once, typically at night through a mainframe. Many organizations have separate systems so that they can do both. For example, an insurer could have one system to process applications from their self-service website in real-time. Then, the insurer could have another system to process applications from their brokers in batch once a day.

Rete Cycle: Evaluate

For our illustration, let’s assume that we process transactions in real-time. After the Rete network has been constructed, the inference rules engine will go through the evaluation phase. Here, customer data (facts) propagates or travels through the Rete network to determine which rules apply to that customer (where all conditions are satisfied). So, let’s say Joe is a rewards member of this particular airline. He already has 150k reward miles. He takes an economy flight from DC (IAD) to San Francisco (SFO). Total flight is 2,419 miles.

How many rewards miles will he get? When the Account alpha node references Joe, he meets the “>100k” condition. Therefore, he is Gold status. Rule #2 (from my original list of rules above) applies to him. When the Flight alpha node references IAD-SFO, that flight meet the “>= 500 mi” condition. Therefore, he will earn total flight miles. Rule #4 also applies to him. We’re going to assume that the rules service does not store member status but instead calculates it when invoked. Therefore, at this time, his status is unknown. So while the flight also meets the “not partner” condition, we do not meet the other condition in the joint. After evaluation, we know 2 rules are satisfied.

Rete Cycle: Execute

Next, the inference rules engine goes through the execution phase. The 2 satisfied rules are now “active” in the agenda. The agenda contains the list of all rules that should execute, along with the list of objects that are responsible for the conditions to be true. The engine will sort the agenda according to priority (and other conflict resolution methods). If the execution on one rule invalidates another with a lower priority, then the latter will not execute. Therefore, just because a rule is in the agenda doesn’t necessarily mean that it will execute. Remember from the beginning of this post, a member starts out at Silver status (with 99k miles), but becomes Gold status after he receives his flight miles. Without prioritization, both the Silver and Gold bonus rules would apply to him.

Side note: Priorities are a touchy subject in the Rules community as some purists are set against using them. Fortunately in our example, order doesn’t matter. Let’s assume the flight miles reward runs first: He will earn 2,419 miles.

Rete Cycle: Re-Evaluate & Execute

After execution of this first rule, facts are repropagated and re-evaluated. His account changes from 150k to 152,419 miles. Since no information related to Flight has changed, none of the Flight paths need to be re-evaluated. However, there has been an Account change so the Account paths need to be re-evaluated. After re-evaluation, the same Gold status rule still applies. This rule remains active in the agenda as is ready to be executed: Joe’s status is Gold.

Now after execution of this second rule, facts are repropagated. Now that his status is known, he meets the “Gold status” condition. This completes the joint with “not partner” condition which means a new rules applies to him: “+100% bonus miles.” This new rule is added to the agenda and executes: Joe earns an additional 2,419 miles. In the end, he receives 4,839 miles, bringing his account to 154,839 miles.

Reuse in Subsequent Cycles

As mentioned earlier, the Rete network will reuse the same nodes as much as possible as you add more rules. Imagine trying to replicate this by hand (manual code). Coding the joints alone turns it into spaghetti that’s a nightmare to debug and maintain. The algorithm takes care of all this. The performance gains from reusing conditions in both evaluation and execution more than compensates for the initial overhead of constructing the Rete network.

Conclusion

In my opinion, the Rete algorithm is second to none. Charles developed an algorithmic solution that properly enforces many rules in an uncertain order. In other words, his approach assesses very large volumes of rules in a short amount of time. Even so, Non-Rete vendors and critics have used the term “Rete Wall” to warn about the potential performance limits of the Rete algorithm. However, Charles has responded with higher performing versions to address their concerns: Rete II, Rete III and lately Rete-NT.

At the end of the day, the Rete algorithm is much faster than any other algorithm when rules need to be executed repeatedly on a given data set. It’s no wonder we haven’t seen a new break-through algorithm since Rete. It reminds me of sharks. Back in my life science days, I remember learning that sharks have not evolved at all in a very long time because they’re essentially kings of the ocean and perfectly adapted to their environment.