Получить всех детей и их детей, рекурсивный SQL

Question

Рассмотрим следующие строки в базе данных:

Id      |   Parent
__________________
1           null
2           1
3           2
4           3
5           null
6           5

Каждый Id, имеющий null Parent, является "владельцем" / "суперпопулярным".

Каков наилучший подход с точки зрения производительности, чтобы собрать родителей и их детей?Должен ли я использовать LINQ или Хранимые процедуры ?

Я хочу, чтобы конечный результат был IEnumerable<IEnumerable<int>>.

Answer 1

В SQL вы можете выполнять запросы, используя CTE.Например, чтобы получить список узлов с их родителем и наивысшим родителем в их дереве:

declare @t table (id int, parent int)
insert @t (id, parent) values (1, null), (2,1), (3,2), (4,3), (5,null), (6,5)

; with cte as (
    select  id, parent, id as head
    from    @t
    where   parent is null
    union all
    select  child.id, child.parent, parent.head
    from    @t child
    join    cte parent
    on      parent.id = child.parent
)
select  *
from    cte

Это даст:

id  parent  head
1   NULL    1
2   1       1
3   2       1
4   3       1
5   NULL    5
6   5       5

Обратите внимание, что я изменил данные вашего примера, чтобы строка2 уже не дитя само по себе, а дитя ряда 1.

Answer 2

Вы также можете использовать чисто SQL-решение; Вот пример для SQL Server. Нетрудно переписать его для другого менеджера БД:

/* Create table */
CREATE TABLE dbo.Nodes (ID int NOT NULL PRIMARY KEY, Parent int)

/* Insert sample data */
INSERT INTO Nodes VALUES (1,NULL)
INSERT INTO Nodes VALUES (2,1)
INSERT INTO Nodes VALUES (3,2)
INSERT INTO Nodes VALUES (4,3)
INSERT INTO Nodes VALUES (5,NULL)
INSERT INTO Nodes VALUES (6,5)

/* Create recursive function */
CREATE function dbo.fn_Root(@ID int) returns int
AS BEGIN
   DECLARE @R int

   SELECT @R = CASE WHEN Parent IS NULL THEN ID
                    ELSE dbo.fn_Root(Parent)
                 END
            FROM Nodes
           WHERE id = @id

   RETURN @R
END

/* Query the table */
SELECT ID, Parent, dbo.fn_Root(ID) AS Root
  FROM Nodes

/* Also, in SQL Server you can create a calculated column */
ALTER TABLE Nodes ADD Root AS dbo.fn_Root(id)

Это базовая версия. Но этот не удастся, если ваши данные имеют замкнутые циклы (не древовидная структура). Чтобы запретить ввод кода в бесконечном цикле, функцию можно улучшить следующим образом:

CREATE function dbo.fn_Root(@ID int, @Initial int) returns int
AS BEGIN
   DECLARE @R int

   DECLARE @Parent int
   SELECT @Parent = Parent FROM Nodes WHERE ID = @ID

   IF @Parent IS NULL 
      SELECT @R = @ID   /* No parent, the root is the node itself */
   ELSE
      IF @Parent = @Initial 
         /* We have returned to initial node: endless loop. We return NULL to indicate no root exists */
         SELECT @R = NULL
      ELSE
         /* The root will be the root of the parent node */
         SELECT @R = dbo.fn_Root(@Parent,@Initial)   

   RETURN @R

END

/* Query the table */
SELECT ID, Parent, dbo.fn_Root(ID,ID) AS Root FROM Nodes

С этой модификацией, если функция возвращает NULL, это означает, что узел является частью цикла, и поэтому у него нет корневого узла.

Answer 3

Если таблица не слишком большая, вам лучше всего вернуть всю таблицу, выполнив это db.Categories

После того, как вся таблица категорий будет выбрана в Entity Framework, EF будет использовать диапазон отношений для исправления.объект граф, поэтому, когда вы делаете category.SubCategories вы получите все дети.Преимущество этого в том, что ваш sql не будет сложным, потому что он будет в основном выбирать * из категорий.EF проделает большую часть тяжелой работы по исправлению графа объектов, чтобы все дети правильно совмещались со своими родителями.

Вы также можете использовать то, что упоминал кто-то другой, используя общее табличное выражение.

Я рассматриваю два таких понятия в своей книге.

5-11 Использование диапазона отношений 5-2 Загрузка полного графа объектов (CTE)

Answer 4

Базы данных не предназначены для произвольной рекурсии глубины.Вот требуемая операция, выполненная локально.

List<Item> items = context.Items.ToList();

Dictionary<int, Item> itemsById = items.ToDictionary(item => item.Id);

Dictionary<int, List<Item>> itemsByRoot = new Dictionary<int, List<Item>>();
List<Item> cyclicals = new List<Item>();

foreach(Item item in items)
{
  HashSet<int> seenIt = new HashSet<int>();
  Item parent = item;
  while (parent.ParentId != null && !seenIt[parent.Id])
  {
    seenIt.Add(parent.Id);
    parent = itemsById[parent.ParentId];
  }

  if (parent.ParentId == null)
  {
    if (!itemsByRoot.ContainsKey(parent.Id))
    {
      itemsByRoot[parent.Id] = new List<Item>();
    }
    itemsByRoot[parent.Id].Add(item);
  }
  else
  {
    cyclicals.Add(item);
  }
}