Expanding Hierarchies

Databases often store hierarchical information. For example, the following data is a hierarchical representation of regions of the world. This representation does not clearly show the structure implied by the data.

Parent                             Child                            

---------------------------------- ----------------------------------

World                              Europe                           

World                              North America                    

Europe                             France                           

France                             Paris                            

North America                      United States                    

North America                      Canada                           

United States                      New York                         

United States                      Washington                       

New York                           New York City                    

Washington                         Redmond                          

  

This example is easier to interpret:

World

    North America

        Canada

        United States

            Washington

                Redmond

            New York

                New York City

    Europe

        France

            Paris

  

The following Transact-SQL procedure expands an encoded hierarchy to any arbitrary depth. Although Transact-SQL supports recursion, it is more efficient to use a temporary table as a stack to keep track of all of the items for which processing has begun but is not complete. When processing is complete for a particular item, it is removed from the stack. New items are added to the stack as they are identified.

CREATE PROCEDURE expand (@current char(20)) as

SET NOCOUNT ON

DECLARE @level int, @line char(20)

CREATE TABLE #stack (item char(20), level int)

INSERT INTO #stack VALUES (@current, 1)

SELECT @level = 1

  

WHILE @level > 0

BEGIN

    IF EXISTS (SELECT * FROM #stack WHERE level = @level)

        BEGIN

            SELECT @current = item

            FROM #stack

            WHERE level = @level

            SELECT @line = space(@level - 1) + @current

            PRINT @line

            DELETE FROM #stack

            WHERE level = @level

                AND item = @current

            INSERT #stack

                SELECT child, @level + 1

                FROM hierarchy

                WHERE parent = @current

            IF @@ROWCOUNT > 0

                SELECT @level = @level + 1

        END

    ELSE

        SELECT @level = @level - 1

END -- WHILE

  

The input parameter (@current) indicates the place in the hierarchy to start. It also keeps track of the current item in the main loop.

The two local variables used are @level, which keeps track of the current level in the hierarchy, and @line, which is a work area used to construct the indented line.

The SET NOCOUNT ON statement avoids cluttering up the output with ROWCOUNT messages from each SELECT.

The temporary table, #stack, is created and primed with the item identifier of the starting point in the hierarchy, and @level is set to match. The level column in #stack allows the same item to appear at multiple levels in the database. Although this situation does not apply to the geographic data in the example, it can apply in other examples.

In this example, when @level is greater than 0, the procedure follows several steps:

  1. If there are any items in the stack at the current level (@level), the procedure chooses one and calls it @current.
  2. Indents the item @level spaces, and then prints the item.
  3. Deletes the item from the stack so it won’t be processed again, and then adds all its child items to the stack at the next level (@level + 1). This is the only place where the hierarchy table (#stack) is used.

    Note With a conventional programming language, you would have to find each child item and add it to the stack individually. With Transact-SQL, you can find all child items and add them with a single statement, avoiding another nested loop.


  4. If there are child items (IF @@ROWCOUNT > 0), descends one level to process them (@level = @level + 1); otherwise, continues processing at the current level.
  5. Finally, if there are no items on the stack awaiting processing at the current level, goes back up one level to see if there are any awaiting processing at the previous level (@level = @level - 1). When there is no previous level, the expansion is complete.

  


(c) 1988-98 Microsoft Corporation. All Rights Reserved.