Recursive CTE while Parent Id not in a List

Question

I have the following Nested Set

That results in this tree

1 -
  |---- 2 -
  |       |---- 4 -
  |               |---- 7
  |               |---- 8
  |----10 -
          |---- 9
3 -
  |----  5
  |----  6
13-
  |---- 11
  |---- 12

I have a list of produts SELECT Id, Name ... FROM Products

A many-to-many relationship with the categories. All Categories can have Promotions. Ok now the problem.

Let's say I have a ProductX in the categories 7,8,6. And Promotions in the categories 1,2,3. I need get the closest parent with a promotion per category or until there is no more parents.

The end result should be

CategoryId PromotionPrice
    2          price...
    3          price...

What I have

WITH Promotions (CategoryId, PromotionPrice)
{
    SELECT CategoryId, PromotionPrice
    FROM Promotions
}
SELECT CategoryId, PromotionPrice
FROM NestedSet s1
    LEFT JOIN NestedSet s2 ON s1.ParentId = s2.Id
    LEFT JOIN Promotions p ON s1.CategoryId = p.CategoryId

And then get the Better Promotion (that I know how to do) and apply to the main query SELECT * FROM Products; For each product (so just a simple join).

My problem is that I know I need to use (or I think I need to use) a recursive CTE, but I have no idea how to do that. Since it should only be recursive for each line and only until it find a promotion for that row.

EDIT (I'll try to explain the logic).

ProductId  CategoryId
     1         7
     1         8
     1         6

This product have 2 direct parents: 4 (from 7 and 8) and 3 (from 6) I have promotions in the CategoryIds: 1, 2, 3. First round query result

CategoryId ParentId PromotionPrice
     7         4         NULL
     8         4         NULL 
     6         3          10

What matters is the ParentId so I can GroupBy ParentId and the result would be

CategoryId PromotionPrice
     4         NULL
     3          10

Ok, since promotionPrice is NULL I need to go the his parent(in this case 2) so the query above would need to return

CategoryId ParentId PromotionPrice
     4       2         NULL
     3      NULL       10

Since PromotionPrice is Null I have to check if there is a Promotion for the Category2 so the result would be

CategoryId ParentId PromotionPrice
     2       1         15
     3      NULL       10

It stops there. In case I removed the promotion from Category2 it should go another round:

CategoryId ParentId PromotionPrice
     1      NULL       5
     3      NULL       10

at this point since there is no more parents it doesn't matter if PromotionPrice is null or not. The thing is I need to go all the way up trying to find a promotion.

As I'm lookin the SortPath already have all the info, would only need to break it down and recursively go backwards until find a ID that has a promotion, still I'm clueless on how to achieve that.

Hope this helps a bit explaining.

Answer 1

Note: I edited slightly to reflect the sample data you provided.

The Setup

Here is what I have to represent your nested set:

declare @nestedSet table (
    id int,
    parentId int
);

insert @nestedSet values 
    (1, null), (2, 1), (4, 2), (7, 4), (8, 4), (10, 1), (9, 10), (1004, 1),
    (3, null), (5, 3), (6, 3),
    (13, null), (11, 13), (12, 13);

Here is what I built for your promotions:

declare @promotions table (
    promotionId int identity(1,1),
    categoryId int,
    price float
);

insert @promotions values (1, 5), (2, 15), (3, 10);

And your products, which I have renamed productCategories to better reflect its contents:

declare @productCategories table (productId int, categoryId int);
insert @productCategories values (1,7),(1,8),(1,6);

The Solution

As an anchor, I just pulled in the products table. But I think in your use case you'll want a filter to pick out the appropriate base products. Then I did a calculation to check to see if the category was already a promotion. If it was, then it represented a leaf node.

In the recursion, I simply moved up the hierarchy of nested set for every node that was not a leaf. I again did the calculation to see if the category was a promotion to see if it was a leaf node or not.

From the results, I selected all leaf nodes, ordered by price, and output the top one.

declare @productId int = 1;

with

    traverse as (

        select      categoryId, 
                    parentId, 

                    isLeaf = iif(exists (
                        select 0  
                        from @promotions pm 
                        where pd.categoryId = pm.categoryId
                    ), 1, 0)

        from        @productCategories pd
        join        @nestedSet n on pd.categoryId = n.id
        where       pd.productId = @productId 

        union all
        select      categoryId = par.id,
                    par.parentId,

                    isLeaf = iif(exists (
                        select 0 
                        from @promotions pm 
                        where par.id = pm.categoryId
                    ), 1, 0)

        from        traverse pd
        join        @nestedSet par on pd.parentId = par.id
        where       pd.isLeaf = 0

    )


    select      
    top 1       p.*
    from        traverse t
    join        @promotions p on t.categoryId = p.categoryId
    where       isLeaf = 1
    order by    p.price