Tabelas com hierarquia: crie uma restrição para impedir a circularidade através de chaves estrangeiras

Suponha que tenhamos uma tabela que tenha uma restrição de chave estrangeira, assim:

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

Esta tabela terá os seguintes registros:

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

Há casos em que esse tipo de design pode fazer sentido (por exemplo, o relacionamento típico de "funcionário e chefe-funcionário") e, em qualquer caso: estou em uma situação em que tenho isso no meu esquema.

Infelizmente, esse tipo de design permite circularidade nos registros de dados, como mostra o exemplo acima.

Minha pergunta então é:

1. É possível escrever uma restrição que verifique isso? e
2. É possível escrever uma restrição que verifique isso? (se necessário apenas até uma certa profundidade)

Para a parte (2) desta pergunta, pode ser relevante mencionar que espero apenas centenas ou talvez, em alguns casos, milhares de registros em minha tabela, normalmente não aninhados mais do que cerca de 5 a 10 níveis.

PS. MS SQL Server 2008

Atualização 14 de março de 2012
Houve várias boas respostas. Aceitei agora o que me ajudou a entender a possibilidade / viabilidade mencionada. Existem várias outras ótimas respostas, algumas com sugestões de implementação também; portanto, se você chegou aqui com a mesma pergunta, consulte todas as respostas;)

Você está usando o modelo de lista de adjacências , onde é difícil impor essa restrição.

Você pode examinar o modelo Conjunto Aninhado , onde apenas hierarquias verdadeiras podem ser representadas (sem caminhos circulares). Isso tem outras desvantagens, como inserções / atualizações lentas.

Eu vi duas maneiras principais de impor isso:

1, a maneira antiga:

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

A coluna FooHierarchy conteria um valor como este:

"|1|27|425"

Onde os números são mapeados para a coluna FooId. Você aplicaria que a coluna Hierarquia termina com "| id" e o restante da string corresponde ao FooHieratchy do PAI.

2, a nova maneira:

O SQL Server 2008 tem um novo tipo de dados chamado HierarchyID , que faz tudo isso para você.

Ele opera da mesma maneira que a OLD, mas é tratado com eficiência pelo SQL Server e é adequado para uso como SUBSTITUIÇÃO da coluna "ParentID".

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

É meio que possível: você pode chamar uma UDF escalar a partir da verificação de restrição e meio que pode detectar ciclos de qualquer tamanho. Infelizmente, essa abordagem é extremamente lenta e não confiável: você pode ter falsos positivos e falsos negativos.

Em vez disso, eu usaria o caminho materializado.

Outra maneira de evitar ciclos é ter um CHECK (ID> ParentID), o que provavelmente também não é muito viável.

Outra maneira de evitar ciclos é adicionar mais duas colunas, LevelInHierarchy e ParentLevelInHierarchy, (ParentID, ParentLevelInHierarchy) se referem a (ID, LevelInHierarchy) e têm um CHECK (LevelInHierarchy> ParentLevelInHierarchy).

Eu acredito que é possível:

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)

Eu posso ter perdido alguma coisa (desculpe, não consigo testá-la completamente), mas parece funcionar.

Aqui está outra opção: um gatilho que permite atualizações de várias linhas e não impõe ciclos. Ele funciona percorrendo a cadeia ancestral até encontrar um elemento raiz (com o pai NULL), provando assim que não há ciclo. É limitado a 10 gerações, pois é claro que um ciclo é interminável.

Ele funciona apenas com o conjunto atual de linhas modificadas, desde que as atualizações não atinjam um grande número de itens muito profundos na tabela, o desempenho não deve ser muito ruim. Ele precisa percorrer todo o caminho da cadeia para cada elemento, para ter algum impacto no desempenho.

Um gatilho verdadeiramente "inteligente" procuraria ciclos diretamente, verificando se um item chegava a si próprio e, em seguida, bloqueando. No entanto, isso requer a verificação do estado de todos os nós encontrados anteriormente durante cada loop e, portanto, requer um loop WHILE e mais codificação do que eu queria fazer agora. Isso não deve ser realmente mais caro, porque a operação normal seria não ter ciclos e, nesse caso, será mais rápido trabalhando apenas com a geração anterior, em vez de todos os nós anteriores durante cada loop.

Gostaria muito da contribuição de @AlexKuznetsov ou de qualquer outra pessoa sobre como isso se sairia no isolamento de instantâneos. Eu suspeito que não iria muito bem, mas gostaria de entender melhor.

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;

Atualizar

Eu descobri como evitar uma junção extra de volta à tabela Inserida. Se alguém vir uma maneira melhor de fazer o GROUP BY para detectar aqueles que não contêm um NULL, entre em contato.

Eu também adicionei uma opção para READ COMMITTED se a sessão atual estiver no nível SNAPSHOT ISOLATION. Isso evitará inconsistências, mas, infelizmente, causará maior bloqueio. Isso é inevitável para a tarefa em questão.

Se seus registros estiverem aninhados em mais de um nível, uma restrição não funcionará (suponho que você queira dizer, por exemplo, o registro 1 é o pai do registro 2 e o registro 3 é o pai do registro 1). A única maneira de fazer isso seria no código pai ou com um gatilho, mas se você estiver vendo uma tabela grande e vários níveis, isso seria bastante intenso.