Detecting circular references in SQL

Question

I have the following table:

CREATE TABLE X ( A SOMETYPE NOT NULL, B SOMETYPE NOT NULL, C SOMETYPE NULL, PRIMARY KEY (A,B), FOREIGN KEY (A,C) REFERENCES X (A,B) ); 

Objects stored in X are hierarchically organized: if there is a string (A1,B1,C1) and C1 IS NOT NULL , then it is considered a “child” of (A1,C1,C2) any C2 . Since the element cannot descend from itself, I would like to make it illegal if there are cyclic hierarchical sequences:

 -- legal INSERT INTO X (A1,B1,NULL); INSERT INTO X (A1,B2,B1); INSERT INTO X (A1,B3,B2); INSERT INTO X (A1,B4,B2); -- currently legal, but I want to make it illegal UPDATE X SET C = B1 WHERE B = B1; /* B1-B1 */ UPDATE X SET C = B2 WHERE B = B1; /* B1-B2-B1 */ UPDATE X SET C = B3 WHERE B = B1; /* B1-B2-B3-B1 */ UPDATE X SET C = B4 WHERE B = B1; /* B1-B2-B4-B1 */ UPDATE X SET C = B2 WHERE B = B2; /* B2-B2 */ UPDATE X SET C = B3 WHERE B = B2; /* B2-B3-B2 */ UPDATE X SET C = B4 WHERE B = B2; /* B2-B4-B2 */ UPDATE X SET C = B3 WHERE B = B3; /* B3-B3 */ UPDATE X SET C = B4 WHERE B = B4; /* B4-B4 */ 

How to do it?

---

Alternatively, I could add a field representing the "level" in the hierarchy to the table:

 CREATE TABLE X ( A SOMETYPE NOT NULL, B SOMETYPE NOT NULL, C SOMETYPE NULL, LEVEL INT NOT NULL, PRIMARY KEY (A,B), FOREIGN KEY (A,C) REFERENCES X (A,B) ); 

Then I would like to require LEVEL be 0 when C IS NULL and parent LEVEL + 1 otherwise.

---

I am using SQL Server 2008 R2.

Answer 1

To check circular references, I used a trigger and a recursive CTE:

 CREATE TRIGGER trgIU_X_CheckCircularReferences ON dbo.X AFTER INSERT, UPDATE AS BEGIN SET NOCOUNT ON; DECLARE @Results TABLE ([Exists] BIT); WITH CteHierarchy AS ( SELECT xA, xB, XC, 1 AS [Type] FROM inserted i JOIN X x ON iA = xA AND iC = xB UNION ALL SELECT xA, xB, XC, 2 AS [Type] FROM CteHierarchy i JOIN X x ON iA = xA AND iC = xB WHERE NOT EXISTS ( SELECT * FROM inserted a WHERE aA = xA AND aB = xB ) ) INSERT @Results ([Exists]) SELECT TOP(1) 1 FROM CteHierarchy h JOIN X x ON hA = xA AND hC = xB OPTION(MAXRECURSION 1000); IF EXISTS(SELECT * FROM @Results) BEGIN ROLLBACK; RAISERROR('Circular references detected', 16, 1); END END GO 

Now we can perform some tests:

 --Test 1 - OK PRINT '*****Test 1 - OK*****'; SELECT * FROM X; BEGIN TRANSACTION; UPDATE X SET C = 'B1' WHERE B = 'B4'; SELECT * FROM X; --This transaction can be commited without problems --but I will cancel all modification so we can run the second test ROLLBACK TRANSACTION; PRINT '*****End of test 1*****'; GO --Test 2 - NOT OK PRINT '*****Test 2 - NOT OK*****'; SELECT * FROM X; BEGIN TRANSACTION; UPDATE X SET C = 'B1' WHERE B = 'B1'; --Useless in this case (test 2 & test 3) --Read section [If a ROLLBACK TRANSACTION is issued in a trigger] from http://msdn.microsoft.com/en-us/library/ms181299.aspx SELECT * FROM X; --Useless ROLLBACK TRANSACTION; --Useless PRINT '*****End of test 2*****'; GO PRINT '*****Test 3 - NOT OK*****'; SELECT * FROM X; BEGIN TRANSACTION; UPDATE X SET C = 'B4' WHERE B = 'B1'; GO 

Results:

 *****Test 1 - OK***** (4 row(s) affected) (0 row(s) affected) (1 row(s) affected) (4 row(s) affected) *****End of test 1***** *****Test 2 - NOT OK***** (4 row(s) affected) (1 row(s) affected) Msg 50000, Level 16, State 1, Procedure trgIU_X_CheckCircularReferences, Line 34 Circular references detected Msg 3609, Level 16, State 1, Line 8 The transaction ended in the trigger. The batch has been aborted. *****Test 3 - NOT OK***** (4 row(s) affected) (1 row(s) affected) Msg 50000, Level 16, State 1, Procedure trgIU_X_CheckCircularReferences, Line 34 Circular references detected Msg 3609, Level 16, State 1, Line 7 The transaction ended in the trigger. The batch has been aborted. 

In the second test, you can see how this trigger canceled a transaction ( ROLLBACK TRANSACTION ), and after UPDATE nothing was done (in the current batch).