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

10

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

Jeroen
fonte

Respostas:

6

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.

ypercubeᵀᴹ
fonte
+1 ótimos links, e danado, gostaria de experimentar o modelo de conjunto aninhado e aceitar a resposta como a que funcionou para mim.
Jeroen
Estou aceitando essa resposta, porque foi a única que me ajudou a entender a possibilidade e a viabilidade , ou seja, respondeu à pergunta para mim. No entanto, qualquer pessoa que chegue a essa pergunta deve examinar a resposta de @ a1ex07 para uma restrição que funciona em casos simples e a resposta de @ JohnGietzen para os ótimos links aos HIERARCHYIDquais parece ser uma implementação nativa do modelo de conjunto aninhado MSSQL2008.
Jeroen
7

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 )
John Gietzen
fonte
11
Você tem uma demonstração de origem ou breve demonstrativa que HIERARCHYIDimpede a criação de loops de hierarquia?
21412 Nick Chammas #
6

É 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).

AK
fonte
UDFs nas restrições CHECK não funcionam. Você não pode obter uma imagem consistente em nível de tabela do estado proposto após a atualização a partir de uma função que é executada em uma linha por vez. Você deve usar um gatilho AFTER e retroceder ou um gatilho INSTEAD OF e recusar a atualização.
ErikE
Mas agora vejo os comentários na outra resposta sobre atualizações de várias linhas.
ErikE
@ ErikE é isso mesmo, UDFs nas restrições CHECK não funcionam.
AK
@Alex Concordou. Demorei algumas horas para provar isso uma vez.
ErikE
4

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.

a1ex07
fonte
11
Concordo que "parece funcionar", mas pode falhar em atualizações de várias linhas, falhar sob isolamento de instantâneo e é muito lento.
AK
@AlexKuznetsov: Percebo que as consultas recursivas são relativamente lentas e concordo que as atualizações de várias linhas podem ser um problema (elas podem ser desativadas).
precisa saber é
@ a1ex07 Thx para esta sugestão. Eu tentei e, em casos simples, parece funcionar bem. Ainda não tenho certeza se a falha nas atualizações de várias linhas é um problema (embora provavelmente seja). Não sei se o que você quer dizer com "eles podem ser desativados"?
Jeroen
No meu entendimento, a tarefa implica lógica baseada em cursor (ou linha). Portanto, faz sentido desabilitar as atualizações que modificam mais de 1 linha (simples em vez do gatilho de atualização que gera um erro se a tabela inserida tiver mais de 1 linha).
A1ex07 6/03/12
Se você não conseguir reprojetar a tabela, eu criaria um procedimento que verifica todas as restrições e adiciona / atualiza o registro. Depois, assegurarei que ninguém, exceto este sp, possa inserir / atualizar esta tabela.
a1ex07
3

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.

ErikE
fonte
Você deve usar a dica WITH (READCOMMITTEDLOCK). Hugo Kornelis escreveu um exemplo: sqlblog.com/blogs/hugo_kornelis/archive/2006/09/15/…
AK
Obrigado @Alex, esses artigos eram dinamite e me ajudaram a entender muito melhor o isolamento de instantâneos. Eu adicionei uma opção condicional para ler não confirmada no meu código.
ErikE
2

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.

whiterainbow
fonte