Databases often store hierarchical information. For example, consider the following table, which contains data that hierarchically represents the regions of the world.
CREATE TABLE Hierarchy (Parent VARCHAR(20) NOT NULL, Child VARCHAR(20), CONSTRAINT UIX_ParentChild UNIQUE NONCLUSTERED (Parent,Child)) CREATE CLUSTERED INDEX CIX_Parent ON Hierarchy(Parent) GO INSERT Hierarchy VALUES('World','Europe') INSERT Hierarchy VALUES('World','North America') INSERT Hierarchy VALUES('Europe','France') INSERT Hierarchy VALUES('France','Paris') INSERT Hierarchy VALUES('North America','United States') INSERT Hierarchy VALUES('North America','Canada') INSERT Hierarchy VALUES('United States','New York') INSERT Hierarchy VALUES('United States','Washington') INSERT Hierarchy VALUES('New York','New York City') INSERT Hierarchy VALUES('Washington','Redmond') GO
This representation does not show clearly 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 @lvl int, @line char(20) CREATE TABLE #stack (item char(20), lvl int) INSERT INTO #stack VALUES (@current, 1) SELECT @lvl = 1 WHILE @lvl > 0 BEGIN IF EXISTS (SELECT * FROM #stack WHERE lvl = @lvl) BEGIN SELECT @current = item FROM #stack WHERE lvl = @lvl SELECT @line = space(@lvl - 1) + @current PRINT @line DELETE FROM #stack WHERE lvl = @lvl AND item = @current INSERT #stack SELECT Child, @lvl + 1 FROM Hierarchy WHERE Parent = @current IF @@ROWCOUNT > 0 SELECT @lvl = @lvl + 1 END ELSE SELECT @lvl = @lvl - 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 local variables used are @lvl, 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 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 @lvl is set to match. The lvl 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 @lvl is greater than 0, the procedure follows these steps:
- If there are any items in the stack at the current level (@lvl), the procedure chooses one and calls it @current.
- Indents the item @lvl spaces, and then prints the item.
- Deletes the item from the stack so it will not be processed again, and then adds all its child items to the stack at the next level (@lvl + 1). This is the only place where the hierarchy table (#stack) is used.
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.
- If there are child items (IF @@ROWCOUNT > 0), descends one level to process them (@lvl = @lvl + 1); otherwise, continues processing at the current level.
- If there are no items on the stack awaiting processing at the current level, goes back one level to see if there are any awaiting processing at the previous level (@lvl = @lvl - 1). When there is no previous level, the expansion is complete.
Executing the procedure expand with different parameters will return result sets illustrating the level in the hierarchy in which the specified parameter belongs.
EXEC expand 'World' --This is the result set. World North America United States Washington Redmond New York New York City Canada Europe France Paris EXEC expand 'United States' --This is the result set. United States Washington Redmond New York New York City