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

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

знаю, что можно сделать процедурой в виде цикла, но не хотелось заморачиваться и перебивать алгоритм на новые рельсы
к тому же дебаг процедур в SSMS осложнен тем, что в новых версиях убрали отладчик
хотелось бы по возможности допилить это простое решение


IF OBJECT_ID('dbo.TAB1') IS NOT NULL
	DROP TABLE dbo.TAB1

CREATE TABLE TAB1 (
	COLUMN11 NVARCHAR(10) NOT NULL,
	COLUMN12 NVARCHAR(10) NOT NULL,
	COLUMN21 NVARCHAR(10) NOT NULL,
	COLUMN22 NVARCHAR(10) NOT NULL,
	PRIMARY KEY CLUSTERED (COLUMN11, COLUMN12, COLUMN21, COLUMN22)
)

INSERT INTO TAB1
VALUES 
('111', '01', '111', '02'),
('111', '02', '111', '03'),
('111', '03', '222', '01'),
('222', '01', '222', '02'),
('222', '02', '111', '02'),
('333', '01', '333', '02'),
('333', '02', '333', '03'),
('333', '03', '333', '01')

go

;WITH CYCLE AS (
	SELECT DISTINCT 
		COLUMN11 AS beg1,
		COLUMN12 AS beg2,
		CONVERT(NVARCHAR(MAX), '\' + COLUMN11 + '_' + COLUMN12 + '\') AS pth, 
		0 AS repeats
	FROM TAB1

	UNION ALL
		
	SELECT
		nx.COLUMN11 AS beg1, 
		nx.COLUMN12 AS beg2, 
		cur.pth + nx.COLUMN11 + '_' + nx.COLUMN12 + '\' AS pth,
		(
			CASE
				WHEN CHARINDEX('\' + nx.COLUMN11 + '_' + nx.COLUMN12 + '\', cur.pth) > 0
					THEN cur.repeats + 1
				ELSE cur.repeats
			END
		) AS repeats
	FROM cycle AS cur 
	JOIN TAB1 AS nx
		ON cur.beg1 = nx.COLUMN21
		AND cur.beg2 =  nx.COLUMN22
	WHERE cur.repeats < 1
)
SELECT pth AS CyclePaths
FROM cycle
WHERE repeats = 1
ORDER BY LEN(PTH)
OPTION (MAXRECURSION 0)


Сообщение было отредактировано: 14 сен 21, 13:29
14 сен 21, 13:31    [22371717]     Ответить | Цитировать Сообщить модератору
 Re: Поиск цикла по иерархической структуре  [new]
uaggster
Member

Откуда:
Сообщений: 1105
Вот тут - исчерпывающе:

https://stackoverflow.com/questions/40574229/is-there-a-way-to-detect-a-cycle-in-hierarchical-queries-in-sql-server
14 сен 21, 15:33    [22371764]     Ответить | Цитировать Сообщить модератору
 Re: Поиск цикла по иерархической структуре  [new]
aleks222
Member

Откуда:
Сообщений: 1685
uaggster
Вот тут - исчерпывающе:

https://stackoverflow.com/questions/40574229/is-there-a-way-to-detect-a-cycle-in-hierarchical-queries-in-sql-server

Там забыли объяснить как исключить повторные циклы.
Тредстартер хочет не только "факт наличия цикла", но "сам цикл в единственном экземпляре".
ВашЪ КО.
14 сен 21, 15:38    [22371766]     Ответить | Цитировать Сообщить модератору
 Re: Поиск цикла по иерархической структуре  [new]
aleks222
Member

Откуда:
Сообщений: 1685
Вселенский тормоз.
IF OBJECT_ID('dbo.TAB1') IS NOT NULL
	DROP TABLE dbo.TAB1

CREATE TABLE TAB1 (
	COLUMN11 NVARCHAR(10) NOT NULL,
	COLUMN12 NVARCHAR(10) NOT NULL,
	COLUMN21 NVARCHAR(10) NOT NULL,
	COLUMN22 NVARCHAR(10) NOT NULL,
    id int identity unique,
	PRIMARY KEY CLUSTERED (COLUMN11, COLUMN12, COLUMN21, COLUMN22)
)

INSERT INTO TAB1
VALUES 
('111', '01', '111', '02'),
('111', '02', '111', '03'),
('111', '03', '222', '01'),
('222', '01', '222', '02'),
('222', '02', '111', '02'),
('333', '01', '333', '02'),
('333', '02', '333', '03'),
('333', '03', '333', '01')

go

;WITH c AS ( SELECT id, 0 AS cnt, Cycle = cast(0 as bit), COLUMN11 AS beg1, COLUMN12 AS beg2 FROM TAB1
             UNION ALL
            SELECT c.id, c.cnt + 1 as cnt, Cycle = cast(iif(c.id = n.id, 1, 0) as bit), n.COLUMN11 AS beg1, n.COLUMN12 AS beg2
                FROM c 
                JOIN TAB1 AS n on c.beg1 = n.COLUMN21 AND c.beg2 = n.COLUMN22
                WHERE c.Cycle = 0
    )
    , ac as ( SELECT * FROM c where exists( select * from c as x where x.id = c.id and x.Cycle = 1 ) )
  select * from ac
    where not exists( select * from ac as x where x.id < ac.id 
                                    and not exists(select beg1, beg2 from ac as y where id = x.id except select beg1, beg2 from ac as y where id = ac.id) 
                                    and not exists(select beg1, beg2 from ac as y where id = ac.id except select beg1, beg2 from ac as y where id = x.id)
                      )
    ORDER BY id, cnt


Сообщение было отредактировано: 14 сен 21, 18:01
14 сен 21, 18:09    [22371855]     Ответить | Цитировать Сообщить модератору
 Re: Поиск цикла по иерархической структуре  [new]
a_voronin
Member

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

Вот здесь есть пример защиты от зацикливания в рекурсии.

https://www.sql.ru/forum/1322566/rekursiya-s-dublyami
14 сен 21, 18:26    [22371868]     Ответить | Цитировать Сообщить модератору
 Re: Поиск цикла по иерархической структуре  [new]
newbie876454
Member

Откуда:
Сообщений: 57
спасибо.
интересный метод с битмапом, не знал о таком

Сообщение было отредактировано: 14 сен 21, 21:42
14 сен 21, 21:52    [22371921]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить