Hierarchical Data in SQL Server

What is Hierarchical Data?

Let's try and understand the concept of Hierarchical Data first. Very simply put, when data is organized in a tree like structure it is called hierarchical data. The hierarchical data structure works in a parent/child relationship where each parent can have multiple child whilst a child can have only one parent. Examples are umpteen in the real world. One of the most commonly stated examples is one that of organization hierarchies in a company, where the senior-subordinate relationship is often shown visually in a tree like structure called organization chart.

Just like a family tree, you have the option to call Test Lead an ancestor (or parent) of Tester, and conversely, you may call a Tester a descendant (or child) of the Test Lead. Each such data structure has one top level parent node, often called root node. The root node doesn’t have any parent but it may have one or more children. Each of the intermediate child nodes may have zero or more children, thus they may become parent nodes to its children. At the Leaf level, the nodes do not have any children. Other than the facts that root node doesn’t have a parent node and the leaf nodes do not have child nodes, all the nodes are functionally same, especially when we say that no node can exist in isolation. Well, in some out-of-the-world scenario, we can actually have a root node without any children, but I would hate to call it a tree – a seed would perhaps be a better choice!

Nested Set Model

As I was going to St Ives
I met a man with seven wives
Each wife had seven sacks
Each sack had seven cats
Each cat had seven kits
Kits, cats, sacks, wives
How many were going to St Ives?

No prizes for guessing the answer! Anyone with the mathematical knowledge of Standard III and with a bit of patience can come up with the correct answer in the first try (Not really! There is more to it than some mere calculations. And the whole thing dates back to thousands of years ago. That's a story I'll cover in some other blog - promise!).

This rhyme is considered to be created or gained popularity around 1730 in England. Even though there are more than one place called St. Ives in England, the one mentioned in the rhyme could most probably be St. Ives, Oxfordshire, as this place grew as a prominent market place in the last 1000 years of its history and therefore it makes sense that several people or groups go to that same place in the same day.

Back to the problem. If you try a little, you wouldn't have any problem creating organisation charts like above for this rhyme. You may make the "a man" as the root node, followed by seven intermediate nodes (wives), each wife-node having seven child nodes (sacks) and so on. However, it is also possible to represent the situation in terms of Set Theory. Instead of going into too much of jargons as I find them too much antediluvian way of making a point, let's try and draw a Venn diagram:

In the above nested set representation, the man contains seven wives, each wife contains seven sacks, each sack contains seven cats etc. I didn't draw the whole of the solution because I didn't want to give away the answer :) If you look at it closely, you will notice that either way you look at it (organization chart or nested set diagram), the data itself is hierarchical in nature with that 0-to-Many concept - a parent may have zero or more child and a child must have one and only one parent. Thinking in these lines, you will find that such hierarchical data abounds in our daily life: catalogues in book or movie libraries, departments in an organization, product categories in a departmental store and almost every other taxonomical entities.

Now that we made some progress in understanding what Hierarchical Data is, in my next posts I will discuss different ways of implementing such data structure in databases and how each one fares against the other. Adieu.