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

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
PL/SQL query 14 51
MS SQL 2014 get SPIDs of users 6 27
TSQL cursor within a batch takes long time.. 16 20
Syntax using Declare 3 16
For both online and offline retail, the cross-channel business is the most recent pattern in the B2C trade space.
Ever wondered why sometimes your SQL Server is slow or unresponsive with connections spiking up but by the time you go in, all is well? The following article will show you how to install and configure a SQL job that will send you email alerts includ…
This video shows how to set up a shell script to accept a positional parameter when called, pass that to a SQL script, accept the output from the statement back and then manipulate it in the Shell.
Viewers will learn how to use the UPDATE and DELETE statements to change or remove existing data from their tables. Make a table: Update a specific column given a specific row using the UPDATE statement: Remove a set of values using the DELETE s…

747 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

12 Experts available now in Live!

Get 1:1 Help Now