Иерархия SQL - разрешить полный путь для всех предков данного узла

Question

У меня есть иерархия, описываемая списком смежности. Существует не обязательно один корневой элемент, но у меня есть данные для идентификации элементов листа (терминала) в hiearchy. Итак, иерархия, которая выглядела так:

1 
- 2 
- - 4 
- - - 7 
- 3 
- - 5 
- - 6 
8 
- 9 

... был бы описан таблицей, как это. ПРИМЕЧАНИЕ: У меня нет возможности изменить этот формат.

id parentid isleaf 
--- -------- ------ 
1 null  0 
2 1  0 
3 1  0 
4 2  0 
5 3  1 
6 3  1 
7 4  1 
8 null  0 
9 8  1 

здесь образец определение таблицы и данные:

CREATE TABLE [dbo].[HiearchyTest](
    [id] [int] NOT NULL, 
    [parentid] [int] NULL, 
    [isleaf] [bit] NOT NULL 
) 
GO 

INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (1, NULL, 0) 
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (2, 1, 0) 
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (3, 1, 0) 
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (4, 2, 0) 
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (5, 3, 1) 
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (6, 3, 1) 
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (7, 4, 1) 
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (8, NULL, 0) 
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (9, 8, 1) 
GO 

Исходя из этого, необходимо предоставить любой идентификатор и получить список всех предков, включая все потомок каждый. Так что, если я обеспечил вход ид = 6, я ожидал бы следующее:

id descendentid 
-- ------------ 
1 1 
1 3 
1 6 
3 3 
3 6 
6 6 

• идентификатора 6 раз сам имеет
• родительские, идентификатор 3 будет иметь decendents 3 и 6
• его родитель, ID 1 будет иметь decendents 1, 3 и 6

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

Я выполнил это, используя два возвратных элемента - один, чтобы получить «терминал» для каждого узла в hiearchy. Затем, второй, где я получаю полную предков моего выбранного узла (так, 6 разрешается до 6, 3, 1), чтобы подняться и получить полный набор. Я надеюсь, что я что-то упустил и что это можно сделать за один раунд. Вот пример кода двойной рекурсии:

declare @test int = 6; 

with cte as (

    -- leaf nodes 
    select id, parentid, id as terminalid 
    from HiearchyTest 
    where isleaf = 1 

    union all 

    -- walk up - preserve "terminal" item for all levels 
    select h.id, h.parentid, c.terminalid 
    from HiearchyTest as h 
    inner join 
    cte as c on h.id = c.parentid 

) 

, cte2 as (

    -- get all ancestors of our test value 
    select id, parentid, id as descendentid 
    from cte 
    where terminalid = @test 

    union all 

    -- and walkup from each to complete the set 
    select h.id, h.parentid, c.descendentid 
    from HiearchyTest h 
    inner join cte2 as c on h.id = c.parentid 

) 

-- final selection - order by is just for readability of this example 
select id, descendentid 
from cte2 
order by id, descendentid 

Дополнительная деталь: «реальная» иерархия будет гораздо больше, чем, например. Он может технически иметь бесконечную глубину, но реалистично он редко бывал более чем на 10 уровнях.

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

Answer 1

Хорошо, это беспокоило меня, так как я прочитал вопрос, и я только что вернулся, чтобы снова подумать об этом ..... Во всяком случае, зачем вам возвращаться, чтобы получить всех потомков? Вы попросили предков, а не потомков, и ваш результирующий набор не пытается получить других братьев и сестер, внуков и т. Д. В этом случае он получает родителя и великого родителя. Ваш первый cte дает вам все, что вам нужно знать, кроме случаев, когда id предка также является родителем. Таким образом, с объединением все, немного волшебства, чтобы настроить изначального предка, и у вас есть все, что вам нужно, без второй рекурсии.

declare @test int = 6; 

with cte as (

    -- leaf nodes 
    select id, parentid, id as terminalid 
    from HiearchyTest 
    where isleaf = 1 

    union all 

    -- walk up - preserve "terminal" item for all levels 
    select h.id, h.parentid, c.terminalid 
    from HiearchyTest as h 
    inner join 
    cte as c on h.id = c.parentid 

) 

, cteAncestors AS (

    SELECT DISTINCT 
     id = IIF(parentid IS NULL, @Test, id) 
     ,parentid = IIF(parentid IS NULL,id,parentid) 
    FROM 
     cte 
    WHERE 
     terminalid = @test 

    UNION 

    SELECT DISTINCT 
     id 
     ,parentid = id 
    FROM 
     cte 
    WHERE 
     terminalid = @test 
) 

SELECT 
    id = parentid 
    ,DecendentId = id 
FROM 
    cteAncestors 
ORDER BY 
    id 
    ,DecendentId 

Ваш набор результатов с первого cte дает Вам 2 ancestors и сам, связанные с их ancestor за исключением случая возникая предков кто есть parentidis null. Это null - это специальный случай, с которым я поговорю через минуту.

Запомнить на этом этапе ваш запрос производит Ancestors не descendants, но то, что он не дает вам это само ссылки означает grandparent = grandparent, parent = parent, self = self. Но все, что вам нужно сделать, это добавить строки для каждого id и сделать parentid равным их id. следовательно, union. Теперь ваш результирующий набор почти полностью подтянулись:

Особый случай null parentid. Таким образом, null parentid идентифицирует originatingancestor, что означает, что ancestor не имеет других ancestor в вашем наборе данных. И вот как вы будете использовать это в своих интересах. Поскольку вы начали свою первоначальную рекурсию на leaf level, прямой привязку к id, с которой вы начали с originating ancestor, но есть на каждом другом уровне, просто захватите этот нулевой родительский идентификатор и переверните значения вокруг, и теперь у вас есть предок для вашего листа.

Затем, в конце концов, если вы хотите, чтобы таблица потомков переключать столбцы и вы закончите. Последнее примечание DISTINCT s есть в случае повторения id с дополнительным parentid. Например. 6 | 3 и еще один рекорд для 6 | 4

Answer 2

Я не уверен, если это работает лучше, или даже производит соответствующие результаты во всех случаях, но вы могли бы захватить список узлов, а затем использовать функциональные возможности XML, чтобы разобрать его и крест применить к списку ID:

declare @test int = 6; 

;WITH cte AS (SELECT id, parentid, CAST(id AS VARCHAR(MAX)) as IDlist 
       FROM HiearchyTest 
       WHERE isleaf = 1 
       UNION ALL 
       SELECT h.id, h.parentid , CAST(CONCAT(c.IDlist,',',h.id) AS VARCHAR(MAX)) 
       FROM HiearchyTest as h 
       JOIN cte as c 
       ON h.id = c.parentid 
      ) 
    ,cte2 AS (SELECT *, CAST ('<M>' + REPLACE(IDlist, ',', '</M><M>') + '</M>' AS XML) AS Data 
       FROM cte 
       WHERE IDlist LIKE '%'+CAST(@test AS VARCHAR(50))+'%' 
      ) 
SELECT id,Split.a.value('.', 'VARCHAR(100)') AS descendentid 
FROM cte2 a 
CROSS APPLY Data.nodes ('/M') AS Split(a); 

Answer 3

Поскольку ваши данные древовидной структуры, мы можем использовать тип данных hierarchyid` в для удовлетворения ваших потребностей (несмотря на Ваше высказывание, что вы не можете в комментариях). Во-первых, легкая часть - генерации hierarchyid` в с рекурсивного CTE

with cte as (

    select id, parentid, 
     cast(concat('/', id, '/') as varchar(max)) as [path] 
    from [dbo].[HiearchyTest] 
    where ParentID is null 

    union all 

    select child.id, child.parentid, 
     cast(concat(parent.[path], child.id, '/') as varchar(max)) 
    from [dbo].[HiearchyTest] as child 
    join cte as parent 
     on child.parentid = parent.id 
) 
select id, parentid, cast([path] as hierarchyid) as [path] 
into h 
from cte; 

Далее, столик-функция я писал:

create function dbo.GetAllAncestors(@h hierarchyid, @ReturnSelf bit) 
returns table 
as return 
    select @h.GetAncestor(n.n) as h 
    from dbo.Numbers as n 
    where n.n <= @h.GetLevel() 
     or (@ReturnSelf = 1 and n.n = 0) 

    union all 

    select @h 
    where @ReturnSelf = 1; 

Вооруженный с этим, получение нужного набора результатов не тоже плохо:

declare @h hierarchyid; 

set @h = (
    select path 
    from h 
    where id = 6 
); 

with cte as (
    select * 
    from h 
    where [path].IsDescendantOf(@h) = 1 
     or @h.IsDescendantOf([path]) = 1 
) 
select h.id as parent, c.id as descendentid 
from cte as c 
cross apply dbo.GetAllAncestors([path], 1) as a 
join h 
    on a.h = h.[path] 
order by h.id, c.id; 

конечно, вам не хватает на много выгоды от использования hierarchyid` в, не сохраняющиеся его (вы должны либо держать его в актуальном состоянии в тумбочке или генерировать Это каждый раз). Но ты туда.