Sql Server 2012 : Hierarchical Data and the Relational Database - Populating the Hierarchy (part 3) - The GetAncestor Method

The GetAncestor Method

The GetAncestor method accepts an integer parameter that specifies how many levels to traverse up from the node it is invoked on to reach one of that node’s ancestors, and then returns the hierarchyid of the ancestor node. A value of 1, as you are using here, returns the immediate parent of the node on which the GetAncestor method is invoked. By requesting all rows with hierarchyid values whose immediate parent is the same as the parent requested by the caller for the new employee, the preceding WHERE clause retrieves all the existing siblings of the employee about to be added. Because this can return multiple siblings, you apply the MAX aggregate function to retrieve the sibling with the highest-valued hierarchyid (which is the last sibling in the set) into the @LastManagerChild local variable. If there are no existing siblings, the WHERE clause will return no rows at all and NULL will be assigned into @LastManagerChild. In either case, you have established the appropriate value in @LastManagerChild to be used as the first positional parameter for the call to GetDescendant, as shown here:

-- Assign a new hierarchyid positioned at the end of any existing siblings
SELECT @NewEmployeeNodeId =
 @ManagerNodeId.GetDescendant(@LastManagerChild, NULL)

You have now assigned an appropriate hierarchyid value for the new employee in @NewEmployeeNodeId by invoking GetDescendant on the parent (@ManagerNodeId). The two parameters passed to GetDescendant specify that the new employee should be inserted between the last sibling that exists (@LastManagerChild) and the end of the sibling list (NULL), which effectively means that it will be appended to the end. If NULL was assigned into @LastManagerChild because there were no previously existing siblings, GetDescendant is called with two NULL values, which (as you’ve already seen) is the correct way to call GetDescendant when adding the very first child beneath a parent.

All that’s needed now is a straightforward INSERT statement that adds the new employee to the table at the correct node position beneath the parent specified by the caller, as shown here:

-- Add the row
INSERT INTO Employee
  (NodeId, EmployeeId, EmployeeName, Title)
 VALUES
  (@NewEmployeeNodeId, @EmployeeId, @EmployeeName, @Title)

The last part of this stored procedure that bears explanation is its use of a transaction surrounding the SELECT and INSERT statements. The purpose here is to guarantee that no other sibling nodes can be added by another user between the time the hierarchyid value of the last sibling is obtained and the time the new row is actually inserted. Without wrapping this logic inside of a transaction, you have no such guarantee, and the hierarchyid value determined to be the last sibling in the set might no longer be the last sibling in the set at the time the new employee is added. A collision could therefore occur between two concurrent processes attempting to add two different new employees beneath the same parent in the same position at the same time. Such an attempt would result in a primary key constraint violation, because both inserts would be attempting to store the same hierarchyid value into the NodeId column defined as the primary key. Although the SELECT and INSERT statements could be combined into a single complex statement without using an explicit transaction (as you saw earlier when you added the employee row for Amy), the logic is much clearer (and thus more maintainable) when coding these as separate statements.

Now that you have created the uspAddEmployee stored procedure and understand how it works, adding the rest of the employees in your organizational chart is easy. All you need to do for each one is specify the employee ID of the new employee’s parent, followed by the new employee’s ID, name, and title, as shown here:

EXEC uspAddEmployee 6, 271, 'John', 'Marketing Specialist'
EXEC uspAddEmployee 6, 119, 'Jill', 'Marketing Specialist'
EXEC uspAddEmployee 46, 269, 'Cheryl', 'Marketing Assistant'
EXEC uspAddEmployee 46, 389, 'Wanda', 'Business Assistant'
EXEC uspAddEmployee 271, 272, 'Mary', 'Marketing Assistant'
EXEC uspAddEmployee 119, 291, 'Kevin', 'Marketing Intern'
EXEC uspAddEmployee 269, 87, 'Richard', 'Business Intern'
EXEC uspAddEmployee 269, 90, 'Jeff', 'Business Intern'

The ToString method on each row’s hierarchyid value in NodeId confirms that the tree structure correctly represents your organizational chart:

SELECT NodeId.ToString() AS NodeIdPath, *
 FROM Employee
 ORDER BY NodeLevel, NodeId
GO

NodeIdPath NodeId NodeLevel EmployeeId  EmployeeName Title
---------- ------ --------- ----------- ------------ --------------------
/          0x     0         6           Dave         Marketing Manager
/1/        0x58   1         46          Amy          Marketing Specialist
/2/        0x68   1         271         John         Marketing Specialist
/3/        0x78   1         119         Jill         Marketing Specialist
/1/1/      0x5AC0 2         269         Cheryl       Marketing Assistant
/1/2/      0x5B40 2         389         Wanda        Business Assistant
/2/1/      0x6AC0 2         272         Mary         Marketing Assistant
/3/1/      0x7AC0 2         291         Kevin        Marketing Intern
/1/1/1/    0x5AD6 3         87          Richard      Business Intern
/1/1/2/    0x5ADA 3         90          Jeff         Business Intern

(10 row(s) affected)

The ToString method certainly displays a hierarchyid value in a more intelligible form than the raw internal varbinary value, but the string returned is still rather cryptic. With a little code, you can create a user-defined function (UDF) that will accept any NodeId and return a more meaningful “breadcrumb-style” representation of the path leading up to that node. Example 6 shows the code for the fnGetFullDisplayPath UDF that uses the GetLevel and GetAncestor methods together to do just that.

Example 6. Creating a UDF that builds a breadcrumb-style display path for a given node.

CREATE FUNCTION dbo.fnGetFullDisplayPath(@EntityNodeId hierarchyid)
 RETURNS varchar(max)
AS
  BEGIN
    DECLARE @EntityLevelDepth smallint
    DECLARE @LevelCounter smallint
    DECLARE @DisplayPath varchar(max)
    DECLARE @ParentEmployeeName varchar(max)

    -- Start with the specified node
    SELECT @EntityLevelDepth = NodeId.GetLevel(),
           @DisplayPath = EmployeeName
     FROM  Employee
     WHERE NodeId = @EntityNodeId

    -- Loop through all its ancestors
    SET @LevelCounter = 0
    WHILE @LevelCounter < @EntityLevelDepth BEGIN

       SET @LevelCounter = @LevelCounter + 1

       SELECT @ParentEmployeeName = EmployeeName
        FROM  Employee
        WHERE NodeId = (
              SELECT NodeId.GetAncestor(@LevelCounter)
               FROM Employee
               WHERE NodeId = @EntityNodeId)

       -- Prepend the ancestor name to the display path
       SET @DisplayPath = @ParentEmployeeName + ' > ' + @DisplayPath

    END

    RETURN(@DisplayPath)
   END

After declaring a few local variables, the function starts by first selecting the node specified by the @EntityNodeId parameter (the node’s hierarchyid value). It obtains the level of the node by calling GetLevel and stores it in the @EntityLevelDepth variable, and also retrieves the employee name into the @DisplayPath variable. The function will return @DisplayPath after it finishes prepending it with all of the employee names of the node’s ancestors, all the way up to the root.

The function then establishes a @LevelCounter integer variable, initialized to 0, and enters a loop that increments @LevelCounter with each iteration. The loop is terminated when the @LevelCounter value reaches @EntityLevelDepth. Inside the loop, the incrementing @LevelCounter value is fed to the GetAncestor method to retrieve the next employee name up the chain, which is then prepended to @DisplayPath along with the ‘ > ’ level-separation string. In this manner, the code obtains the parent, grandparent, great-grandparent, and so on, all the way up to the root. When the loop terminates, @DisplayPath is returned to the caller. Here is the output from the fnGetFullDisplayPath function when run against the employee table:

SELECT
  NodeId,
  NodeId.ToString() AS NodeIdPath,
  dbo.fnGetFullDisplayPath(NodeId) AS NodeIdDisplayPath,
  EmployeeName
 FROM
  Employee
 ORDER BY
  NodeLevel, NodeId
GO

NodeId NodeIdPath NodeIdDisplayPath             EmployeeName
------ ---------- ----------------------------- ------------
0x     /          Dave                          Dave
0x58   /1/        Dave > Amy                    Amy
0x68   /2/        Dave > John                   John
0x78   /3/        Dave > Jill                   Jill
0x5AC0 /1/1/      Dave > Amy > Cheryl           Cheryl
0x5B40 /1/2/      Dave > Amy > Wanda            Wanda
0x6AC0 /2/1/      Dave > John > Mary            Mary
0x7AC0 /3/1/      Dave > Jill > Kevin           Kevin
0x5AD6 /1/1/1/    Dave > Amy > Cheryl > Richard Richard
0x5ADA /1/1/2/    Dave > Amy > Cheryl > Jeff    Jeff

(10 row(s) affected)

The NodeIdDisplayPath in this result set shows the employee names along the hierarchical paths in each row.

Populating a hierarchical table does require some effort up front, as you’ve seen. However, once your data is in place, you can leverage the power of the hierarchyid data type by invoking its methods to easily query and reorganize the tree structure. We’re almost ready to dive into that, but first let’s take a moment to talk about the indexing options that you need to know about.