4.8 Manipulating Hierarchies Recursively

4.8.1 Problem

You want to add and delete vertices and their subtrees. When you hire a new employee or open a new project in your company, you need to add this information into your system. To maintain the hierarchical structure of your employee information, special procedures must be followed.

4.8.2 Solution

To add a vertex to a hierarchy, you simply insert the row into the table with the proper parent pointer. No other action is necessary. If the vertex you just added has children, you insert those children in the same manner. No additional manipulations are needed.

Things become more complex when you need to delete a vertex, because you not only need to delete the row for the vertex, you need to delete any rows that represent children as well. For this purpose, you can use a modified version of the traversing algorithm shown in the previous recipe. The following RemoveProjectsRecursive procedure will delete a specified vertex and all vertices that fall underneath it:

CREATE PROCEDURE RemoveProjectsRecursive
@VertexId INTEGER
AS
   SET NOCOUNT ON
   DECLARE @LocalVertex INTEGER
   SELECT @LocalVertex=@VertexId

   DECLARE subprojects CURSOR LOCAL FOR
      SELECT VertexId FROM Projects WHERE Parent=@VertexId      

   OPEN subprojects
      FETCH NEXT FROM subprojects INTO @LocalVertex
      WHILE @@FETCH_STATUS=0 BEGIN
         EXEC RemoveProjectsRecursive @LocalVertex
         FETCH NEXT FROM subprojects INTO @LocalVertex
      END
    
   CLOSE subprojects
   DEALLOCATE subprojects

   DELETE FROM Projects WHERE VertexId=@VertexId

   PRINT 'Vertex ' +CONVERT(VARCHAR(8),@VertexId) + ' removed!'

To delete a vertex, simply invoke the RemoveProjectsRecursive procedure and pass in the vertex ID as a parameter. In the following example, the procedure is used to delete the vertex for Specifications, which happens to be vertex 2:

RemoveProjectsRecursive 2

Vertex 3 removed!
Vertex 4 removed!
Vertex 5 removed!
Vertex 7 removed!
Vertex 6 removed!
Vertex 2 removed!

Six rows were deleted as a result of deleting the Specifications vertex. Four of the rows are for the four children, one row is for a child of a child, and the sixth row is for the Specifications vertex, itself. This procedure always deletes the parent nodes last to avoid any foreign-key violations.

4.8.3 Discussion

Obviously, adding new members to a hierarchy is fairly easy since a hierarchical structure does not have any limitations on the number of children or levels of hierarchy that you can have. Inserting a new row under a parent is easy.

For deleting, we used the traversing algorithm from the previous recipe. When we adapted that algorithm for deleting a vertex, we were careful to have it remove all children before finally removing a parent node. If a parent is removed before its children, the table would contain nodes with no parents. Such nodes would need to be collected and eliminated using a specially coded garbage-collection mechanism. While such a mechanism is possible, you have the problem of how to differentiate valid parent-free nodes (project roots) from the orphan nodes that remain because you deleted their parents.

The algorithm shown in this recipe is fairly efficient; it removes leaf nodes and parent nodes with the same procedure, and it does not result in significant overhead if you are removing just a leaf vertex.