T-SQL получить корневой узел в иерархии

Question

Таким образом, у меня есть две таблицы структурированы следующим образом:

CREATE TABLE #nodes(node int NOT NULL); 
ALTER TABLE #nodes ADD CONSTRAINT PK_nodes PRIMARY KEY CLUSTERED (node); 

CREATE TABLE #arcs(child_node int NOT NULL, parent_node int NOT NULL); 
ALTER TABLE #arcs ADD CONSTRAINT PK_arcs PRIMARY KEY CLUSTERED (child_node, parent_node); 

INSERT INTO #nodes(node) 
VALUES (1), (2), (3), (4), (5), (6), (7); 

INSERT INTO #arcs(child_node, parent_node) 
VALUES (2, 3), (3, 4), (2, 6), (6, 7); 

Если у меня есть два узла, предположим, что 1 и 2. Я хочу, чтобы список их корневых узлов. В этом случае это будут 1, 4 и 7. Как я могу написать запрос, чтобы получить эту информацию?

Я принял удар, написав его, но столкнулся с проблемой, что не могу использовать LEFT-соединение в рекурсивной части CTE по неизвестной причине. Вот запрос, который будет работать, если мне разрешено делать LEFT JOIN.

WITH root_nodes 
AS (
    -- Grab all the leaf nodes I care about and their parent 
    SELECT n.node as child_node, a.parent_node 
    FROM #nodes n 
    LEFT JOIN #arcs a 
     ON n.node = a.child_node 
    WHERE n.node IN (1, 2) 

    UNION ALL 

    -- Grab all the parent nodes 
    SELECT rn.parent_node as child_node, a.parent_node 
    FROM root_nodes rn 
    LEFT JOIN #arcs a -- <-- LEFT JOINS are Illegal for some reason :(
     ON rn.parent_node = a.child_node 
    WHERE rn.parent_node IS NOT NULL 
) 
SELECT DISTINCT rn.child_node as root_node 
FROM root_nodes rn 
WHERE rn.parent_node IS NULL 

Есть ли способ, которым я могу реорганизовать запрос, чтобы получить то, что я хочу? Я не могу реструктурировать данные, и я бы предпочел держаться подальше от временных таблиц или делать что-то дорогое.

Спасибо, Рауль

Answer 1

Как о перемещении LEFT JOIN из КТР?

WITH root_nodes 
AS (
    -- Grab all the leaf nodes I care about 
    SELECT NULL as child_node, n.node as parent_node 
    FROM #nodes n 
    WHERE n.node IN (1, 2) 

    UNION ALL 

    -- Grab all the parent nodes 
    SELECT rn.parent_node as child_node, a.parent_node 
    FROM root_nodes rn 
     JOIN #arcs a 
     ON rn.parent_node = a.child_node 
) 
SELECT DISTINCT rn.parent_node AS root_node 
FROM root_nodes rn 
    LEFT JOIN #arcs a 
    ON rn.parent_node = a.child_node 
WHERE a.parent_node IS NULL 

Результирующий набор 1, 4, 7.