• Article

Working with hierarchyid Data

This topic includes information about common activities in managing and querying a hierarchical data tree.

In this Topic

Managing a Tree Using hierarchyid

Enforcing a tree

Example Using CLR

Moving Subtrees

Managing a Tree Using hierarchyid

Although a hierarchyid column does not necessarily represent a tree, an application can easily ensure that it does.

  • When generating new values, do one of the following:

    • Keep track of the last child number in the parent row.

    • Compute the last child. Doing this efficiently requires a breadth-first index.

  • Enforce uniqueness by creating a unique index on the column, perhaps as part of a clustering key. To ensure unique values are inserted, do one of the following:

    • Determining the uniqueness of each new child node and insert it, in a serializable transaction.

    • Detect unique key violation failures and retry.

Example Using Error Detection

In the following example, the sample code computes the new child EmployeeId value, and then detects any key violation and returns to INS_EMP marker to recompute the EmployeeId value for the new row:

USE AdventureWorks2008R2;
GO

CREATE TABLE Org_T1
   (
    EmployeeId hierarchyid PRIMARY KEY,
    OrgLevel AS EmployeeId.GetLevel(),
    EmployeeName nvarchar(50) 
   ) ;
GO

CREATE INDEX Org_BreadthFirst ON Org_T1(OrgLevel, EmployeeId)
GO

CREATE PROCEDURE AddEmp(@mgrid hierarchyid, @EmpName nvarchar(50) ) 
AS
BEGIN
    DECLARE @last_child hierarchyid
INS_EMP: 
    SELECT @last_child = MAX(EmployeeId) FROM Org_T1 
    WHERE EmployeeId.GetAncestor(1) = @mgrid
INSERT Org_T1 (EmployeeId, EmployeeName)
SELECT @mgrid.GetDescendant(@last_child, NULL), @EmpName 
-- On error, return to INS_EMP to recompute @last_child
IF @@error <> 0 GOTO INS_EMP 
END ;
GO

Example Using a Serializable Transaction

The Org_BreadthFirst index insures determining @last_child is a range seek. In addition to other error cases an application might want to check, a duplicate key violation after the insert indicates an attempt to add multiple employees with the same id, and therefore @last_child must be recomputed. The following code uses a serializable transaction and a breadth-first index to compute the new node value:

CREATE TABLE Org_T2
    (
    EmployeeId hierarchyid PRIMARY KEY,
    LastChild hierarchyid, 
    EmployeeName nvarchar(50) 
    ) ;
GO

CREATE PROCEDURE AddEmp(@mgrid hierarchyid, @EmpName nvarchar(50)) 
AS
BEGIN
DECLARE @last_child hierarchyid
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
BEGIN TRANSACTION 

UPDATE Org_T2 
SET @last_child = LastChild = EmployeeId.GetDescendant(LastChild,NULL)
WHERE EmployeeId = @mgrid
INSERT Org_T2 (EmployeeId, EmployeeName) 
    VALUES(@last_child, @EmpName)
COMMIT
END ;

The following code populates the table with three rows and returns the results:

INSERT Org_T2 (EmployeeId, EmployeeName) 
    VALUES(hierarchyid::GetRoot(), 'David') ;
GO
AddEmp 0x , 'Sariya'
GO
AddEmp 0x58 , 'Mary'
GO
SELECT * FROM Org_T2

Here is the result set.

EmployeeId LastChild EmployeeName
---------- --------- ------------
0x        0x58       David
0x58      0x5AC0     Sariya
0x5AC0    NULL       Mary

Arrow icon used with Back to Top linkBack to Top

Enforcing a tree

The above examples illustrate how an application can ensure a tree is maintained. To enforce a tree via constraints, a computed column that defines the parent of each node can be created with a foreign key constraint back to the primary key id.

CREATE TABLE Org_T3
(
   EmployeeId hierarchyid PRIMARY KEY,
   ParentId AS EmployeeId.GetAncestor(1) PERSISTED  
      REFERENCES Org_T3(EmployeeId),
   LastChild hierarchyid, 
   EmployeeName nvarchar(50)
)
GO

This method of enforcing a relationship is preferred when code that is not trusted to maintain the hierarchical tree has direct DML access to the table. This method might reduce performance because the constraint must be checked on every DML operation.

Arrow icon used with Back to Top linkBack to Top

Example Using CLR

A common operation involving two nodes in a hierarchy is to find the lowest common ancestor. This can be written in either Transact-SQL or CLR, because the hierarchyid type is available in both. CLR is recommended because performance will be faster.

Use the following CLR code to find list ancestors and find the lowest common ancestor:

using System;
using System.Collections;
using System.Text;
using Microsoft.SqlServer.Server;
using Microsoft.SqlServer.Types;

public partial class HierarchyId_Operations
{
    [SqlFunction(FillRowMethodName = "FillRow_ListAncestors")]
    public static IEnumerable ListAncestors(SqlHierarchyId h)
    {
        while (!h.IsNull)
        {
            yield return (h);
            h = h.GetAncestor(1);
        }
    }
    public static void FillRow_ListAncestors(Object obj, out SqlHierarchyId ancestor)
    {
        ancestor = (SqlHierarchyId)obj;
    }

    public static HierarchyId CommonAncestor(SqlHierarchyId h1, HierarchyId h2)
    {
        while (!h1.IsDescendant(h2))
            h1 = h1.GetAncestor(1);
        
        return h1;
    }
}

To use the ListAncestor and CommonAncestor methods in the following Transact-SQL examples, build the DLL and create the HierarchyId_Operations assembly in SQL Server by executing code similar to the following:

CREATE ASSEMBLY HierarchyId_Operations 
FROM '<path to DLL>\ListAncestors.dll'
GO

Arrow icon used with Back to Top linkBack to Top

Listing Ancestors

Creating a list of ancestors of a node is a common operation, for instance to show position in an organization. One way of doing this is by using a table-valued-function using the HierarchyId_Operations class defined above:

Using Transact-SQL:

CREATE FUNCTION ListAncestors (@node hierarchyid)
RETURNS TABLE (node hierarchyid)
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.ListAncestors
GO

Example of usage:

DECLARE @h hierarchyid
SELECT @h = OrgNode 
FROM HumanResources.EmployeeDemo  
WHERE LoginID = 'adventure-works\janice0' -- /1/1/5/2/

SELECT LoginID, OrgNode.ToString() AS LogicalNode
FROM HumanResources.EmployeeDemo AS ED
JOIN ListAncestors(@h) AS A 
   ON ED.OrgNode = A.Node
GO

Finding the Lowest Common Ancestor

Using the HierarchyId_Operations class defined above, create the following Transact-SQL function to find the lowest common ancestor involving two nodes in a hierarchy:

CREATE FUNCTION CommonAncestor (@node1 hierarchyid, @node2 hierarchyid)
RETURNS hierarchyid
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.CommonAncestor
GO

Example of usage:

DECLARE @h1 hierarchyid, @h2 hierarchyid

SELECT @h1 = OrgNode 
FROM  HumanResources.EmployeeDemo 
WHERE LoginID = 'adventure-works\jossef0' -- Node is /1/1/3/

SELECT @h2 = OrgNode 
FROM HumanResources.EmployeeDemo  
WHERE LoginID = 'adventure-works\janice0' -- Node is /1/1/5/2/

SELECT OrgNode.ToString() AS LogicalNode, LoginID 
FROM HumanResources.EmployeeDemo  
WHERE OrgNode = dbo.CommonAncestor(@h1, @h2) ;

The resultant node is /1/1/

Arrow icon used with Back to Top linkBack to Top

Moving Subtrees

Another common operation is moving subtrees. The procedure below takes the subtree of @oldMgr and makes it (including @oldMgr) a subtree of @newMgr.

CREATE PROCEDURE MoveOrg(@oldMgr nvarchar(256), @newMgr nvarchar(256) )
AS
BEGIN
DECLARE @nold hierarchyid, @nnew hierarchyid
SELECT @nold = OrgNode FROM HumanResources.EmployeeDemo WHERE LoginID = @oldMgr ;

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
BEGIN TRANSACTION
SELECT @nnew = OrgNode FROM HumanResources.EmployeeDemo WHERE LoginID = @newMgr ;

SELECT @nnew = @nnew.GetDescendant(max(OrgNode), NULL) 
FROM HumanResources.EmployeeDemo WHERE OrgNode.GetAncestor(1)=@nnew ;

UPDATE HumanResources.EmployeeDemo  
SET OrgNode = OrgNode.GetReparentedValue(@nold, @nnew)
WHERE OrgNode.IsDescendantOf(@nold) = 1 ; 

COMMIT TRANSACTION
END ;
GO