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

10

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

Jeroen
la source

Réponses:

6

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.

ypercubeᵀᴹ
la source
+1 d'excellents liens, et sacrément j'aimerais pouvoir essayer le modèle de jeu imbriqué, puis accepter cette réponse comme celle qui a fonctionné pour moi.
Jeroen
J'accepte cette réponse, car c'est celle qui m'a aidé à comprendre la possibilité et la faisabilité , c'est-à-dire qu'elle a répondu à la question pour moi. Cependant, quiconque atterrit à cette question devrait jeter un œil à la réponse de @ a1ex07 pour une contrainte qui fonctionne dans des cas simples, et à la réponse de @ JohnGietzen pour les excellents liens vers HIERARCHYIDlesquels semble être une implémentation native MSSQL2008 du modèle d'ensemble imbriqué.
Jeroen
7

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 )
John Gietzen
la source
1
Avez-vous une source ou une brève démonstration qui HIERARCHYIDempêche la création de boucles de hiérarchie?
Nick Chammas
6

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

AK
la source
Les FDU dans les contraintes CHECK ne fonctionnent PAS. Vous ne pouvez pas obtenir une image cohérente au niveau de la table de l'état proposé après la mise à jour à partir d'une fonction qui s'exécute sur une ligne à la fois. Vous devez utiliser un déclencheur APRÈS et annuler ou un déclencheur AU LIEU DE et refuser de mettre à jour.
ErikE
Mais maintenant, je vois les commentaires de l'autre réponse sur les mises à jour multi-lignes.
ErikE
@ErikE c'est vrai, les FDU dans les contraintes CHECK ne fonctionnent PAS.
AK
@Alex a accepté. J'ai pris quelques heures pour le prouver solidement une fois.
ErikE
4

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.

a1ex07
la source
1
Je suis d'accord que "cela semble fonctionner", mais il peut échouer pour les mises à jour multi-lignes, échouer sous l'isolement de l'instantané et est très lent.
AK
@AlexKuznetsov: Je me rends compte que les requêtes récursives sont relativement lentes et je conviens que les mises à jour à plusieurs lignes peuvent être un problème (elles peuvent cependant être désactivées).
a1ex07
@ a1ex07 Thx pour cette suggestion. Je l'ai essayé, et dans des cas simples, cela semble bien fonctionner. Je ne sais pas encore si l'échec des mises à jour multi-lignes est un problème (bien que ce soit probablement le cas). Je ne sais pas trop ce que vous entendez par "ils peuvent être désactivés"?
Jeroen
À ma connaissance, la tâche implique une logique basée sur le curseur (ou la ligne). Il est donc logique de désactiver les mises à jour qui modifient plus de 1 ligne (simple au lieu du déclencheur de mise à jour qui génère une erreur si la table insérée a plus de 1 ligne).
a1ex07
Si vous ne pouvez pas repenser la table, je créerais une procédure qui vérifie toutes les contraintes et ajoute / met à jour l'enregistrement. Ensuite, je m'assurerai que personne sauf ce sp ne pourra insérer / mettre à jour ce tableau.
a1ex07
3

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.

ErikE
la source
Vous devez utiliser l'indication WITH (READCOMMITTEDLOCK). Hugo Kornelis a écrit un exemple: sqlblog.com/blogs/hugo_kornelis/archive/2006/09/15/…
AK
Merci @Alex, ces articles étaient de la dynamite et m'ont beaucoup aidé à mieux comprendre l'isolement des instantanés. J'ai ajouté un commutateur conditionnel pour lire non engagé dans mon code.
ErikE
2

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.

arc blanc
la source