如何在 SQL 中生成通向给定节点的层次结构路径？

Question

在我的 MS SQL 2008 R2 数据库中，我有这个表：

TABLE [Hierarchy]
[ParentCategoryId] [uniqueidentifier] NULL,
[ChildCategoryId] [uniqueidentifier] NOT NULL

我需要编写一个查询来生成通向给定节点的所有路径。

假设我有一棵树：

A
-B
--C
-D
--C

将存储为：

NULL | A
A    | B
A    | D
B    | C
D    | C

当询问 C 的路径时，我想返回两条路径（或多或少像这样写）：

A > B > C,
A > D > C

Answer 1

这是我的解决方案，Sql Fiddle

DECLARE @child VARCHAR(10) = 'C'

    ;WITH children AS
    (

       SELECT 
         ParentCategoryId,
        CAST(ISNULL(ParentCategoryId + '->' ,'')  + ChildCategoryId AS VARCHAR(4000)) AS Path
       FROM Hierarchy
       WHERE ChildCategoryId =  @child
     UNION ALL
       SELECT 
         t.ParentCategoryId,
         list= CAST(ISNULL(t.ParentCategoryId  + '->' ,'')  + d.Path AS VARCHAR(4000))
       FROM Hierarchy t
       INNER JOIN children  AS d
            ON t.ChildCategoryId = d.ParentCategoryId
     )

    SELECT Path 
    from children c
    WHERE ParentCategoryId IS NULL

输出：

A->D->C 
A->B->C 

---

更新：

@AlexeiMalashkevich，要获取 id，你可以尝试这个

SQL 小提琴

DECLARE @child VARCHAR(10) = 'C'

;WITH children AS
(

   SELECT 
     ParentCategoryId,
     ChildCategoryId  AS Path
   FROM Hierarchy
   WHERE ChildCategoryId =  @child
 UNION ALL
   SELECT 
     t.ParentCategoryId,
     d.ParentCategoryId 
   FROM Hierarchy t
   INNER JOIN children  AS d
        ON t.ChildCategoryId = d.ParentCategoryId
 )

SELECT DISTINCT PATH
from children c

Answer 2

可能的解决方案是使用@a_horse_with_no_name中提到的递归CTE：

CREATE TABLE [Hierarchy](
[ParentCategoryId] CHAR(1) NULL,
[ChildCategoryId] CHAR(1) NOT NULL
);


INSERT INTO Hierarchy
SELECT NULL, 'A' UNION ALL
SELECT 'A', 'B' UNION ALL
SELECT 'A', 'D' UNION ALL
SELECT 'B', 'C' UNION ALL
SELECT 'D', 'C';


WITH CTE AS (
    SELECT 
        ParentCategoryId, ChildCategoryId, 
        CAST(ISNULL(ParentCategoryId,'') + ChildCategoryId AS VARCHAR(255)) [Path] 
    FROM Hierarchy
    WHERE ParentCategoryId IS NULL

    UNION ALL

    SELECT 
        H.ParentCategoryId, H.ChildCategoryId, 
        CAST(C.[Path] + ' > ' + H.ChildCategoryId AS VARCHAR(255)) [Path] 
    FROM Hierarchy H
    INNER JOIN CTE C ON C.ChildCategoryId = H.ParentCategoryId
) SELECT * FROM CTE;

Answer 3

这是一个有趣的层次结构。似乎允许父母可能是他们孩子的孩子。如果发生这种情况，代码逻辑就会中断，但只要不发生这种情况，就应该可以工作。

Create  Function dbo.IdentifyHierarchyPaths (@DeepestChildNode UniqueIdentifier)
Returns @hierarchy Table
(
        Hierarchy Varchar(Max)
)
As
Begin
        ;With   BuildHier As
        (
                Select  Convert(Varchar(Max),h2.ChildCategoryId) As child, Convert(Varchar(Max),h1.ChildCategoryId) + ' > ' +  Convert(Varchar(Max),h2.ChildCategoryId) As hier
                From    Hierarchy h1
                Left    Join Hierarchy h2
                        On  h1.ChildCategoryId = h2.ParentCategoryId
                Where   h1.ParentCategoryId Is Null
                Union   All
                Select  Convert(Varchar(Max),h1.ChildCategoryId) As child, bh.hier + ' > ' +  Convert(Varchar(Max),h1.ChildCategoryId) As hier
                From    BuildHier bh
                Join    Hierarchy h1
                        On  bh.child = h1.ParentCategoryId
        ),      HierWithTopLevel As
        (
                Select  Convert(Varchar(Max),ChildCategoryId) As hierarchy
                From    Hierarchy
                Where   ParentCategoryId Is Null
                Union   
                Select  hier
                From    BuildHier
        )
        Insert  @hierarchy
        Select  hierarchy
        From    HierWithTopLevel
        Where   Right(hierarchy,36) = Convert(Varchar(36),@DeepestChildNode);
        Return;
End;

Answer 4

我发现自己遇到了一个非常相似的问题，只不过我根本没有使用 MS SQL！但有了 MariaDB。

幸运的是，我们在 @Oleksandr 的启发下找到了解决方案。我当然通过谷歌找到了这个问题，但是如果其他人遇到这个特定问题并且他们碰巧使用 MariaDB，请不要担心。 SqlFiddle

WITH RECURSIVE MyTree AS (
    SELECT NULL AS ParentCategoryId, 'A' AS ChildCategoryId UNION ALL
    SELECT 'A', 'C' UNION ALL
    SELECT 'A', 'B' UNION ALL
    SELECT 'A', 'D' UNION ALL
    SELECT 'B', 'E' UNION ALL
    SELECT 'E', 'C' UNION ALL
    SELECT 'D', 'C'
),
CTE AS (
    -- Anchor member: select leaf nodes
    SELECT 
        ChildCategoryId AS Node,
        ParentCategoryId AS Parent,
        CAST(ChildCategoryId AS CHAR(100)) AS NodePath,
        1 AS Level
    FROM MyTree
    WHERE ChildCategoryId NOT IN (SELECT DISTINCT ParentCategoryId FROM MyTree WHERE ParentCategoryId IS NOT NULL)
    
    UNION ALL
    
    -- Recursive member: join to previous results and extend the path
    SELECT 
        CTE.Node,
        mt.ParentCategoryId AS Parent,
        CONCAT(mt.ChildCategoryId, ' > ', CTE.NodePath) AS NodePath,
        Level + 1 AS Level
    FROM CTE
    JOIN MyTree mt ON CTE.Parent = mt.ChildCategoryId
)
-- Final SELECT for the recursive CTE to return results without NULL Parents
SELECT DISTINCT
    TRIM(TRAILING ' > ' FROM NodePath) AS 'FullPath'
FROM CTE
WHERE Parent IS NULL
ORDER BY Level DESC;