SQL сложный рекурсивный CTE

Question

Я работаю в SQL Server 2014. У меня странная ситуация с иерархией данных. (По крайней мере, я не испытывал ничего подобного раньше.)

В моей иерархии есть несколько объектов корневого / высшего уровня. Каждый объект ниже корневого уровня отображается на один и только один объект над ним. Не каждый путь узла имеет одинаковую длину. Например, один путь может содержать 2 уровня объекта, а другой путь может содержать 20 уровней объекта.

Каждый объект в иерархии имеет IsInherited атрибут, а также некоторые другие атрибуты (назовите его SomeAttribute). IsInherited атрибут указывает, наследует ли данный объект значение SomeAttribute от его самого непосредственного родителя. Естественно, если объект IsInherited атрибут "Y", то данный объект наследует значение SomeAttribute от самого непосредственного родителя (который, в свою очередь, может наследовать его значение для самого непосредственного родителя и т. д.). В противном случае объект SomeAttribute значение указано.

Теперь все вышеперечисленное не обязательно является редкостью. Что делает эту ситуацию необычной, так это конкретная реализация этого наследования. Эта иерархия хранится в одной таблице (делает ли это модель списка смежности?), А значение SomeAttribute не заполняется для данного объекта / строки, если его IsInherited Атрибут "Y".

Моя цель - вернуть ценность SomeAttribute для всех объектов в иерархии.

Пример таблицы выглядит следующим образом:

CREATE TABLE hierarchy (
    ID int NOT NULL
    ,ParentID int NULL
    ,SomeAttribute char(1) NULL
    ,IsInherited char(1) NOT NULL
)
;
INSERT INTO hierarchy (ID, ParentID, SomeAttribute, IsInherited)
VALUES
(1, NULL, 'a', 'N')
,(2, NULL, 'b', 'N')
,(3, NULL, 'c', 'N')
,(4, NULL, 'd', 'N')
,(5, NULL, 'e', 'N')
,(6, NULL, 'f', 'N')
,(7, NULL, 'g', 'N')
,(8, 2, NULL, 'Y')
,(9, 3, 'h', 'N')
,(10, 4, NULL, 'Y')
,(11, 5, 'j', 'N')
,(12, 6, NULL, 'Y')
,(13, 6, 'k', 'N')
,(14, 7, 'l', 'N')
,(15, 7, 'm', 'N')
,(16, 10, NULL, 'Y')
,(17, 11, NULL, 'Y')
,(18, 16, NULL, 'Y')
,(19, 17, NULL, 'Y')
,(20, 19, 'o', 'N')
;

Это дает нам следующие пути к узлам:

1
2-8
3-9
4-10-16-18
5-11-17-19-20
6-12,13
7-14,15

Итак, с этим образцом таблицы я ожидаю возврата:

ID    SomeAttribute
1     a
2     b
3     c
4     d
5     e
6     f
7     g
8     b (inherited from 2)
9     h
10    d (inherited from 4)
11    j
12    f (inherited from 6)
13    k
14    l
15    m
16    d (inherited from 10, inherited from 4)
17    j (inherited from 11)
18    d (inherited from 16, inherited from 10, inherited from 4)
19    j (inherited from 17, inherited from 11)
20    o

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

Answer 1

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

И рекурсивный CTE будет выглядеть так:

 with q as
(
  select id, SomeAttribute, cast(id as varchar(max)) SomeAttributePath
  from hierarchy
  where ParentID is null
  union all
  select c.id, case when c.IsInherited = 'Y' then q.SomeAttribute else c.SomeAttribute end as SomeAttribute, cast(concat(q.SomeAttributePath,'-',c.id) as varchar(max))
  from q
  join hierarchy c
  on c.ParentID = q.ID
)
select *
from q
order by id

Outputing:

id          SomeAttribute SomeAttributePath
----------- ------------- -----------------
1           a             1
2           b             2
3           c             3
4           d             4
5           e             5
6           f             6
7           g             7
8           b             2-8
9           h             3-9
10          d             4-10
11          j             5-11
12          f             6-12
13          k             6-13
14          l             7-14
15          m             7-15
16          d             4-10-16
17          j             5-11-17
18          d             4-10-16-18
19          j             5-11-17-19
20          o             5-11-17-19-20