The new HIERARCHYID data type has been introduced to SQL Server 2008 via a CLR UDT (Common Language Runtime User Defined Type), or in other words, the data type has been coded as a C# class using the .NET Framework and as such, it is possible to disassemble the class with the use of Lutz Roeder’s .NET Reflector (if that’s something that interests you), we will however not discuss nor examine the way in which the HIERARCHYID data type has been built as its far beyond the scope of this article. What we will examine however is how it functions and how we can leverage the power of hierarchal data within out tables.

What exactly is hierarchal data and why is it needed in a DBMS? Good questions, to answer the first question, hierarchal data is defined as a set of data items related to one another in a hierarchy, that is, a parent node has a child and so forth. An example of such a hierarchy could be an organizational structure in an organization, perhaps enterprise, military, etc. To answer the second question, hierarchal data is common in organizations and even file systems, consider that of your hard drive, the root of the hierarchy would be / (on a Unix plat form, or C:\ on Windows) and each folder would be a child of the root node, and each child of the root would have other children and so on and so forth thus building a hierarchy. The Windows Explorer is an example of displaying data in a hierarchal way.

Before we analyze the HIERARCHYID data type let us consider alternatives to the HIERARCHYID data type. Consider that we wish to represent the structure of an organization. Each employee will be associated with his or her supervisor and so forth up to the president of the organization who will have no supervisor thus the parent column for the president will be NULL. This sort of technique is considered to be a graph represented as an adjacency list or the parent/child approach. Refer to figure below for details on the organizational structure (represented as a tree).

Organizational Structure

Representing this structure in a table is quite easy, the table should consist of two important columns, employee ID and supervisor ID, as stated, all employees will be associated with his or her supervisor and so forth up to the president of the organization who will have no supervisor thus the supervisors ID column for the president will be NULL. While this is slightly early in the game for us to examine the CREATE TABLE T-SQL statement, consider the following code never the less.

CREATE TABLE EmployeesPC
([ID] INT PRIMARY KEY NOT NULL IDENTITY,
 Name VARCHAR(255) NOT NULL,
 Title VARCHAR(255) NOT NULL,
 HireDate DATE NOT NULL,
 SupervisorID INT FOREIGN KEY REFERENCES EmployeesPC(ID) NULL)

Notice that the SupervisorID column references the ID column of the same table, thus if we were to insert the organizations employees the content of the table would be as follows.

ID Name Title HireDate SupervisorID
1 Matthew Ellis President 2007-01-01 NULL
2 Danielle CFO 2008-01-10 1
3 Bill COO 2008-01-15 1
4 Kate Controller 2008-01-28 2

Notice that just as I’ve said, the SupervisorID column contains the ID of that employee’s supervisor. SQL Server 2008 however presents us with the new HIERARCHYID data type that can be used to represent such data in a hierarchal structure. The HIERARCHYID data type is optimized for representing trees, which are the most common type of hierarchal data. The HIERARCHYID data type should be used to represent the position in a hierarchy, that is, a column of type HIERARCHYID does not represent a tree itself, it simply represents the position within a defined tree of that row. In other words, as the database developer, the job of constructing the tree falls upon our shoulders.

Note

While this is beyond the scope of this article, for the sake of completeness, a tree is based upon a graph and a graph can simply be defined as a set of objects often named vertices or nodes and connected to each other by way of edges or links. There are many different types of graphs, undirected, directed, finite, linear, etc. A tree on the other hand is based upon a graph and also has several different notions; however the tree in particular I will discuss is that of the rooted tree. A rooted tree has a distinguishable node or vertex from the others, this is called the root of the tree. A child node is called an ancestor of its parent node, for example, given the rooted tree T with the root node bring r, and a child node x, then r is an ancestor of x and x is a descendant of r. Every node is both an ancestor and descendant of itself.

Consider the figure below which demonstrates a rooted tree. Also note that while graphs may have cycles (loops), a tree cannot. Every node of a tree is connected, no node sits by itself, as if a node did, it would no longer be considered a tree.

image

First and foremost, note that the tree structure is identical to that of any organizational structure or even file system structure. The root node in figure 2.6 is R and X and Y is an ancestor of R, while R is a descendant of X and Y and so forth.

For more details refer to the book Introduction to Algorithms, MIT Press (ISBN 9780262032933).

A column of HIERARCHYID has the following properties for representing hierarchal positions:

  • Very compact
  • depth-first compression
  • Support for arbitrary insertion and deletion

To better understand the properties in the above list, let’s briefly analyze each.

Very Compact

The HIERARCHYID data type, as again stated does not represent a hierarchy itself but rather represents the position within a hierarchy for any given node. The average bits required to represent a node within a tree is quite small, however depends on the average fan-out, that is, the average number of children for each node. For example, given the tree T, which has 100,000 nodes, with an average fan-out of 6, we can determine the size in bits required to represent the position of a node in the tree T with the following formula, 6*logAn. Where A is the average fan-out and n is the number of nodes, in this case 100,000, thus, log6(100000) = 66.42549 ~= 100,000 and finally, 6*6.42549 = 38.55. Rounded to 40 and that’s the number of bits required for storage.

Depth-first Compression

Depth-first order, as the name implies has to do with the way the nodes are ordered when indexed. Nodes close to each other in a depth-first traversal are placed near each other when indexed. To illustrate, given the structure of an organization, similar to that shown above, all employees who report to any given manager will have their records located near that of their managers when indexed. This is discussed in greater detail, as well as the other method of indexing HIERARCHYID data types – breadth-first in my book Microsoft SQL Server 2008 Beginners Roadmap (as of the date of this writing, it has not yet been released).

Support for Arbitrary Insertion and Deletion of Nodes

The HIERARCHYID data type also implements numerous methods which can be used to support the insertion and deletion of arbitrary nodes. For example, the GetDescendant() method can be invoked passing as arguments the children which you wish to place a new node between. That is, you it’s always possible to generate a sibling to the right of any given node, to the left of any given node, or between any two siblings.

Such capabilities are required in many hierarchal structures, for example, consider that of the organizational example previously used, if a new employee has been hired who is to report directly to Danielle then we must insert a new descendant of Danielle into the structure.

Making Use of HIERARCHYID

First and foremost, before we discuss the T-SQL code which can be used to insert, query and manage HIERARCHYID data type columns we should discuss how data is actually stored within the HIERARCHYID data type. Data stored within the HIERARCHYID column is stored in binary format and represents the physical location of that row within the hierarchy. For example, the root of the tree represented in hexadecimal is 0x, which when a table is queried the positions those rows represent within a hierarchy will be presented in hexadecimal unless otherwise indicated using the HIERARCHYID::ToString() method. The ToString() method will reveal the position within the hierarchy as a string representation and thus infinitely more readable, again, the root of a tree represented as a string would simply be ‘/’, while a child of the root would be ‘/1’, ‘/2’, etc. For example, if we were to analyze the organizational structure shown above again, we could represent each level as it would be represented by the HIERARCHYID data type. Refer to the figure below.

image

I think the idea is relatively basic to understand, each node is represented as its position within the structure and is built just as you would imagine any hierarchal structure, for example, consider a file system, the path to my documents can be represented in a manner exactly as that shown above – C:\Users\Matt\Documents. The path /1/1/2/ in the above figure represents a node; we can easily traverse the tree upwards until we find that nodes direct parent or even grandparent and so forth.

To begin understanding the strength and weaknesses exposed by the HIERARCHYID data type we’ll construct a table which contains a HIERARCHYID column that is to represent a position within a hierarchy for that row.

We’re going to construct a table that can be used to represent an organizational structure, to begin, define a table with a column of type HIERARCHYID. Refer to the listing below.

CREATE TABLE Employees
([ID] INT PRIMARY KEY NOT NULL IDENTITY,
 Name VARCHAR(255) NOT NULL,
 Title VARCHAR(255) NOT NULL,
 HireDate DATE NOT NULL,
 OrgLevel HIERARCHYID)

Lets focus on the column defined as HIERARCHYID. This column will represent the position of this row within a hierarchal structure, again as stated, the use of the HIERARCHYID data type does not automatically represent a tree structure, it simply represent the position within a tree, and its entirely up to us as the database/application developer to ensure that the position represented is actually that of a node in a tree. Again, I can’t iterate enough, just because a column has been defined as the HIERARCHYID data type does not mean you’ve built a hierarchy structure or a tree, it simply means that you’re making use of a data type optimized for representing a position within a tree, for example, the HIERARCHYID data type exposes many different methods which can be invoked to retrieve a list of ancestors and descendants as well as a means of traversing a tree.

Let’s begin by inserting the root of our node into the Employees table, the root should be the president of our organization and represented by a HIERARCHYID data type as the string literal ‘/’.

INSERT INTO Employees (Name, Title, HireDate, OrgLevel)
    VALUES ('Matthew Ellis', 
        'President', GETDATE(), HIERARCHYID::GetRoot())

Notice that we make use of the GetRoot() method exposed by the HIERARCHYID data type. This method, as the name suggests returns the root node of a hierarchy, as no other rows have been defined within the table, the root node is ‘/’, thus when interested into the table, the value stored within the OrgLevel column (which is of type HIERARCHYID) is the string literal ‘/’.

To model the hierarchal positions after that of the organizational structure that we’ve defined above we must now add the two direct subordinates to the president, that is, Danielle as CFO and Bill as the COO. You must remember that the HIERARCHYID data type will not ensure uniqueness, that is, there’s nothing stopping us from inserting a new row into the Employee table with the same position within the hierarchy as the president. The row is that of Danielle, the organizations CFO and should be beneath the president in the hierarchal structure of the organization. To solve such an issue we can ensure uniqueness by creating a constraint or forcing uniqueness in applications which make use of this database structure.

To insert a new row into the Employee table and define that new row as a descendant to the root node within the hierarchal structure we will make use of the GetDescendant() method. This method has following T-SQL prototype:

hierarchyid parent.GetDescendant ( child1 , child2 )

The return value is that of a HIERARCHYID object and represents the desired descendant node. The method is not static and should be invoked from the parents scope, that is, the node whose descendants you wish to retrieve. The parent object must be of type HIERARCHYID and can be retrieved in a number of different ways, which will examine in a moment. This method performs different actions based on the values of the child1 and child2 parameters, the table below examines the different behaviors based on the values of the child1 and child2 parameters.

Scenario Result
child1 and child2 are both NULL The result will be a child of the parent node. This behavior should be used when the first child of a parent is to be inserted into the hierarchal structure.
child1 is not NULL and child2 is NULL A child of the parent greater than that of child1 will be returned, that is, a sibling of child1 will be returned. For example, if child1 is /1/ in the hierarchal structure, the returned value will be /2/.
child1 is NULL and child2 is not NULL A child of the parent less than child2 will be returned. For example, if child2 is /1/ then the inserted sibling will be /0/, however a value cannot be less than 0, thus any calls made hereafter will result in /0/ being returned as well.
child1 and child2 are not NULL A child of the parent greater than child1 but less than child2 will be returned.

Using the above table as a reference, we know that we can insert our second node into the hierarchy; this node should be a child of the root, that is, the president. As we’re inserting a child of the root node we may make use of the GetRoot() method again to retrieve the root node from our hierarchy.

Note

A static instance as referred to with a programming language, in its simplest form as it relates to our needs, defines an instance of a method that may be invoked without a variable of that type first being declared and initialized. For example, refer to the above listing, we invoked the static instance of the GetRoot() method, that is, HIERARCHYID::GetRoot().

DECLARE @President HIERARCHYID
SELECT @Manager = HIERARCHYID::GetRoot() FROM Employees
INSERT INTO Employees (Name, Title, HireDate, OrgLevel)
    VALUES ('Danielle', 
        'CFO', GETDATE(), @President.GetDescendant(NULL, NULL))

Using the GetDescendant() method of the @President instance (that is, the root node) and specifying both arguments child1 and child2 as NULL the value for the first child of the root will be returned, that is, ‘/1/’. Again, as the HIERARCHYID data type does not guarantee uniqueness we may execute the above T-SQL code over and over again, resulting in numerous rows all indicating that their the direct descendant of the root node, not exactly producing a tree but more of a mess if you ask me. Great, what about inserting a sibling of Danielle into the hierarchy? Well, again, referring to the table above we can do so by invoking the GetDescendant() method again, this time however, passing an instance of the Danielle node (‘/1/’) as the value for the child1 argument, which leaves us with another question. How can we retrieve the value of the Danielle node? Actually a few ways, we can simply take for granted that this is the second descendant of the president, thus we know that the first descendant can be retrieved using GetDescendant() to retrieve the value of the first descendant and we base our insertion of the second descendant based on the value of the first, we can use the Parse() method to convert the canonical string representation of a HIERARCHYID to a HIERARCHYID object, that is, as we know that the first descendant is ‘/1/’ we can simply parse ‘/2/’ into a HIERARCHYID object. And, finally we may also use an aggregate function to retrieve the maximum value from the result set, the aggregate function in which I speak of is MAX and will return a single maximum value. For example, if we wanted to find the last child of a parent, that is, the child node that should be referenced in the GetDescendant() method we can use T-SQL code similar to that shown in the code listing below.

DECLARE @ParentNode HIERARCHYID
SELECT @ParentNode = HIERARCHYID::GetRoot() FROM Employees
SELECT MAX(OrgLevel.ToString()) FROM Employees
WHERE OrgLevel.GetAncestor(1) = @ParentNode

In the above listing we retrieve the last child node, that is, the maximum child of the parent, thus, from this information we know that the returned value from the above SELECT statement can be passed to the GetDescendant() method, thus inserting a sibling after (or before, depending on how you define the methods arguments).

To continue with our example above, we must insert the sibling of Danielle into the hierarchy, this can be done either by using what we know (we know Danielle’s position within the hierarchy is /1/), or a more modular solution would be that of the T-SQL code shown in listing above which makes use of the MAX aggregate function. Consider the listing below which inserts Bill, the COO after Danielle, the CFO.

-- Get the root node we wish to insert a descendant of
DECLARE @ParentNode HIERARCHYID
SELECT @ParentNode = HIERARCHYID::GetRoot() FROM Employees

-- Determine the last child position
DECLARE @LastChildPosition HIERARCHYID
SELECT @LastChildPosition = MAX(OrgLevel) FROM Employees
WHERE OrgLevel.GetAncestor(1) = @ParentNode

-- Insert Bill, the COO
INSERT INTO Employees (Name, Title, HireDate, OrgLevel)
    VALUES ('Bill', 
        'COO', GETDATE(), @ParentNode.GetDescendant(@LastChildPosition, NULL))

Ideally we’d construct a T-SQL stored procedure which would add a child node to the specified parent, for now however, we’ll not examine that. Let’s assume we’ve constructed the entire organizational hierarchy, the next obvious task would be to query the hierarchy for desired data.

Querying hierarchal data is actually very simple. Imagine that we wish to determine all employees who report directly to Bill, the COO. Such a task can be accomplished by utilizing the IsDescendant() method associated with the HIERARCHYID data type. The prototype is pretty simple and accepts a single argument, a node which the comparison should be made. The prototype is as follows.

bit parent.IsDescendant ( child )

As indicated, the return type is a BIT where 0 indicates false, that is the specified child is not a descendant of the parent and 1 indicates true, that the specified child is, in fact, a descendant of the parent. The IsDescendant() method is not a static method and thus must be invoked from an object of type HIERARCHYID, the parent. Refer to the listing below which can be used to list all employees who report directly to Bill, the organizations COO.

Note

Remember above I stated that all nodes are both ancestors and descendants of itself. Hence, Bill will also be displayed in the result set, not only the employees who report directly to him.

DECLARE @Bill HIERARCHYID
SELECT @Bill = OrgLevel FROM Employees WHERE Name = 'Bill'
SELECT * FROM Employees WHERE @Bill.IsDescendant(OrgLevel) = 1

Basically what we do is check each and every employee within the Employees table, if the return value of the IsDescendant() method equals 1, then that employee is, in fact, a descendant of Bill and will be included within the result set.

Conclusion

That's it for now, I think you'll find the HIERARCHYID data type quite flexible and useful for representing tree-based structures such as organizational units, file systems, etc.