Помогите написать запрос / Microsoft SQL Server / Sql.ru

Добро пожаловать в форум, Guest >> Войти \| Регистрация \| Поиск \| Правила \|			В избранное \| Подписаться
Все форумы / Microsoft SQL Server

Помогите написать запрос [new]
Roust_m Member Откуда: Сидней Сообщений: 981	Добрый день! Есть таблица, в которой описано дерево. Первый столбец номер ноды, второй - его предок, например: Node Ancestor 1 0 2 1 3 1 4 2 5 2 6 3 7 6 Здесь нода 1 есть основание, то есть у него нет предков. Ноды 2 и 3 есть прямые потомки ноды 1. Ноды 4 и 5 - потомки ноды 2. Нода 6 - потомок ноды 3 и нода 7 - потомок ноды 6. Надо написать запрос (или цикл) на tsql, который рекурсивно, вне зависимости от размера дерева создаст так называемую closure table, где есть Предок, Потомок и расстояние между ними: Ancestor Descendant Distance 1 1 0 1 2 1 1 3 1 1 4 2 1 5 2 1 6 2 1 7 3 2 2 0 2 4 1 2 5 1 3 3 0 3 6 1 3 7 2 4 4 0 5 5 0 6 6 0 6 7 1 Нода 1 есть предок всех остальных, включая себя (между собой расстояние 0), между 1 и его прямыми потомками расстояние 1. Между 1 и "внуками" - расстояние 2 и т.д. для каждого нода. Если у нода нет потомков, как у 4,5 и 7, то записываем только расстояние с самим собой. Для теста можно взять такое дерево: Id Ancestor 1 0 2 1 3 2 4 3 5 4 6 4 7 3 8 7 9 7 10 7 11 7 12 7 13 3 14 7 15 7 16 7 17 7 18 7 19 7 20 3 21 20 22 20 23 20 24 20 25 20 26 3 27 26 28 26 29 26 30 26 31 26 32 26 33 3 34 33 35 33 36 33 37 33 38 33 39 33 40 3 41 40 42 40 43 40 44 40 45 3 46 45 47 45 48 45 49 45 50 45 51 45 В реальности потребуется обрабатывать дерево с числом нод до 2000. Спасибо.
12 апр 19, 10:39 [21860238] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
TaPaK Member Откуда: Kiev Сообщений: 6376	Roust_m, это же прям пример из хелпа
12 апр 19, 10:55 [21860261] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

court
Member

Откуда:
Сообщений: 1733

declare @t table (Id int, Ancestor int)
insert into @t values
(1	,0   ),
(2	,1	 ),
(3	,2	 ),
(4	,3	 ),
(5	,4	 ),
(6	,4	 ),
(7	,3	 ),
(8	,7	 ),
(9	,7	 ),
(10	,7	 ),
(11	,7	 ),
(12	,7	 ),
(13	,3	 ),
(14	,7	 ),
(15	,7	 ),
(16	,7	 ),
(17	,7	 ),
(18	,7	 ),
(19	,7	 ),
(20	,3	 ),
(21	,20	 ),
(22	,20	 ),
(23	,20	 ),
(24	,20	 ),
(25	,20	 ),
(26	,3	 ),
(27	,26	 ),
(28	,26	 ),
(29	,26	 ),
(30	,26	 ),
(31	,26	 ),
(32	,26	 ),
(33	,3	 ),
(34	,33	 ),
(35	,33	 ),
(36	,33	 ),
(37	,33	 ),
(38	,33	 ),
(39	,33	 ),
(40	,3	 ),
(41	,40	 ),
(42	,40	 ),
(43	,40	 ),
(44	,40	 ),
(45	,3	 ),
(46	,45	 ),
(47	,45	 ),
(48	,45	 ),
(49	,45	 ),
(50	,45	 ),
(51	,45	 )


;with cte as (
	select 
		Ancestor		=Id
		,Descendant		=Id
		,Distance		=0
		,Parent			=Id  
		,[Path]			='/'+cast(Id as varchar(max))+'/'
	from @t 

	union all

	select
		cte.Ancestor
		,t.Id
		,cte.Distance+1
		,t.Id
		,cte.[Path]+cast(t.Id as varchar(max))+'/'
	from @t t inner join cte on cte.Parent=t.Ancestor
	where cte.[Path] not like '%/'+cast(t.Id as varchar(max))+'/%'
	
)

select Ancestor, Descendant, Distance  
from cte 
order by 1, 2
option (maxrecursion 0)

12 апр 19, 11:18 [21860280] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

court
Member

Откуда:
Сообщений: 1733

Path, как бы и не нужен (дерево ж всё таки) ... :)

;with cte as (
	select 
		Ancestor		=Id
		,Descendant		=Id
		,Distance		=0
		,Parent			=Id  
--		,[Path]			='/'+cast(Id as varchar(max))+'/'
	from @t 

	union all

	select
		cte.Ancestor
		,t.Id
		,cte.Distance+1
		,t.Id
--		,cte.[Path]+cast(t.Id as varchar(max))+'/'
	from @t t inner join cte on cte.Parent=t.Ancestor
--	where cte.[Path] not like '%/'+cast(t.Id as varchar(max))+'/%'
	
)

select Ancestor, Descendant, Distance  
from cte 
order by 1, 2
option (maxrecursion 0)

12 апр 19, 11:38 [21860313] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
Roust_m Member Откуда: Сидней Сообщений: 981	court, Спасибо.
15 апр 19, 02:09 [21861837] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
Roust_m Member Откуда: Сидней Сообщений: 981	А можно ли их еще упорядочить на каждом уровне, например, в маленьком дереве выше, потомки ноды 1имеют номера 2 и 3. Как добавить столбец, в котором у них будут дополнительные номера 1 и 2? Также под нодой 2 потомки 4 и 5 тоже должны иметь номера 1 и 2. Это желательно сделать в первой таблице: Node Ancestor Order 1 0 1 2 1 1 3 1 2 4 2 1 5 2 2 6 3 1 7 6 1
15 апр 19, 04:48 [21861866] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
Roust_m Member Откуда: Сидней Сообщений: 981	Таже было бы здорово, если бы в первой таблице можно было автоматически вычислить предков по типу ноды: Id node_type ancestor 1 Domain 2 Element 3 Thread 4 Section 5 Indicator 6 Indicator 7 Section 8 Indicator 9 Indicator 10 Indicator 11 Indicator 12 Indicator 13 Section 14 Subsection 15 Indicator 16 Indicator 17 Indicator 18 Indicator 19 Indicator 20 Section 21 Heading 22 Indicator 23 Indicator 24 Indicator 25 Indicator 26 Section 27 Subsection 28 Heading 29 Indicator 30 Indicator 31 Indicator 32 Indicator 33 Section 34 Subsection 35 Heading 36 Indicator 37 Indicator 38 Indicator 39 Indicator 40 Section 41 Indicator 42 Indicator 43 Indicator 44 Indicator 45 Section 46 Indicator 47 Indicator 48 Indicator 49 Indicator 50 Indicator 51 Indicator Тип может быть предствален или именем или номером: Domain 1 Element 2 Thread 3 Section 4 Subsection 5 Heading 6 Indicator 7 Domain всегда у основания дерева, он всеобщий предок. Его следующие потомки: Element. Дальше идут Thread, после них Section. Дальше начинает чехарда, могут быть варианты: Section Indicator или Section Heading Indicator или Section Subsection Heading Indicator То есть каждому Indicator надо найти ближайший к нему выше по списку Section, Subsection или Heading. Думаю проще будет, если их представить номерами и найти ближайший выше по списку номер, который меньше. То есть предком для Indicator (7) будет ближайшая нода с номером типа меньше 7 (например 4, 5 или 6). Для Heading - 4 или 5, для Subsection - 4 и т.д. Заранее спасибо.
15 апр 19, 05:33 [21861875] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
dklim.kzn Member Откуда: Казань Сообщений: 123	... from @t t inner join cte on cte.Parent=t.Ancestor and t.type not in ("Section", "Subsection", "Heading") ...
15 апр 19, 08:35 [21861919] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
dklim.kzn Member Откуда: Казань Сообщений: 123	а упорядочение оконной функцией select node, ancestor, row_number() over (partition by node order by ancestor) n from table order by n
15 апр 19, 08:41 [21861927] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
dklim.kzn Member Откуда: Казань Сообщений: 123	но опять думаю, что всё это древостроение скорее всего что-то не то из серии разработать алгоритм поиска ближайшего расстояния между любыми двумя точками при этом для всех точек строим такие деревья соседей и соседей соседей тогда как алгоритм строится и без них, sql прекрасно бегает по всему полю сам, параллельно и пачками))
15 апр 19, 08:47 [21861930] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
dklim.kzn Member Откуда: Казань Сообщений: 123	всё перепутал, конечно а упорядочение оконной функцией select id, ancestor, row_number() over (partition by ancestor order by id) n from @t order by ancestor, n
15 апр 19, 08:50 [21861933] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

Roust_m
Member

Откуда: Сидней
Сообщений: 981

dklim.kzn
всё перепутал, конечно а упорядочение оконной функцией select id, ancestor, row_number() over (partition by ancestor order by id) n from @t order by ancestor, n

Нет, это не то, что мне нужно. Запрос выше, это запрос построения так называемой clouser table.

Мне исходную таблицу надо расширить:
Node Ancestor Order
1 0 1
2 1 1
3 1 2
4 2 1
5 2 2
6 3 1
7 6 1

Т.е. добавить столбец Order, который показвает порядок нодов на каждом уровне.

15 апр 19, 09:36 [21861972] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

Roust_m
Member

Откуда: Сидней
Сообщений: 981

dklim.kzn
... from @t t inner join cte on cte.Parent=t.Ancestor and t.type not in ("Section", "Subsection", "Heading") ...

Не совсем понял, мне нужно получить из вот этой исходной таблицы:

node_id node_type node_type_id ancestor
1 Domain 1 NULL
2 Element 2 NULL
3 Thread 3 NULL
4 Section 4 NULL
5 Indicator 8 NULL
6 Indicator 8 NULL
7 Section 4 NULL
8 Indicator 8 NULL
9 Indicator 8 NULL
10 Indicator 8 NULL
11 Indicator 8 NULL
12 Indicator 8 NULL
13 Section 4 NULL
14 Indicator 8 NULL
15 Indicator 8 NULL
16 Indicator 8 NULL
17 Indicator 8 NULL
18 Indicator 8 NULL
19 Indicator 8 NULL
20 Section 4 NULL
21 Indicator 8 NULL
22 Indicator 8 NULL
23 Indicator 8 NULL
24 Indicator 8 NULL
25 Indicator 8 NULL
26 Section 4 NULL
27 Indicator 8 NULL
28 Indicator 8 NULL
29 Indicator 8 NULL
30 Indicator 8 NULL
31 Indicator 8 NULL
32 Indicator 8 NULL
33 Section 4 NULL
34 Indicator 8 NULL
35 Indicator 8 NULL
36 Indicator 8 NULL
37 Indicator 8 NULL
38 Indicator 8 NULL
39 Indicator 8 NULL
40 Section 4 NULL
41 Indicator 8 NULL
42 Indicator 8 NULL
43 Indicator 8 NULL
44 Indicator 8 NULL
45 Section 4 NULL
46 Indicator 8 NULL
47 Indicator 8 NULL
48 Indicator 8 NULL
49 Indicator 8 NULL
50 Indicator 8 NULL
51 Indicator 8 NULL

Вот эту:
node_id node_type node_type_id ancestor
1 Domain 1 0
2 Element 2 1
3 Thread 3 2
4 Section 4 3
5 Indicator 8 4
6 Indicator 8 4
7 Section 4 3
8 Indicator 8 7
9 Indicator 8 7
10 Indicator 8 7
11 Indicator 8 7
12 Indicator 8 7
13 Section 4 3
14 Indicator 8 13
15 Indicator 8 13
16 Indicator 8 13
17 Indicator 8 13
18 Indicator 8 13
19 Indicator 8 13
20 Section 4 3
21 Indicator 8 20
22 Indicator 8 20
23 Indicator 8 20
24 Indicator 8 20
25 Indicator 8 20
26 Section 4 3
27 Indicator 8 26
28 Indicator 8 26
29 Indicator 8 26
30 Indicator 8 26
31 Indicator 8 26
32 Indicator 8 26
33 Section 4 3
34 Indicator 8 33
35 Indicator 8 33
36 Indicator 8 33
37 Indicator 8 33
38 Indicator 8 33
39 Indicator 8 33
40 Section 4 3
41 Indicator 8 40
42 Indicator 8 40
43 Indicator 8 40
44 Indicator 8 40
45 Section 4 3
46 Indicator 8 45
47 Indicator 8 45
48 Indicator 8 45
49 Indicator 8 45
50 Indicator 8 45
51 Indicator 8 45

Т.е. посчитать кто чей предок. У домена предок - 0.

15 апр 19, 09:43 [21861978] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

court
Member

Откуда:
Сообщений: 1733

Roust_m

А можно ли их еще упорядочить на каждом уровне, например, в маленьком дереве выше, потомки ноды 1имеют номера 2 и 3. Как добавить столбец, в котором у них будут дополнительные номера 1 и 2? Также под нодой 2 потомки 4 и 5 тоже должны иметь номера 1 и 2. Это желательно сделать в первой таблице:

Node Ancestor Order
1 0 1
2 1 1
3 1 2
4 2 1
5 2 2
6 3 1
7 6 1

...

select Ancestor, Descendant, Distance,
    Order = row_number()over(partition by Ancestor order by Descendant)  
from cte 
order by 1, 2
option (maxrecursion 0)

15 апр 19, 09:49 [21861985] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

dklim.kzn
Member

Откуда: Казань
Сообщений: 123

Roust_m

dklim.kzn
всё перепутал, конечно а упорядочение оконной функцией select id, ancestor, row_number() over (partition by ancestor order by id) n from @t order by ancestor, n

давайте, Вы запустите? )))
я просто последний месяц оконки топчу, как-то уверен в своем запросе)))

15 апр 19, 14:42 [21862569] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
Roust_m Member Откуда: Сидней Сообщений: 981	dklim.kzn, Прошу пардон, не туда запрос присобачил, все работает.
16 апр 19, 02:46 [21863143] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

Roust_m
Member

Откуда: Сидней
Сообщений: 981

Я нашел как расчитать предка по типу ноды. Пришлось делать цикл, одним запросом не получилось:

Сначала создал столбец для node_type_id во временной таблице и заполнил его цифрами от 1 до 8 (в зависимости от типа ноды)

update old.pn_staging set node_type_id = 1 where node_type = 'Domain'
update old.pn_staging set node_type_id = 2 where node_type = 'Element'
update old.pn_staging set node_type_id = 3 where node_type = 'Thread'
update old.pn_staging set node_type_id = 4 where node_type = 'Section'
update old.pn_staging set node_type_id = 5 where node_type = 'Subsection'
update old.pn_staging set node_type_id = 6 where node_type = 'Heading'
update old.pn_staging set node_type_id = 7 where node_type = 'Subheading'
update old.pn_staging set node_type_id = 8 where node_type = 'Indicator'

Потом в цикле искал ближайшую выше по списку ноды у которой тип ноды меньше чем у текущей ноды:

set nocount on
  declare @node_id int, @ancestor int, @node_type_id int
  select @node_id = min(node_id)   from [old].pn_staging
  select @node_type_id = node_type_id from [old].pn_staging where node_id = @node_id
  while @node_id is not null
  begin
	--select @node_id, @node_type_id
	select @ancestor = max(node_id) FROM old.pn_staging where node_id < @node_id and node_type_id < @node_type_id
	update old.pn_staging set ancestor_test = ISNULL(@ancestor, 0) where node_id = @node_id 
	select @node_id = min(node_id)   from [old].pn_staging where node_id > @node_id
	select @node_type_id = node_type_id from [old].pn_staging where node_id = @node_id
  end
set nocount off

16 апр 19, 10:04 [21863318] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
Roust_m Member Откуда: Сидней Сообщений: 981	А можно ли одним запросом рекурсивно удалить ноду и всех ее потомков? Например в дереве ниже, при удалении ноды 4 удаляются также ноды 5 и 6. А при удалении ноды 2 также удаляются все ноды от 3 до 51. Ну и при удалении ноды 1 удаляется все. Node_id Ancestor 1 0 2 1 3 2 4 3 5 4 6 4 7 3 8 7 9 7 10 7 11 7 12 7 13 3 14 7 15 7 16 7 17 7 18 7 19 7 20 3 21 20 22 20 23 20 24 20 25 20 26 3 27 26 28 26 29 26 30 26 31 26 32 26 33 3 34 33 35 33 36 33 37 33 38 33 39 33 40 3 41 40 42 40 43 40 44 40 45 3 46 45 47 45 48 45 49 45 50 45 51 45
16 апр 19, 10:09 [21863328] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
Roust_m Member Откуда: Сидней Сообщений: 981	Можно конечно удалить ноду, а потом в цикле искать другие ноды у которых несуществующий потомок и удалять их пока не дойдешь до самого нижнего уровня, но это не очень лаконично.
16 апр 19, 10:14 [21863333] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
TaPaK Member Откуда: Kiev Сообщений: 6376	Roust_m, DELETE a FROM @t a WHERE EXISTS (SELECt 1 FROM cte WHERE Descendant = a.Id AND Ancestor =4) option (maxrecursion 0)
16 апр 19, 10:25 [21863353] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]
TaPaK Member Откуда: Kiev Сообщений: 6376	Хотя правильнее фильтровать для удаления в самом cte, большие деревья это не всегда быстро. Мы вообще всегда храними паралkельно таблицу ParentId - ChildId
16 апр 19, 10:32 [21863361] Ответить \| Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

Roust_m
Member

Откуда: Сидней
Сообщений: 981

TaPaK
Хотя правильнее фильтровать для удаления в самом cte, большие деревья это не всегда быстро. Мы вообще всегда храними паралkельно таблицу ParentId - ChildId

Спасибо.

В дереве будет от силы 1000 нодов, не думаю, что это станет большой проблемой. Подход "Closure table" тестировали на примере дерева в пол-ляма нодов и оно работало достаточно шустро.

16 апр 19, 10:39 [21863374] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

TaPaK
Member

Откуда: Kiev
Сообщений: 6376

Roust_m

TaPaK
Хотя правильнее фильтровать для удаления в самом cte, большие деревья это не всегда быстро. Мы вообще всегда храними паралkельно таблицу ParentId - ChildId

"Closure table" какой табле?

В остальном наличие мозгов приветсвуется не только у сервера

16 апр 19, 10:43 [21863378] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 2717

court
Path, как бы и не нужен (дерево ж всё таки) ... :)

всё от юзера зависит и от задачи.
Можно использовать hierarchyid, там будет и путь, и индекс и практически прямой доступ к узлам

16 апр 19, 10:58 [21863401] Ответить | Цитировать Сообщить модератору

Re: Помогите написать запрос [new]

Roust_m
Member

Откуда: Сидней
Сообщений: 981

TaPaK

Roust_m
пропущено... Спасибо. В дереве будет от силы 1000 нодов, не думаю, что это станет большой проблемой. Подход "Closure table" тестировали на примере дерева в пол-ляма нодов и оно работало достаточно шустро.

"Closure table" какой табле?

В остальном наличие мозгов приветсвуется не только у сервера

Там на англицком правда.

17 апр 19, 02:31 [21864345] Ответить | Цитировать Сообщить модератору

Все форумы / Microsoft SQL Server

Ссылка на сообщение

Ссылка (включая название темы)

Ссылка (URL)