SQL Server 递归层次结构查询

Question

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

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

我的第二次尝试涉及临时表和 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评论，不需要检查路径，因为关系表中有主键(我没有注意到)我们可以查找主键在先前的递归中以避免无限循环。