В табличке хранятся разные деревья, т.е. группы записей, иерархически связанные по ParentId -> Id (ParentId is null — "корни").
Упрощенно, такая структура:
create table Trees (
Id int identity (1, 1) primary key, -- автоинкрементное поле в синтаксисе MS SQL
ParentId int null foreign key references Trees(Id), -- можно и без констрейнта, не суть
TreeId int not null ) -- все узлы с одним TreeId - это одно дерево, а "корней" м.б. и несколько
Задача — склонировать дерево (для каждой записи из набора с одним TreeId создать по 1 записи с новым TreeId с сохранением структуры ссылок ParentId -> Id).
Можно ли написать такую процедуру/скрипт без всякой рекурсии и циклов, простыми insert/update?
А без временных таблиц и т.п.?
Старые Id могут быть с разрывами, а новые Id пойдут подряд — это автоинкремент, мы до вставки их вообще не узнаем.
На входе — 2 параметра/переменных, @OldTreeId и @NewTreeId (можно рассчитывать, что записей с TreeId=@NewTreeId в табличке нет.)
И можно рассчитывать, что все связи ParentId -> Id — внутри группы записей с одним TreeId.
Решение я нашел, а у вас получится? Задача на реальном проекте возникла, кстати.
Здравствуйте, L_G, Вы писали:
L_G>TreeId int not null ) -- все узлы с одним TreeId — это одно дерево, а "корней" м.б. и несколько L_G>[/sql]
Если корней может быть несколько, то это уже не дерево, а лес, и поле должно называться не TreeId, а ForestId.
Мир не просто сложнее, чем мы себе представляем, -- он сложнее, чем мы можем себе представить.
Здравствуйте, L_G, Вы писали:
L_G>Можно ли написать такую процедуру/скрипт без всякой рекурсии и циклов, простыми insert/update? L_G>А без временных таблиц и т.п.?
Это должно быть одно выражение или несколько? ANSI SQL или можно пользоваться современными расширениями типа Common Table Expression?
Здравствуйте, L_G, Вы писали:
L_G>В табличке хранятся разные деревья, т.е. группы записей, иерархически связанные по ParentId -> Id (ParentId is null — "корни"). L_G>Упрощенно, такая структура: L_G>
L_G>create table Trees (
L_G>Id int identity (1, 1) primary key, -- автоинкрементное поле в синтаксисе MS SQL
L_G>ParentId int null foreign key references Trees(Id), -- можно и без констрейнта, не суть
L_G>TreeId int not null ) -- все узлы с одним TreeId - это одно дерево, а "корней" м.б. и несколько
L_G>
Задача — склонировать дерево (для каждой записи из набора с одним TreeId создать по 1 записи с новым TreeId с сохранением структуры ссылок ParentId -> Id). L_G>Можно ли написать такую процедуру/скрипт без всякой рекурсии и циклов, простыми insert/update? L_G>А без временных таблиц и т.п.?
Легко
insert into Trees (ParentId, TreeId)
select Id, @NewTreeId
from Trees
where TreeId = @OldTreeId
update t1
set ParentId = t3.Id
from Trees t1
join Trees t2 on t1.ParentId = t2.Id
join Trees t3 on t3.ParentId = t2.ParentId
where t1.TreeId = @NewTreeId
and t2.TreeId = @OldTreeId
and t3.TreeId = @NewTreeId
В универе же такое делают на уроках про графы\спиcки\деревья
INSERT INTO Trees(ParentId, ForestId)
SELECT Id, @NewForestId FROM Trees
WHERE ForestId = @OldForestId;
UPDATE T2
SET ParentId = T3.Id
FROM Trees AS T1
JOIN Trees AS T2
ON T1.Id = T2.ParentId
AND T2.ForestId = @NewForestId
LEFT JOIN Trees AS T3
ON T1.ParentId = T3.ParentId
AND T3.ForestId = @NewForestId;
Мир не просто сложнее, чем мы себе представляем, -- он сложнее, чем мы можем себе представить.
C>Это должно быть одно выражение или несколько? ANSI SQL или можно пользоваться современными расширениями типа Common Table Expression?
Ограничений с моей стороны не ставится. Лично мои критерии — 1) краткость и 2) понятность (читабельность).
В одно SQL-выражение не уверен, что возможно, но посмотреть было бы интересно.
Если через СТЕ собираетесь делать рекурсию — то нежелательно.
Но если это даст более красивое и понятное решение, чем на ANSI SQL — то ОК. Сравним.
W>Если ты ожидаешь именно "своего" решения, то нужно указать СУБД и версию. Возможности разные.
У меня был MS SQL 2016, но не думаю, что это принципиально.
Не знаю, как в ANSI SQL выглядит описание автоинкрементных полей, но если они там есть, то мой вариант должен быть совместим с ANSI.
Здравствуйте, L_G, Вы писали:
L_G>gandjustas, L_G>ОК, почти совпадает с моим. L_G>Только второй джойн должен быть left, а то "корни" не проджойнятся.
L_G>Оказывается, прямо "из учебника" решение?
Почти. Очень похоже на алгоритм копирования двусвязного списка, который обобщается до копирования любых многосвязных структур.
L_G>Или в универе такие задачи без ответов дают и все сами должны догадаться?
А чего сложного в этой задаче?
1) Так как у нас Id генерируется, то мы не можем в одном запросе связать новые узлы с родительскими, так как id родительских неизвестны в момент вставки
2) Очевидное решение — сохранить где-то id старых узлов и после вставки обновить parentid в новом дереве, получив id новых узлов по сохраненным старым
2) Неочевидное, но часто используемое в других алгоритмах, решение — использовать parentid новых для сохранения старых id
Здравствуйте, gandjustas, Вы писали:
G>2) Неочевидное, но часто используемое в других алгоритмах, решение — использовать parentid новых для сохранения старых id
При наличии констрейнта на ссылки только внутри "своего" дерева не прокатило бы.
G>А чего сложного в этой задаче?
Для профи-алгоритмиста ничего сложного, но для среднего студента...
хотя я не знаком с программой обучения по этому курсу, может быть, их так постепенно подводят к этому, по нарастающей сложности, что в каждой подобной задаче ничего сложного по сравнению с предыдущей нет.
Здравствуйте, L_G, Вы писали:
G>>А чего сложного в этой задаче? L_G>Для профи-алгоритмиста ничего сложного, но для среднего студента...
Как раз для студента проще, у него академические знания в голове еще не остыли, он может вспомнить что проходил пару лет назад на курсах по SQL и алгоритмам.
