Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Constraint на "кольцевую" рукурсию  [new]
PaulWist
Member

Откуда:
Сообщений: 2231
Братья, помогите!

Имеется стандартное "дерево"

create table #test (ID int, Parent_ID int)

insert into #test (ID, Parent_ID) values (1, null)
insert into #test (ID, Parent_ID) values (2, 1)
insert into #test (ID, Parent_ID) values (3, 2)

-- замыкаем дерево само на себя, получается "кольцо"
update #test set Parent_ID = 3 
where Parent_ID is null

select * from #Test

drop table #test


Собственно вопрос, какое условие надо написать, что бы избежать "кольцевой" рекурсии?
7 мар 17, 13:42    [20270977]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
iap
Member

Откуда: Москва
Сообщений: 46981
PaulWist,

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

Однако, вы в "стандартом" дереве удаляете корень!
В этом-то случае и проверять ничего не надо - "не трожь корень!", и всё.
7 мар 17, 13:55    [20271030]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
TaPaK
Member

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

Из личной практики - мы держим "развёрнутое" дерево рядом с таблицей (для каждого Id все подчинённые), тогда легко работать с ветками и контролировать. Но вопрос размера всего этого, или раскручивать в триггере как пишет iap
7 мар 17, 14:01    [20271052]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
PaulWist
Member

Откуда:
Сообщений: 2231
iap
можно, например, в триггере проверять рекурсивным CTE.
Но как это будет влиять на скорость?
Я затрудняюсь сказать.


СТЕ валится с ошибкой на вложенности рекурсии.


iap

Однако, вы в "стандартом" дереве удаляете корень!
В этом-то случае и проверять ничего не надо - "не трожь корень!", и всё.


Корень - это частный случай, замкнуть "кольцо" можно на любом уровне (тут корень без изменения, а рекурсия на дочерних узлах)

create table #test (ID int, Parent_ID int)

insert into #test (ID, Parent_ID) values (1, null)
insert into #test (ID, Parent_ID) values (2, 1)
insert into #test (ID, Parent_ID) values (3, 2)

-- замыкаем дерево само на себя, получается "кольцо"
update #test set Parent_ID = 3
where ID = 2

select * from #Test

drop table #test
7 мар 17, 14:05    [20271079]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
iap
Member

Откуда: Москва
Сообщений: 46981
PaulWist
СТЕ валится с ошибкой на вложенности рекурсии
OPTION(MAXRECURSION 0) вам в руки (внимательно читаем документацию).
Или не 0, а допустимый максимальный уровень (может, вы его знаете).
7 мар 17, 14:08    [20271102]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
iap
Member

Откуда: Москва
Сообщений: 46981
iap
PaulWist
СТЕ валится с ошибкой на вложенности рекурсии
OPTION(MAXRECURSION 0) вам в руки (внимательно читаем документацию).
Или не 0, а допустимый максимальный уровень (может, вы его знаете).
Кстати, если OPTION не писать, то уровень ограничен числом 100.
Неужели у вас такая большая вложенность?
Или вы не контролируете прохождение каждого узла более одного раза?
Это просто сделать, например, в рекурсивнеой части CTE, отслеживая узлы в текстовом поле, например.
Трудно рассуждать - ведь отсюда не видно, что вы делаете и как.
7 мар 17, 14:12    [20271129]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4738
iap
iap
пропущено...
OPTION(MAXRECURSION 0) вам в руки (внимательно читаем документацию).
Или не 0, а допустимый максимальный уровень (может, вы его знаете).
Кстати, если OPTION не писать, то уровень ограничен числом 100.
Неужели у вас такая большая вложенность?
Или вы не контролируете прохождение каждого узла более одного раза?
Это просто сделать, например, в рекурсивнеой части CTE, отслеживая узлы в текстовом поле, например.
Трудно рассуждать - ведь отсюда не видно, что вы делаете и как.


Вряд ли вложенность на практике большая. Оно валится, если возник бесконечный цикл. Генерируйте в рекурсии строковую константу типа такой

'-000001-000005-000022-'

И проверяйте, что рассматриваемый на данном уровне id ещё не встречался.
7 мар 17, 14:24    [20271190]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
лолл
Member

Откуда:
Сообщений: 450
А как вообще встала задача контроля образования колец в дереве? Быть может лучше решить задачу с другого конца, дабы не нагружать сервер лишней работой?
7 мар 17, 14:38    [20271280]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 7768
От массового апдейта поможет наложение на Parent_ID ограничение внешнего ключа.
7 мар 17, 14:39    [20271284]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
Wlr-l
Member

Откуда:
Сообщений: 522
1.Изучить способы добавления, перемещения и удаления элемента из дерева.

2.Использовать для этих операций только хранимые процедуры.
7 мар 17, 15:08    [20271405]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
PaulWist
Member

Откуда:
Сообщений: 2231
iap
Неужели у вас такая большая вложенность?


Не корректно выразился, a_voronin поправил:

a_voronin
Оно валится, если возник бесконечный цикл.


2a_voronin

автор
Генерируйте в рекурсии строковую константу типа такой

'-000001-000005-000022-'

И проверяйте, что рассматриваемый на данном уровне id ещё не встречался.


ОК, спасибо за "наводку", покопаю в эту сторону.

2лолл

лолл
А как вообще встала задача контроля образования колец в дереве? Быть может лучше решить задачу с другого конца, дабы не нагружать сервер лишней работой?


А как её решить с "другого" конца? Подкиньте идею.

2Владислав Колосов
автор
От массового апдейта поможет наложение на Parent_ID ограничение внешнего ключа.


Ну, "наложи" FK на Parent_ID, что должно получиться, какая ошибка? (репо-код приведи)

2Wlr-l
Wlr-l
1.Изучить способы добавления, перемещения и удаления элемента из дерева.

2.Использовать для этих операций только хранимые процедуры.


1. ОК, ссылочку киньте, буду признателен.

2. Какая разница с помощью какого механизма получить бесконечный цикл?
7 мар 17, 15:21    [20271462]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
iap
Member

Откуда: Москва
Сообщений: 46981
PaulWist
ОК, спасибо за "наводку", покопаю в эту сторону.
Советую покопать прямо на этом форуме.
Десятки раз обсуждалось.
7 мар 17, 15:23    [20271469]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
PaulWist
Member

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

Из личной практики - мы держим "развёрнутое" дерево рядом с таблицей (для каждого Id все подчинённые), тогда легко работать с ветками и контролировать. Но вопрос размера всего этого, или раскручивать в триггере как пишет iap


Правильно ли я понял, что "развёрнутое" дерево - это аналог предложения от a_voronin

'-000001-000005-000022-'
7 мар 17, 15:24    [20271473]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
iap
Member

Откуда: Москва
Сообщений: 46981
PaulWist
TaPaK
Из личной практики - мы держим "развёрнутое" дерево рядом с таблицей (для каждого Id все подчинённые), тогда легко работать с ветками и контролировать. Но вопрос размера всего этого, или раскручивать в триггере как пишет iap


Правильно ли я понял, что "развёрнутое" дерево - это аналог предложения от a_voronin

'-000001-000005-000022-'
Я бы это назвал путём обхода дерева.
Тут, кстати, это вычисляемое поле CTE обычно называют Path. (Чтобы проще искать было)
7 мар 17, 15:26    [20271488]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
PaulWist
Member

Откуда:
Сообщений: 2231
iap
PaulWist
ОК, спасибо за "наводку", покопаю в эту сторону.
Советую покопать прямо на этом форуме.
Десятки раз обсуждалось.


Блин, уже "копал" (не первый год замужем) :), вменяемого ничего не нашел, либо неправильно "копал" :)
7 мар 17, 15:27    [20271495]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 6801
PaulWist
TaPaK
Из личной практики - мы держим "развёрнутое" дерево рядом с таблицей (для каждого Id все подчинённые), тогда легко работать с ветками и контролировать. Но вопрос размера всего этого, или раскручивать в триггере как пишет iap


Правильно ли я понял, что "развёрнутое" дерево - это аналог предложения от a_voronin

'-000001-000005-000022-'
нет у нас вторая таблица аля ParentId | ChildId где для каждого вашего ID = 1 будет 3 записи 1-1 1-2 1-3
7 мар 17, 15:29    [20271500]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
лолл
Member

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

лолл
А как вообще встала задача контроля образования колец в дереве? Быть может лучше решить задачу с другого конца, дабы не нагружать сервер лишней работой?


А как её решить с "другого" конца? Подкиньте идею.


Я не знаю природу возникновения таких ситуаций, предположу, что в GUI (drag-n-drop или как-либо); тогда как вариант - исключить такие ситуации в GUI.
7 мар 17, 16:00    [20271656]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 7768
Я имел в виде страховку "от несчастного случая"
USE [tempdb]
GO

create table test500 (ID int CONSTRAINT PK_ID PRIMARY KEY, Parent_ID int)

insert into test500 (ID, Parent_ID) values (1, null)
insert into test500 (ID, Parent_ID) values (2, 1)
insert into test500 (ID, Parent_ID) values (3, 2)

ALTER TABLE test500 ADD CONSTRAINT FK_1 FOREIGN KEY (Parent_ID) REFERENCES test500 (ID);

DELETE test500 WHERE ID = 2;
GO

UPDATE test500 SET ID = 3;
GO

DROP TABLE test500
GO


Предотвращение "петель" на лету кажется неординарной задачей. При использовании hierarchyid зацикливание, скорее всего будет автоматически игнорировано...
7 мар 17, 17:16    [20272009]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
Кесарь
Member

Откуда:
Сообщений: 453
ИМХО надо писать путь обхода и анализировать текущий и следующий узел. Если они совпадают, значит по такому пути мы уже шли и пора прекращать работу.
7 мар 17, 17:28    [20272060]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
buven
Member

Откуда:
Сообщений: 792
PaulWist
Корень - это частный случай, замкнуть "кольцо" можно на любом уровне (тут корень без изменения, а рекурсия на дочерних узлах)

create table #test (ID int, Parent_ID int)

insert into #test (ID, Parent_ID) values (1, null)
insert into #test (ID, Parent_ID) values (2, 1)
insert into #test (ID, Parent_ID) values (3, 2)

-- замыкаем дерево само на себя, получается "кольцо"
update #test set Parent_ID = 3
where ID = 2

select * from #Test

drop table #test


Вот отсюда взял. Вроде не сама рекурсия валится. Не в ту степь?
+
create table relationshipTest
(
    rowId int primary key,
    parentRowId int null
)
go

create trigger relationshipTest_insertUpdate
on relationshipTest
after insert,update
as
set nocount on
declare @errorTable table (trouble bit)

        ;WITH relationshipTestCTE(rowId, parentRowId, level,originalRowId)
        AS
        (
             SELECT rowId, parentRowId, 1 as level, rowId as originalRowId
             FROM   inserted
                     

             UNION ALL

             --gets other levels of tree.  If there is a circular reference, you will always 
             --loop back to yourself.
             SELECT relationshipTest.rowId, relationshipTest.parentRowId, 
                            level + 1 as level, originalRowId
             FROM   relationshipTest
                        JOIN relationshipTestCTE
                                on relationshipTest.parentRowId = relationshipTestCTE.rowId
             where  level <= 100 --stop at max recursion, change max 
                                            --recursion to allow deeper tree
        )
        insert into @errorTable
        select  top 1 1
        from    relationshipTestCTE as relationshipTestCTE
                  join relationshipTestCTE  as validate
                        on relationshipTestCTE.level = 1
                           --here we are looking for other rows in the hierarchy, other than the first
                           and validate.level > 1
                           --the same rows shouldn't show up in another level of the tree
                           and validate.rowId  = relationshipTestCTE.originalRowId
                               --correlates groups, in case of >1 row
                           and validate.originalRowId  = relationshipTestCTE.originalRowId 

if exists(select * from @errorTable)
 begin
    raiserror('Operation would cause illegal circular reference in relationshipTest',16,1)
    rollback transaction
    return 
 end
go



insert into relationshipTest (rowId, parentRowId) values (1, null)
insert into relationshipTest (rowId, parentRowId) values (2, 1)
insert into relationshipTest (rowId, parentRowId) values (3, 2)
go

update relationshipTest set parentRowId = 3
where rowId = 2

GO
7 мар 17, 18:23    [20272223]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
s_ustinov
Member

Откуда: Munchen, DE
Сообщений: 2199
PaulWist

Имеется стандартное "дерево"

Собственно вопрос, какое условие надо написать, что бы избежать "кольцевой" рекурсии?

Недавно решал похожую проблему. В результате "ручных" корректировок граф перемещений некоторых партий товара закольцовывался - в одном физическом перемещении между складами одна и та же физическая партия присутствовала два раза.

Как бы я решал проблему в вашем случае:
create table #test_track (Track_ID int, Step int, Used_ID int, Parent_ID int);
CREATE UNIQUE NONCLUSTERED INDEX [Unique ID] ON [#test_track]
(
Track_ID,
Used_ID
)

В качестве Track_ID используем ID, которые не являются "родителями" - конечные листья (ни разу не встречаются в #test.Parent_ID).
И в цикле заполняем таблицу для каждого Track_ID, пока Parent_ID не примет значение Null. То есть для каждого конечного элемента иерархии (Track_ID) прослеживаем всё дерево иерархии до корневого элемента, а индекс гарантирует, что в этой цепочке нет "петель".
После построения иерархий выполняем еще одну проверку - все #test.ID должны хотя бы раз присутствовать в #test_track.Used_ID
Если не присутствует - значит есть кольцо. В примере ID 2 и 3 как раз и образуют такое кольцо.
8 мар 17, 13:10    [20274261]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
s_ustinov
Member

Откуда: Munchen, DE
Сообщений: 2199
Но как сделать именно Constraint надо много думать - в таком виде это очень тяжелая процедура.
Для поиска проблемных мест она подходит, а вот постоянно отрабатывать в триггере при модификации таблицы - очень накладно.
8 мар 17, 13:13    [20274271]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
лолл
Member

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

не думаю, что ваш метод эффективнее простого обхода дерева в триггере. слишком много накладных расходов.
9 мар 17, 09:43    [20276415]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
iap
Member

Откуда: Москва
Сообщений: 46981
create table #test (ID int, ParentID int)

insert into #test (ID, ParentID) values (1, 3)
insert into #test (ID, ParentID) values (2, 1)
insert into #test (ID, ParentID) values (3, 2);


WITH CTE(ID, Parent_ID, [Path], [Loop], [Level]) AS
(
 SELECT ID, ParentID, '.'+CAST(ID AS VARCHAR(MAX))+'.', 0, 0 FROM #test WHERE ID=1 -- в триггере это может быть выборка из inserted
 UNION ALL
 SELECT T.ID,T.ParentID,CTE.[Path]+CAST(T.ID AS VARCHAR(MAX))+'.',CASE WHEN CTE.[Path] LIKE '%.'+CAST(T.ID AS VARCHAR(MAX))+'.%' THEN CTE.[Loop]+1 ELSE CTE.[Loop] END, CTE.[Level]+1
 FROM #test T
 JOIN CTE ON T.ParentID=CTE.ID
 WHERE CTE.[Loop]<1
)
SELECT * FROM CTE WHERE [Loop]>0;
9 мар 17, 11:31    [20276757]     Ответить | Цитировать Сообщить модератору
 Re: Constraint на "кольцевую" рукурсию  [new]
PaulWist
Member

Откуда:
Сообщений: 2231
2iap, БРАВО!!!

Всё гениальное просто, спасибо!
9 мар 17, 12:25    [20277027]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить