Recursive CTE - recalculate the tree after exclusions

Viewed 97

Lets say I have a table called #OrgList

CREATE TABLE #OrgList (
    OrgUnitId int,
    ParentOrgUnitId int,
    PersonId int,
    isExcluded bit
);

INSERT INTO #OrgList(OrgUnitId, ParentOrgUnitId, PersonId, isExcluded) VALUES
    (1, NULL, 100, 0), (2,1, 101, 0), (3,1,102,0), (4,2,103,1), (5,2,104,0), (6,3,105,0), (7,4,106,0), (8,4,107,0), (9,4,108,0), (10,4,109,0), (11,4,110,1), (12,11,111,0)

My hierarchy tree structure looks like this

enter image description here

and my cte like this:

    ;
with cte as (
select OrgUnitId, ParentOrgUnitId, PersonId, isExcluded , 0 as level_num
from #OrgList
where ParentOrgUnitId is null
UNION ALL
select o.OrgUnitId, o.ParentOrgUnitId, o.PersonId, o.isExcluded , level_num+1 as level_num
from #OrgList o
join cte on o.ParentOrgUnitId=cte.OrgUnitId
)
select * from cte

I exclude OrgUnitId=4 and =11, then I want to update my recursive query that will recalculate the tree and show the new tree details, including level moves (there can be more levels and more consecutive exclusions, of course except the root node):

enter image description here

4 Answers

My approach:

  1. Extend your initial CTE with an exclusion counter (ExclusionCount), counting the number of excluded nodes going from root to leaf nodes.
  2. Add another recursive CTE to construct the upward path (cte_upwards) for each leaf node. Now decrement the counter added in the initial CTE.
  3. Use a cross apply to select the first node where the upward path reaches an exlusion count of zero.

Solution:

with cte as                                                     -- initial CTE
(
    select  OrgUnitId,
            ParentOrgUnitId,
            PersonId,
            IsExcluded,
            convert(int, IsExcluded) as 'ExclusionCount',       -- new counter
            0 as 'level_num'
    from #OrgList
    where ParentOrgUnitId is null
        union all
    select  o.OrgUnitId,
            o.ParentOrgUnitId,
            o.PersonId,
            o.IsExcluded,
            cte.ExclusionCount + convert(int, o.isExcluded),    -- increment counter
            cte.level_num + 1
    from #OrgList o
    join cte on o.ParentOrgUnitId = cte.OrgUnitId
),
cte_upwards as
(
    select  cte.OrgUnitId,
            cte.ParentOrgUnitId as 'NewParentOrgUnitId',
            cte.IsExcluded,
            cte.ExclusionCount,
            cte.level_num
    from cte
    where cte.ParentOrgUnitId is not null   -- only leaf nodes (not a root)
      and not exists (  select top 1 'x'    -- only leaf nodes (not an intermediate node)
                        from cte cp
                        where cp.ParentOrgUnitId = cte.OrgUnitId )
        union all
    select  cte_upwards.OrgUnitId,
            cte.ParentOrgUnitId,
            cte.IsExcluded,
            cte_upwards.ExclusionCount - cte.IsExcluded,    -- decrement counter
            cte.level_num
    from cte_upwards
    join cte
        on cte.OrgUnitId = cte_upwards.NewParentOrgUnitId
)
select  cte.OrgUnitId,
        cte.ParentOrgUnitId,
        cte.IsExcluded,
        x.NewParentOrgUnitId,
        coalesce(x.NewParentOrgUnitId, cte.ParentOrgUnitId) as 'Recalculated'
from cte
outer apply (   select top 1 cu.NewParentOrgUnitId
                from cte_upwards cu
                where cu.OrgUnitId = cte.OrgUnitId
                  and cu.ExclusionCount = 0         -- node without excluded parent nodes
                order by cu.level_num desc ) x      -- select lowest node in upwards path
order by cte.OrgUnitId;

Result:

OrgUnitId   ParentOrgUnitId IsExcluded NewParentOrgUnitId Recalculated
----------- --------------- ---------- ------------------ ------------
1           NULL            0          NULL               NULL
2           1               0          NULL               1
3           1               0          NULL               1
4           2               1          NULL               2
5           2               0          2                  2
6           3               0          3                  3
7           4               0          2                  2
8           4               0          2                  2
9           4               0          2                  2
10          4               0          2                  2
11          4               1          NULL               4
12          11              0          2                  2

You should just add a second UNION ALL in your cte:

with cte as (

select OrgUnitId, ParentOrgUnitId, PersonId, isExcluded , 0 as level_num
from #OrgList
where ParentOrgUnitId is null
UNION ALL
select o.OrgUnitId, o.ParentOrgUnitId, o.PersonId, o.isExcluded , level_num+1 as level_num
from #OrgList o
join cte on o.ParentOrgUnitId=cte.OrgUnitId
where cte.isExcluded = 0 
UNION ALL
select o.OrgUnitId, cte.ParentOrgUnitId, o.PersonId, o.isExcluded , level_num as level_num
from #OrgList o
join cte on o.ParentOrgUnitId=cte.OrgUnitId
where cte.isExcluded = 1

)
select * from cte
;
with cte as (
select OrgUnitId, ParentOrgUnitId, PersonId, isExcluded , 0 as level_num, 0 as level_after_exclusions, 
cast(',' as varchar(max)) + case isExcluded when 1 then cast(OrgUnitId as varchar(20)) else '' end as excludedmembers,
case isExcluded when 1 then ParentOrgUnitId end as newParentId
from #OrgList
where ParentOrgUnitId is null
UNION ALL
select o.OrgUnitId, o.ParentOrgUnitId, o.PersonId, o.isExcluded , level_num + 1, level_after_exclusions + case o.isExcluded when 1 then 0 else 1 end, 
excludedmembers + case o.isExcluded when 1 then cast(o.OrgUnitId as varchar(20))+',' else '' end,
case when excludedmembers like '%,'+cast(o.ParentOrgUnitId as varchar(20))+',%' then newParentId else o.ParentOrgUnitId  end 

from #OrgList o
join cte on o.ParentOrgUnitId=cte.OrgUnitId
)
select *, level_num - level_after_exclusions as shiftbylevels
from cte

I've added a VirtualParentOrgUnitId, which contains the parent with excluded nodes taken into account. I've also added a counter, VirtualDistance, which will report how many real hops there are between this node and it's virtual parent.

VirtualParentOrgUnitId will use the parent's ID if is not excluded, otherwise it will use it's parents's VirtualParentOrgUnitId, which allows chaining of multiple levels.

DROP TABLE IF EXISTS #OrgList
CREATE TABLE #OrgList (
    OrgUnitId int,
    ParentOrgUnitId int,
    PersonId int,
    isExcluded bit
);

INSERT INTO #OrgList(OrgUnitId, ParentOrgUnitId, PersonId, isExcluded) VALUES
    (1, NULL, 100, 0), (2,1, 101, 0), (3,1,102,0), (4,2,103,1), (5,2,104,0), (6,3,105,0), (7,4,106,0), (8,4,107,0), (9,4,108,0), (10,4,109,0), (11,4,110,1), (12,11,111,0)

DROP TABLE IF EXISTS #Excludes
CREATE Table #Excludes (
    OrgUnitId int
);

INSERT INTO #Excludes VALUES (4), (11);

with cte as (
select OrgUnitId, ParentOrgUnitId, ParentOrgUnitId VirtualParentOrgUnitId, 1 as VirtualDistance , PersonId, isExcluded , 0 as level_num
from #OrgList
where ParentOrgUnitId is null
UNION ALL
select o.OrgUnitId, o.ParentOrgUnitId, IIF(o.ParentOrgUnitId IN (SELECT OrgUnitId FROM #Excludes),cte.VirtualParentOrgUnitId,  o.ParentOrgUnitId ), IIF(o.ParentOrgUnitId IN (SELECT OrgUnitId FROM #Excludes),VirtualDistance + 1,  1 ), o.PersonId, o.isExcluded , level_num+1 as level_num
from #OrgList o
join cte on o.ParentOrgUnitId=cte.OrgUnitId

)
select * from cte

Here are the results:

OrgUnitId   ParentOrgUnitId VirtualParentOrgUnitId VirtualDistance PersonId    isExcluded level_num
----------- --------------- ---------------------- --------------- ----------- ---------- -----------
1           NULL            NULL                   0               100         0          0
2           1               1                      0               101         0          1
3           1               1                      0               102         0          1
6           3               3                      0               105         0          2
4           2               2                      0               103         1          2
5           2               2                      0               104         0          2
7           4               2                      1               106         0          3
8           4               2                      1               107         0          3
9           4               2                      1               108         0          3
10          4               2                      1               109         0          3
11          4               2                      1               110         1          3
12          11              2                      2               111         0          4
Related