Recursive select with inner join

Question

So I'm trying to write a recursive query that will get an item and it's parents. The problem is my structure can have many parents and the query isn't getting the last row. The structure is:

Entity

Id |
1  |
2  |
3  |


EntityMembership

ChildId | ParentId
3       | 2
2       | 1

And so far the query looks like :

with results(BaseId, Id, ParentId) as
(
 select e.id as BaseId, e.id, em.parentid
 from entity e
 left join EntityMembership em on e.Id = em.ChildID
 union all
 select r.BaseId, e.id, em.parentid
 from entity e
 inner join EntityMembership em on e.Id = em.ChildID
 inner join results r on r.parentid = e.id
 where r.Id<> r.ParentId
)
select results.Id
from results
where BaseId = 3

Which comes out as:

3 |
2 |

Obviously the inner join is preventing the "1" from appearing in the results because it doesn't have a parent, but I have no idea how to rewrite this to include it.

Answer 1

The problem is that you are doing an inner join on EntityMembership in the second part of your CTE, so you aren't getting "1" in the results. It should be an outer join (as in the first part), but you aren't allowed to have an outer join in a recursive CTE. My solution is to join Entity and EntityMembership ahead of time in another CTE and use that in the recursion instead.

with joined(ChildId, ParentId) as
(select e.id, em.parentid
 from entity e 
 left outer join entitymembership em on em.childid = e.id
 ), 
 results(BaseId, Id, ParentId) as
(
 select j.ChildId as BaseId, j.ChildId, j.parentid
 from joined j 
 union all
 select r.BaseId, j.ChildId, j.parentid
 from joined j
 inner join results r on r.parentid = j.ChildId
 where r.Id <> r.ParentId
)

select Id
from results
where BaseId = 3

Here's a slightly different way to write it, filtering on the child Id inside the CTE instead of afterwards:

with joined(ChildId, ParentId) as
(select e.id, em.parentid
 from entity e 
 left outer join entitymembership em on em.childid = e.id
 )
,results(ChildId, ParentId) as
(
 select j.childid, j.parentid
 from joined j
 where j.childid = 3
 union all
 select j.childid, j.parentid
 from joined j
 join results r on r.parentid = j.childid 
)


select ChildId
from results