Tabele z hierarchią: utwórz ograniczenie, aby zapobiec cykliczności za pomocą kluczy obcych

Załóżmy, że mamy tabelę, która ma dla siebie ograniczenie klucza obcego, takie jak:

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

Ta tabela będzie zawierać następujące rekordy:

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

Są przypadki, w których ten rodzaj projektu może mieć sens (np. Typowa relacja „pracownik-szef-pracownik”), a w każdym razie: jestem w sytuacji, w której mam to w swoim schemacie.

Ten rodzaj konstrukcji niestety pozwala na zachowanie okrągłości w rekordach danych, jak pokazano w powyższym przykładzie.

Moje pytanie brzmi zatem:

1. Czy można napisać ograniczenie, które to sprawdza? i
2. Czy jest możliwe napisanie ograniczenia, które to sprawdza? (w razie potrzeby tylko do określonej głębokości)

W części (2) tego pytania warto wspomnieć, że oczekuję tylko setek, a może w niektórych przypadkach tysięcy rekordów w mojej tabeli, zwykle nie zagnieżdżonych głębiej niż około 5 do 10 poziomów.

PS. MS SQL Server 2008

Aktualizacja 14 marca 2012 r.
Było kilka dobrych odpowiedzi. Teraz zaakceptowałem ten, który pomógł mi zrozumieć wspomnianą możliwość / wykonalność. Istnieje jednak kilka innych świetnych odpowiedzi, niektóre z sugestiami implementacyjnymi, więc jeśli trafiłeś tutaj z tym samym pytaniem, przejrzyj wszystkie odpowiedzi;)

Używasz modelu listy ograniczeń , gdzie trudno jest egzekwować takie ograniczenie.

Możesz zbadać model zestawu zagnieżdżonego , w którym mogą być reprezentowane tylko prawdziwe hierarchie (bez ścieżek kołowych). Ma to jednak inne wady, takie jak powolne wstawki / aktualizacje.

Widziałem 2 główne sposoby egzekwowania tego:

1, stary sposób:

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

Kolumna FooHierarchy zawierałaby następującą wartość:

"|1|27|425"

Gdzie liczby są odwzorowane na kolumnę FooId. Następnie wymusiłbyś, aby kolumna Hierarchia kończyła się na „| id”, a reszta ciągu była zgodna z FooHieratchy dla RODZICIELA.

2, NOWY sposób:

SQL Server 2008 ma nowy typ danych o nazwie HierarchyID , który robi to wszystko za Ciebie.

Działa na tej samej zasadzie, co w STARY sposób, ale jest skutecznie obsługiwany przez SQL Server i nadaje się do użycia jako WYMIANA kolumny „ParentID”.

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

Jest to w pewnym sensie możliwe: możesz wywołać skalarny UDF od ciebie Ograniczenie SPRAWDŹ, i może wykryć cykle o dowolnej długości. Niestety, takie podejście jest bardzo powolne i zawodne: możesz mieć fałszywie dodatnie i fałszywe negatywy.

Zamiast tego użyłbym zmaterializowanej ścieżki.

Innym sposobem na uniknięcie cykli jest sprawdzenie (ID> ParentID), co prawdopodobnie również nie jest bardzo wykonalne.

Jeszcze innym sposobem na uniknięcie cykli jest dodanie dwóch kolejnych kolumn, LevelInHierarchy i ParentLevelInHierarchy, odwołanie (ParentID, ParentLevelInHierarchy) do (ID, LevelInHierarchy) i sprawdzenie ((LevelInHierarchy> ParentLevelInHierarchy).

Wierzę, że to możliwe:

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)

Mogłem coś przeoczyć (przepraszam, nie jestem w stanie go dokładnie przetestować), ale wydaje się, że działa.

Oto kolejna opcja: wyzwalacz, który umożliwia aktualizacje w wielu wierszach i nie wymusza żadnych cykli. Działa poprzez przemierzanie łańcucha przodka, aż znajdzie element główny (z rodzica NULL), co dowodzi, że nie ma cyklu. Jest ograniczony do 10 pokoleń, ponieważ oczywiście cykl nie ma końca.

Działa tylko z bieżącym zestawem zmodyfikowanych wierszy, więc dopóki aktualizacje nie dotykają ogromnej liczby bardzo głębokich elementów w tabeli, wydajność nie powinna być tak zła. Musi iść w górę łańcucha dla każdego elementu, więc będzie miał pewien wpływ na wydajność.

Prawdziwie „inteligentny” wyzwalacz szukałby cykli bezpośrednio, sprawdzając, czy przedmiot doszedł do siebie, a następnie ratował. Wymaga to jednak sprawdzenia stanu wszystkich wcześniej znalezionych węzłów podczas każdej pętli, a zatem wymaga pętli WHILE i większego kodowania, niż chciałem teraz. Nie powinno to być tak naprawdę droższe, ponieważ normalną operacją byłoby brak cykli, w tym przypadku szybsza będzie praca tylko z poprzednią generacją niż ze wszystkimi poprzednimi węzłami w każdej pętli.

Chciałbym uzyskać informacje od @AlexKuznetsov lub kogokolwiek innego na temat tego, jak by to wyglądało w izolacji migawkowej. Podejrzewam, że to nie bardzo dobrze, ale chciałbym to lepiej zrozumieć.

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;

Aktualizacja

Wymyśliłem, jak uniknąć dodatkowego łączenia z powrotem do wstawionego stołu. Jeśli ktoś widzi lepszy sposób wykonania GROUP BY w celu wykrycia tych, które nie zawierają wartości NULL, proszę dać mi znać.

Dodałem również przełącznik READ COMMITTED, jeśli bieżąca sesja jest na poziomie SNAPSHOT ISOLATION. Zapobiegnie to niespójnościom, choć niestety spowoduje zwiększone blokowanie. Jest to rodzaj nieuniknionego zadania.

Jeśli twoje rekordy są zagnieżdżone na więcej niż 1 poziomie, ograniczenie nie zadziała (zakładam, że masz na myśli, że np. Rekord 1 jest rodzicem rekordu 2, a rekord 3 jest rodzicem rekordu 1). Jedynym sposobem na zrobienie tego byłoby użycie kodu nadrzędnego lub wyzwalacza, ale jeśli patrzysz na dużą tabelę i wiele poziomów, byłoby to dość intensywne.