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

Откуда:
Сообщений: 1214
/*можно размотать до конца */
DECLARE @TableGood TABLE (id int, ownerid int) 
INSERT INTO @TableGood SELECT 1, 0
INSERT INTO @TableGood SELECT 2, 1 
INSERT INTO @TableGood SELECT 3, 2
INSERT INTO @TableGood SELECT 4, 3

  
/*плохая таблица, зациклится при обходе*/
DECLARE @TableBad TABLE (id int, ownerid int) 
INSERT INTO @TableBad SELECT 1, 0
INSERT INTO @TableBad SELECT 2, 1 
INSERT INTO @TableBad SELECT 3, 2
INSERT INTO @TableBad SELECT 4, 1
25 май 17, 17:19    [20512289]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
TaPaK
Member

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

а чем она там плохая?
25 май 17, 17:50    [20512436]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 940
TaPaK
Cammomile,

а чем она там плохая?

тем, что вывалится с MAX RECURSION limit reached 100? :D
25 май 17, 18:36    [20512591]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 940
DECLARE @test TABLE ( [id] INT, [ownerid] INT ) 
INSERT INTO @test
VALUES
( 1, 0 ),
( 2, 1 ), 
( 3, 2 ),
( 4, 1 )
;
WITH
cte AS (
  SELECT
    [init] = t.[id],
    [lvl] = 1,
    t.[id],
    t.[ownerid],
    [is_cycle] = 0
  FROM
    @test t
  WHERE
    t.[ownerid] = 0
  UNION ALL
  SELECT
    cte.[init],
    [lvl] = cte.[lvl] + 1,
    t.[id],
    t.[ownerid],
    [is_cycle] = CASE WHEN cte.[lvl] >= 2 AND cte.[init] = cte.[ownerid] THEN 1 ELSE 0 END
  FROM
    cte
    INNER JOIN @test t ON (
          t.[ownerid] = cte.[id] )
  WHERE
    cte.[init] != t.[id] 
)
SELECT
  *
FROM
  cte
25 май 17, 18:42    [20512613]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 940
Сорян. Написанному не верить...
25 май 17, 18:44    [20512621]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 940
Как-то так...
WITH
cte AS (
  SELECT
    [init] = t.[id],
    [lvl] = 1,
    t.[id],
    t.[ownerid]
  FROM
    @test t
  WHERE
    t.[ownerid] = 0
  UNION ALL
  SELECT
    cte.[init],
    [lvl] = cte.[lvl] + 1,
    t.[id],
    t.[ownerid]
  FROM
    cte
    INNER JOIN @test t ON (
          t.[ownerid] = cte.[id] )
  WHERE
    cte.[init] != t.[id] 
)
SELECT
  t1.*,
  [is_cycle] = CASE WHEN EXISTS( SELECT * FROM cte t2 WHERE t2.[id] = t1.[ownerid] AND t2.[init] != t1.[ownerid] AND t2.[lvl] < t1.[lvl] ) THEN 1 ELSE 0 END
FROM 
  cte t1
25 май 17, 18:50    [20512643]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
msLex
Member

Откуда:
Сообщений: 8091
Руслан Дамирович
TaPaK
Cammomile,

а чем она там плохая?

тем, что вывалится с MAX RECURSION limit reached 100? :D

Где?

Там обычное дерево без циклов

0
|
->1
|
-> 2
| |
| -> 3
|
-> 4

И почему ваша "проверка" вдруг решила, что в 3-ем узел зацикливание?
Он вообще ничьим родителем не является
25 май 17, 18:51    [20512645]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Cammomile, не знаю, как вы ее обходите, но у меня она не зацикливается.

Вот плохая и код с проверкой на бесконечную рекурсию:

/*плохая таблица, зациклится при обходе*/
DECLARE @TableBad TABLE (id int, ownerid int) 
INSERT INTO @TableBad SELECT 1, 0
INSERT INTO @TableBad SELECT 2, 1 
INSERT INTO @TableBad SELECT 3, 2
INSERT INTO @TableBad SELECT 4, 3;
INSERT INTO @TableBad SELECT 2, 3;

with t as
(select tb.id , cast('\' + cast(tb.id as varchar(max)) as varchar(max)) as rec_path, cast(null as varchar(max)) as warn
	from @TableBad as tb
	where tb.ownerid = 0
	union all
	select tb.id, t.rec_path + '\' + cast(tb.id as varchar(max))
		, cast(case when patindex('%\' + cast(tb.id as varchar(max)) + '\%', t.rec_path) > 1 then 'achtung!' else null end as varchar(max))
	from @TableBad as tb inner join t on tb.ownerid = t.id)
	select * from t
25 май 17, 18:54    [20512659]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 940
Мое лицо красно...
25 май 17, 18:57    [20512662]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
TaPaK
Member

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

патентуйте!
25 май 17, 19:50    [20512761]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Мимо шел
Guest
Если это дерево. То количество переходов будет количество узлов минус 1. Т.е. если для 5ти узлов 5 строк с переходами, не повторяющимися, то цикл есть. Если меньше 4х строк то это не дерево. Связей не хватает. У каждого узла максимум и минимум один овнер. Проверяется на раз. Рекурсивно разматывать совсем не надо. Только если надо выделить подцикл.
25 май 17, 21:09    [20512900]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Мимо шел
Guest
Мимо шел
Если это дерево. То количество переходов будет количество узлов минус 1. Т.е. если для 5ти узлов 5 строк с переходами, не повторяющимися, то цикл есть. Если меньше 4х строк то это не дерево. Связей не хватает. У каждого узла максимум и минимум один овнер. Проверяется на раз. Рекурсивно разматывать совсем не надо. Только если надо выделить подцикл.

Один овнер кроме корня
25 май 17, 21:11    [20512904]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Cammomile
Member

Откуда:
Сообщений: 1214
Всем утро!

Ну может я там в примере ошибся, короче дерево само на себя зациклено где-то в центре.

Ид Папа
1 2
2 3
3 4
4 3

На 3-4 4-3 зациклится
26 май 17, 09:51    [20513560]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
TaPaK
Minamoto,

патентуйте!

Боюсь, я далеко не первый :) Сам решал такую задачу с год назад, потребовалось некоторое время, чтобы додуматься, вроде решил сам, если моя память меня не подводит, но при гуглинге достаточно легко находятся аналоги от 12-го года:

https://dba.stackexchange.com/questions/16111/cte-running-in-infinite-loop (второй ответ, а не тот, что отмечен правильным).

Да и на этом форуме вроде мелькало решение.
26 май 17, 09:52    [20513563]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Cammomile
Member

Откуда:
Сообщений: 1214
Да я и сам решал такую год назад, только не через патиндекс, а как-то через отметки и искльчение годных записей из выборки.
Вот только память отшибло, а прям сейчас сидеть думать времени нет.
26 май 17, 09:56    [20513571]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Cammomile, так же и решали, скорее всего, только можно не patindex, а тупо like использовать - разницы особой не будет.

Тут нюанс в том, что в рекурсивной части CTE таблица CTE содержит только записи предыдущего уровня, поэтому найти, были ли на более ранних уровнях такие же значения, нельзя никак, кроме как построив полное дерево ключей от самого начала.
26 май 17, 10:01    [20513593]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
PaulWist
Member

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

https://www.sql.ru/forum/1252440/constraint-na-kolcevuu-rukursiu?hl=paulwist

См. код от iap
26 май 17, 10:01    [20513594]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Cammomile
Member

Откуда:
Сообщений: 1214
Код от iap, как обычно, отличный. Чтоб русскоязычное коммунити без него делало, я даже и не знаю.
26 май 17, 10:17    [20513671]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 7759
Для типа hierarchyid зацикливание невозможно в принципе, т.к. все цепочки у него развёрнуты, достаточно наложить ограничение уникальности на столбец.
26 май 17, 11:14    [20513961]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Cammomile
Member

Откуда:
Сообщений: 1214
Владислав Колосов
Для типа hierarchyid зацикливание невозможно в принципе, т.к. все цепочки у него развёрнуты, достаточно наложить ограничение уникальности на столбец.


Владислав Колосов, спасибо за содержательный и ценный ответ. Без него, я бы не смог решить поставленные руководством задачи! Ваш вклад в общее дело форума сложно переоценить, продолжайте в том же духе!
26 май 17, 11:23    [20514003]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Владислав Колосов
Member

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

раз, что Вы всегда ходите прямо и не рассматриваете варианты. Результаты Вашей работы всегда оставят место для работы других нуждающихся в ней.
26 май 17, 11:31    [20514034]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Валдай
Member

Откуда:
Сообщений: 113
Ловля подциклов без like & pathindex

DECLARE @TableBad TABLE (id int, ownerid int) 
INSERT INTO @TableBad SELECT 1, 0
INSERT INTO @TableBad SELECT 2, 1 
INSERT INTO @TableBad SELECT 3, 2
INSERT INTO @TableBad SELECT 4, 3
INSERT INTO @TableBad SELECT 2, 3

declare 
  @root    int = (select ownerid from @TableBad r where not exists (select * from @TableBad where id = r.ownerid)) ,
  @maxrank int = (select count(*) from ( select id from @TableBad union select ownerid from @tablebad )v ) - 1

select @maxrank, @root

;with cte ( lvl, first_id, id, ownerid, fullpath ) as
(
  SELECT 
    lvl=0, first_id=id, id, ownerid, fullpath = cast( id as varchar(max))
  FROM @TableBad WHERE ownerid != @root

  UNION ALL

  SELECT 
    case when lvl>0 and c.first_id = t.id then @maxrank + 2 else lvl+1 end, 
    c.first_id, 
    t.id, 
    t.ownerid,
    fullpath = fullpath +'->' + cast(t.id as varchar(max))
  FROM cte c
  inner join @TableBad t on t.id = c.ownerid  
  WHERE lvl<=@maxrank
)
select distinct msg='loop', fullpath, lvl
from cte
where lvl = @maxrank+2
26 май 17, 14:06    [20514809]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
msLex
Member

Откуда:
Сообщений: 8091
Валдай
Ловля подциклов без like & pathindex

DECLARE @TableBad TABLE (id int, ownerid int) 
INSERT INTO @TableBad SELECT 1, 0
INSERT INTO @TableBad SELECT 2, 1 
INSERT INTO @TableBad SELECT 3, 2
INSERT INTO @TableBad SELECT 4, 3
INSERT INTO @TableBad SELECT 2, 3

declare 
  @root    int = (select ownerid from @TableBad r where not exists (select * from @TableBad where id = r.ownerid)) ,
  @maxrank int = (select count(*) from ( select id from @TableBad union select ownerid from @tablebad )v ) - 1

select @maxrank, @root

;with cte ( lvl, first_id, id, ownerid, fullpath ) as
(
  SELECT 
    lvl=0, first_id=id, id, ownerid, fullpath = cast( id as varchar(max))
  FROM @TableBad WHERE ownerid != @root

  UNION ALL

  SELECT 
    case when lvl>0 and c.first_id = t.id then @maxrank + 2 else lvl+1 end, 
    c.first_id, 
    t.id, 
    t.ownerid,
    fullpath = fullpath +'->' + cast(t.id as varchar(max))
  FROM cte c
  inner join @TableBad t on t.id = c.ownerid  
  WHERE lvl<=@maxrank
)
select distinct msg='loop', fullpath, lvl
from cte
where lvl = @maxrank+2


Вы же понимаете, что при наличии в дереве 10000 элементов и 5-и уровнях вложенности, вы узнаете о "зацикленности" после того как сделаете 2000 "витков" по ней?
26 май 17, 15:25    [20515265]     Ответить | Цитировать Сообщить модератору
 Re: Как проверить, что иерархический справочник не зациклен?  [new]
Валдай
Member

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

Вы же понимаете, что при наличии в дереве 10000 элементов и 5-и уровнях вложенности, вы узнаете о "зацикленности" после того как сделаете 2000 "витков" по ней?


О зацикленности или о том что граф не дерево я узнаю сразу. Если количество неповторяющихся строк в таблице не равно 9999.

Да, согласен, поиск самих циклов неоптимален.
26 май 17, 16:35    [20515558]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить