在自引用表中查找最顶层的父级

Question

给定一些ID，每个ID可能连接到同一张表中的其他条目，我想找到它们的顶级父项。也就是那些父ID为NULL的行。因此，每个红色单元下方都将与相应的绿色单元链接起来，如下所示:

借鉴了这个非常相似问题中的答案，以下是模拟架构。

DECLARE @t TABLE (ID INT, link INT)

INSERT INTO @t VALUES
(1, NULL),
(2, 1),
(3, 2),
(4, 3),
(5, 3),
(6, 2),
(7, 1),

(8, NULL),
(9, 8),
(10, 9),
(11, 9),
(12, 9),
(13, 12),
(14, 12),
(15, 8);

我有一组ID，例如6和13，它们是两个底层节点。然后我希望得到一个结果集，如(6, 1) 和 (13, 8)。为了构建每个链接，答案建议使用常见表达式。

WITH cte AS (
    SELECT ID, link
    FROM @t
    WHERE ID IN (6, 13)

    UNION ALL

    SELECT t.ID, t.link
    FROM @t t
    JOIN cte c ON t.ID = c.link
    WHERE t.link IS NOT NULL
)

SELECT *
FROM cte

这将产生以下结果：

 ID | link
----+------
  6 |   2
 13 |  12
 12 |   9
  9 |   8
  2 |   1

然而，我不确定如何将此组合为每个起始点的一个结果。对于一个ID，我可以选择结果集的最后一行并获取链接ID，但无法处理多个ID。请注意，自然可以有多个顶级父级（尽管分支只向下延伸，因此对于给定节点只有一个父级），也可以选择中间级别的条目作为起始点。

与其使用UNION ALL，我天真地尝试了JOIN，但结果发现不允许使用这样的CTE。

这是上面所有红色节点：(3, 6, 11, 13, 15)。它们应该映射到(1, 1, 8, 8, 8)。

- Felix

---

你应该使用hierarchyid而不是自引用。通过可索引的列进行快速搜索，而不是昂贵的递归。 - Panagiotis Kanavos

@PanagiotisKanavos 哇，太棒了！谢谢。不过，如果存在一种方法超出这个明显的最优解，那将会很有趣。对于那些已经建立的架构和纯粹的好奇心。 - Felix

Answer 1

代码存在两个问题：

1. 你需要通过递归跟踪起始ID；
2. 递归部分的where条件实际上会阻止你得到结果。

因此，最初的回答应该是：

WITH cte AS (
    SELECT ID, link, ID as [StartID]
    FROM @t
    WHERE ID IN (6, 7)
    UNION ALL
    SELECT t.ID, t.link, c.StartID
    FROM @t t
    JOIN cte c ON t.ID = c.link
)
SELECT c.StartID, c.ID
FROM cte c
where c.link is null;

- Roger Wolf

Answer 2

记住起点，跟踪级别，取最大级别。

DECLARE @t TABLE (ID INT, link INT)

INSERT INTO @t VALUES
(1, NULL),
(2, 1),
(3, 1),
(4, 2),
(5, 3),
(6, 4),
(7, 5);

WITH cte AS (
    SELECT ID, link, 1 as [level], id as [start]
    FROM @t
    WHERE ID IN (6, 7)

    UNION ALL

    SELECT t.ID, t.link, c.[level] + 1, c.[start]
    FROM @t t
    JOIN cte c ON t.ID = c.link
    WHERE t.link IS NOT NULL
)

SELECT TOP(1) WITH TIES [start], link
FROM cte
ORDER BY [level] DESC;

- Serg

---

正如OP所提到的，这些图可以有多个根节点(即它们不是树形结构)。您的方法只会返回具有最长路径的根节点。 - Roger Wolf

@RogerWolf 很好的观察！确实，如果第6行的父级是第2行，则不会在结果集中返回。虽然不确定确切的术语，但我认为它们仍然是树。只是有多个树。 - Felix

@RogerWolf 多个根节点，但如 OP 图像所示，该节点可能只有一个根节点。我猜这是一片森林，而不是网络。 - Serg

@Serg，如果它们被倒置了怎么办？ :D - Roger Wolf

哦，不好意思，图片已经解释清楚了。请忽略我之前的评论。 - Roger Wolf

Answer 3

您可以调整查询以获得您想要的内容：

WITH cte AS (
    SELECT ID as orig_id, ID, link, 1 as lev
    FROM @t
    WHERE ID IN (6, 7)

    UNION ALL

    SELECT c.orig_id, t.ID, t.link, lev + 1
    FROM @t t JOIN
         cte c
         ON t.ID = c.link
    WHERE t.link IS NOT NULL
)
SELECT orig_id, link
FROM (SELECT c.*, MAX(lev) OVER (PARTITION BY orig_id) as max_lev
      FROM cte c
     )  c
WHERE lev = max_lev;

更改内容如下：

• 在CTE中包含原始id。
• 跟踪关系的级别（“高度”）。
• 选择每个原始id的最高级别。

- Gordon Linoff

---

类似于Serg的回答，但可以正确处理不同长度的路线！谢谢。 - Felix

与@Serg的答案相同的问题，多个根未显示。将(6, 10), (10, null)添加到数据集中，您将看到。 - Roger Wolf

@RogerWolf 我在模式中重新创建了示例图片，以测试每个节点，并且它们使用此方法映射到正确的父级。 - Felix

@Felix，你的图片只有单一根节点，但是你在问题中提到“自然地可能存在多个顶级父节点”。这个小细节改变了一切。 - Roger Wolf

@RogerWolf，照片中有两个。话说表述不太清楚，是的，现在我看明白了，但如果有多个链接，整个链接的事情就行不通了，对吧？每个条目只有一个值，无法向另一个方向分支。 - Felix

@Felix……我认为其他答案都很好。 不知道为什么，在我写这篇文章时我没有看到这些答案。 - Gordon Linoff