Tabel dengan hierarki: buat batasan untuk mencegah sirkularitas melalui kunci asing

Misalkan kita memiliki tabel yang memiliki batasan kunci asing untuk dirinya sendiri, seperti:

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

Tabel ini akan memiliki catatan berikut:

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

Ada kasus-kasus di mana desain semacam ini bisa masuk akal (misalnya hubungan "karyawan-dan-bos-karyawan" yang khas), dan dalam kasus apa pun: Saya berada dalam situasi di mana saya memiliki ini dalam skema saya.

Sayangnya, jenis desain ini memungkinkan untuk melingkar dalam catatan data, seperti ditunjukkan pada contoh di atas.

Pertanyaan saya kemudian adalah:

1. Apakah mungkin untuk menulis batasan yang memeriksa ini? dan
2. Apakah layak untuk menulis batasan yang memeriksa ini? (jika hanya perlu sampai kedalaman tertentu)

Untuk bagian (2) dari pertanyaan ini, mungkin relevan untuk menyebutkan bahwa saya mengharapkan hanya ratusan atau mungkin dalam beberapa kasus ribuan catatan dalam tabel saya, biasanya tidak bersarang lebih dalam dari level sekitar 5 hingga 10.

PS. MS SQL Server 2008

Pembaruan 14 Maret 2012
Ada beberapa jawaban bagus. Saya sekarang telah menerima salah satu yang membantu saya memahami kemungkinan / kelayakan yang disebutkan. Ada beberapa jawaban hebat lainnya, beberapa dengan saran implementasi juga, jadi jika Anda mendarat di sini dengan pertanyaan yang sama, lihat semua jawaban;)

Anda menggunakan model Daftar Adjacency , di mana sulit untuk menegakkan batasan seperti itu.

Anda bisa memeriksa model Nested Set , di mana hanya hierarki sejati yang dapat diwakili (tidak ada jalur melingkar). Ini memiliki kelemahan lain, seperti Sisipan / Pembaruan lambat.

Saya telah melihat 2 cara utama untuk menegakkan ini:

1, jalan LAMA:

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

Kolom FooHierarchy akan berisi nilai seperti ini:

"|1|27|425"

Di mana angka dipetakan ke kolom FooId. Anda kemudian akan menegakkan bahwa kolom Hierarki berakhir dengan "| id" dan seluruh string cocok dengan FooHieratchy dari PARENT.

2, cara BARU:

SQL Server 2008 memiliki tipe data baru yang disebut HierarchyID , yang melakukan semua ini untuk Anda.

Ini beroperasi pada prinsip yang sama dengan cara LAMA, tetapi ditangani secara efisien oleh SQL Server, dan cocok untuk digunakan sebagai PENGGANTIAN untuk kolom "ParentID" Anda.

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

Ini agak mungkin: Anda dapat memanggil UDF skalar dari Anda PERIKSA kendala, dan itu semacam dapat mendeteksi siklus berapa pun panjangnya. Sayangnya, pendekatan ini sangat lambat dan tidak dapat diandalkan: Anda dapat memiliki positif palsu dan negatif palsu.

Sebaliknya, saya akan menggunakan jalur terwujud.

Cara lain untuk menghindari siklus adalah memiliki PERIKSA (ID> ParentID), yang mungkin juga sangat tidak layak.

Namun cara lain untuk menghindari siklus adalah menambahkan dua kolom lagi, LevelInHierarchy dan ParentLevelInHierarchy, merujuk (ParentID, ParentLevelInHierarchy) merujuk ke (ID, LevelInHierarchy), dan memiliki PERIKSA (LevelInHierarchy> ParentLevelInHierarchy).

Saya percaya itu mungkin:

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)

Saya mungkin telah melewatkan sesuatu (maaf, saya tidak dapat mengujinya secara menyeluruh), tetapi sepertinya berhasil.

Berikut adalah pilihan lain: pemicu yang memungkinkan pembaruan multi-baris dan tidak memaksakan siklus. Ia bekerja dengan melintasi rantai leluhur sampai menemukan elemen root (dengan orangtua NULL), sehingga membuktikan tidak ada siklus. Ini terbatas pada 10 generasi karena siklus tentu saja tidak ada habisnya.

Ini hanya bekerja dengan set baris yang dimodifikasi saat ini, sehingga selama pembaruan tidak menyentuh sejumlah besar item yang sangat dalam di tabel, kinerja seharusnya tidak terlalu buruk. Itu harus pergi semua jalan sampai rantai untuk setiap elemen, sehingga akan memiliki beberapa dampak kinerja.

Pemicu yang benar-benar "cerdas" akan mencari siklus secara langsung dengan memeriksa untuk melihat apakah suatu barang mencapai dirinya sendiri dan kemudian menyerah. Namun, ini membutuhkan keadaan pemeriksaan semua node yang ditemukan sebelumnya selama setiap loop dan dengan demikian mengambil loop WHILE dan lebih banyak pengkodean daripada yang ingin saya lakukan sekarang. Ini seharusnya tidak benar-benar lebih mahal karena operasi normal adalah tidak memiliki siklus dan dalam hal ini akan lebih cepat bekerja hanya dengan generasi sebelumnya daripada semua node sebelumnya selama setiap loop.

Saya ingin masukan dari @AlexKuznetsov atau siapa pun tentang bagaimana hal ini akan terjadi dalam isolasi snapshot. Saya menduga itu tidak terlalu baik, tetapi ingin memahaminya dengan lebih baik.

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;

Memperbarui

Saya menemukan cara untuk menghindari tambahan bergabung kembali ke tabel Dimasukkan. Jika ada yang melihat cara yang lebih baik untuk melakukan GROUP BY untuk mendeteksi mereka yang tidak mengandung NULL, beri tahu saya.

Saya juga menambahkan peralihan ke READ COMMITTED jika sesi saat ini di tingkat ISOLASI SNAPSHOT. Ini akan mencegah inkonsistensi, meskipun sayangnya akan menyebabkan pemblokiran yang meningkat. Itu agak tidak bisa dihindari untuk tugas yang dihadapi.

Jika catatan Anda bersarang lebih dari 1 tingkat, batasan tidak akan berfungsi (saya berasumsi maksud Anda misalnya catatan 1 adalah induk dari catatan 2, dan catatan 3 adalah induk dari catatan 1). Satu-satunya cara untuk melakukan ini adalah dengan kode induk atau dengan pemicu, tetapi jika Anda melihat tabel besar dan beberapa level ini akan cukup intensif.