4.7 Traversing Hierarchies Recursively

4.7.1 Problem

You need to step through a hierarchy and print out a report listing all vertices. You want the report to show the hierarchical nature of the data by indenting children under their parent node.

4.7.2 Solution

One solution is to use a recursive algorithm to traverse the tree. To do that, encapsulate the algorithm in a stored procedure. The following code creates a stored procedure named TraversProjectsRecursive. The stored procedure takes one argument, specifying from which node to begin. The procedure then works its way down through that node's children, grandchildren, and so forth.

CREATE PROCEDURE TraverseProjectsRecursive
@VertexId INTEGER
AS
   /* to change action on each vertex, change these lines */
   DECLARE @Name VARCHAR(20)
   SELECT @Name=(SELECT Name 
                    FROM Projects WHERE VertexId=@VertexId) 
   PRINT SPACE(@@NESTLEVEL*2)+STR(@VertexId)+' '+@Name
   /* ****** */

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

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

When calling the procedure, you need to specify the initial node from which you want the procedure to start traversing. If you want to print out the entire hierarchy, then specify the root node (in our case 1). For example:

 TraverseProjectsRecursive 1
 
 1 New SW
   2 Specifications
     3 Interviews
     4 Drafts
     5 Consolidations
     6 Final document
       7 Presentation
   8 Prototype
     9 UI Design
     10 Calculations
       11 Correctness Testing
     12 Database
   13 Development
     14 UI Implementation
     15 Coding
     16 Inital testing
   17 Beta testing
     18 Final adjustments
   19 Production testing

4.7.3 Discussion

The algorithm used by the TraverseProjectsRecursive procedure is a classical tree-traversal method adapted to the specifics of SQL. You can easily adapt this procedure for use with other hierarchical structures besides the projects structure shown in this chapter. To adapt this procedure, change only the SELECT and PRINT statements.

When you create a recursive procedure such as the one shown here, MS SQL Server will warn you with a message such as the following: "Cannot add rows to sysdepends for the current stored procedure because it depends on the missing object 'TraverseProjectsRecursive.' The stored procedure will still be created.'' Do not worry about this message. Recursive procedures are a special case, and you can safely ignore the warning.

The first SELECT statement in the procedure retrieves the name associated with the vertex that is passed in as a parameter. That name is placed into the @Name variable, which is then used in the subsequent PRINT statement:

PRINT SPACE(@@NESTLEVEL*2)+STR(@VertexId)+' '+@Name 

In this PRINT statement, we use the @@NESTLEVEL variable. That variable is maintained automatically by SQL Server and returns the current nesting level. This information is a great advantage when working with stored procedures. In our case, we want to indent every project proportionally to its depth. To do that, we multiply the nesting level by two to indent each child two spaces underneath its parent.

After we print the name of the current vertex, we need to go forward to its children. A vertex can have more than one child, so we define a cursor to select these:

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

This cursor definition uses the LOCAL clause, ensuring that the cursor is defined for the current procedure only. By default, cursors are global, which means that any cursor defined is visible from all code executed within the current connection. Since this procedure calls itself repeatedly within the context of one connection, we must specify that this cursor definition be local to each invocation of the procedure.

After opening the subprojects cursor, we simply step through the list of subprojects and recursively invoke the TraverseProjectsRecursive procedure on each one:

FETCH NEXT FROM subprojects INTO @VertexId
   WHILE @@FETCH_STATUS=0 BEGIN
      EXEC TraverseProjectsRecursive @VertexId
      FETCH NEXT FROM subprojects INTO @VertexId
   END

Even though the recursive mechanisms are very elegant, they are not very efficient. Furthermore, in SQL Server they have a limit of only 32 nesting levels. If you query your hierarchy infrequently, then the overhead of recursion may be acceptable, and you need not bother with other mechanisms. However, if you do this type of thing often, some further optimizations might be necessary to give you adequate performance. Sometimes it's useful to use recursion for prototyping, because recursive solutions are simple to code. Later, you can optimize your code with a nonrecursive solution before you go to production.