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

Откуда: Сидней
Сообщений: 950
Добрый день!

Есть таблица, в которой описано дерево. Первый столбец номер ноды, второй - его предок, например:
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
Сообщений: 6155
Roust_m,

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

Откуда:
Сообщений: 1647
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)

+
AncestorDescendantDistance
110
121
132
143
154
164
173
184
194
1104
1114
1124
1133
1144
1154
1164
1174
1184
1194
1203
1214
1224
1234
1244
1254
1263
1274
1284
1294
1304
1314
1324
1333
1344
1354
1364
1374
1384
1394
1403
1414
1424
1434
1444
1453
1464
1474
1484
1494
1504
1514
220
231
242
253
263
272
283
293
2103
2113
2123
2132
2143
2153
2163
2173
2183
2193
2202
2213
2223
2233
2243
2253
2262
2273
2283
2293
2303
2313
2323
2332
2343
2353
2363
2373
2383
2393
2402
2413
2423
2433
2443
2452
2463
2473
2483
2493
2503
2513
330
341
352
362
371
382
392
3102
3112
3122
3131
3142
3152
3162
3172
3182
3192
3201
3212
3222
3232
3242
3252
3261
3272
3282
3292
3302
3312
3322
3331
3342
3352
3362
3372
3382
3392
3401
3412
3422
3432
3442
3451
3462
3472
3482
3492
3502
3512
440
451
461
550
660
770
781
791
7101
7111
7121
7141
7151
7161
7171
7181
7191
880
990
10100
11110
12120
13130
14140
15150
16160
17170
18180
19190
20200
20211
20221
20231
20241
20251
21210
22220
23230
24240
25250
26260
26271
26281
26291
26301
26311
26321
27270
28280
29290
30300
31310
32320
33330
33341
33351
33361
33371
33381
33391
34340
35350
36360
37370
38380
39390
40400
40411
40421
40431
40441
41410
42420
43430
44440
45450
45461
45471
45481
45491
45501
45511
46460
47470
48480
49490
50500
51510
12 апр 19, 11:18    [21860280]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос  [new]
court
Member

Откуда:
Сообщений: 1647
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

Откуда: Сидней
Сообщений: 950
court,

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

Откуда: Сидней
Сообщений: 950
А можно ли их еще упорядочить на каждом уровне, например, в маленьком дереве выше, потомки ноды 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

Откуда: Сидней
Сообщений: 950
Таже было бы здорово, если бы в первой таблице можно было автоматически вычислить предков по типу ноды:

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

Откуда: Казань
Сообщений: 101
...
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

Откуда: Казань
Сообщений: 101
а упорядочение оконной функцией

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

Откуда: Казань
Сообщений: 101
но опять думаю, что всё это древостроение скорее всего что-то не то
из серии разработать алгоритм поиска ближайшего расстояния между любыми двумя точками
при этом для всех точек строим такие деревья соседей и соседей соседей

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

Откуда: Казань
Сообщений: 101
всё перепутал, конечно

а упорядочение оконной функцией

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

Откуда: Сидней
Сообщений: 950
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

Откуда: Сидней
Сообщений: 950
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

Откуда:
Сообщений: 1647
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

Откуда: Казань
Сообщений: 101
Roust_m
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, 14:42    [21862569]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос  [new]
Roust_m
Member

Откуда: Сидней
Сообщений: 950
dklim.kzn,

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

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

Сначала создал столбец для 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

Откуда: Сидней
Сообщений: 950
А можно ли одним запросом рекурсивно удалить ноду и всех ее потомков? Например в дереве ниже, при удалении ноды 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

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

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

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


Спасибо.

В дереве будет от силы 1000 нодов, не думаю, что это станет большой проблемой. Подход "Closure table" тестировали на примере дерева в пол-ляма нодов и оно работало достаточно шустро.
16 апр 19, 10:39    [21863374]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос  [new]
TaPaK
Member

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


Спасибо.

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

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

В остальном наличие мозгов приветсвуется не только у сервера
16 апр 19, 10:43    [21863378]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 2487
court
Path, как бы и не нужен (дерево ж всё таки) ... :)


всё от юзера зависит и от задачи.
Можно использовать hierarchyid, там будет и путь, и индекс и практически прямой доступ к узлам
16 апр 19, 10:58    [21863401]     Ответить | Цитировать Сообщить модератору
 Re: Помогите написать запрос  [new]
Roust_m
Member

Откуда: Сидней
Сообщений: 950
TaPaK
Roust_m
пропущено...


Спасибо.

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

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

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




Там на англицком правда.
17 апр 19, 02:31    [21864345]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить