Need help with recursion in SQL Server 2005

Question

I am representing a tree in a table, and I need to be able to get the root node (TOP ID) of a specific element. The root node always has a ParentID of null. For example, if the table looks like this:

ID   ParentID
1   null
2   null
3   null
4   2
5   1
6   2
7   6
8   4
9   8
10  6

When ID=10, the TOP ID = 2; when ID=9, the TOP ID = 3; and so on. Is it possible to write a SQL server function, which returns TOP ID when given ID?

Answer 1

MSDN has a pretty good set of examples for using Common Table Expressions to write recursive queries. It was a big pain in the rear to do these prior to SQL Server 2005 (dealing with that exact problem in an old Server 2000 app right now).

Answer 2

MSDN brough up this article which will most likely explain it better than you are likely to get in the format we are allowed on this sight.

Answer 3

Here is a recursive example from a sproc I have that will find the Parent (parent ID = null) for any given ID - (@ID) given to the sproc. Is this whaat you're looking for?

    WITH recurseUp (ID, ParentID)
    AS
    (
     SELECT ID, ParentID
     FROM myTable
     WHERE ID = @ID 
     UNION ALL
     SELECT b.ID, b.ParentID
     FROM recurseUp a JOIN myTable b 
     ON (a.ParentID = b.ID)
    )
SELECT ID FROM recurseUP WHERE ParentID is null

Answer 4

It's possible, but the only method I know is to use a CURSOR and a recursive stored procedure. This is a really bad way to do things from a performance standpoint (usually). If possible you may want to consider the cost of having an extra root parent node that you keep updated via code as you move along.

Answer 5

WITH    q AS
        (
        SELECT  id, parentID
        FROM    mytable
        WHERE   id = 10
        UNION ALL
        SELECT  mytable.id, mytable.parentid
        FROM    q
        JOIN    mytable
        ON      mytable.parentId = q.id
        )
SELECT  *
FROM    q
WHERE   parentID IS NULL

Answer 6

Recursion in SQL prior to SQL 2003 (i.e. SQL Server 2000) is somewhat ugly; for each level in your tree you'd need to write a separate join statement back onto the original table. Provided that the number of levels in your hierarchy is fixed you could write something like this.

create table #Hell (
parent int,
id int,
name varchar(30)
)

insert into #Hell values (NULL, 1, 'The Boss')
insert into #Hell values (1, 2, 'The Boss'' PA')
insert into #Hell values (1, 3, 'Production Director')
insert into #Hell values (3, 4, 'Jim''l Fixit')


select * from #Hell H1
inner join #Hell H2
ON H1.id=H2.parent
inner join #Hell H3
ON H2.id=H3.parent
WHERE H3.Id=4  --Find the boss for Jim

drop table #Hell

Luckily SQL Server 2005 has a with common table expression that allows recursive operations to be written quite easily. See See http://www.4guysfromrolla.com/webtech/071906-1.shtml

You should also be aware of the various ways of representing trees in a database. Take a look at the slides on Trees in SQL from this presentation http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back