sqlsql-servercommon-table-expressionfamily-treerecursive-cte

Recursive CTE for a family tree keeps going into an infinite loop


I am trying to design a RDBM model for a family tree using SQL Server and currently I have the 3 tables that looks somewhat as follows

Members - Stores basic details of members of the family.

---------------------
| ID    | Firstname |
---------------------
  1000  Ranjith
  1001  Shilpa
  1002  Ramamkrishna
  1003  Jayasree
  1004  Sabarinadhan
  1005  Sushama
  1006  Shyamala
  1007  Mukundarao
  1008  Ramadevi
  1009  Gopinath
  1010  Reshmi
  1011  Raj
  1012  Pratham

Families - Stores the Members.ID of the patners that were together

------------------------------
| ID    | Spouse1 | Spouse2 |
------------------------------
  1     1002        1003
  2     1000        1001
  3     1004        1005
  4     1006        1007
  5     1008        1009
  6     1010        1011

Families_Children - Stores the Families.ID of each family and the Member.ID of the children of that family.

------------------------------
| ID    | FamilyID | ChildId |
------------------------------
    1       1         1000
    2       3         1001
    3       4         1002
    4       4         1008
    5       5         1010
    6       6         1012

What I want now is to use a recursive CTE to travese the tree given a member ID. So if I give a member ID as 1007, I want to find all families they are part of and then their children's families till the last node in the that particular tree. This is the query I have so far

WITH family_tree AS (
    SELECT 
        f.Id as FamilyId, 
        f.Spouse1Id as Spouse1Id,
        mfs1.FirstName as Spouse1,
        f.Spouse2Id as Spouse2Id,
        mfs2.FirstName as Spouse2,
        fc.ChildId as ChildId,
        mc.FirstName as Child
    FROM Families f
    INNER JOIN Families_Children fc
        ON fc.FamilyId = f.Id
    INNER JOIN Members mfs1
        ON mfs1.Id = f.Spouse1Id
    INNER JOIN Members mfs2
        ON mfs2.Id = f.Spouse2Id
    INNER JOIN Members mc
        ON mc.Id = fc.ChildId
    WHERE f.Spouse1Id = 1007 OR f.Spouse2Id = 1007
    
    UNION ALL
        
        SELECT
            ft.FamilyId, 
            ft.Spouse1Id,
            ft.Spouse1,
            ft.Spouse2Id,
            ft.Spouse2,
            ft.ChildId,
            ft.Child
        FROM 
            Families f, family_tree ft
        WHERE ft.ChildId = f.Spouse1Id OR ft.ChildId = f.Spouse2Id
)

SELECT * from family_tree;

The first part of the CTE (family_tree) is pretty straight forward and returns the family where the member with ID 1007 is part of.

------------------------------------------------------------------
|FamilyId| Spouse1Id| Spouse1| Spouse2Id| Spouse2 | ChildId| Child
------------------------------------------------------------------
  4       1006      Shyamala  1007    Mukundarao  1002    Ramamkrishna
  4       1006      Shyamala  1007    Mukundarao  1008    Ramadevi

In the union, I am trying to recurse through the Families table again for each row returned by the family_tree where the child in the family is either spouse1 or spouse2. But the entire thing just keeps going into an infinite loop and I can't figure out what's wrong with the termination clause. Any help would really be appreciated.

Thanks.


Solution

  • I took siggemannen's advice and updated the DB model to have a single Member_Parents table

    CREATE TABLE Member_Parents(
        Id INT NOT NULL IDENTITY PRIMARY KEY,
        MemberId INT NOT NULL FOREIGN KEY REFERENCES Members(Id),
        ParentId INT NOT NULL FOREIGN KEY REFERENCES Members(Id),
    );
    

    and was able to solve the problem pretty quickly as follows

    WITH Family_Tree AS (
        SELECT 
            mp.MemberId,
            mp.ParentId
        FROM
            Member_Parents mp
        WHERE mp.ParentID = 1008
    
        UNION ALL
    
        SELECT
            mp.MemberId,
            mp.ParentId
        FROM
            Member_Parents mp,
            Family_Tree ft
        WHERE mp.ParentID = ft.MemberId
    )
    
    SELECT 
        ft.MemberId,
        mm.FirstName AS Member,
        ft.ParentId,
        mp.FirstName AS Parent
    FROM Family_Tree ft
    INNER JOIN Members mm
        ON mm.Id = ft.MemberId
    INNER JOIN Members mp
        ON mp.Id = ft.ParentId
    

    The query turned out to be pretty straight forward without too many joins. I also agree that my CTE was incorrect and I guess it was due to my understanding of the recursive CTE (learnt it just a couple of days back).

    It would really be appreciated if you could review this query.

    I am now trying to figure out a way to fetch the ancestors for a given member (traverse up the tree).

    Thanks.

    UPDATE Was able to quickly get the ancestor tree as well for a give member

    WITH Ancestor_Tree AS (
        SELECT 
            mp.MemberId,
            mp.ParentId
        FROM
            Member_Parents mp
        WHERE mp.MemberId = 1012
    
        UNION ALL
    
        SELECT
            mp.MemberId,
            mp.ParentId
        FROM
            Member_Parents mp,
            Ancestor_Tree ft
        WHERE mp.MemberId = ft.ParentId
    )
    
    SELECT 
        ft.MemberId,
        mm.FirstName AS Member,
        ft.ParentId,
        mp.FirstName AS Parent
    FROM Ancestor_Tree ft
    INNER JOIN Members mm
        ON mm.Id = ft.MemberId
    INNER JOIN Members mp
        ON mp.Id = ft.ParentId