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)
);

The entities stored in X are hierarchically organized: If a row (A1,B1,C1) exists and C1 IS NOT NULL then it is considered to be a "child" of (A1,C1,C2) whatever C2 is. Since an item cannot descend from itself, I would like to make it illegal that circular hierarchical sequences exist:

-- 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 do I do this?

---

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 that LEVEL be 0 when C IS NULL, and parent's LEVEL + 1 otherwise.

---

I am using SQL Server 2008 R2.

Answer 1

To check for circular references i have used a trigger and 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  x.A, x.B, X.C, 1 AS [Type]
        FROM    inserted i
        JOIN    X x ON i.A = x.A AND i.C = x.B
        UNION ALL
        SELECT  x.A, x.B, X.C, 2 AS [Type]
        FROM    CteHierarchy i
        JOIN    X x ON i.A = x.A AND i.C = x.B
        WHERE   NOT EXISTS 
        (
                SELECT  *
                FROM    inserted a
                WHERE   a.A = x.A AND a.B = x.B
        )   
    )
    INSERT  @Results ([Exists])
    SELECT  TOP(1) 1
    FROM    CteHierarchy h
    JOIN    X x ON h.A = x.A AND h.C = x.B
    OPTION(MAXRECURSION 1000);

    IF EXISTS(SELECT * FROM @Results)
    BEGIN
        ROLLBACK;
        RAISERROR('Circular references detected', 16, 1);
    END
END
GO

Now, we can run 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.

For the second test, you can see how this trigger has canceled (ROLLBACK TRANSACTION) the transaction and, after UPDATE, nothing has been executed (in current batch).