4.7 Traversing Hierarchies Recursively4.7.1 ProblemYou 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 SolutionOne 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 DiscussionThe 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.
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. |