Click here to Skip to main content
15,860,861 members
Articles / Database Development / SQL Server

Modeling Hierarchies

Rate me:
Please Sign up or sign in to vote.
4.95/5 (10 votes)
17 Aug 2002MIT5 min read 106K   67   11
A solution to the problem of storing hierarchical data in a relational database

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

Table

Key

Data

1

a

2

b

3

c

4

d

5

e

6

f

 

Structure

ParentKey

ChildKey

Depth

1

2

1

1

3

1

1

4

2

1

5

3

1

6

1

3

4

1

3

5

2

4

5

1

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

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

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

SQL
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. :-)

History

  • 18th August, 2002: Initial version

License

This article, along with any associated source code and files, is licensed under The MIT License


Written By
Founder Wischner Ltd
United Kingdom United Kingdom
Writing code since 1982 and still enjoying it.

Comments and Discussions

 
GeneralOr you can just use a single column and Binary Trees... Pin
adamfowleruk12-Jan-09 23:42
adamfowleruk12-Jan-09 23:42 
GeneralHierarchical Database Pin
manojmmj29-Jun-05 1:32
manojmmj29-Jun-05 1:32 
QuestionHave you seen the modified preorder alternative? Pin
dross128-Jul-03 9:10
dross128-Jul-03 9:10 
GeneralMaintenance Issues Pin
Brett Smith10-Jun-03 1:28
Brett Smith10-Jun-03 1:28 
GeneralRe: Maintenance Issues - Not as bad as it seems. Pin
James Simpson21-Dec-04 4:55
James Simpson21-Dec-04 4:55 
Great article, very well explained ( I was actually going to write on the same subject )

This is still a recursive model. A hierarchy is a hierarchy and is recursive, the method mentioned above is a different approach to representing the same type of data.

You don't loose much overhead if you implement both parent/child and the sequence table. but what you do gain is the ability to find leaf nodes, find all the children, siblings etc...

To maintain the sequence table a couple of triggers on the hierarchy table can help that:

Append leaf node needs to generate its sequence records (one for each level)

Delete Node needs to remove each sequence record associated with itself.

Move Node is a bit trickier, you will need to update the sequence for each node and its child node.

A Well indexed table and a couple of good triggers makes this a very strong method for working with hierarchy data.

Just my two cents.

James

James Simpson
Web Developer
imebgo@hotmail.com

P S - This is what part of the alphabet would look like if Q and R were eliminated
Mitch Hedberg

Generalwonderful! Pin
bluesoul22-Aug-02 23:20
bluesoul22-Aug-02 23:20 
GeneralAn Interesting Approach Pin
Marc Clifton18-Aug-02 4:00
mvaMarc Clifton18-Aug-02 4:00 
GeneralRe: An Interesting Approach Pin
wayward18-Aug-02 6:37
wayward18-Aug-02 6:37 
GeneralRe: An Interesting Approach Pin
Tomaž Štih19-Aug-02 2:01
Tomaž Štih19-Aug-02 2:01 
GeneralRe: An Interesting Approach Pin
Martinac22-Aug-02 0:05
Martinac22-Aug-02 0:05 
GeneralRe: An Interesting Approach Pin
Marc Clifton25-Aug-02 12:09
mvaMarc Clifton25-Aug-02 12:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.