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

10

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

Jeroen
źródło

Odpowiedzi:

6

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.

ypercubeᵀᴹ
źródło
Daj +1 świetnym linkom i do diabła, szkoda, że ​​nie mogę przejść dalej i wypróbować Modelu Zagnieżdżonego Zestawu, a następnie zaakceptować tę odpowiedź jako tę, która zadziałała dla mnie.
Jeroen
Przyjmuję tę odpowiedź, ponieważ to ta pomogła mi zrozumieć możliwość i wykonalność , tj. Odpowiedziała na pytanie. Jednak każdy, lądowanie na to pytanie należy przyjrzeć się użytkownika @ a1ex07 odpowiedź na przymus, który działa w prostych przypadkach, i @ JohnGietzen na odpowiedź dla wielkich linki do HIERARCHYIDktórego wydaje się być natywna implementacja MSSQL2008 o model zbiorów zagnieżdżonych.
Jeroen
7

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 )
John Gietzen
źródło
1
Czy masz źródło lub krótką wersję demonstracyjną, która HIERARCHYIDuniemożliwia tworzenie pętli hierarchii?
Nick Chammas
6

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

AK
źródło
UDF w ograniczeniach CHECK NIE działają. Nie można uzyskać spójnego obrazu na poziomie tabeli proponowanego stanu po aktualizacji z funkcji działającej w jednym wierszu na raz. Musisz użyć PO wyzwalaczu i wycofać lub INSTEAD z wyzwalacza i odmówić aktualizacji.
ErikE
Ale teraz widzę komentarze do drugiej odpowiedzi na temat aktualizacji w wielu wierszach.
ErikE
@ErikE to prawda, UDF w ograniczeniach CHECK NIE działają.
AK
@Alex Agreed. Pewnego razu zajęło mi to kilka godzin.
ErikE
4

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.

a1ex07
źródło
1
Zgadzam się, że „wydaje się działać”, ale może się nie powieść w przypadku aktualizacji w wielu wierszach, może się nie powieść przy izolacji migawki i jest bardzo wolny.
AK
@AlexKuznetsov: Zdaję sobie sprawę, że zapytania rekurencyjne są stosunkowo wolne i zgadzam się, że aktualizacje w wielu wierszach mogą stanowić problem (można je jednak wyłączyć).
a1ex07
@ a1ex07 Thx za tę sugestię. Próbowałem i w prostych przypadkach wydaje się, że działa naprawdę dobrze. Nie jestem jeszcze pewien, czy awaria aktualizacji wielu wierszy stanowi problem (choć prawdopodobnie tak jest). Nie jestem jednak pewien, co rozumiesz przez „można je wyłączyć”?
Jeroen
W moim rozumieniu zadanie to opiera się na logice opartej na kursorach (lub wierszach). Dlatego sensowne jest wyłączenie aktualizacji, które modyfikują więcej niż 1 wiersz (prosty zamiast wyzwalacza aktualizacji, który powoduje błąd, jeśli wstawiona tabela ma więcej niż 1 wiersz).
a1ex07
Jeśli nie możesz przeprojektować tabeli, utworzę procedurę, która sprawdza wszystkie ograniczenia i dodaje / aktualizuje rekord. Następnie upewnię się, że nikt oprócz tego sp nie może wstawić / zaktualizować tej tabeli.
a1ex07
3

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.

ErikE
źródło
Powinieneś używać Z PODAJNIKIEM (READCOMMITTEDLOCK) podpowiedzi. Hugo Kornelis napisał przykład: sqlblog.com/blogs/hugo_kornelis/archive/2006/09/09/15/…
AK
Dzięki @Alex te artykuły były dynamitem i pomogły mi lepiej zrozumieć izolację migawkową. Dodałem przełącznik warunkowy, aby czytać niezaangażowany do mojego kodu.
ErikE
2

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.

whiterainbow
źródło