Here is another option: a trigger that allows multi-row updates and enforces no cycles. It works by traversing the ancestor chain until it finds a root element (with parent NULL), thus proving there is no cycle. It is limited to 10 generations since of course a cycle is endless.
It only works with the current set of modified rows, so as long as updates don't touch a huge number of very deep items in the table, performance shouldn't be too bad. It does have to go all the way up the chain for each element, so it will have some performance impact.
A truly "intelligent" trigger would look for cycles directly by checking to see if an item reached itself and then bailing. However, this requires checking state of all previously-found nodes during each loop and thus takes a WHILE loop and more coding than I wanted to do right now. This shouldn't be really any more expensive because the normal operation would be to not have cycles and in this case it will be faster working with only the prior generation rather than all previous nodes during each loop.
I'd love input from @AlexKuznetsov or anyone else on how this would fare in snapshot isolation. I suspect it wouldn't very well, but would like to understand it better.
CREATE TRIGGER TR_Foo_PreventCycles_IU ON Foo FOR INSERT, UPDATE
AS
SET NOCOUNT ON;
SET XACT_ABORT ON;
IF EXISTS (
SELECT *
FROM sys.dm_exec_session
WHERE session_id = @@SPID
AND transaction_isolation_level = 5
)
BEGIN;
SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
END;
DECLARE
@CycledFooId bigint,
@Message varchar(8000);
WITH Cycles AS (
SELECT
FooId SourceFooId,
ParentFooId AncestorFooId,
1 Generation
FROM Inserted
UNION ALL
SELECT
C.SourceFooId,
F.ParentFooId,
C.Generation + 1
FROM
Cycles C
INNER JOIN dbo.Foo F
ON C.AncestorFooId = F.FooId
WHERE
C.Generation <= 10
)
SELECT TOP 1 @CycledFooId = SourceFooId
FROM Cycles C
GROUP BY SourceFooId
HAVING Count(*) = Count(AncestorFooId); -- Doesn't have a NULL AncestorFooId in any row
IF @@RowCount > 0 BEGIN
SET @Message = CASE WHEN EXISTS (SELECT * FROM Deleted) THEN 'UPDATE' ELSE 'INSERT' END + ' statement violated TRIGGER ''TR_Foo_PreventCycles_IU'' on table "dbo.Foo". A Foo cannot be its own ancestor. Example value is FooId ' + QuoteName(@CycledFooId, '"') + ' with ParentFooId ' + Quotename((SELECT ParentFooId FROM Inserted WHERE FooID = @CycledFooId), '"');
RAISERROR(@Message, 16, 1);
ROLLBACK TRAN;
END;
Update
I figured out how to avoid an extra join back to the Inserted table. If anyone sees a better way to do the GROUP BY to detect those that don't contain a NULL please let me know.
I also added a switch to READ COMMITTED if the current session is in SNAPSHOT ISOLATION level. This will prevent inconsistencies, though unfortunately will cause increased blocking. That is kind of unavoidable for the task at hand.