Web developers wiki ASP.NET Sitecore Sharepoint Kentico by Evident Interactive

HierarchyID - Introduction

Modified: 2008/12/31 16:11 by vanthoog - Categorized as: SQL Server
This article gives a brief introduction to the new data type HierarchyID in SQL Server 2008.

Edit

General

The data type HierarchyID is a new data type for representing hierarchical data. It contains the path to an item in a hierarchical structure which is stored as a variable-length byte stream. The data type HierarchyID has in fact been implemented as a CLR user-defined type (UDT) and is based on the sytem type varbinary.

The path is represented as a string containing a sequence of all parents of the item up to the root item. In this sequence every item is represented by a number, a slash (/) separates a parent from its child and the string starts and ends with a slash. The number representing an item is usually an integer, but in fact it may also be a decimal and it may in fact also be a negative number. Here are some examples of valid paths:
- /
- /1/
- /1/5/
- /1/0.5/
- /1/2.9/3/-4/6/

Edit

Example

In this article a company hierarchical structure is used to show to characteristics and behavior of the HierarchyID data type. This company structure is stored in a (simple) table called Company containing the following columns:

Column  Data type    Content
------- ------------ ------------------------------
Node    HierarchyID  The path of the company within the hierarchical structure.
ID      Int          The id of the company.
Title   Varchar(28)  The title of the company.

The sql-statements for creating this table are:

CREATE TABLE Company
(
   Node hierarchyid NOT NULL,
   ID int NOT NULL,
   Title varchar(28) NULL
) ;
GO

ALTER TABLE Company
	ADD CONSTRAINT UQ_Company UNIQUE CLUSTERED (Node)
GO

ALTER TABLE Company
	ADD CONSTRAINT PK_Company PRIMARY KEY (ID)
GO

The column ID is not really necessary for the examples in this article. It has however been added anyway because it is generally a good idea to access specific records by using an ID column and by implementing foreign keys (in other tables) referencing an ID column. The unique key on the column Node has been specified as a clustered key because this will produce nicely ordered results when not using an ORDER BY clause within SELECT statements. The table is filled with the following sample data:

INSERT INTO Company (Node,ID,Title)
     VALUES	(hierarchyid::Parse('/'),1,'Allround computer company'),
			(hierarchyid::Parse('/1/'),11,'Hardware division'),
			(hierarchyid::Parse('/1/1/'),111,'Disk factory'),
			(hierarchyid::Parse('/1/2/'),112,'Processor factory'),
			(hierarchyid::Parse('/2/'),12,'Software division'),
			(hierarchyid::Parse('/2/1/'),121,'OS''s'),
			(hierarchyid::Parse('/2/2/'),122,'Office tools')

GO

SELECT Node.ToString() AS NodePath , Node, ID , Title FROM Company

NodePath   Node         ID          Title
---------- ------------ ----------- ----------------------------
/          0x           1           Allround computer company
/1/        0x58         11          Hardware division
/1/1/      0x5AC0       111         Disk factory
/1/2/      0x5B40       112         Processor factory
/2/        0x68         12          Software division
/2/1/      0x6AC0       121         OS's
/2/2/      0x6B40       122         Office tools

Edit

Standard Methods of UDT’s

Because HierarchyID is a CLR user-defined type (UDT), it supports the standard methods of UDT’s. Be aware that these standard methods are case-sensitive! These standard methods are:

Edit

ToString()

This method translates the binary representation of a path into a readable string representation.

Example:

SELECT Node , Node.ToString() AS NodePath FROM Company

Node         NodePath
------------ ----------
0x           /
0x58         /1/
0x68         /2/
0x5AC0       /1/1/
0x5B40       /1/2/
0x6AC0       /2/1/
0x6B40       /2/2/

Edit

Parse()

This static method translates a string representation of a path into a binary representation. It is basically the opposite of ToString().

Example:

SELECT hierarchyid::Parse('/5/4/3/2/1/')

------------
0x8E17B560

Edit

Specific methods for HierarchyID

HierarchyID has a number of specific methods which are described in this section. Be aware that these methods are also case-sensitive!

Edit

GetRoot()

This static method returns the path of the root element. As such it always returns the path ‘/’.

Example:

SELECT hierarchyid::GetRoot() , hierarchyid::GetRoot().ToString()

             
------------ ----------
0x           /

Edit

GetLevel()

Returns the level of the path of this item within the hierarchy.

Example:

SELECT Node.ToString() AS NodePath , Node.GetLevel() AS Level 
FROM Company

NodePath   Level
---------- ------
/          0
/1/        1
/2/        1
/1/1/      2
/1/2/      2
/2/1/      2
/2/2/      2

Edit

GetAncestor(n)

Returns the parent of the item n-levels above this item. If n is greater than level of the specified item, null is returned.

Example:

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetAncestor(1) AS Parent , 
  Node.GetAncestor(2).ToString() AS ParentsParent 
FROM Company

NodePath   Parent     ParentsParent
---------- ---------- -------------
/          NULL       NULL
/1/        /          NULL
/2/        /          NULL
/1/1/      /1/        /
/1/2/      /1/        /
/2/1/      /2/        /
/2/2/      /2/        /

Edit

GetDescendant(child1, child2)

Returns the path of a child underneath this item. The parameters child1 and child2 can be used to specify the position of the desired child within the hierarchy and may be null. These two parameters require some explanation. The child being returned is the first child whose path is greater than the path of child1 and smaller than the path of child2. Or in other words, the child being returned lies in the hierarchy directly underneath this item and in between child1 and child2. The parameters child1 and child2 may both be null. If so, these parameters will be ignored. This means for example that if both parameters are null, the very first child of this item is returned.

Example:

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(NULL , NULL).ToString() AS FirstChild 
FROM Company

NodePath   FirstChild
---------- ----------
/          /1/
/1/        /1/1/
/2/        /2/1/
/1/1/      /1/1/1/
/1/2/      /1/2/1/
/2/1/      /2/1/1/
/2/2/      /2/2/1/

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/1/') , NULL).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
/          /2/

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(NULL , hierarchyid::Parse('/2/')).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
/          /1/

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/1/') , hierarchyid::Parse('/3/')).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
/          /2/

The parameter child2 seems pretty useless. In most cases it doesn’t really do anything. In the following example all queries produce exactly the same output and the only difference between these queries is the content of the parameter child2:

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/1/') , NULL).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
/          /2/

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/1/') , hierarchyid::Parse('/3/')).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
/          /2/

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/1/') , hierarchyid::Parse('/666/')).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
/          /2/

The following example shows a case in which the parameter child2 does have an actual impact on the output of GetDescendant:

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/1/') , hierarchyid::Parse('/1.2/')).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
/          /1.1/

It is important to know that GetDescendant does not check for the actual existence of the returned child. In the following example GetDescendant returns the path of a child which does not exist:

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/4/') , hierarchyid::Parse('/9/')).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
/          /5/

The contents of the parameters child1 and child2 is checked within the context of this item. They must both be direct children underneath this item, i.e. their level should be the level of this item plus 1. Furthermore the path of child1 must be smaller than the path of child2. The following example contains a number of queries which will fail because the parameter child1 or child2 contain invalid content.

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/1/') , NULL).ToString() AS Child 
FROM Company

NodePath   Child
---------- ----------
/          /2/
avhsql2008(AVHSQL2008\Administrator): Msg 6522, Level 16, State 2, Line 1
A .NET Framework error occurred during execution of user defined routine or aggregate 'hierarchyid': 
Microsoft.SqlServer.Types.HierarchyIdException: 24008: SqlHierarchyId.GetDescendant failed because 'child1' must be a child of 'this'.  'child1' was '/1/' and 'this' was '/1/'.
Microsoft.SqlServer.Types.HierarchyIdException: 
   at Microsoft.SqlServer.Types.XmlIdGenerator.Init(OrdPath pordpathParent, OrdPath pordpathLeft, OrdPath pordpathRight)
   at Microsoft.SqlServer.Types.SqlHierarchyId.GetDescendant(SqlHierarchyId child1, SqlHierarchyId child2)
.

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/3/') , hierarchyid::Parse('/2/')).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
avhsql2008(AVHSQL2008\Administrator): Msg 6522, Level 16, State 2, Line 1
A .NET Framework error occurred during execution of user defined routine or aggregate 'hierarchyid': 
Microsoft.SqlServer.Types.HierarchyIdException: 24007: SqlHierarchyId.GetDescendant failed because 'child1' must be less than 'child2'.  'child1' was '/3/' and 'child2' was '/2/'.
Microsoft.SqlServer.Types.HierarchyIdException: 
   at Microsoft.SqlServer.Types.ex_raise(Int32 major, Int32 minor, Int32 sev, Int32 state, Object param1, Object param2, Object param3)
   at Microsoft.SqlServer.Types.XmlIdGenerator.Init(OrdPath pordpathParent, OrdPath pordpathLeft, OrdPath pordpathRight)
   at Microsoft.SqlServer.Types.SqlHierarchyId.GetDescendant(SqlHierarchyId child1, SqlHierarchyId child2)
.

SELECT 
  Node.ToString() AS NodePath , 
  Node.GetDescendant(hierarchyid::Parse('/3/4/') , NULL).ToString() AS Child 
FROM Company 
WHERE Node = hierarchyid::Parse('/')

NodePath   Child
---------- ----------
avhsql2008(AVHSQL2008\Administrator): Msg 6522, Level 16, State 2, Line 1
A .NET Framework error occurred during execution of user defined routine or aggregate 'hierarchyid': 
Microsoft.SqlServer.Types.HierarchyIdException: 24008: SqlHierarchyId.GetDescendant failed because 'child1' must be a child of 'this'.  'child1' was '/3/4/' and 'this' was '/'.
Microsoft.SqlServer.Types.HierarchyIdException: 
   at Microsoft.SqlServer.Types.OrdPath.ExtractOrdComponentFake(OrdPath parent, Boolean fLeft, UInt16& bitOffset, Int64& ord, levelType& type)
   at Microsoft.SqlServer.Types.XmlIdGenerator.Init(OrdPath pordpathParent, OrdPath pordpathLeft, OrdPath pordpathRight)
   at Microsoft.SqlServer.Types.SqlHierarchyId.GetDescendant(SqlHierarchyId child1, SqlHierarchyId child2)
.

Edit

IsDescendantOf(parent)

Determines whether this item is a child of the item specified by the parameter parent. It returns 1 (i.e. true) if the position of this item in the hierarchy lies anywhere underneath parent or if this item is equal to parent.

Example:

SELECT 
  Node.ToString() AS NodePath, 
  Node.IsDescendantOf(hierarchyid::Parse('/2/')) AS IsDescendantOf 
FROM Company

NodePath   IsDescendantOf
---------- --------------
/          0
/1/        0
/2/        1
/1/1/      0
/1/2/      0
/2/1/      1
/2/2/      1

Edit

GetReparentedValue(oldparent, newparent)

Determines a new path for this item. The new path is determined by replacing within the path of this item the subpath specified by oldparent by the subpath specified by newparent. Both parameters must be specified and the parameter oldparent must be a parent of this item. The parameter newparent may be any path within the hierarchy and does not need to be at the same level within the hierarchy as oldparent.

In the following examples a new path is determined for some items, but the items are not actually moved. The only thing we do is to determine the new path without actually performing an update.

Here is an example in which some items are “moved” to another parent at the same level:

SELECT 
  Node.ToString() AS NodePath, 
  Node.GetReparentedValue(hierarchyid::Parse('/1/') , hierarchyid::Parse('/5/')).ToString() AS NodeNewPath 
FROM Company 
WHERE Node.IsDescendantOf(hierarchyid::Parse('/1/')) = 1

NodePath   NodeNewPath
---------- -----------
/1/        /5/
/1/1/      /5/1/
/1/2/      /5/2/

Here is an example in which some items are “moved” to another parent at a lower level:

SELECT 
  Node.ToString() AS NodePath, 
  Node.GetReparentedValue(hierarchyid::Parse('/1/') , hierarchyid::Parse('/2/1/')).ToString() AS NodeNewPath 
FROM Company 
WHERE Node.IsDescendantOf(hierarchyid::Parse('/1/')) = 1

NodePath   NodeNewPath
---------- -----------
/1/        /2/1/
/1/1/      /2/1/1/
/1/2/      /2/1/2/

The following example will fail because the parameter oldparent is not a parent of this item:

SELECT 
  Node.ToString() AS NodePath, 
  Node.GetReparentedValue(hierarchyid::Parse('/2/') , hierarchyid::Parse('/5/1/')).ToString() AS NodeNewPath 
FROM Company 
WHERE hierarchyid::Parse('/1/').IsDescendantOf(Node) = 1

NodePath   NodeNewPath
---------- -----------
avhsql2008(AVHSQL2008\Administrator): Msg 6522, Level 16, State 2, Line 1
A .NET Framework error occurred during execution of user defined routine or aggregate 'hierarchyid': 
Microsoft.SqlServer.Types.HierarchyIdException: 24009: SqlHierarchyId.GetReparentedValue failed because 'oldRoot' was not an ancestor node of 'this'.  'oldRoot' was '/2/', and 'this' was '/1/'.
Microsoft.SqlServer.Types.HierarchyIdException: 
   at Microsoft.SqlServer.Types.SqlHierarchyId.GetReparentedValue(SqlHierarchyId oldRoot, SqlHierarchyId newRoot)
.

GetReparentedValue is typically used for restructuring the hierarchy. One should however be very careful when using this method. GetReparentedValue returns a theoretical new path, but it doesn’t check whether that path is valid. It is for example possible that an item already exists with that path or that the direct parent of the new path does not exist. It is therefore very important that you check the output of GetReparentedValue before actually performing an update of the records in the database.

Here is an example in which some items are “moved” to a non-existent parent (at a lower level):

SELECT 
  Node.ToString() AS NodePath, 
  Node.GetReparentedValue(hierarchyid::Parse('/1/') , hierarchyid::Parse('/5/1/')).ToString() AS NodeNewPath 
FROM Company 
WHERE Node.IsDescendantOf(hierarchyid::Parse('/1/')) = 1

NodePath   NodeNewPath
---------- -----------
/1/        /5/1/
/1/1/      /5/1/1/
/1/2/      /5/1/2/

GetReparentedValue doesn’t also automatically update all children underneath this item. It is up to the programmer to make sure that when changing the path of a parent, the path of all children is updated as well.

Edit

Indexing strategies

There are basically two indexing strategies for columns using data type HierarchyID, being depth-first or breadth-first.

When using depth-first the index is build based on the paths of the items. This means that within the index the items are stored next to or very near their parent.
A depth-first index

A depth-first index


A depth-first index is applied by putting an index directly on the column of data type HierarchyID. This is the approach used in the example used in this article.

When using breadth-first the index is build based on the level of the paths of the items. This means that within the index the items at the same level within the hierarchy are stored next to each other.

A breadth-first index

A breadth-first index

A breadth-first index is applied by adding a computed column containing the level of the path of an item and putting an index on that computed column.

In the following example the depth-first unique constraint is dropped and a breadth-first unique constraint is added:

-- Show the output without an "order by" with the depth-first unique constraint in place.
SELECT Node.ToString() AS NodePath , Node , ID , Title FROM Company
GO

NodePath   Node         ID          Title
---------- ------------ ----------- ----------------------------
/          0x           1           Allround computer company
/1/        0x58         11          Hardware division
/1/1/      0x5AC0       111         Disk factory
/1/2/      0x5B40       112         Processor factory
/2/        0x68         12          Software division
/2/1/      0x6AC0       121         OS's
/2/2/      0x6B40       122         Office tools

-- Drop the depth-first unique constraint.
ALTER TABLE Company
 	DROP CONSTRAINT UQ_Company
GO

-- Add the computed column Level.
ALTER TABLE Company
 	ADD Level AS Node.GetLevel()
GO

-- Add the breadth-first unique constraint.
ALTER TABLE Company
	ADD CONSTRAINT UQ_Company UNIQUE CLUSTERED (Level , Node)
GO

-- Show the output without an "order by" with the breadth-first unique constraint in place.
SELECT Node.ToString() AS NodePath , Node , ID , Title FROM Company

NodePath   Node         ID          Title
---------- ------------ ----------- ----------------------------
/          0x           1           Allround computer company
/1/        0x58         11          Hardware division
/2/        0x68         12          Software division
/1/1/      0x5AC0       111         Disk factory
/1/2/      0x5B40       112         Processor factory
/2/1/      0x6AC0       121         OS's
/2/2/      0x6B40       122         Office tools

 © Evident Interactive BV