SQL树遍历从根节点向下并返回上一个节点

Question

我有一个表格（ObjectStates），想要获取根节点以及根节点的第一个子节点：

ID    Title    ParentID
1     Draft    null
2     Green    null
3     Red      null
4     Foo      1
5     Bar      4
6     Some1    1
7     Some2    6
8     XYZ      2
9     Some3    7

我希望获得以下输出：

GetState(5)
-- returns root: 1, first-child: 4
GetState(6)
-- returns root: 1, first-child: 6
GetState(7)
-- returns root: 1, first-child: 6
GetState(9)
-- returns root: 1, first-child: 6
GetState(8)
-- returns root: 2, first-child: 8

无论我查询的层次有多深，我总是需要根元素和第一个子元素。如果您考虑这棵树，无论我在树的哪个深度，我总是需要红色和蓝色的元素。

我可以像这样获取“root”状态：

WITH CTEHierarchy
AS (
    SELECT 
    ID
        ,0 AS LEVEL
        ,ID AS root

    FROM ObjectStates
    WHERE  ParentID IS NULL

    UNION ALL

    SELECT 
    ObjectStates.ID
        ,LEVEL + 1 AS LEVEL
        ,[root]

    FROM ObjectStates
    INNER JOIN CTEHierarchy uh ON uh.id = ObjectStates.ParentID
    )    
    SELECT [root]
    FROM CTEHierarchy
    WHERE ID = @ObjectStateID 

这让我得到了我所期望的根结果：

GetState(5)
-- returns root: 1
GetState(9)
-- returns root: 1
GetState(2)
-- returns root: 2

我应该如何从那里向上遍历？从根节点获取树中的下一个子节点？还是反过来 - 获取根节点以及第一层级。递归让我很困惑。

- Dennis G

---

我尝试过一些丑陋的CASE语句，比如CASE WHEN uh.Level = 0 THEN ObjectStates.ID ELSE null END AS firstchild，但这并不起作用，因为它不能将子节点进一步传递到树下方。 - Dennis G

我的初步想法是添加另一列TopParentID，并为每个条目计算它（使用一些代码！）。然后，您可以选择TopParentID，min(ID) <简单的自连接和分组>. 使用SQL进行这种树遍历总是一个问题（除了奇怪的Oracle中，那里有扩展选择语句）。 - Vinny Roe

你所说的TopParentID是什么意思？你是指根节点吗？我知道根节点及其ID。但我无法从那里向上遍历，因为它不仅仅是ID+1或min(ID)，而是取决于它所在的树的层级，而不是ID。 - Dennis G

@Justin 因为我总是需要根节点和根节点的第一个子节点 - 无论我从哪里来（当然 GetState(1) 只能返回 1 | 1）。GetState(6) 必须是 1 | 6，因为 1 是根节点，6 是第一个子节点。GetState(9) 同理 - 根节点是 1，第一个子节点是 6。我想要当前元素的根节点以及根节点之前的元素（从元素的方向看）。 - Dennis G

是的，我指的是根节点。如果您对每个记录都有根节点的值，那么获取“第一个”子节点只需要进行自连接和min(ID)操作，不是吗？ - Vinny Roe

@VinnyRoe 看看“Draft”示例。你不能简单地获取根节点的第一个子节点，因为你不知道你来自哪个路径。第一个子节点可能是Foo或Some1，具体取决于你来自哪里。 - Dennis G

Answer 1

我认为您需要首先向上遍历层次结构，然后获取顶部两个级别：

WITH cteHierarchy As
(
   SELECT
      ID,
      ParentID,
      0 As Level
   FROM
      ObjectStates
   WHERE
      ID = @ObjectStateID

   UNION ALL

   SELECT
      OS.ID,
      OS.ParentID,
      H.Level + 1
   FROM
      cteHierarchy As H
      INNER JOIN ObjectStates As OS
      ON H.ParentID = OS.ID
),
cteReveresedHierarchy As
(
   SELECT
      ID,
      ROW_NUMBER() OVER (ORDER BY Level DESC) As RowNumber
   FROM
      cteHierarchy
)
SELECT
   ID
FROM
   cteReveresedHierarchy
WHERE
   RowNumber In (1, 2)
;

编辑
将两个项目放在同一行：

如果您可以保证永远不从根开始，您可以将过滤器更改为WHERE RowNumber = 2，并包括ParentID列。但是，如果您从根开始，您只会有一行，因此该查询无法工作。

为了允许查询从根开始，您需要获取第二行（如果存在），否则获取第一行：

WITH cteHierarchy As
(
   SELECT
      ID,
      ParentID,
      0 As Level
   FROM
      ObjectStates
   WHERE
      ID = @ObjectStateID

   UNION ALL

   SELECT
      OS.ID,
      OS.ParentID,
      H.Level + 1
   FROM
      cteHierarchy As H
      INNER JOIN ObjectStates As OS
      ON H.ParentID = OS.ID
),
cteReveresedHierarchy As
(
   SELECT
      ID,
      ParentID,
      ROW_NUMBER() OVER (ORDER BY Level DESC) As RowNumber
   FROM
      cteHierarchy
)
SELECT TOP 1
   ParentID As [root]
   ID As [FirstChild]
FROM
   cteReveresedHierarchy
WHERE
   RowNumber In (1, 2)
ORDER BY
   RowNumber DESC
;

- Richard Deeming

---

RowNumber 似乎做到了！现在我只想把那两行放进两列中。请参考这个 SQLFiddle：http://sqlfiddle.com/#!3/768b7/19 - Dennis G

有点丑？但是能用：SELECT TOP 1 (SELECT ID FROM cteReveresedHierarchy WHERE RowNumber = 1) AS RootID, (SELECT ID FROM cteReveresedHierarchy WHERE RowNumber = 2) AS FirstChildID 在最后一个select语句中。更新的SQLFiddle链接：http://sqlfiddle.com/#!3/768b7/30 - Dennis G

@moontear：看我的编辑 - 只需从相关行中获取“ID”和“ParentID”更容易。 - Richard Deeming

Answer 2

我今天在研究遍历主键和外键关系的查询，以跟踪整个路径，这个问题似乎很相似。所以我把同样的代码粘贴过来了。您可以直接运行此代码并检查是否符合您的需求。

该查询在CTE中添加了两列，即Hops和Path，其中Hops表示元素的级别，Path表示从起点到终点遍历的节点。

WITH cte
AS
(
    SELECT 
        fk.create_date
        , fk.modify_date
        , fkc.constraint_object_id AS ConstraintId
        , OBJECT_NAME(fkc.constraint_object_id) AS ConstraintName
        , OBJECT_NAME(fkc.referenced_object_id) AS PrimaryKeyTableName
        , rc.name AS PrimaryKeyColumnName
        , OBJECT_NAME(fk.parent_object_id) AS ForeignKeyTableName
        , lc.name AS ForeignKeyColumnName
    FROM sys.foreign_key_columns fkc
    INNER JOIN sys.columns rc 
        ON  rc.OBJECT_ID = fkc.referenced_object_id 
        AND fkc.referenced_column_id = rc.column_id
    INNER JOIN sys.foreign_keys fk 
        ON  fk.OBJECT_ID = fkc.constraint_object_id
    INNER JOIN sys.columns lc 
        ON  lc.OBJECT_ID = fk.parent_object_id
        AND fkc.parent_column_id = lc.column_id
)
, cte2(create_date, modify_date, ConstraintName
        , PrimaryKeyTableName, PrimaryKeyColumnName
        , ForeignKeyTableName, ForeignKeyColumnName
        , Hops, path ) AS 
    (
        SELECT
            create_date, modify_date, ConstraintName
            , PrimaryKeyTableName, PrimaryKeyColumnName
            , ForeignKeyTableName, ForeignKeyColumnName 
            , 1 , CAST(QUOTENAME(PrimaryKeyTableName + '.' + PrimaryKeyColumnName) AS VARCHAR(4000))
        FROM cte
    UNION ALL
        SELECT 
            cte.create_date, cte.modify_date, cte.ConstraintName
            , cte.PrimaryKeyTableName, cte.PrimaryKeyColumnName
            , cte.ForeignKeyTableName, cte.ForeignKeyColumnName
            , cte2.Hops +1, CAST(cte2.path + '-> ' +QUOTENAME(cte.PrimaryKeyTableName+ '.' + cte.PrimaryKeyColumnName) AS VARCHAR(4000))
        FROM cte2 INNER JOIN cte ON cte2.ForeignKeyTableName = cte.PrimaryKeyTableName
        AND cte2.ForeignKeyColumnName != cte.PrimaryKeyColumnName
    )
SELECT 
ConstraintName
        , PrimaryKeyTableName, PrimaryKeyColumnName
        , ForeignKeyTableName, ForeignKeyColumnName
        , Hops, path + '-> ' + QUOTENAME(ForeignKeyTableName + '.' + ForeignKeyColumnName) AS Path
FROM cte2

仅当数据库中存在外键约束时，此查询才有效。

- Shantanu Gupta

---

在我的情况下并没有帮助，因为我没有外键或者主键。而且我还需要重写你整个查询。 - Dennis G