Section 4.7. Traversing Hierarchies Recursively

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.