Simplest way to do a recursive self-join?

Question

What is the simplest way of doing a recursive self-join in SQL Server? I have a table like this:

PersonID | Initials | ParentID
1          CJ         NULL
2          EB         1
3          MB         1
4          SW         2
5          YT         NULL
6          IS         5

And I want to be able to get the records only related to a hierarchy starting with a specific person. So If I requested CJ's hierarchy by PersonID=1 I would get:

PersonID | Initials | ParentID
1          CJ         NULL
2          EB         1
3          MB         1
4          SW         2

And for EB's I'd get:

PersonID | Initials | ParentID
2          EB         1
4          SW         2

I'm a bit stuck on this can can't think how to do it apart from a fixed-depth response based on a bunch of joins. This would do as it happens because we won't have many levels but I would like to do it properly.

Thanks! Chris.

Solution 1

WITH    q AS 
        (
        SELECT  *
        FROM    mytable
        WHERE   ParentID IS NULL -- this condition defines the ultimate ancestors in your chain, change it as appropriate
        UNION ALL
        SELECT  m.*
        FROM    mytable m
        JOIN    q
        ON      m.parentID = q.PersonID
        )
SELECT  *
FROM    q

By adding the ordering condition, you can preserve the tree order:

WITH    q AS 
        (
        SELECT  m.*, CAST(ROW_NUMBER() OVER (ORDER BY m.PersonId) AS VARCHAR(MAX)) COLLATE Latin1_General_BIN AS bc
        FROM    mytable m
        WHERE   ParentID IS NULL
        UNION ALL
        SELECT  m.*,  q.bc + '.' + CAST(ROW_NUMBER() OVER (PARTITION BY m.ParentID ORDER BY m.PersonID) AS VARCHAR(MAX)) COLLATE Latin1_General_BIN
        FROM    mytable m
        JOIN    q
        ON      m.parentID = q.PersonID
        )
SELECT  *
FROM    q
ORDER BY
        bc

By changing the ORDER BY condition you can change the ordering of the siblings.

Solution 2

Using CTEs you can do it this way

DECLARE @Table TABLE(
        PersonID INT,
        Initials VARCHAR(20),
        ParentID INT
)

INSERT INTO @Table SELECT     1,'CJ',NULL
INSERT INTO @Table SELECT     2,'EB',1
INSERT INTO @Table SELECT     3,'MB',1
INSERT INTO @Table SELECT     4,'SW',2
INSERT INTO @Table SELECT     5,'YT',NULL
INSERT INTO @Table SELECT     6,'IS',5

DECLARE @PersonID INT

SELECT @PersonID = 1

;WITH Selects AS (
        SELECT *
        FROM    @Table
        WHERE   PersonID = @PersonID
        UNION ALL
        SELECT  t.*
        FROM    @Table t INNER JOIN
                Selects s ON t.ParentID = s.PersonID
)
SELECT  *
FROm    Selects

Solution 3

The Quassnoi query with a change for large table. Parents with more childs then 10: Formating as str(5) the row_number()

WITH    q AS 
        (
        SELECT  m.*, CAST(str(ROW_NUMBER() OVER (ORDER BY m.ordernum),5) AS VARCHAR(MAX)) COLLATE Latin1_General_BIN AS bc
        FROM    #t m
        WHERE   ParentID =0
        UNION ALL
        SELECT  m.*,  q.bc + '.' + str(ROW_NUMBER()  OVER (PARTITION BY m.ParentID ORDER BY m.ordernum),5) COLLATE Latin1_General_BIN
        FROM    #t m
        JOIN    q
        ON      m.parentID = q.DBID
        )
SELECT  *
FROM    q
ORDER BY
        bc

Solution 4

Check following to help the understand the concept of CTE recursion

DECLARE
@startDate DATETIME,
@endDate DATETIME

SET @startDate = '11/10/2011'
SET @endDate = '03/25/2012'

; WITH CTE AS (
    SELECT
        YEAR(@startDate) AS 'yr',
        MONTH(@startDate) AS 'mm',
        DATENAME(mm, @startDate) AS 'mon',
        DATEPART(d,@startDate) AS 'dd',
        @startDate 'new_date'
    UNION ALL
    SELECT
        YEAR(new_date) AS 'yr',
        MONTH(new_date) AS 'mm',
        DATENAME(mm, new_date) AS 'mon',
        DATEPART(d,@startDate) AS 'dd',
        DATEADD(d,1,new_date) 'new_date'
    FROM CTE
    WHERE new_date < @endDate
    )
SELECT yr AS 'Year', mon AS 'Month', count(dd) AS 'Days'
FROM CTE
GROUP BY mon, yr, mm
ORDER BY yr, mm
OPTION (MAXRECURSION 1000)

Solution 5

SQL 2005 or later, CTEs are the standard way to go as per the examples shown.

SQL 2000, you can do it using UDFs -

CREATE FUNCTION udfPersonAndChildren
(
    @PersonID int
)
RETURNS @t TABLE (personid int, initials nchar(10), parentid int null)
AS
begin
    insert into @t 
    select * from people p      
    where personID=@PersonID

    while @@rowcount > 0
    begin
      insert into @t 
      select p.*
      from people p
        inner join @t o on p.parentid=o.personid
        left join @t o2 on p.personid=o2.personid
      where o2.personid is null
    end

    return
end

(which will work in 2005, it's just not the standard way of doing it. That said, if you find that the easier way to work, run with it)

If you really need to do this in SQL7, you can do roughly the above in a sproc but couldn't select from it - SQL7 doesn't support UDFs.

View more solutions

Comments

[boydc7]

Which version of SQL Server are you using? i.e. Sql 2000, 2005, 2008?

[OMG Ponies]

SO questions regarding recursive queries: stackoverflow.com/search?q=sql-server+recursive

[Can Sahin]

+1, except that Chris would need PersonID = theIdYouAreLookingFor instead of ParentID IS NULL.

[Kishore Kumar]

I have posted a new question on SO, stackoverflow.com/questions/13535003/…

[Oli B]

Good complete answer with the important WHERE PersonID = @PersonID

[Quassnoi]

@Aaroninus: The parent node is defined by the topmost (anchor) query in the WITH clause. If you need specifics, please create a fiddle on sqlfiddle.com and post the link here.

[Josh McGee]

This query doesn't work for me until I change the first line to "WITH RECURSIVE q AS", for reference I'm using "10.3.23-MariaDB-0+deb10u1"

[Quassnoi]

@JoshMcGee: why did you expect an SQL Server query work on MariaDB without changes?

[Josh McGee]

just posting for reference in case someone else using MariaDB has the same problem