Modeling Hierarchies

The Dogma

Storing hierarchical data in a relational database seems to be a common problem.

Although much has been written on the topic, the technique I am describing here is not widely known. It seems most authors have accepted the basic recursive pointer model, shown in Figure 1 as optimal.

Figure 1. Solution with a recursive pointer

Some authors, such as Martin Fowler or David C. Hay improved this model in various ways. For example, they separate the structure from the data as shown in Figure 2. They go as far as introducing knowledge level to the model.

But as analysts they seem more interested in dealing with the trivial and achieving theoretical beauty of the model rather then proposing its optimal physical implementation.

Figure 2. Separating the structure from the data

Others, such as Ken Henderson, the author of the Guru's Guide to Transact SQL don't question the model - instead, they emphasize on techniques to work with it.

The Real Life Problem

That was not what I needed to solve my problem. I was developing a data exchange kernel.

Each data exchange logged hundreds of events. Classical logging with a flat table was not appropriate. Not only were there too many events but also they were on different level of abstraction.

For example when the order confirmation identifier could not be matched to the original order this was a business logic error. But when the recipient’s public key could not be found this was purely technical problem.

In addition, on a daily basis many data exchanges with different customers occurred. Having them all in one log would not provide a localized chronological overview.

Even advanced filtering would not be sufficient to make flat log user friendly in this situation.

Therefore I decided to implement hierarchical logging. Each data exchange invocation would be logged as single entry on the top level. When you would expand it, you could explore the details. You could then drill-down to get even more detailed logging information.

To highlight usability again, the user would not be happy if he had to drill-down entire tree to find out if an error occurred.

Thus errors had to be propagated from lower levels to higher levels. When data exchange had an error or a warning on the lowest level (but the error caused parent operation to fail and transaction to rollback!), the parent icon in the tree control indicated that children have errors, etc.

So on the top level you could see which data exchanges were successful and which failed. For effective troubleshooting you could then drill-down the hierarchy to locate the cause of an error.

A search option was also required. When performed on top it needed to search top level and all child levels, but only in given sub-tree.

If classic recursive pointer model (or its mutation) would be used then all these requirements would result in expensive and complex queries with self-joins and perhaps temporary tables to retrieve the data.

The Solution

To enable execution of these operations with single joins the data model was extended as shown in Figure 3. 

Figure 3. Introducing Depth field

With it I introduce redundancy to the model. For each parent I store all of its children (and grand children) with appropriate depth for each child. Figure 4 shows how I store sample hierarchy to my table.

Figure 4. Storing hierarchical data with depth

One might ask about the combinatorial explosion? When we store all children for each parent, surely we introduce a lot of overhead?

We do introduce some overhead, but the database does not grow exponentially. For each child we simply have to store all the parent relationships. That means that for each record on the 5^th level, we need 4 entries in the Structure table. No more. And how many levels can you have in a tree control while still letting the user feel in control?

Benefits

Following are samples of how you may leverage the new structure. In samples, I will use very simple SQL (no INNER JOIN, etc.) to show that with the new structure it is possible to work effectively even with simple SQL server engines.

I will use T-SQL to increase the clarity and readability of code, when necessary.

Get Root Nodes

To get the root node simply find all nodes that do not have any entries in the structure table acting as children.

SELECT *
FROM [table]
WHERE NOT EXISTS
  (SELECT * FROM structure WHERE structure.childId=[table].keyid)

Implementing Search

You would like to make a search for certain data throughout hierarchy starting with (but not including) parent. Here is how you can do it.

DECLARE @parent_node int
SET @parent_node=1
DECLARE @searched_data varchar(2)
SET @searched_data='e'
SELECT *
FROM [table],structure
WHERE
  [table].Data=@searched_data AND
  [table].KeyId=structure.ChildId AND
  structure.ParentId=@parent_node

Implementing Propagation

Suppose you would like to implement propagation. In my description of the hierarchical log I mentioned that all errors are propagated from lower levels to higher levels.

Following sample demonstrates similar problem. Instead of checking if given parent has children with errors it checks if given parent has children that contain certain sub-string. It returns a number > 0 if it yes and 0 if no.

DECLARE @parent_node int
SET @parent_node=2
DECLARE @searched_data varchar(2)
SET @searched_data='e'
SELECT COUNT(*)
FROM [table],structure
WHERE
  [table].Data=@searched_data AND
  [table].KeyId=structure.ChildId AND
  structure.ParentId=@parent_node

Summary

I needed a solution for real life problem, but was unable to find it in the existing engineering arsenal.

Describe model is not an optimal solution for all cases, but in my case the new structure offered so many benefits over the classic model, that the price of overhead is reasonable.

Here are some other cases, where the model will work for you:

• When you need to execute joins with entire sub-trees,
• When you need to perform an operation on a sub-tree, for example, calculate the bill of material, and
• When you need to propagate data downward from the parent to the children or upwards from the children to the parents.

I do hope you find it as helpful as I did. :-)