Как предотвратить вставку циклической ссылки в SQL
У меня есть следующая таблица:
create table dbo.Link
(
FromNodeId int not null,
ToNodeId int not null
)
Строки в этой таблице представляют ссылки между узлами.
Я хочу, чтобы вставки или обновления этой таблицы не создавали циклические отношения между узлами.
Так что, если таблица содержит:
(1,2)
(2,3)
не должно быть разрешено содержать любое из следующего:
(1,1)
(2,1)
(3,1)
Я с удовольствием рассмотрю (1,1) отдельно (например, с помощью CHECK CONSTRAINT), если это делает решение более простым.
Я думал о создании триггера AFTER INSERT с рекурсивным CTE (хотя может быть более простой способ сделать это).
Предполагая, что это путь, каким будет определение триггера? Если есть более элегантный способ, что это?
2 ответа
Во-первых, обратите внимание, что предпочтительно обнаруживать циклы в другой среде, поскольку рекурсивные CTE не известны своей хорошей производительностью, и при этом ни один из триггеров не будет работать для каждого оператора вставки. Для больших графиков решение, основанное на приведенном ниже решении, вероятно, будет неэффективным.
Предположим, вы создали таблицу следующим образом:
CREATE TABLE dbo.lnk (
node_from INT NOT NULL,
node_to INT NOT NULL,
CONSTRAINT CHK_self_link CHECK (node_from<>node_to),
CONSTRAINT PK_lnk_node_from_node_to PRIMARY KEY(node_from,node_to)
);
Это будет блокировать вставки с node_from равно node_toи для строк, которые уже существуют.
Следующий триггер должен обнаруживать циклические ссылки, генерируя исключение, если циклическая ссылка обнаружена:
CREATE TRIGGER TRG_no_circulars_on_lnk ON dbo.lnk AFTER INSERT
AS
BEGIN
DECLARE @cd INT;
WITH det_path AS (
SELECT
anchor=i.node_from,
node_to=l.node_to,
is_cycle=CASE WHEN i.node_from/*anchor*/=l.node_to THEN 1 ELSE 0 END
FROM
inserted AS i
INNER JOIN dbo.lnk AS l ON
l.node_from=i.node_to
UNION ALL
SELECT
dp.anchor,
node_to=l.node_to,
is_cycle=CASE WHEN dp.anchor=l.node_to THEN 1 ELSE 0 END
FROM
det_path AS dp
INNER JOIN dbo.lnk AS l ON
l.node_from=dp.node_to
WHERE
dp.is_cycle=0
)
SELECT TOP 1
@cd=is_cycle
FROM
det_path
WHERE
is_cycle=1
OPTION
(MAXRECURSION 0);
IF @cd IS NOT NULL
THROW 67890, 'Insert would cause cyclic reference', 1;
END
Я проверил это для ограниченного числа вставок.
INSERT INTO dbo.lnk(node_from,node_to)VALUES(1,2); -- OK
INSERT INTO dbo.lnk(node_from,node_to)VALUES(2,3); -- OK
INSERT INTO dbo.lnk(node_from,node_to)VALUES(3,4); -- OK
А также
INSERT INTO dbo.lnk(node_from,node_to)VALUES(2,3); -- PK violation
INSERT INTO dbo.lnk(node_from,node_to)VALUES(1,1); -- Check constraint violation
INSERT INTO dbo.lnk(node_from,node_to)VALUES(3,2); -- Exception: Insert would cause cyclic reference
INSERT INTO dbo.lnk(node_from,node_to)VALUES(3,1); -- Exception: Insert would cause cyclic reference
INSERT INTO dbo.lnk(node_from,node_to)VALUES(4,1); -- Exception: Insert would cause cyclic reference
Он также обнаруживает циклические ссылки, уже присутствующие во вставленных строках, если вставлять более одной строки одновременно или если в графике будет введен путь, длина которого превышает одно ребро. Обойдемся на тех же начальных вставках:
INSERT INTO dbo.lnk(node_from,node_to)VALUES(8,9),(9,8); -- Exception: Insert would cause cyclic reference
INSERT INTO dbo.lnk(node_from,node_to)VALUES(4,5),(5,6),(6,1); -- Exception: Insert would cause cyclic reference
РЕДАКТИРОВАТЬ: обрабатывать вставки из нескольких записей, перемещать логику в отдельной функции
Я рассмотрел процедурный подход, он очень быстрый и практически не зависит от количества записей в таблице ссылок и графе "плотность"
Я проверил это на таблице с 10'000 ссылок со значениями узлов от 1 до 1000.
Это действительно очень быстро и не страдает от размера таблицы ссылок или "плотности"
Кроме того, эту функцию можно использовать для проверки значений перед вставкой или (например), если вы вообще не хотите использовать триггер для проверки логики перемещения клиента.
Рассмотрение рекурсивного CTE: будьте осторожны!
Я проверил принятый ответ в своей тестовой таблице (10 тыс. Строк), но через 25 минут я отменил операцию вставки одной строки, потому что запрос завис без результата... Уменьшение таблицы до 5 тыс. Строк при вставке Отдельная запись может длиться до 2-3 минут. Это очень зависит от "населения" графа. Если вы вставляете новый путь или добавляете узел к пути с низкой степенью ветвления, это довольно быстро, но вы не можете это контролировать. Когда график станет более "плотным", это решение взорвется вам в лицо.
Рассмотрим ваши потребности очень тщательно.
Итак, давайте посмотрим, как...
Прежде всего я установил PK таблицы в оба столбца и добавил индекс для второго столбца для полного охвата. (CHECK на FromNodeId<>ToNodeId не нужен, потому что алгоритм уже охватывает этот случай).
CREATE TABLE [dbo].[Link](
[FromNodeId] [int] NOT NULL,
[ToNodeId] [int] NOT NULL,
CONSTRAINT [PK_Link] PRIMARY KEY CLUSTERED ([FromNodeId],[ToNodeId])
)
GO
CREATE NONCLUSTERED INDEX [ToNodeId] ON [dbo].[Link] ([ToNodeId])
GO
Затем я построил функцию для проверки правильности одной ссылки:
drop function fn_test_link
go
create function fn_test_link(@f int, @t int)
returns int
as
begin
--SET NOCOUNT ON
declare @p table (id int identity primary key, l int, t int, unique (l,t,id))
declare @r int = 0
declare @i int = 0
-- link is not self-referencing
if @f<>@t begin
-- there are links that starts from where new link wants to end (possible cycle)
if exists(select 1 from link where fromnodeid=@t) begin
-- PAY ATTENTION.. HERE LINK TABLE ALREADY HAVE ALL RECORDS ADDED (ALSO NEW ONES IF PROCEDURE IS CALLED FROM A TRIGGER AFTER INSERT)
-- LOAD ALL THE PATHS TOUCHED BY DESTINATION OF TEST NODE
set @i = 0
insert into @p
select distinct @i, ToNodeId
from link
where fromnodeid=@t
set @i = 1
-- THERE IS AT LEAST A STEP TO FOLLOW DOWN THE PATHS
while exists(select 1 from @p where l=@i-1) begin
-- LOAD THE NEXT STEP FOR ALL THE PATHS TOUCHED
insert into @p
select distinct @i, l.ToNodeId
from link l
join @p p on p.l = @i-1 and p.t = l.fromnodeid
-- CHECK IF THIS STEP HAVE REACHED THE TEST NODE START
if exists(select 1 from @p where l=@i and t=@f) begin
-- WE ARE EATING OUR OWN TAIL! CIRCULAR REFERENCE FOUND
set @r = -1
break
end
-- THE NODE IS STILL GOOD
-- DELETE FROM LIST DUPLICATED ALREADY TESTED PATHS
-- (THIS IS A BIG OPTIMIZATION, WHEN PATHS CROSSES EACH OTHER YOU RISK TO TEST MANY TIMES SAME PATHS)
delete p
from @p p
where l = @i
and (exists(select 1 from @p px where px.l < p.l and px.t = p.t))
set @i = @i + 1
end
if @r<0
-- a circular reference was found
set @r = 0
else
-- no circular reference was found
set @r = 1
end else begin
-- THERE ARE NO LINKS THAT STARTS FROM TESTED NODE DESTINATIO (CIRCULAR REFERENCE NOT POSSIBLE)
set @r = 1
end
end; -- link is not self-referencing
--select * from @p
return @r
end
GO
Теперь давайте назовем это из триггера.
Если будет вставлено более одной строки, триггер проверит каждую ссылку на всю вставку (старая таблица + новые записи), если все они действительны и окончательная таблица будет согласованной, вставка будет завершена, если одна из них недействительна, Вставка будет прервана.
DROP TRIGGER tr_test_circular_reference
GO
CREATE TRIGGER tr_test_circular_reference ON link AFTER INSERT
AS
BEGIN
SET NOCOUNT ON
declare @p table (id int identity primary key, l int, f int, t int)
declare @f int = 0
declare @t int = 0
declare @n int = 0
declare @i int = 1
declare @ins table (id int identity primary key, f int, t int)
insert into @ins select * from inserted
set @n = @@ROWCOUNT;
-- there are links to insert
while @i<=@n begin
-- load link
select @f=f, @t=t from @ins where id = @i
if dbo.fn_test_link(@f, @t)=0 begin
declare @m nvarchar(255)
set @m = formatmessage('Insertion of link (%d,%d) would cause circular reference (n.%d)', @f, @t, @i);
THROW 50000, @m, 1
end
set @i = @i + 1
end
END
GO
Я надеюсь, это поможет