HierarchyID

SQL Server 2008 introduces the HIERARCHYID data type, which is designed to support storing and manipulating data representing a hierarchy. Examples of hierarchies that you might need to represent in a SQL Server database include employee organizational charts, folder lists, forum discussions, and so on. This article is the first in a two-part series about the new HIERARCHYID data type. This month I’ll introduce you to the new data type, and I’ll explain how to define and index the table that will hold the hierarchy data, how to insert new nodes into the table, and how to query the hierarchy. Next month I’ll explain how to handle changes in the hierarchy (e.g., reparenting nodes) and how to convert a traditional parent-child hierarchy (aka an adjacency list) to a representation with the new HIERARCHYID data type.

Creating and Populating the Hierarchy
The HIERARCHYID data type provides the means to store and manipulate data representing a hierarchy. HIERARCHYID is a system-supplied CLR type with a set of methods that allow manipulation of the type. The methods supported by the type include GetLevel, GetRoot, GetDescendant, ToString, Parse, IsDescendantOf, GetAncestor, GetReparentedValue, Read, and Write. I’ll describe some of the methods this month and some next month.

The type internally holds a binary value as large as 892 bytes that represents the path of ancestors leading to the current node. The value positions the current node among other nodes in the hierarchy—both in terms of parent-child positioning, and in terms of positioning among siblings. For example, if you use the HIERARCHYID data type to represent a hierarchy of employees, the value holds the path of all managers leading to the current node; the value represents the correct manager-subordinate relationships, and even the correct position among direct subordinates of the same manager, in case there’s a need for it.

The HIERARCHYID type provides topological sorting—a term taken from graph theory—meaning that the value of a node is greater than the values of all ancestors of the node and less than the values of all descendants of the node. The fact that the type provides topological sorting means that when sorting by HIERARCHYID values, a child would always appear in the output after the parent.

I’ll use a hierarchy of employees in my examples. Run the code in Web Listing 1 (www.sqlmag.com, InstantDoc ID 99036) to create the Employees table, as well as indexes on the table to support querying the hierarchy. The hid column in the Employees table (see Web Table 1) is of a HIERARCHYID data type, and it represents the position of the current employee in the hierarchy. Notice the computed persisted column called lvl that is defined by a call to the GetLevel method of the hid column. The GetLevel method returns the level of the node in the hierarchy, starting with 0 for the root, 1 for the direct subordinates of the root, and so on.

Besides creating the Employees table, Web Listing 1 also contains statements that create two indexes to support querying the hierarchy; the first is a unique clustered index created on the hid column and the second is a unique nonclustered index created on the lvl and hid columns. These indexes implement two indexing strategies called depth-first and breadth-first, respectively. The depth-first index organizes all members of a subtree (manager and all subordinates in all levels) close to each other; therefore it will support requests to return a whole subtree. This index will also support requests to sort the hierarchy by the hid column (in topological order). The breadth-first index organizes all members of the same level close to each other; therefore it will support requests for siblings from the same level (e.g., a request for all direct subordinates of a manager). Later in the article, I’ll demonstrate such requests and the way they are optimized.

To insert a new row into the Employees table representing a new employee in the hierarchy, you need to generate a HIERARCHYID value for the hid column. The value should represent the correct position of the employee in the hierarchy. You can use methods of the type to help in this task. For the root of the hierarchy—the big boss or the CEO—you can use the HIERARCHYID::GetRoot static method. This method simply produces a HIERARCHYID value that is internally an empty binary string representing the root of the tree. If the new node you are adding is not the root, you can produce the HIERARCHYID value for the new node by invoking the method GetDescendant on the hid value of the manager of the new node. This method accepts two HIERARCHYID inputs; I’ll call them @lft and @rgt. If both values are not NULL, the method produces a new value positioned between the two. If both are NULL, the method produces a value simply below the manager at hand. If @lft is not NULL and @rgt is NULL, the method produces a value greater than @lft. Finally, if @lft is NULL and @rgt is not NULL, the method produces a value smaller than @rgt.

Run the code in Web Listing 2 to create the usp_ AddEmp procedure that is in charge of adding a new node into the hierarchy. If the new employee is the root employee, the procedure uses the HIERARCHYID:: GetRoot static method to produce the HIERARCHYID value for the new employee. If the new employee is not the root, the procedure first obtains the hid value of the new employee’s manager, as well as the maximum hid value among the direct subordinates of that manager. The procedure then uses the GetDescendant method to produce the hid value of the new employee as the last node under the given manager.

To populate the Employees table with sample data, run the code in Web Listing 3. As long as the hierarchy doesn’t contain a large number of levels, the HIERARCHYID values are quite economical.

The HIERARCHYID data type also exposes a method called ToString that produces a canonical string representation of the hierarchical value as a path using a slash as a separator between levels. Unlike the raw binary representation of a HIERARCHYID value, the string representation produced by ToString is more meaningful to the naked eye. For example, the ToString method returns the string ‘/2/1/1/3/’ for the HIERARCHYID value 0x6AD6F0. You can easily see in the string representation of the value that the node is positioned at level 4, and that it’s the child of the parent node with the path ‘/2/1/1/’. To convert a given canonical string representation of a hierarchical value to HIERARCHYID, you can either use the static method HIERARCHYID::Parse, or simply use the CAST or CONVERT functions. For example, the expression CAST('/2/1/1/3/' AS HIERARCHYID) returns the HIERARCHYID value 0x6AD6F0.

To return the current contents of the Employees table, along with the logical string representations of the hid values, run the following query:

SELECT hid, hid.ToString() AS path, lvl, empid, empname,
  salary
FROM dbo.Employees
ORDER BY hid;

Querying the Hierarchy
Now that I’ve covered how to create and populate the hierarchy, I’ll explain how to query the hierarchy to answer common requests such as sorting the hierarchy, and returning a subtree, a path, direct subordinates, and so on.

Remember that earlier I mentioned that the HIERARCHYID type provides topological sorting. So if you want to sort the employees such that a subordinate will be returned after a manager, you can simply sort by the hid column. You can use the lvl column to produce indentation, replicate some string lvl times, and concatenate the employee name. The following query demonstrates both sorting topologically and producing indentation:

SELECT empid, REPLICATE(‘ | ‘, lvl) + empname AS emp
FROM dbo.Employees
ORDER BY hid;

Continue on Page 2

   Previous  [1]  2  Next