How to prevent a self-referencing table from becoming circular

Question

This is a pretty common problem but I haven't yet found the exact question and answer I'm looking for.

I have one table that has a FK pointing to its own PK, to enable an arbitrarily deep hierarchy, like the classic tblEmployee that has a column Manager that is a FK with the PK tblEmployee.EmployeeID.

Let's say in my app, the user

1. Creates new employees Alice and Dave, with no manager because they're the CEO and President. So tblEmployee.Manager is NULL for those two records.
2. Create new employee Bob, with Alice as manager. Then create Charles with Bob as his manager. Their Manager fields contain the Primary Key value of another record in tblEmployee.
3. Edit employee record for Alice, meaning to assign Dave has her manager (which would be fine) but accidentally set Alice's manager to be Charles, who is two levels down from Alice in the tree.

Now the table is in a circular reference instead of a proper tree.

What is the best way to make sure that Step 3 cannot be done in an application? I just need to make sure that it will refuse to do that last SQL update, and instead show some error message.

I'm not picky about whether it's a database constraint in SQL Server (has to work in 2008 or 2012) or with some kind of validation routine in the business logic layer of my C# app.

Answer 1

You can do this with a CHECK CONSTRAINT that validates manager id is not a cycle. You can't have complex queries in a check constraint, but if you wrap it in a function first you can:

create function CheckManagerCycle( @managerID int )
returns int
as
begin

    declare @cycleExists bit
    set @cycleExists = 0

    ;with cte as (
        select E.* from tblEmployee E where ID = @managerID
        union all
        select E.* from tblEmployee E join cte on cte.ManagerID = E.ID and E.ID <> @managerID
    )
    select @cycleExists = count(*) from cte E where E.ManagerID = @managerID

    return @cycleExists;

end

Then you can use a constraint like this:

alter table tblEmployee
ADD CONSTRAINT chkManagerRecursive CHECK ( dbo.CheckManagerCycle(ManagerID) = 0 )

This will prevent adding or updating records to create a cycle from any source.

---

Edit: An important note: check constraints are validated on the columns they reference. I originally coded this to check cycles on the Employee ID, rather than the Manager ID. However, that did not work because it only triggered on changes to the ID column. This version does work because it is triggered any time the ManagerID changes.

Answer 2

You can add 'level' integer column.

Alice and Dave will have level == 0 If You will set manager for employee his (employee) level will be level+1 of his manager.

During update You should check if manager level is smaller than level of employee...

This will be faster than using procedure...

Answer 3

You can include a check in your UPDATE statement:

DECLARE @Employee INT = 2
       ,@NewManager INT = 4
;WITH cte AS (SELECT *
              FROM tblEmployee
              WHERE Manager = @Employee
              UNION  ALL
              SELECT a.*
              FROM tblEmployee a
              JOIN cte b
                ON a.manager = b.EmployeeID)
UPDATE a
SET a.Manager = @NewManager
FROM tblEmployee a
WHERE EmployeeID = @Employee
    AND NOT EXISTS (SELECT *
                    FROM cte b
                    WHERE a.EmployeeID = b.Manager)

Demo: SQL Fiddle