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 AdventureWorks ;
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
.gif "Arrow icon used with Back to Top link")
Back 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.
Back 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
Back 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/
Back 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 @nold.IsDescendant(OrgNode) = 1 ;
COMMIT TRANSACTION
END ;
GO