SQL Server (terminal result) hierarchy map-CodePudding

In SQL Server 2016, I have a table with the following chaining structure:

dbo.Item

OriginalItem	ItemID
NULL	1
1	2
2	3
3	4
NULL	5
5	6
NULL	7

Importantly, this example is a trivialized version of the real data, and the neatly ascending entries is not something that is present in the actual data, I'm just doing that to simplify the understanding.

I've constructed a query to get what I'm calling the TerminalItemID, which in this example case is ItemID 4, 6, and 7, and populated that into a temporary table @TerminalItems, the resultset of which would look like:

@TerminalItems

TerminalItemID
4
6
7

What I need, is a final mapping table that would look something like this (using the above example -- note that it also contains for 4, 6, and 7 mapping to themselves, this is needed by the business logic):

@Mapping

ItemID	TerminalItemID
1	4
2	4
3	4
4	4
5	6
6	6
7	7

What I need help with is how to build this last @Mapping table. Any assistance in this direction is greatly appreciated!

CodePudding user response：

This should do:

with MyTbl as (
    select *
    from (values 
     (NULL, 1 )
    ,(1,    2 )
    ,(2,    3 )
    ,(3,    4 )
    ,(NULL, 5 )
    ,(5,    6 )
    ,(NULL, 7 )
    ) T(OriginalItem,   ItemID)
)
, TerminalItems as (
    /* Find all leaf level items: those not appearing under OriginalItem column */
    select LeafItem=ItemId, ImmediateOriginalItem=M.OriginalItem
    from MyTbl M
    where M.ItemId not in
                    (select distinct OriginalItem
                      from MyTbl AllParn
                      where OriginalItem is not null
                      )
), AllLevels as (
    /* Use a recursive CTE to find and report all parents */
    select ThisItem=LeafItem, ParentItem=ImmediateOriginalItem
    from TerminalItems
    union all
    select ThisItem=AL.ThisItem, M.OriginalItem
    from AllLevels AL
         inner join
         MyTbl M
         on M.ItemId=AL.ParentItem
     )
select ItemId=coalesce(ParentItem,ThisItem), TerminalItemId=ThisItem
from AllLevels
order by 1,2

Beware of the MAXRECURSION setting; by default SQLServer iterates through recursion 100 times; this would mean that the depth of your tree can be 100, max (the maximum number of nodes between a terminal item and its ultimate original item). This can be increased by OPTION(MAXRECURSION nnn) where nnn can be adjusted as needed. It can also be removed entirely by using 0 but this is not recommended because your data can cause infinite loops.

CodePudding user response：

You can use a recursive CTE to compute the last item in the sequence. For example:

with
n (orig_id, curr_id, lvl) as (
  select itemid, itemid, 1 from item
 union all
  select n.orig_id, i.itemid, n.lvl   1
  from n
  join item i on i.originalitem = n.curr_id
)
select *
from (
  select *, row_number() over(partition by orig_id order by lvl desc) as rn from n
) x
where rn = 1

Result:

 orig_id  curr_id  lvl  rn 
 -------- -------- ---- -- 
 1        4        4    1  
 2        4        3    1  
 3        4        2    1  
 4        4        1    1  
 5        6        2    1  
 6        6        1    1  
 7        7        1    1

See running example at db<>fiddle.

CodePudding user response：

This is a typical gaps-and-islands problem and can also be carried out without recursion in three steps:

assign 1 at the beginning of each partition
compute a running sum over your flag value (generated at step 1)
extract the max "ItemID" on your partition (generated at step 2)

WITH cte1 AS (
    SELECT *, CASE WHEN OriginalItem IS NULL THEN 1 ELSE 0 END AS changepartition 
    FROM Item
), cte2 AS (
    SELECT *, SUM(changepartition) OVER(ORDER BY ItemID) AS parts
    FROM cte1
)
SELECT ItemID, MAX(ItemID) OVER(PARTITION BY parts) AS TerminalItemID 
FROM cte2

Check the demo here.

Assumption: Your terminal id items correspond to the "ItemID" value preceding a NULL "OriginalItem" value.