4.9 Aggregating Hierarchies

4.9.1 Problem

You want to aggregate hierarchical data. For example, you wish to sum the cost of a project or task, beginning from a specific vertex and working your way down through all levels of the hierarchy underneath that vertex.

4.9.2 Solution

With respect to the projects example that we have been using for these general hierarchy recipes, you can use the following stored procedure to summarize the costs of all subprojects for a specific project. You specify the project by passing its vertex ID as a parameter to the procedure.

CREATE PROCEDURE AggregateProjects
@VertexId INTEGER
AS
SET NOCOUNT ON
   DECLARE @lvl INTEGER
   DECLARE @Name VARCHAR(20) 
   DECLARE @Cost INTEGER
   DECLARE @Sum INTEGER

   CREATE TABLE #stack (
      VertexId INTEGER, 
      Name VARCHAR(20),
      Cost INTEGER,
      Lvl INTEGER
   )
   
   SELECT @Sum=0
   SELECT @Lvl = 1
   
   INSERT INTO #stack 
      SELECT VertexId, Name, Cost, 1 FROM Projects 
      WHERE VertexID=@VertexId  
   
   WHILE @Lvl > 0 BEGIN
      IF EXISTS (SELECT * FROM #stack WHERE lvl = @lvl) BEGIN

         SELECT TOP 1 @VertexId = VertexId, @Name=Name, @Cost=Cost 
            FROM #stack WHERE lvl = @lvl
            ORDER BY VertexId

         /* to change action each vertex, change this line */
         SELECT @Sum=@Sum+@Cost
         /* ******* */

         DELETE FROM #stack WHERE vertexId = @VertexId

         INSERT #stack
            SELECT VertexId, Name, Cost, @lvl + 1 
            FROM Projects WHERE parent = @VertexId

         IF @@ROWCOUNT > 0
            SELECT @lvl = @lvl + 1
      END ELSE 
         SELECT @lvl = @lvl - 1
      
   END
   PRINT 'Sum of project costs is '+STR(@Sum)+'.'
   DROP TABLE #stack
SET NOCOUNT OFF

The following examples show the results of executing this procedure for all projects (VertexId=1) and for the Specifications project (VertexId=2).

AggregateProjects 1
Sum of project costs is         231.

AggregateProjects 2
Sum of project costs is         33.

4.9.3 Discussion

The algorithm shown here is adapted from the SQL Server Books Online recommendation for expanding hierarchies. Those familiar with algorithms and data structures will notice that it is a nonrecursive implementation of a recursive traversing algorithm. The code uses an internal stack implemented as a temporary table. The stack holds interesting information from the hierarchical Projects table, plus an additional column named lvl. The lvl column records the level that each entry holds in the hierarchy. The stack definition is as follows:

CREATE TABLE #stack (
      VertexId INTEGER, 
      Name VARCHAR(20),
      Cost INTEGER,
      Lvl INTEGER
   )

After the #stack table is created, two variables are initialized. The @lvl variable tracks the current level on which the code is operating, while the @sum variable accumulates the sum of all costs. Next, an INSERT statement is used to store the root onto the stack. Note that the root in our case is the vertex identified by @VertexId.

The code then loops through each element on the stack. The loop begins by popping one element from the stack. The retrieved data contains a cost, which is added to the total cost being accumulated in @sum:

SELECT TOP 1 @VertexId = VertexId, @Name=Name, @Cost=Cost 
   FROM #stack WHERE lvl = @lvl
   ORDER BY VertexId

SELECT @Sum=@Sum+@Cost

After accumulating the cost for the vertex just pulled from the stack, the code deletes that read vertex and adds all of its children to the stack:

DELETE FROM #stack WHERE vertexId = @VertexId

INSERT #stack
   SELECT VertexId, Name, Cost, @lvl + 1 
   FROM Projects WHERE parent = @VertexId

IF @@ROWCOUNT > 0
   SELECT @lvl = @lvl + 1

The IF statement that you see in this code ensures that if the vertex just deleted from the stack has any children, the @lvl value is increased to indicate that the code is moving one level down in the hierarchy.

The IF EXISTS clause at the beginning of the loop ensures that so long as there are some candidates available on the current level, the loop repeats and browses through them all. The SET NOCOUNT ON directive at the beginning of the procedure just limits the number of messages displayed from the procedure. It does not affect the logic of the algorithm. Without SET NOCOUNT ON, you'll see a steady stream of "(1 row(s) affected)" messages as the code executes.

This algorithm is general enough that it can be used for any kind of operation for which you prefer traversing the hierarchy in a nonrecursive manner. If you want to change the operation that is performed on each node, change the code where current cost is added to the total sum.

The code demonstrates why the general model for hierarchies has a limited application in SQL. When you need to traverse over more than one level efficiently, the code starts to expand to an almost unreadable size.