Иерархия Рекурсивного SQL Server Query

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, который является родителем D, который является дочерним по отношению к C.

Это не стандартный запрос иерархии, так как нет никакого реального корня, и мне нужно получить ссылки в обоих направлениях. Таким образом, это означает, что я не могу использовать рекуррентное трюк КТР .. здесь была моя попытка:

--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 

Моя вторая попытка включал временную таблицу и во время цикла. Это работает, но оказывается очень медленно:

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 

END

Можно ли предложить приемлемое решение для этого?

Answer 1

Мы сопоставляем каждую строку с каждой другой строкой на основе каждой комбинации родительских и дочерних идентификаторов и сохраняем путь по пути. Рекурсивные мы делаем это сопоставление и сделать путь для того, чтобы избежать бесконечных циклов мы проверяем путь не пройден ранее, в конце концов у нас есть все узлы, которые имеют путь к нужному узлу (@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 комментариев, нет необходимости для проверки пути, поскольку есть первичный ключ в таблице соотношения (который я не заметил), мы можем искать для первичного ключа в предыдущей рекурсии к избегайте бесконечных циклов.