Tabellen mit Hierarchie: Erstellen Sie eine Einschränkung, um die Zirkularität durch Fremdschlüssel zu verhindern

10

Angenommen, wir haben eine Tabelle, für die eine Fremdschlüsseleinschränkung gilt:

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

Diese Tabelle enthält die folgenden Datensätze:

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

Es gibt Fälle, in denen diese Art von Design sinnvoll sein könnte (z. B. die typische Beziehung "Mitarbeiter und Chef-Mitarbeiter"), und auf jeden Fall: Ich bin in einer Situation, in der ich dies in meinem Schema habe.

Diese Art von Design ermöglicht leider eine Zirkularität in Datensätzen, wie im obigen Beispiel gezeigt.

Meine Frage ist dann:

  1. Ist es möglich , eine Einschränkung zu schreiben, die dies überprüft? und
  2. Ist es möglich , eine Einschränkung zu schreiben, die dies überprüft? (bei Bedarf nur bis zu einer bestimmten Tiefe)

Für Teil (2) dieser Frage kann es relevant sein zu erwähnen, dass ich nur Hunderte oder in einigen Fällen Tausende von Datensätzen in meiner Tabelle erwarte, die normalerweise nicht tiefer als etwa 5 bis 10 Ebenen verschachtelt sind.

PS. MS SQL Server 2008


Update 14. März 2012
Es gab mehrere gute Antworten. Ich habe jetzt die akzeptiert, die mir geholfen hat , die erwähnte Möglichkeit / Machbarkeit zu verstehen . Es gibt jedoch noch einige andere gute Antworten, einige auch mit Implementierungsvorschlägen. Wenn Sie also mit derselben Frage hier gelandet sind, sehen Sie sich alle Antworten an;)

Jeroen
quelle

Antworten:

6

Sie verwenden das Adjacency List- Modell, bei dem es schwierig ist, eine solche Einschränkung durchzusetzen.

Sie können das Nested Set- Modell untersuchen, bei dem nur echte Hierarchien dargestellt werden können (keine Kreisbahnen). Dies hat jedoch andere Nachteile, wie langsame Einfügungen / Aktualisierungen.

ypercubeᵀᴹ
quelle
+1 tolle Links, und verdammt, ich wünschte, ich könnte das verschachtelte Set-Modell ausprobieren und dann diese Antwort als die akzeptieren, die für mich funktioniert hat.
Jeroen
Ich akzeptiere diese Antwort, weil sie mir geholfen hat, die Möglichkeit und Durchführbarkeit zu verstehen , dh sie hat die Frage für mich beantwortet. Jeder, der auf diese Frage stößt, sollte sich die Antwort von @ a1ex07 für eine Einschränkung ansehen, die in einfachen Fällen funktioniert, und die Antwort von @ JohnGietzen für die großartigen Links, zu HIERARCHYIDdenen eine native MSSQL2008-Implementierung des verschachtelten Mengenmodells zu gehören scheint.
Jeroen
7

Ich habe zwei Hauptmethoden gesehen, um dies durchzusetzen:

1, der alte Weg:

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

Die Spalte FooHierarchy würde einen Wert wie den folgenden enthalten:

"|1|27|425"

Wo die Zahlen der FooId-Spalte zugeordnet sind. Sie würden dann erzwingen, dass die Hierarchiespalte mit "| id" endet und der Rest der Zeichenfolge mit der FooHieratchy der PARENT übereinstimmt.

2, der NEUE Weg:

SQL Server 2008 verfügt über einen neuen Datentyp namens HierarchyID , der all dies für Sie erledigt.

Es arbeitet nach dem gleichen Prinzip wie OLD, wird jedoch von SQL Server effizient verwaltet und eignet sich als ERSATZ für Ihre Spalte "ParentID".

CREATE TABLE Foo 
    (FooId BIGINT PRIMARY KEY,
     FooHierarchy HIERARCHYID )
John Gietzen
quelle
1
Haben Sie eine Quelle oder eine kurze Demo, HIERARCHYIDdie die Erstellung von Hierarchieschleifen verhindert?
Nick Chammas
6

Es ist irgendwie möglich: Sie können eine skalare UDF aus Ihrer CHECK-Einschränkung aufrufen und Zyklen beliebiger Länge erkennen. Leider ist dieser Ansatz extrem langsam und unzuverlässig: Sie können falsch positive und falsch negative Ergebnisse erzielen.

Stattdessen würde ich einen materialisierten Pfad verwenden.

Eine andere Möglichkeit, Zyklen zu vermeiden, besteht darin, einen CHECK (ID> ParentID) zu haben, was wahrscheinlich auch nicht sehr machbar ist.

Eine weitere Möglichkeit, Zyklen zu vermeiden, besteht darin, zwei weitere Spalten hinzuzufügen, LevelInHierarchy und ParentLevelInHierarchy, auf die (ParentID, ParentLevelInHierarchy) verweisen (ID, LevelInHierarchy) und einen CHECK (LevelInHierarchy> ParentLevelInHierarchy).

AK
quelle
UDFs in CHECK-Einschränkungen funktionieren NICHT. Sie können von einer Funktion, die jeweils in einer Zeile ausgeführt wird, kein konsistentes Bild des vorgeschlagenen Status nach der Aktualisierung auf Tabellenebene erhalten. Sie müssen einen AFTER-Trigger und ein Rollback oder einen STATT-Trigger verwenden und die Aktualisierung ablehnen.
ErikE
Aber jetzt sehe ich die Kommentare zu der anderen Antwort über mehrzeilige Updates.
ErikE
@ErikE das stimmt, UDFs in CHECK-Einschränkungen funktionieren NICHT.
AK
@ Alex Einverstanden. Ich habe ein paar Stunden gebraucht, um dies einmal zu beweisen.
ErikE
4

Ich glaube es ist möglich:

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)

Ich habe vielleicht etwas verpasst (sorry, ich kann es nicht gründlich testen), aber es scheint zu funktionieren.

a1ex07
quelle
1
Ich bin damit einverstanden, dass "es zu funktionieren scheint", aber es kann bei mehrzeiligen Updates fehlschlagen, bei Snapshot-Isolation fehlschlagen und ist sehr langsam.
AK
@AlexKuznetsov: Mir ist klar, dass rekursive Abfragen relativ langsam sind, und ich stimme zu, dass mehrzeilige Aktualisierungen ein Problem darstellen können (sie können jedoch deaktiviert werden).
a1ex07
@ a1ex07 Danke für diesen Vorschlag. Ich habe es versucht, und in einfachen Fällen scheint es tatsächlich gut zu funktionieren. Ich bin mir noch nicht sicher, ob ein Fehler bei mehrzeiligen Updates ein Problem ist (obwohl dies wahrscheinlich der Fall ist). Ich bin mir nicht sicher, was Sie unter "sie können deaktiviert werden" verstehen.
Jeroen
Nach meinem Verständnis impliziert die Aufgabe eine Cursor- (oder Zeilen-) Logik. Daher ist es sinnvoll, Aktualisierungen zu deaktivieren, die mehr als eine Zeile ändern (einfach anstelle des Aktualisierungsauslösers, der einen Fehler auslöst, wenn die eingefügte Tabelle mehr als eine Zeile enthält).
a1ex07
Wenn Sie die Tabelle nicht neu gestalten können, würde ich eine Prozedur erstellen, die alle Einschränkungen überprüft und Datensätze hinzufügt / aktualisiert. Dann werde ich sicherstellen, dass niemand außer diesem SP diese Tabelle einfügen / aktualisieren kann.
a1ex07
3

Hier ist eine weitere Option: Ein Trigger, der mehrzeilige Aktualisierungen ermöglicht und keine Zyklen erzwingt. Es durchläuft die Ahnenkette, bis ein Stammelement (mit dem übergeordneten NULL) gefunden wird, wodurch bewiesen wird, dass kein Zyklus vorhanden ist. Es ist auf 10 Generationen begrenzt, da ein Zyklus natürlich endlos ist.

Es funktioniert nur mit dem aktuellen Satz geänderter Zeilen. Solange Aktualisierungen nicht eine große Anzahl sehr tiefer Elemente in der Tabelle berühren, sollte die Leistung nicht zu schlecht sein. Es muss für jedes Element die gesamte Kette hinaufgehen, damit es einige Auswirkungen auf die Leistung hat.

Ein wirklich "intelligenter" Auslöser würde direkt nach Zyklen suchen, indem er prüft, ob ein Gegenstand sich selbst erreicht hat, und dann auf Kaution geht. Dies erfordert jedoch die Überprüfung des Status aller zuvor gefundenen Knoten während jeder Schleife und erfordert daher eine WHILE-Schleife und mehr Codierung, als ich gerade wollte. Dies sollte eigentlich nicht teurer sein, da der normale Betrieb darin besteht, keine Zyklen zu haben. In diesem Fall ist es schneller, nur mit der vorherigen Generation zu arbeiten, als mit allen vorherigen Knoten während jeder Schleife.

Ich würde gerne Beiträge von @AlexKuznetsov oder anderen dazu erhalten, wie sich dies bei der Isolierung von Schnappschüssen auswirken würde. Ich vermute, es wäre nicht sehr gut, würde es aber gerne besser verstehen.

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;

Aktualisieren

Ich habe herausgefunden, wie ich eine zusätzliche Verknüpfung mit der eingefügten Tabelle vermeiden kann. Wenn jemand einen besseren Weg sieht, die GROUP BY durchzuführen, um diejenigen zu erkennen, die kein NULL enthalten, lassen Sie es mich bitte wissen.

Ich habe auch einen Schalter zu READ COMMITTED hinzugefügt, wenn sich die aktuelle Sitzung in der Stufe SNAPSHOT ISOLATION befindet. Dies verhindert Inkonsistenzen, führt jedoch leider zu einer erhöhten Blockierung. Das ist für die anstehende Aufgabe unvermeidlich.

ErikE
quelle
Sie sollten den WITH-Hinweis (READCOMMITTEDLOCK) verwenden. Hugo Kornelis schrieb ein Beispiel: sqlblog.com/blogs/hugo_kornelis/archive/2006/09/15/…
AK
Dank @Alex waren diese Artikel Dynamit und haben mir geholfen, die Isolation von Schnappschüssen viel besser zu verstehen. Ich habe einen bedingten Schalter hinzugefügt, um nicht festgeschriebenen Code zu lesen.
ErikE
2

Wenn Ihre Datensätze mehr als eine Ebene verschachtelt sind, funktioniert eine Einschränkung nicht (ich gehe davon aus, dass Sie damit meinen, dass Datensatz 1 das übergeordnete Element von Datensatz 2 und Datensatz 3 das übergeordnete Element von Datensatz 1 ist). Die einzige Möglichkeit, dies zu tun, wäre entweder im übergeordneten Code oder mit einem Auslöser. Wenn Sie sich jedoch eine große Tabelle und mehrere Ebenen ansehen, wäre dies ziemlich intensiv.

Weißbogen
quelle