Hierarchical Data Part 3: Displaying the Tree

At the end of the previous post, I showed the results of a query displaying an organisational hierarchy in tree form.

This post covers the query that was used to produce that.

To make it easier to see how the query works, I’ll include a few extra columns in the output.

There are three main aspects of the query which are critical to making the output look how it should.

  1. Most obvious is the indenting of child nodes to place them subordinate to their parent node.
  2. Most important, is the sort order of the entire query. We need to ensure that the child nodes appear below their immediate parent, separated from it only by other nodes at the same tree depth or child nodes of the nodes which are at the same depth.
  3. The sort order within each group of child nodes that share the same parent node. We need a descending row number within each group so that we can draw the corner └─ piece, rather than continuing the vertical line downwards.

One further aspect of the indenting is that by using the REPLICATE function, we can easily control the overall indenting depth using a variable (or parameter to a function).

For the overall sort order, the query uses what is known as a materialised path. A materialised path may take slightly different forms depending on the purpose for which it is needed, but the basic idea is to store information with each item which contains the full path to that node in the tree.

A materialised path containing the unique id of all the ancestor nodes (frequently stored as a delimited string) is a common method used to eliminate the need for a recursive query in order to access information from ancestor nodes.

In our case, rather than storing a path of ancestor node ids, the nodes are being assigned a sort order within the group of all sibling nodes (i.e. nodes that share the same parent), and that sort order is appended to at each level in order to produce a value that uniquely identifies each node’s position. This single column can then be used to sort the entire query output ensuring that all nodes are positioned correctly.

The query casts the values to the VARBINARY type before concatenating them, which eliminates the need for string separators or padding that would otherwise be needed with a string data-type.

Here is the full query (including output of the additional columns):

The output, with the extra columns, is below.
The descending sort order within each group (InverseSortOrder) is used in combination with the recursion depth (Level) to “draw” the tree connecting all the nodes.

* The names that appear in this data were generated randomly by computer code using separate lists of possible of forenames and surnames.

This is part of a series of posts focusing on various aspects of working with hierarchical data in SQL. You can find a list of the other posts in the series here.

Leave a Reply