Таблицы с иерархией: создайте ограничение для предотвращения округлости через внешние ключи

Предположим, у нас есть таблица, которая имеет ограничение внешнего ключа, например:

CREATE TABLE Foo 
    (FooId BIGINT PRIMARY KEY,
     ParentFooId BIGINT,
     FOREIGN KEY([ParentFooId]) REFERENCES Foo ([FooId]) )

INSERT INTO Foo (FooId, ParentFooId) 
VALUES (1, NULL), (2, 1), (3, 2)

UPDATE Foo SET ParentFooId = 3 WHERE FooId = 1

Эта таблица будет иметь следующие записи:

FooId  ParentFooId
-----  -----------
1      3
2      1
3      2

Бывают случаи, когда такой дизайн может иметь смысл (например, типичные отношения «сотрудник-босс-сотрудник»), и в любом случае: я нахожусь в ситуации, когда это происходит в моей схеме.

Такая конструкция, к сожалению, допускает цикличность в записях данных, как показано в примере выше.

Мой вопрос:

1. Является ли это возможно , чтобы написать ограничение , которое проверяет это? а также
2. Является ли это возможно , чтобы написать ограничение , которое проверяет это? (если нужно только на определенную глубину)

Для части (2) этого вопроса может быть уместно упомянуть, что я ожидаю только сотни или, возможно, в некоторых случаях тысячи записей в моей таблице, обычно не вложенных глубже, чем примерно на 5-10 уровней.

PS. MS SQL Server 2008

Обновление 14 марта 2012 г.
Было несколько хороших ответов. Я теперь принял тот, который помог мне понять упомянутую возможность / осуществимость. Есть и несколько отличных ответов, некоторые с предложениями по реализации, так что, если вы попали сюда с тем же вопросом, посмотрите на все ответы;)

Вы используете модель списка смежности , в которой трудно применить такое ограничение.

Вы можете исследовать модель Nested Set , где могут быть представлены только истинные иерархии (без круговых путей). Это имеет и другие недостатки, такие как медленные вставки / обновления.

Я видел 2 основных способа обеспечить это:

1, старый способ:

CREATE TABLE Foo 
    (FooId BIGINT PRIMARY KEY,
     ParentFooId BIGINT,
     FooHierarchy VARCHAR(256),
     FOREIGN KEY([ParentFooId]) REFERENCES Foo ([FooId]) )

Столбец FooHierarchy будет содержать значение, подобное этому:

"|1|27|425"

Где числа отображаются в столбце FooId. Затем вы должны убедиться, что столбец Hierarchy оканчивается на «| id», а остальная часть строки соответствует FooHieratchy of PARENT.

2, новый способ:

SQL Server 2008 имеет новый тип данных, называемый HierarchyID , который делает все это за вас.

Он работает на том же принципе, что и OLD, но эффективно обрабатывается SQL Server и подходит для использования в качестве ЗАМЕНЫ для вашего столбца «ParentID».

CREATE TABLE Foo 
    (FooId BIGINT PRIMARY KEY,
     FooHierarchy HIERARCHYID )

Это возможно: вы можете вызывать скалярный UDF из ограничения CHECK, и он может обнаруживать циклы любой длины. К сожалению, этот подход чрезвычайно медленный и ненадежный: у вас могут быть ложные срабатывания и ложные отрицания.

Вместо этого я бы использовал материализованный путь.

Другой способ избежать циклов - использовать CHECK (ID> ParentID), что, вероятно, также не очень выполнимо.

Еще один способ избежать циклов состоит в том, чтобы добавить еще два столбца, LevelInHierarchy и ParentLevelInHierarchy, иметь (ParentID, ParentLevelInHierarchy) ссылку на (ID, LevelInHierarchy) и иметь CHECK (LevelInHierarchy> ParentLevelInHierarchy).

Я считаю, что это возможно:

create function test_foo (@id bigint) returns bit
as
begin
declare @retval bit;

with t1 as (select @id as FooId, 0 as lvl  
union all 
 select f.FooId , t1.lvl+1 from t1 
 inner join Foo f ON (f.ParentFooId = t1.FooId)
 where lvl<11) -- you said that max nested level 10, so if there is any circular   
-- dependency, we don't need to go deeper than 11 levels to detect it

 select @retval =
 CASE(COUNT(*)) 
 WHEN 0 THEN 0 -- for records that don't have children
 WHEN 1 THEN 0 -- if a record has children
  ELSE 1 -- recursion detected
 END
 from t1
 where t1.FooId = @id ;

return @retval; 
end;
GO
alter table Foo add constraint CHK_REC1 CHECK (dbo.test_foo(ParentFooId) = 0)

Возможно, я что-то пропустил (извините, я не смог проверить это полностью), но, похоже, это работает.

Вот еще один вариант: триггер, который разрешает многострочные обновления и обеспечивает отсутствие циклов. Он работает путем обхода цепочки предков, пока не найдет корневой элемент (с родительским NULL), что доказывает отсутствие цикла. Он ограничен 10 поколениями, поскольку цикл, конечно, бесконечен.

Он работает только с текущим набором измененных строк, поэтому, если обновления не затрагивают огромное количество очень глубоких элементов в таблице, производительность не должна быть слишком плохой. Он должен пройти весь путь вверх по цепочке для каждого элемента, так что это окажет некоторое влияние на производительность.

По-настоящему «интеллектуальный» триггер будет искать циклы напрямую, проверяя, достиг ли элемент сам себя, а затем освобождая его. Однако это требует проверки состояния всех ранее найденных узлов во время каждого цикла и, таким образом, требует цикла WHILE и большего количества кодирования, чем я хотел сделать прямо сейчас. Это не должно быть на самом деле дороже, потому что нормальная операция будет состоять в отсутствии циклов, и в этом случае она будет работать быстрее только с предыдущим поколением, а не со всеми предыдущими узлами во время каждого цикла.

Мне бы очень хотелось узнать мнение @AlexKuznetsov или кого-либо еще о том, как это будет происходить в условиях изоляции. Я подозреваю, что это не очень хорошо, но хотел бы понять это лучше.

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;

Обновить

Я разобрался, как избежать дополнительного объединения обратно во вставленную таблицу. Если кто-нибудь найдет лучший способ сделать GROUP BY для обнаружения тех, которые не содержат NULL, пожалуйста, дайте мне знать.

Я также добавил переключатель READ COMMITTED, если текущий сеанс находится на уровне SNAPSHOT ISOLATION. Это предотвратит несоответствия, хотя, к сожалению, приведет к усилению блокировки. Это как бы неизбежно для поставленной задачи.

Если ваши записи вложены более чем в один уровень, ограничение работать не будет (я предполагаю, что вы имеете в виду, например, что запись 1 является родительской для записи 2, а запись 3 является родительской для записи 1). Единственный способ сделать это - либо в родительском коде, либо с помощью триггера, но если вы смотрите на большую таблицу и несколько уровней, это будет довольно интенсивно.