Recursive Hierarchies And Bridge Tables

This post introduces the hierarchy bridge table, which can be used to navigate recursive hierarchies.

High Trestle Bridge at Night
Photo (c) Carol Bodensteiner

Bridge tables are a popular topic among readers of this blog. Perhaps that's because they can be a bit confusing, yet also enable powerful analysis.

Previously, I've focused on the two simplest uses for bridge tables:  the attribute bridge and the dimension bridge.  See links at the end of this post for more on these.

In this post, I'll tackle a third and final use: how a bridge can aid in the navigation of a recursive hierarchy.

Recursive relationships

In the real world, recursive relationships are common. Employees report to other employees, parts are made of other parts, and so forth.

In an E-R model, a recursive relationship might look like this:

Companies may own other companies.  That dotted relationship line is sometimes called a "pigs ear."  It links each company to the company that owns it.

You can read this relationship in two directions:  each company may have a parent company; each company may be the parent of one or more companies.

Looking up and looking down

From a business perspective, this information may be very useful.  For example, suppose you work for a business whose sells things to companies. You would like to be able to answer questions like these:

1. What are January order dollars from to Company XYZ and its subsidiaries?
2. Show me January orders from Company ABC and any companies above it.

The first question "looks down" from company XYZ.  The second question "looks up" from company ABC.

In both cases, we want to use the hierarchy to aggregate details about orders.

The hierarchy bridge

In a dimensional model, the idea is to support the study of facts (such as "order dollars") in the context of this hierarchy. This can be done using a bridge table, as shown here:

The table in the center is a hierarchy bridge.  This kind of table can be a bit confusing.  First, consider its content.

Each row contains a pair of company keys.  Here are the rules for populating the bridge table:

1. For each company, the bridge contains rows associating it with each of its subordinates.
2. Each company also has 1 row associating it with itself.

With respect to item 1, note each company is linked to all subordinates, not just the direct ones. (That's why the keys have the prefixes "superior" and "subordinate" rather than "parent" and "child".)

Using the bridge

In the picture above, notice that the fact table contains a company_key.  This represents the company from which each order is taken.  

Normally, we would join it to the company table to study "orders by company."

In this case, however, the bridge is inserted between the fact table and the company table. The bridge acts like a multiplexer--linking each company (on the right) to transactions with any and all of its subordinates (on the left).

This allows us to select a single company on the right (say Company XYZ) and aggregate all orders at or beneath that company.  That's called "looking down." It lets us answer question 1.

We can also use this hierarchy to "look up," as in question 2.  We simply reverse the joins--link company to the subordinate key, and the superior key to the fact table.  Then we can select a single company (say Company ABC) and look upward.

Powerful but dangerous

Of course, the danger of the bridge table should be readily apparent.  As you can see from the diagram above, if we forget to select a single parent company, we can easily double count the orders, triple count them, or worse.

For this reason, writing queries that involve the hierarchy must be governed carefully.  Developers or users with little experience can study the facts without using the bridge.  This will be safe, but they will not be able to leverage the hierarchy.

Other kinds of bridge tables

The hierarchy bridge described in this post is one of three kinds of bridge tables.  I've written previously about the other two kinds:

• Resolve Repeating Attributes With a Bridge Table (1/28/11) shows how a bridge can support a repeating attribute, such as a product that has multiple colors or a company that has multiple industry classifications.

• Bridge To Multi-Valued Dimensions (2/9/2011) shows how a bridge can link a single fact to multiple rows in a dimension.  Examples include orders with multiple salespeople, claims with multiple parties, etc.

More on the hierarchy bridge

When it comes to recursive hierarchies, this post only scratches the surface.  If you have questions, send them in.

In the mean time, there's a whole chapter on this topic in my book, Star Schema: The Complete Reference.  That would be Chapter 10:  "Recursive Hierarchies and Bridges." It's a long chapter--the longest one in the book.

And don't forget, when you use the links on this page to buy it from Amazon, you are helping to support this blog.

Photo credit: High Trestle Bridge at Night

Copyright (c) Carol Bodensteiner

Used by permission, with many thanks!