Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Microsoft SQL Server |
![]() ![]() |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
Добрый день! Есть таблица, в которой описано дерево. Первый столбец номер ноды, второй - его предок, например: 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] Ответить | Цитировать Сообщить модератору |
TaPaK Member Откуда: Kiev Сообщений: 6801 |
Roust_m, это же прям пример из хелпа |
12 апр 19, 10:55 [21860261] Ответить | Цитировать Сообщить модератору |
court Member Откуда: Сообщений: 2241 |
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] Ответить | Цитировать Сообщить модератору |
court Member Откуда: Сообщений: 2241 |
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] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
court, Спасибо. |
15 апр 19, 02:09 [21861837] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
А можно ли их еще упорядочить на каждом уровне, например, в маленьком дереве выше, потомки ноды 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] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
Таже было бы здорово, если бы в первой таблице можно было автоматически вычислить предков по типу ноды: 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] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
dklim.kzn Member Откуда: Казань Сообщений: 123 |
но опять думаю, что всё это древостроение скорее всего что-то не то из серии разработать алгоритм поиска ближайшего расстояния между любыми двумя точками при этом для всех точек строим такие деревья соседей и соседей соседей тогда как алгоритм строится и без них, sql прекрасно бегает по всему полю сам, параллельно и пачками)) |
15 апр 19, 08:47 [21861930] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
Нет, это не то, что мне нужно. Запрос выше, это запрос построения так называемой 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] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
Не совсем понял, мне нужно получить из вот этой исходной таблицы: 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] Ответить | Цитировать Сообщить модератору |
court Member Откуда: Сообщений: 2241 |
... 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] Ответить | Цитировать Сообщить модератору |
dklim.kzn Member Откуда: Казань Сообщений: 123 |
давайте, Вы запустите? ))) я просто последний месяц оконки топчу, как-то уверен в своем запросе))) |
||||
15 апр 19, 14:42 [21862569] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
dklim.kzn, Прошу пардон, не туда запрос присобачил, все работает. |
16 апр 19, 02:46 [21863143] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
Я нашел как расчитать предка по типу ноды. Пришлось делать цикл, одним запросом не получилось: Сначала создал столбец для 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] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
А можно ли одним запросом рекурсивно удалить ноду и всех ее потомков? Например в дереве ниже, при удалении ноды 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] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
Можно конечно удалить ноду, а потом в цикле искать другие ноды у которых несуществующий потомок и удалять их пока не дойдешь до самого нижнего уровня, но это не очень лаконично. |
16 апр 19, 10:14 [21863333] Ответить | Цитировать Сообщить модератору |
TaPaK Member Откуда: Kiev Сообщений: 6801 |
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] Ответить | Цитировать Сообщить модератору |
TaPaK Member Откуда: Kiev Сообщений: 6801 |
Хотя правильнее фильтровать для удаления в самом cte, большие деревья это не всегда быстро. Мы вообще всегда храними паралkельно таблицу ParentId - ChildId |
16 апр 19, 10:32 [21863361] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
Спасибо. В дереве будет от силы 1000 нодов, не думаю, что это станет большой проблемой. Подход "Closure table" тестировали на примере дерева в пол-ляма нодов и оно работало достаточно шустро. |
||
16 апр 19, 10:39 [21863374] Ответить | Цитировать Сообщить модератору |
TaPaK Member Откуда: Kiev Сообщений: 6801 |
"Closure table" какой табле? В остальном наличие мозгов приветсвуется не только у сервера |
||||
16 апр 19, 10:43 [21863378] Ответить | Цитировать Сообщить модератору |
Ролг Хупин Member Откуда: Чебаркуль Сообщений: 3970 |
всё от юзера зависит и от задачи. Можно использовать hierarchyid, там будет и путь, и индекс и практически прямой доступ к узлам |
||
16 апр 19, 10:58 [21863401] Ответить | Цитировать Сообщить модератору |
Roust_m Member Откуда: Сидней Сообщений: 1166 |
Там на англицком правда. |
||||
17 апр 19, 02:31 [21864345] Ответить | Цитировать Сообщить модератору |
Все форумы / Microsoft SQL Server | ![]() |