SQL 服务器递归层次结构查询

Question

这是针对 SQL Server 2012 的。我需要生成一个包含链接的数据集，以及来自给定起始 ParentId 的链接的所有链接，给出以下 table

CREATE TABLE Relations (
    Id INT NOT NULL PRIMARY KEY,
    ParentId INT NOT NULL,
    ChildId INT 
);

因此对于以下数据集：

1 A B
2 B C
3 C D
4 F D
5 F G
6 X Y
7 Y Z

从 C 开始，我希望返回第 1 行到第 5 行，因为它们都通过父级或子级层次结构链接到 C。例如。 G 有父 F，F 是 D 的父，D 是 C 的子。

这不是标准的层次结构查询，因为没有真正的根，我需要获得双向链接。所以这意味着我不能使用 CTE 递归技巧。这是我的尝试：

--Hierarchical Query using Common Table Expressions 
WITH ReportingTree (Id, Parent, Child, Lvl) 
AS 
( 
    --Anchor Member 
    SELECT Id,
     ParentId,
     ChildId,
   0 as Lvl
FROM Relations WHERE ParentId = 9488 
UNION ALL 
--Recusive Member 
SELECT 
 cl.Id,
 cl.ParentId,
 cl.ChildId,
 r1.Lvl+1 
FROM [dbo].[CompanyLinks] cl 
    INNER JOIN ReportingTree r1 ON ReportingTree.Parent = cl.Child
    INNER JOIN ReportingTree r2 ON cl.FromCompanyId = r2.Parent  <-- errors
) 
SELECT * FROM ReportingTree

我的第二次尝试涉及临时 table 和 while 循环。这行得通，但结果很慢：

BEGIN   
CREATE TABLE #R (
    Id INT NOT NULL PRIMARY KEY NONCLUSTERED,
    ParentId INT NOT NULL,
    ChildId INT 
);

CREATE CLUSTERED INDEX IX_Parent ON #R (ParentId);
CREATE INDEX IX_Child ON #R (ChildId);

INSERT INTO #R
  SELECT Id,ParentId ChildId
    FROM Relations
    WHERE ParentId = 9488 OR ChildId = 9488;
WHILE @@RowCount > 0
BEGIN
  INSERT INTO #R
    SELECT cl.Id,cl.ParentId, cl.ChildId
      FROM #R INNER JOIN
        Relations AS cl ON cl.ChildId = #R.ChildId OR cl.ParentId = #R.ParentId OR cl.ChildId = #R.Parent OR cl.ParentId = #R.Child
    EXCEPT
    SELECT Id,ParentId, ChildId
      FROM #R;  
END

SELECT * FROM Relations cl inner Join #Relations r ON cl.Id = #R.Id
DROP TABLE #R

结束

任何人都可以为此提出可行的解决方案吗？

Answer 1

我们根据父 ID 和子 ID 的每种组合将每一行与其他每一行进行匹配，并沿途保存路径。我们递归地进行这种匹配并创建路径，为了避免无限循环，我们检查之前没有遍历的路径，最后我们拥有所有具有到所需节点的路径的节点（@Id）：

WITH cte AS ( 
        SELECT CompanyLinks.*, cast('(' + cast(ParentId as nvarchar(max)) + ',' 
                 + cast(ChildId as nvarchar(max))+')' as nvarchar(max)) Path 
          FROM CompanyLinks 
          WHERE ParentId = @Id OR ChildId = @Id
          UNION ALL 

          SELECT a.*,
               cast(
                     c.Path + '(' + 
                     cast(a.ParentId as nvarchar(max)) + ',' + 
                     cast(a.ChildId as nvarchar(max)) + ')' 
                   as nvarchar(max)
                   ) Path 
        FROM CompanyLinks a JOIN cte c ON 
              a.ParentId = c.ChildId 
              OR c.ParentId = a.ChildId 
              OR c.ParentId = a.ParentId 
              OR c.ChildId = a.ChildId 
            where c.Path not like cast(
                     '%(' + 
                     cast(a.ParentId as nvarchar(max)) + ',' + 
                     cast(a.ChildId as nvarchar(max)) + 
                     ')%' 
                   as nvarchar(max)
                   )

)
SELECT DISTINCT a.id, Company.Name, path from (
   SELECT distinct ParentId as id, path FROM cte
   union all 
   SELECT distinct ChildId as id, path FROM cte
) a inner join Company on Company.Id = a.Id

这是一个 fiddle。如果你想要不同的节点，只需使用：

SELECT DISTINCT id from (
   SELECT distinct ParentId as id FROM cte
   union all 
   SELECT distinct ChildId as id FROM cte
) a

查询结束。

这个查询实际上是在无向图上的广度优先搜索。

注意： 根据 Hogan 的评论，不需要检查路径，因为关系 table 中有一个主键（我没有注意到）我们可以在先前的递归中寻找主键以避免无限循环。

SQL 服务器递归层次结构查询

SQL Server Recursive Hierarchy Query

sql

sql-server

recursive-query