Tree Node Calculation - SQL Server

Question

I'd appreciate some help with something I am trying to achieve please.

The parts that my company make are built from sub assemblies and sub assemblies of sub assemblies. This looks like:

             1
         /   \  \
        /     |   \
       2      3    7
      / \    / \
     4   5  4   6

Where 4 & 5 come together to make 2, 4 & 6 make 3, then assemblies 2, 3 & 7 make 1.

My table looks like this;

+------+-----+-------+----------+----------------+
| ROOT | SUB | LEVEL | LEADTIME | TOP LEVEL PART |
+------+-----+-------+----------+----------------+
|    1 |   1 |     0 |        4 |              1 |
|    1 |   2 |     1 |        2 |              1 |
|    1 |   3 |     1 |        5 |              1 |
|    1 |   7 |     1 |       20 |              1 |
|    2 |   4 |     1 |        4 |              1 |
|    2 |   5 |     1 |        1 |              1 |
|    3 |   4 |     2 |        4 |              1 |
|    3 |   6 |     2 |        5 |              1 |
+------+-----+-------+----------+----------------+

Each part has a lead time of how long it takes to make it. What I want to do is pass a top level part number and it calculate the overall lead time for the part.

Originally I thought I could just group by the Level and take the maximum lead time per level and add them together but that wouldn't be accurate. Level 1 Part 7 takes 20 days to make so we would be able to be making all of the other parts whilst 7 was being made. The calculation needs to be based on the part that consumes its parent (for want of a better phrase).

What I need to do is calculate the lead time for every route through the tree and add up the lead times as it goes. So I would like to return a table something like;

+----+----------------+-------------------------+------+------------+
| ID | Top Level Part | Parts Nodes Combination | Days | [BASED ON] |
+----+----------------+-------------------------+------+------------+
| 1  | 1              | 1 >> 2 >> 4             | 10   | 4 + 2 + 4  |
| 2  | 1              | 1 >> 2 >> 5             | 7    | 4 + 2 + 1  |
| 3  | 1              | 1 >> 3 >> 4             | 13   | 4 + 5 + 4  |
| 4  | 1              | 1 >> 3 >> 6             | 14   | 4 + 5 + 5  |
| 5  | 1              | 1 >> 7                  | 24   | 4 + 20     |
+----+----------------+-------------------------+------+------------+

I can then find the MAX of the days column which will tell me that the overall lead time for Part 1 is 24 days.

I really hope I've made my post understandable and all is formatted correctly. I've tried to read up on recursive SQL queries but I'm struggling to get my head around them. The most number of levels I am ever likely to have is 4 so I'd hope it wouldn't be too pc intensive. If so, I'd much rather be able pass all of my parts through, rather than doing them one part at a time (hence why I've got a top level part column in my table).

Any help or advice would be greatly appreciated.

Answer 1

This solution also gets the intermediate nodes

;WITH RecursiveCTE
AS
(
SELECT  [SUB] , 
        [SUB] as [Top Level Part],
        CAST([SUB] as varchar(255)) as [Parts Nodes Combination],
        0 AS [LEVEL],
        [LEADTIME]  as [Days],
        CAST([LEADTIME] as varchar(255)) as [BASED ON]
FROM dbo.Levels s1
WHERE [LEVEL] = 0

UNION ALL

SELECT  s1.SUB as [Top Level Part],
        RecursiveCTE.[Top Level Part],
        CAST(RecursiveCTE.[Parts Nodes Combination]+ ' >> ' + cast(s1.[SUB] as varchar(255)) as varchar(255)),
        RecursiveCTE.[LEVEL] + 1 as [LEVEL],
        RecursiveCTE.[Days] + s1.[LEADTIME] as [Days],
        CAST(RecursiveCTE.[BASED ON] + ' + ' + CAST(s1.[LEADTIME] as varchar(255))  as  varchar(255))
FROM dbo.Levels s1
INNER JOIN RecursiveCTE 
ON s1.[ROOT] = RecursiveCTE.[SUB]
WHERE s1.[LEVEL] > 0
)
SELECT * FROM RecursiveCTE
WHERE [LEVEL] != 0;

Result

SUB Top Level Part  Parts Nodes Combination LEVEL   Days    BASED ON
2       1               1 >> 2                  1       6       4 + 2
3       1               1 >> 3                  1       9       4 + 5
7       1               1 >> 7                  1       24      4 + 20
4       1               1 >> 3 >> 4             2       13      4 + 5 + 4
6       1               1 >> 3 >> 6             2       14      4 + 5 + 5
4       1               1 >> 2 >> 4             2       10      4 + 2 + 4
5       1               1 >> 2 >> 5             2       7       4 + 2 + 1

DB<>Fiddle

If you want to filter out the intermediate nodes:

;WITH RecursiveCTE
AS
(
SELECT  [SUB] , 
        [SUB] as [Top Level Part],
        CAST([SUB] as varchar(255)) as [Parts Nodes Combination],
        0 AS [LEVEL],
        [LEADTIME]  as [Days],
        CAST([LEADTIME] as varchar(255)) as [BASED ON]
FROM dbo.Levels s1
WHERE [LEVEL] = 0

UNION ALL

SELECT  s1.SUB as [Top Level Part],
        RecursiveCTE.[Top Level Part],
        CAST(RecursiveCTE.[Parts Nodes Combination]+ ' >> ' + cast(s1.[SUB] as varchar(255)) as varchar(255)),
        RecursiveCTE.[LEVEL] + 1 as [LEVEL],
        RecursiveCTE.[Days] + s1.[LEADTIME] as [Days],
        CAST(RecursiveCTE.[BASED ON] + ' + ' + CAST(s1.[LEADTIME] as varchar(255))  as  varchar(255))
FROM dbo.Levels s1
INNER JOIN RecursiveCTE 
ON s1.[ROOT] = RecursiveCTE.[SUB]

WHERE s1.[LEVEL] > 0

)

SELECT * FROM RecursiveCTE
WHERE [LEVEL] != 0
AND NOT EXISTS 
(
SELECT * FROM
dbo.Levels s2
WHERE RecursiveCTE.SUB = s2.[ROOT])
;

Result

SUB Top Level Part  Parts Nodes Combination LEVEL   Days    BASED ON
7           1               1 >> 7           1      24      4 + 20
4           1               1 >> 3 >> 4      2      13      4 + 5 + 4
6           1               1 >> 3 >> 6      2      14      4 + 5 + 5
4           1               1 >> 2 >> 4      2      10      4 + 2 + 4
5           1               1 >> 2 >> 5      2      7       4 + 2 + 1

DB<>Fiddle

Table & Data used

CREATE TABLE dbo.Levels ([PARTID] INT,[ROOT] int,[SUB] int,[LEVEL] int, [LEADTIME] int,[TOP LEVEL PART] int);
--PartID added
INSERT INTO dbo.Levels
 ([PARTID], [ROOT] ,[SUB] ,[LEVEL] , [LEADTIME] ,[TOP LEVEL PART])

VALUES
(1,1 , 1 ,0 ,4 ,1 ),
(1,1 , 2 ,1 ,2 ,1 ),
(1,1 , 3 ,1 ,5 ,1 ),
(1,1 , 7 ,1 ,20 ,1 ),
(1,2 , 4 ,1 ,4 ,1 ),
(1,2 , 5 ,1 ,1 ,1 ),
(1,3 , 4 ,2 ,4 ,1 ),
(1,3 , 6 ,2 ,5 ,1 );

Edit

Op comments:

I've noticed the data is repeating a lot (particularly on larger assemblies)

Basically I have Sub Router 1691, on top level router 1731. the Parts node combination is 1731 -- 1727 -- 1691 and this repeats exactly the same columns 8 times. Then, when it introduces another node (so 1731 -- 1727 -- 1691 -- 1682), this one repeats 168 times. This is the case all of the way through. It appears that any 3 level nodes repeat 8 times & any 4 level nodes 168 times.

On a different one it repeats far fewer times. I'm wondering whether it has something to do with the number of unique parts in the tree.

I think I've figured it out! A single sub can appear on several different top level parts. On the join to the recursiveCTE table I've also added 'and RecursiveCTE.[Top Level Part] = s1.TopLevelRouter' and I think it's done the trick.

Part of the query that needed to be changed:

 ...    
FROM dbo.Levels s1
INNER JOIN RecursiveCTE 
ON s1.[ROOT] = RecursiveCTE.[SUB]
and RecursiveCTE.[Top Level Part] = s1.TopLevelRouter
WHERE s1.[LEVEL] > 0
)
SELECT * FROM RecursiveCTE
WHERE [LEVEL] != 0;