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

Windows Server 2016: All you need to know

Learn about Hyper-V features that increase functionality and usability of Microsoft Windows Server 2016. Also, throughout this eBook, you’ll find some basic PowerShell examples that will help you leverage the scripts in your environments!

Question has a verified solution.

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

When you hear the word proxy, you may become apprehensive. This article will help you to understand Proxy and when it is useful. Let's talk Proxy for SQL Server. (Not in terms of Internet access.) Typically, you'll run into this type of problem w…
For both online and offline retail, the cross-channel business is the most recent pattern in the B2C trade space.
Familiarize people with the process of utilizing SQL Server functions from within Microsoft Access. Microsoft Access is a very powerful client/server development tool. One of the SQL Server objects that you can interact with from within Microsoft Ac…
This videos aims to give the viewer a basic demonstration of how a user can query current session information by using the SYS_CONTEXT function

863 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

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now