Learn how to a build a cloud-first strategyRegister Now

  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1490
  • Last Modified:

Tree Walking with SQL server

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?
  • 2
1 Solution
dcparAuthor Commented:
Edited text of question
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.


dcparAuthor Commented:
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 f2.id = 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 f2.id = 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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now