Share via


SQL Server 2008 - HierarchyID - Part I

I am excited by the cool new features that SQL Server 2008 is binging up !

SQL Server 2008 is bringing some commendable new features one of the nice feature is HierarchyID. This a new data type that is available in the in the latest July CTP of the SQL Server 2008 Developer Edition.

Organizations have struggled in past with the representation of tree like structures in the databases, lot of joins lots of complex logic goes into the place, whether it is organization hierarchy or defining a BOM (Bill of Materials) where one finished product is dependent on another semi finished materials / kit items and these kit items are dependent on another semi finished items or raw materials.

SQL Server 2008 has the solution to the problem where we store the entire hierarchy in the data type HierarchyID. HierarchyID is a variable length system data type. HierarchyID is used to locate the position in the hierarchy of the element like Scott is the CEO and Mark as well as Ravi reports to Scott and Ben and Laura report to Mark, Vijay, James and Frank report to Ravi.

Scott

|

Mark                    <- >                Ravi

|                                                |

Ben<-> Laura                              Vijay <-> Frank  <-> James

 

This tree can expand to n nodes.

The average number of bits that are required to represent a node in a tree with n nodes depends on the average fanout (the average number of children of a node). For small fanouts (0-7), the size is about 6*logAn bits, where A is the average fanout. A node in an organizational hierarchy of 100,000 people with an average fanout of 6 levels takes about 38 bits. This is rounded up to 40 bits, or 5 bytes, for storage. It supports the insertion and deletion of nodes.

The HierarchyID can be indexed in two ways

1) Depth First strategy: A depth-first index, rows in a subtree are stored near each other. For example, all employees that report through a manager are stored near their managers' record.

DF

2) Breadth First Strategy : A breadth-first stores the rows each level of the hierarchy together. For example, the records of employees who directly report to the same manager are stored near each other.

BF

 

We can change the strategy as and when we want but the index needs to be dropped and then a new index has to be rebuilt. If if the data is huge and the index is clustered then the table is converted to heap and then indexed again.

The following are the methods in the SQL Server 2008 Database Engine to support HierarchyID data type.

1) GetAncestor

2) GetDescendant

3) GetLevel

4) GetRoot

5) IsDescendant

6) Parse

7) Read

8) Reparent

9) ToString

10) Write

  

GetAncestor()

This method is useful to find the (nth ancestor of the given child node.

 

Syntax: child.GetAncestor ( n )

 

 

GetDescendant()

This method is very useful to get the descendant of a given node. It has a great significance in terms of finding the new descendant position get the descendants etc.

 

Syntax: parent.GetDescendant ( child1 , child2 )

 

This function returns one child node that is a descendant of the parent.

1.
If parent is NULL, returns NULL.

2.
If parent is not NULL, and both child1 and child2 are NULL, returns a child of parent.

3.
If parent and child1 are not NULL, and child2 is NULL, returns a child of parent greater than child1.

4.
If parent and child2 are not NULL and child1 is NULL, returns a child of parent less than child2.

5.
If parent, child1, and child2 are all not NULL, returns a child of parent greater than child1 and less than child2.

6.
If child1 or child2 is not NULL but is not a child of parent, an exception is raised.

7.
If child1 >= child2, an exception is raised.

GetLevel()

This method is useful to find the Level of the current node.

Syntax: node.GetLevel ( )

This function will return an integer that represents the depth of this node in the current tree.

GetRoot()

This method will return the root of the hierarchy tree and this is a static method if you are using it within CLR.

Syntax: hierarchyid::GetRoot ( )

It will return the data type hierarchyID.

IsDescendant()

This method returns true/false (BIT) if the node is a descendant of the parent.

Syntax: parent.IsDescendant ( child )

Parse()

Parse converts the canonical string representation of a hierarchyid to a hierarchyid value. Parse is called implicitly when a conversion from a string type to hierarchyid occurs. Acts as the opposite of ToString(). Parse() is a static method.

Syntax: hierarchyid::Parse ( input )

 

Read()

Read reads binary representation of SqlHierarchyId from the passed-in BinaryReader and sets the SqlHierarchyId object to that value. Read cannot be called by using Transact-SQL. Use CAST or CONVERT instead.

Syntax: void Read( BinaryReader r )

 

Reparent()

This is a very useful method which helps you to reparent a node i.e. suppose if we want to align an existing node to a new parent or any other existing parent then this method is very useful.

 

Syntax: node.Reparent ( oldRoot, newRoot )

 

ToString()

 

This method is useful to get the string representation of the HierarchyID. The method returns a string that is a nvarchar(4000) data type.

 

Syntax: node.ToString ( )

 

 

Write()

 

Write writes out a binary representation of SqlHierarchyId to the passed-in BinaryWriter. Write cannot be called by using Transact-SQL. Use CAST or CONVERT instead.

 

Syntax: void Write( BinaryWriter w )

 

Sample Code

Create Table and Index

 

Use AdventureWorksLT

Go 

--Scheme Creation

Create Schema HumanResources

Go 

--Table Creation

CREATE TABLE HumanResources.EmployeeDemo

(

OrgNode HIERARCHYID,

EmployeeID INT,

LoginID VARCHAR(100),

Title VARCHAR(200),

HireDate DATETIME

)

Go

--Index Creation

CREATE UNIQUE CLUSTERED INDEX idxEmployeeDemo

ON HumanResources.EmployeeDemo (OrgNode,EmployeeID)

 

Data Insertion

--Insert First Row        

 INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)             

 VALUES (hierarchyid       GetRoot(), 1,'adventure-works\scott', 'CEO', '3/11/05') ;

 Go          

 --Insert Second Row      

 DECLARE @Manager hierarchyid           

 SELECT @Manager = hierarchyid           GetRoot() FROM HumanResources.EmployeeDemo;

 INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)             

 VALUES (@Manager.GetDescendant(NULL,NULL), 2, 'adventure-works\Mark',           

 'CTO', '4/05/07')        

 Go

 --Insert Third Row       

 DECLARE @Manager hierarchyid           

 DECLARE @FirstChild hierarchyid        

 SELECT @Manager = hierarchyid           GetRoot() FROM HumanResources.EmployeeDemo;

 Select @FirstChild = @Manager.GetDescendant(NULL,NULL)             

 INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)             

 VALUES (@Manager.GetDescendant(@FirstChild,NULL), 3, 'adventure-works\ravi',           

 'Director Marketing', '4/08/07')       

 Go          

 --Insert the First Descendant of a Child Node        

 DECLARE @Manager hierarchyid           

 SELECT @Manager = CAST('/1/' AS hierarchyid)         

 INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)             

 VALUES (@Manager.GetDescendant(NULL, NULL),45,       

 'adventure-works\Ben','Application Developer', '6/11/07') ;        

 Go          

 --Insert the Second Descendant of a Child Node       

 DECLARE @Manager hierarchyid           

 DECLARE @FirstChild hierarchyid        

 SELECT @Manager = CAST('/1/' AS hierarchyid)         

 SELECT @FirstChild = @Manager.GetDescendant(NULL,NULL)             

 INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)             

 VALUES (@Manager.GetDescendant(@FirstChild, NULL),55,       

 'adventure-works\Laura','Trainee Developer', '6/11/07') ;          

 Go          

 --Insert the first node who is the Descendant of Director Marketing      

 DECLARE @Manager hierarchyid           

 DECLARE @FirstChild hierarchyid        

 SELECT @Manager = CAST('/2/' AS hierarchyid)         

 INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)             

 VALUES (@Manager.GetDescendant(NULL, NULL),551,             

 'adventure-works\frank','Trainee Sales Exec.', '12/11/07') ;       

 Go          

 --Insert the second node who is the Descendant of Director Marketing            

 DECLARE @Manager hierarchyid           

 DECLARE @FirstChild hierarchyid        

 SELECT @Manager = CAST('/2/' AS hierarchyid)         

 SELECT @FirstChild = @Manager.GetDescendant(NULL,NULL)             

 INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)             

 VALUES (@Manager.GetDescendant(@FirstChild, NULL),531,             

 'adventure-works\vijay','Manager Industrial Sales', '12/09/06') ;        

 Go          

 --Insert the third node who is the Descendant of Director Marketing             

 --in between 2 existing descendants           

 DECLARE @Manager hierarchyid           

 DECLARE @FirstChild hierarchyid        

 DECLARE @SecondChild hierarchyid       

 SELECT @Manager = CAST('/2/' AS hierarchyid)         

 SELECT @FirstChild = @Manager.GetDescendant(NULL,NULL)             

 SELECT @SecondChild = @Manager.GetDescendant(@FirstChild,NULL)           

 INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)             

 VALUES (@Manager.GetDescendant(@FirstChild, @SecondChild),543,           

 'adventure-works\james','Manager Consumer Sales', '12/04/06') ;          

 

 

Procedure to insert Employee Record

--Use Serializable Transaction

CREATE PROCEDURE AddEmployee(@ManagerID hierarchyid, @EmpID int,

@LogID varchar(100), @JobTitle as varchar(200), @JoiningDate datetime)

AS

BEGIN

DECLARE @LastChild hierarchyid

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE

BEGIN TRANSACTION

SELECT @LastChild = Max(OrgNode) From HumanResources.EmployeeDemo

WHERE OrgNode = @ManagerID

INSERT HumanResources.EmployeeDemo (OrgNode, EmployeeID, LoginID, Title, HireDate)

VALUES(@LastChild, @EmpID,@LogID , @JobTitle, @JoiningDate)

COMMIT

END ;

Hope you like this article I will write more about HierarchyID very soon. If you like the article or have any doubts then drop me an post.

I am attaching the sample SQL Script along so that you can test it in your test environment.

HierarchyID Query.sql