The Hierarchyid data
type introduced in SQL Server 2008 is actually a system-supplied common
language runtime (CLR) user-defined type (UDT) that can be used for
storing and manipulating hierarchical structures (for example,
parent-child relationships) in a relational database. The Hierarchyid type is stored as a varbinary
value that represents the position of the current node in the hierarchy
(both in terms of parent-child position and position among siblings).
You can perform manipulations on the type in Transact-SQL by invoking
methods exposed by the type.
Creating a Hierarchy
First, let’s define a hierarchy in a table using the Hierarchyid data type. Let’s see how to implement an alternative solution by adding a Hierarchyid column to the Parts table. First, you create a version of the Parts table using the Hierarchyid data type (see Listing 1).
Listing 1. Creating the Parts Table with a Hierarchyid Data Type
Use bigpubs2008
Go
CREATE TABLE PARTS_hierarchy(
partid int NOT NULL,
hid hierarchyid not null,
lvl as hid.GetLevel() persisted,
partname varchar(30) NOT NULL,
PRIMARY KEY NONCLUSTERED (partid),
UNIQUE NONCLUSTERED (partname)
)
|
Note the hid column defined with the Hierarchyid data type. Notice also how the lvl column is defined as a compute column using the GetLevel method of the hid column to define the persisted computed column level. The GetLevel method returns the level of the current node in the hierarchy.
The Hierarchyid
data type provides topological sorting, meaning that a child’s sort
value is guaranteed to be greater than the parent’s sort value. This
guarantees that a node’s sort value will be higher than all its
ancestors. You can take advantage of this feature by creating an index
on the Hierarchyid column because the
index will sort the data in a depth-first manner. This ensures that all
members of the same subtree are close to each other in the leaf level of
the index, which makes the index useful as an efficient mechanism for
returning all descendents of a node. To take advantage of this, you can
create a clustered index on the hid column:
CREATE UNIQUE CLUSTERED INDEX idx_hid_first ON Parts_hierarchy (hid);
You can also use another indexing strategy called breadth-first,
in which you organize all nodes from the same level close to each other
in the leaf level of the index. This is done by building the index such
that the leading column is level in the hierarchy. Queries that need to
get all nodes from the same level in the hierarchy can benefit from
this type of index:
CREATE UNIQUE INDEX idx_lvl_first ON Parts_hierarchy(lvl, hid);
Populating the Hierarchy
Now that you’ve created the
hierarchy table, the next step is to populate it. To insert a new node
into the hierarchy, you must first produce a new Hierarchyid value that represents the correct position in the hierarchy. There are two methods available with the Hierarchyid data type to do this: the HIERARCHYID::GetRoot() method and GetDescendant method. You use the HIERARCHYID::GetRoot() method to produce the value for the root node of the hierarchy. This method simply produces a Hierarchyid value that is internally an empty binary string representing the root of the tree.
You can use the GetDescendant method to produce a value below a given parent. The GetDescendant method accepts two optional Hierarchyid input values that represent the two nodes between which you want to position the new node. If both values are not NULL, the method produces a new value positioned between the two nodes. If the first parameter is not NULL and the second parameter is NULL, the method produces a value greater than the first parameter. Finally, if the first parameter is NULL and the second parameter is not NULL, the method produces a value smaller than the second parameter. If both parameters are NULL, the method produces a value simply below the given parent.
Note
The GetDescendant method does not guarantee that Hierarchyid values are unique. To enforce uniqueness, you must define either a primary key, unique constraint, or unique index on the Hierarchyid column.
The code in Listing 2 uses a cursor to loop through the rows currently in the Parts table and populates the Parts_hierarchy table. If the part is the first node in the hierarchy, the procedure uses the HIERARCHYID::GetRoot() method to assign the hid value for the root node of the hierarchy. Otherwise, the code in the cursor looks for the last child hid value of the new part’s parent part and uses the GetDescendant method to produce a value that positions the new node after the last child of that parent part.
Note
Listing 2 also makes use of a recursive common table expression to traverse the existing Parts
table in hierarchical order to add in the rows at the proper level,
starting with the top-most parent part.
Listing 2. Populating the Parts_hierarchy Table
DECLARE
@hid AS HIERARCHYID,
@parent_hid AS HIERARCHYID,
@last_child_hid AS HIERARCHYID,
@partid int,
@partname varchar(30),
@parentpartid int
declare parts_cur cursor for
WITH PartsCTE(partid, partname, parentpartid, lvl)
AS
(
SELECT partid, partname, parentpartid, 0
FROM PARTS
WHERE parentpartid is null
UNION ALL
SELECT P.partid, P.partname, P.parentpartid, PP.lvl+1
FROM Parts as P
JOIN PartsCTE as PP
ON P.parentpartid = PP.Partid
)
SELECT PartID, Partname, ParentPartid
FROM PartsCTE
order by lvl
open parts_cur
fetch parts_cur into @partid, @partname, @parentpartid
while @@FETCH_STATUS = 0
begin
if @parentpartid is null
set @hid = HIERARCHYID::GetRoot()
else
begin
select @parent_hid = hid from PARTS_hierarchy
where partid = @parentpartid
select @last_child_hid = MAX(hid) from PARTS_hierarchy
where hid.GetAncestor(1) = @parent_hid
select @hid = @parent_hid.GetDescendant(@last_child_hid, NULL)
end
insert PARTS_hierarchy (partid, hid, partname)
values (@partid, @hid, @partname)
fetch parts_cur into @partid, @partname, @parentpartid
end
close parts_cur
deallocate parts_cur
go
|
Querying the Hierarchy
Now
that you’ve populated the hierarchy, you should query it to view the
data and verify the hierarchy was populated correctly. However, If you
query the hid value directly, you see only its binary representation, which is not very meaningful. To view the Hierarchyid value in a more useful manner, you can use the ToString method, which returns a logical string representation of the Hierarchyid.
This string representation is shown as a path with a slash sign used as
a separator between the levels. For example, you can run the following
query to get both the binary and logical representations of the hid value:
select cast(hid as varbinary(6)) as hid,
substring(hid.ToString(), 1, 12) as path,
lvl,
partid,
partname
From parts_hierarchy
go
hid path lvl partid partname
-------------- ------------ ------ ----------- ------------------
0x / 0 22 Car
0x58 /1/ 1 1 DriveTrain
0x68 /2/ 1 23 Body
0x78 /3/ 1 24 Frame
0x5AC0 /1/1/ 2 2 Engine
0x5B40 /1/2/ 2 3 Transmission
0x5BC0 /1/3/ 2 4 Axle
0x5C20 /1/4/ 2 12 Drive Shaft
0x5B56 /1/2/1/ 3 9 Flywheel
0x5B5A /1/2/2/ 3 10 Clutch
0x5B5E /1/2/3/ 3 16 Gear Box
0x5AD6 /1/1/1/ 3 5 Radiator
0x5ADA /1/1/2/ 3 6 Intake Manifold
0x5ADE /1/1/3/ 3 7 Exhaust Manifold
0x5AE1 /1/1/4/ 3 8 Carburetor
0x5AE3 /1/1/5/ 3 13 Piston
0x5AE5 /1/1/6/ 3 14 Crankshaft
0x5AE358 /1/1/5/1/ 4 21 Piston Rings
0x5AE158 /1/1/4/1/ 4 11 Float Valve
0x5B5EB0 /1/2/3/1/ 4 15 Reverse Gear
0x5B5ED0 /1/2/3/2/ 4 17 First Gear
0x5B5EF0 /1/2/3/3/ 4 18 Second Gear
0x5B5F08 /1/2/3/4/ 4 19 Third Gear
0x5B5F18 /1/2/3/5/ 4 20 Fourth Gear
As stated previously, the values stored in a Hierarchyid column provide topological sorting of the nodes in the hierarchy. The GetLevel method can be used to produce the level in the hierarchy (as it was to store the level in the computed lvl column in the Parts_hierarchy table). Using the lvl column or the GetLevel method, you can easily produce a graphical depiction of the hierarchy by simply sorting the rows by hid and generating indentation for each row based on the lvl column, as shown in the following example:
SELECT
REPLICATE('--', lvl)
+ right('>',lvl)
+ partname AS partname
FROM Parts_hierarchy
order by hid
go
partname
-------------------------
Car
-->DriveTrain
---->Engine
------>Radiator
------>Intake Manifold
------>Exhaust Manifold
------>Carburetor
-------->Float Valve
------>Piston
-------->Piston Rings
------>Crankshaft
---->Transmission
------>Flywheel
------>Clutch
------>Gear Box
-------->Reverse Gear
-------->First Gear
-------->Second Gear
-------->Third Gear
-------->Fourth Gear
---->Axle
---->Drive Shaft
-->Body
-->Frame
To return only the subparts of a specific part, you can use the IsDescendantOf method. The parameter passed to this method is a node’s Hierarchyid value. The method returns 1 if the queried node is a descendant of the input node. For example, the following query returns all subparts of the engine:
select child.partid, child.partname, child.lvl
from
parts_hierarchy as parent
inner join
parts_hierarchy as child
on parent.partname = 'Engine'
and child.hid.IsDescendantOf(parent.hid) = 1
go
partid partname lvl
----------- ------------------------------ ------
2 Engine 2
5 Radiator 3
6 Intake Manifold 3
7 Exhaust Manifold 3
8 Carburetor 3
13 Piston 3
14 Crankshaft 3
21 Piston Rings 4
11 Float Valve 4
You can also use the IsDescendantOf method to return all parent parts of a given part:
select parent.partid, parent.partname, parent.lvl
from
parts_hierarchy as parent
inner join
parts_hierarchy as child
on child.partname = 'Piston'
and child.hid.IsDescendantOf(parent.hid) = 1
go
partid partname lvl
----------- ------------------------------ ------
22 Car 0
1 DriveTrain 1
2 Engine 2
13 Piston 3
To return a specific level of subparts for a given part, you can use the GetAncestor
method. You pass this method an integer value indicating the level
below the parent you want to display. The function returns the Hierarchyid value of the ancestor n levels above the queried node. For example, the following query returns all the subparts two levels down from the drivetrain:
select child.partid, child.partname
from
parts_hierarchy as parent
inner join
parts_hierarchy as child
on parent.partname = 'Drivetrain'
and child.hid.GetAncestor(2) = parent.hid
go
partid partname lvl
----------- ------------------------------ ------
9 Flywheel 3
10 Clutch 3
16 Gear Box 3
5 Radiator 3
6 Intake Manifold 3
7 Exhaust Manifold 3
8 Carburetor 3
13 Piston 3
14 Crankshaft 3
