T-SQL get root node in hierarchy

sql, sql-server, sql-server-2008, t-sql

Solution

How about moving the LEFT JOIN out of the CTE?

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

The result set is 1, 4, 7.

Problem

So I have two tables structured like so: ``` 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); ``` If I have two nodes, lets say 1 and 2. I want a list of their root nodes. In this case it would be 1, 4, and 7. How can I write a query to get me that information ? I took a stab at writing it but ran into the issue that I can't use a LEFT join in the recursive part of a CTE for some unknown reason. Here is the query that would work if I was allowed to do a 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 ``` Is there a way I can restructure the query to get what I want ? I can't restructure the data and I would really prefer to stay away from temporary tables or having to do anything expensive. Thanks, Raul

Original source