Рекурсивный иерархический запрос SQL Server

Это для 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.

Это не стандартный запрос иерархии, поскольку реального корня нет, и мне нужно получить ссылки в обоих направлениях. Итак, это означает, что я не могу использовать трюк с рекурсией 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

КОНЕЦ

Может ли кто-нибудь предложить работоспособное решение для этого?


person Marcus K    schedule 28.08.2015    source источник
comment
У каждого узла есть только один ребенок?   -  person Taher Rahgooy    schedule 28.08.2015
comment
Нет, может быть несколько детей и несколько родителей   -  person Marcus K    schedule 28.08.2015
comment
Я бы использовал один CTE для рекурсивного перемещения вниз по иерархии и другой CTE для рекурсивного перемещения вверх по иерархии, а также UNION вместе для обоих наборов результатов.   -  person Biscuits    schedule 28.08.2015
comment
@Biscuits Это приведет к исключению некоторых строк, поскольку дочерний элемент, например D, может иметь несколько родителей, например C и F.   -  person Giorgos Betsos    schedule 28.08.2015
comment
Насколько я понимаю, у вас есть отношения «многие ко многим» между узлами (в отличие от отношений «один ко многим», как с классическими деревьями). Конечно, перемещение вниз по иерархии вернет все узлы, которые происходят от C, а перемещение вверх по иерархии вернет все узлы-предки C. Я не понимаю, как какие-либо узлы, прямо или косвенно связанные с C, могут быть исключены, используя это метод.   -  person Biscuits    schedule 28.08.2015
comment
D является потомком C, поэтому для достижения D нам нужно спуститься вниз по иерархии. Но тогда мы должны подняться, чтобы достичь F, а затем снова спуститься, чтобы достичь G.   -  person Giorgos Betsos    schedule 28.08.2015
comment
Хорошо, теперь я понимаю, что вы имеете в виду. Моего предложения недостаточно. На ум приходит заливка. en.m.wikipedia.org/wiki/Flood_fill   -  person Biscuits    schedule 28.08.2015


Ответы (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

Вот скрипка для этого. Если вам нужны отдельные узлы, просто используйте:

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

в конце запроса.

Этот запрос на самом деле является поиском в ширину на неориентированном графе.

Примечание. Судя по комментарию Хогана, нет необходимости проверять путь, так как в таблице отношений есть первичный ключ (чего я не заметил), мы можем искать первичный ключ в предыдущих рекурсиях чтобы избежать бесконечных циклов.

person Taher Rahgooy    schedule 28.08.2015
comment
не будет ли отдельный идентификатор для данного узла работать так же, как путь кажется проще. - person Hogan; 28.08.2015
comment
Да, я добавил путь, просто чтобы визуализировать процесс поиска. - person Taher Rahgooy; 28.08.2015
comment
Ах, хорошо, вы сказали сделать путь, чтобы избежать, поэтому я предположил, что вы имели в виду именно это. - person Hogan; 28.08.2015
comment
Нет, путь не нужен, чтобы избежать попадания в цикл, я имел в виду включение пути в результат для визуализации процесса поиска. Как мы можем дать отдельный идентификатор каждому узлу? можно подробнее? - person Taher Rahgooy; 28.08.2015
comment
Id INT NOT NULL PRIMARY KEY, ‹-- первичный ключ уникален. Вы можете искать первичный ключ в предыдущих рекурсиях и не беспокоиться о совпадении путей. Это также будет намного быстрее, потому что у него есть index. - person Hogan; 28.08.2015
comment
Да, вы правы, я не заметил, что отношение имеет первичный ключ, обычно отношения «многие ко многим» не имеют уникального идентификатора, я работал, исходя из этого предположения. - person Taher Rahgooy; 28.08.2015