Tree Walking with SQL server

Posted on 1999-01-14
Last Modified: 2008-02-26
I have a table with a self-referencing foreign key on its own primary key, allowing me to implement a hierarchical tree. It's easy to select the immediate children of a particular row, but how do I retrieve all descendents under a particular record? I know that Oracle has the CONNECT BY statement to handle this, but how would I implement this in SQL server?
Question by:dcpar
  • 2

Author Comment

ID: 1092650
Edited text of question

Accepted Solution

cognition earned 200 total points
ID: 1092651
Databases often store hierarchical information. The following data, for example, is a hierarchical representation of regions of the world:
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 representation does not clearly show the structure implied by the data. The following example is easier to interpret:
      North America
            United States
                  New York
                        New York City
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. (Note that this example is for illustration only and it does not come from the pubs database.)
create proc 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
      if exists (select * from #stack where level = @level)
                  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
            select @level = @level - 1
In this example, the input parameter (@current) is used to indicate 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), choose one and call it @current.
      2.      Indent the item @level spaces, and then print the item.
      3.      Delete the item from the stack so it won't be processed again, and then add all its child items to the stack at the next level (@level  1).

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.

This is the only place where the hierarchy table (#stack) is used.
      4.      If there are child items (IF @@ROWCOUNT > 0), descend one level to process them (@level = @level  1); otherwise, continue processing at the current level.
      5.      Finally, if there are no items on the stack awaiting processing at the current level, go 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.



Author Comment

ID: 1092652
I also came up with a way to recursively delete a particular record and its children, provided a delete flag is used. This example illustrates deleting a folder and documents contained within and its children.

      @id int

UPDATE Folder set deleted=1 where id=@id
UPDATE Document set deleted=1 where folderid=@id
WHILE (SELECT max(id) from Folder f where deleted=0 and
      (SELECT count(*) from Folder f2 where = f.parentfolderid and deleted = 1)>0) IS NOT NULL
      DECLARE @@temp_id int
      SELECT @@temp_id = (select max(id) from Folder f where deleted=0 and
             (select count(*) from Folder f2 where = f.parentfolderid and deleted = 1)>0)
      UPDATE Folder set deleted=1 where id=@@temp_id
      UPDATE Document set deleted=1 where folderid=@@temp_id

Featured Post

NAS Cloud Backup Strategies

This article explains backup scenarios when using network storage. We review the so-called “3-2-1 strategy” and summarize the methods you can use to send NAS data to the cloud

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Help in Bulk Insert 9 34
SQL - Update field defined as Text 6 17
SQL Server 2015 Restore - doing it right 2 14
SQL invalid column name 5 13
Slowly Changing Dimension Transformation component in data task flow is very useful for us to manage and control how data changes in SSIS.
I have a large data set and a SSIS package. How can I load this file in multi threading?
This video shows, step by step, how to configure Oracle Heterogeneous Services via the Generic Gateway Agent in order to make a connection from an Oracle session and access a remote SQL Server database table.
Viewers will learn how to use the SELECT statement in SQL and will be exposed to the many uses the SELECT statement has.

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question