Tableaux avec hiérarchie: créez une contrainte pour éviter la circularité via les clés étrangères

Supposons que nous ayons une table qui a une contrainte de clé étrangère pour elle-même, comme celle-ci:

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

Ce tableau contiendra les enregistrements suivants:

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

Il y a des cas où ce type de conception peut avoir du sens (par exemple la relation typique "employé-patron-employé"), et en tout cas: je suis dans une situation où j'ai ceci dans mon schéma.

Ce type de conception permet malheureusement la circularité des enregistrements de données, comme le montre l'exemple ci-dessus.

Ma question est alors:

1. Est-il possible d'écrire une contrainte qui vérifie cela? et
2. Est-il possible d'écrire une contrainte qui vérifie cela? (si nécessaire seulement jusqu'à une certaine profondeur)

Pour la partie (2) de cette question, il peut être pertinent de mentionner que je n'attends que des centaines ou peut-être dans certains cas des milliers d'enregistrements dans ma table, normalement pas imbriqués plus profondément qu'environ 5 à 10 niveaux.

PS. MS SQL Server 2008

Mise à jour du 14 mars 2012
Il y a eu plusieurs bonnes réponses. J'ai maintenant accepté celui qui m'a aidé à comprendre la possibilité / faisabilité mentionnée. Il existe cependant plusieurs autres bonnes réponses, certaines avec des suggestions de mise en œuvre également, donc si vous avez atterri ici avec la même question, jetez un œil à toutes les réponses;)

Vous utilisez le modèle de liste d'adjacence , où il est difficile d'appliquer une telle contrainte.

Vous pouvez examiner le modèle d' ensemble imbriqué , où seules les vraies hiérarchies peuvent être représentées (pas de chemins circulaires). Cela a cependant d'autres inconvénients, comme les insertions / mises à jour lentes.

J'ai vu 2 façons principales d'appliquer cela:

1, la VIEILLE façon:

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

La colonne FooHierarchy contiendrait une valeur comme celle-ci:

"|1|27|425"

Où les nombres correspondent à la colonne FooId. Vous imposeriez alors que la colonne Hiérarchie se termine par "| id" et que le reste de la chaîne corresponde au FooHieratchy du PARENT.

2, la NOUVELLE façon:

SQL Server 2008 a un nouveau type de données appelé HierarchyID , qui fait tout cela pour vous.

Il fonctionne sur le même principe que l'ancienne méthode, mais il est géré efficacement par SQL Server et peut être utilisé comme REMPLACEMENT pour votre colonne "ParentID".

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

C'est un peu possible: vous pouvez invoquer une UDF scalaire à partir de votre contrainte CHECK, et cela peut détecter des cycles de n'importe quelle longueur. Malheureusement, cette approche est extrêmement lente et peu fiable: vous pouvez avoir de faux positifs et de faux négatifs.

Au lieu de cela, j'utiliserais un chemin matérialisé.

Une autre façon d'éviter les cycles est d'avoir un CHECK (ID> ParentID), ce qui n'est probablement pas très faisable non plus.

Une autre façon d'éviter les cycles consiste à ajouter deux colonnes supplémentaires, LevelInHierarchy et ParentLevelInHierarchy, avoir (ParentID, ParentLevelInHierarchy) faire référence à (ID, LevelInHierarchy) et avoir un CHECK (LevelInHierarchy> ParentLevelInHierarchy).

Je pense que c'est possible:

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)

J'ai peut-être manqué quelque chose (désolé, je ne suis pas en mesure de le tester complètement), mais cela semble fonctionner.

Voici une autre option: un déclencheur qui permet des mises à jour sur plusieurs lignes et n'applique aucun cycle. Il fonctionne en parcourant la chaîne des ancêtres jusqu'à ce qu'il trouve un élément racine (avec le parent NULL), prouvant ainsi qu'il n'y a pas de cycle. Elle est limitée à 10 générations car bien sûr un cycle est sans fin.

Cela ne fonctionne qu'avec l'ensemble actuel de lignes modifiées, donc tant que les mises à jour ne touchent pas un grand nombre d'éléments très profonds dans le tableau, les performances ne devraient pas être trop mauvaises. Il doit remonter tout le long de la chaîne pour chaque élément, ce qui aura donc un impact sur les performances.

Un déclencheur véritablement «intelligent» rechercherait directement les cycles en vérifiant si un élément a atteint lui-même, puis en se vidant. Cependant, cela nécessite de vérifier l'état de tous les nœuds précédemment trouvés lors de chaque boucle et prend donc une boucle WHILE et plus de codage que je ne le souhaitais actuellement. Cela ne devrait pas être vraiment plus cher car le fonctionnement normal serait de ne pas avoir de cycles et dans ce cas, il sera plus rapide de travailler uniquement avec la génération précédente plutôt qu'avec tous les nœuds précédents au cours de chaque boucle.

Je serais ravi de la contribution de @AlexKuznetsov ou de toute autre personne sur la façon dont cela se passerait dans l'isolement de l'instantané. Je soupçonne que ce ne serait pas très bien, mais j'aimerais mieux le comprendre.

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;

Mise à jour

J'ai compris comment éviter une jointure supplémentaire dans la table insérée. Si quelqu'un voit une meilleure façon de faire le GROUP BY pour détecter ceux qui ne contiennent pas de NULL, faites-le moi savoir.

J'ai également ajouté un commutateur à READ COMMITTED si la session en cours est au niveau SNAPSHOT ISOLATION. Cela empêchera les incohérences, mais malheureusement, entraînera un blocage accru. C'est un peu inévitable pour la tâche à accomplir.

Si vos enregistrements sont imbriqués sur plus d'un niveau, une contrainte ne fonctionnera pas (je suppose que vous voulez dire par exemple que l'enregistrement 1 est le parent de l'enregistrement 2 et l'enregistrement 3 est le parent de l'enregistrement 1). La seule façon de le faire serait dans le code parent ou avec un déclencheur, mais si vous regardez une grande table et plusieurs niveaux, cela serait assez intensif.