Bagaimana cara menulis kueri yang menemukan semua referensi melingkar ketika tabel referensi itu sendiri?

26

Saya memiliki skema berikut (nama diubah), yang tidak dapat saya ubah:

CREATE TABLE MyTable (
    Id INT NOT NULL PRIMARY KEY,
    ParentId INT NOT NULL
);

ALTER TABLE MyTable ADD FOREIGN KEY (ParentId) REFERENCES MyTable(Id);

Artinya, setiap catatan adalah anak dari catatan lain. Jika record ParentIdsama dengan nya Id, maka record dianggap sebagai root node.

Saya ingin menjalankan kueri yang akan menemukan semua referensi melingkar. Misalnya dengan data

INSERT INTO MyTable (Id, ParentId) VALUES
    (0, 0),
    (1, 0),
    (2, 4),
    (3, 2),
    (4, 3);

kueri harus kembali

Id | Cycle
2  | 2 < 4 < 3 < 2
3  | 3 < 2 < 4 < 3
4  | 4 < 3 < 2 < 4

Saya menulis kueri berikut untuk SQL Server 2008 R2, dan saya ingin tahu apakah kueri ini dapat diperbaiki:

IF OBJECT_ID(N'tempdb..#Results') IS NOT NULL DROP TABLE #Results;
CREATE TABLE #Results (Id INT, HasParentalCycle BIT, Cycle VARCHAR(MAX));

DECLARE @i INT,
    @j INT,
    @flag BIT,
    @isRoot BIT,
    @ids VARCHAR(MAX);

DECLARE MyCursor CURSOR FAST_FORWARD FOR
    SELECT Id
    FROM MyTable;

OPEN MyCursor;
FETCH NEXT FROM MyCursor INTO @i;
WHILE @@FETCH_STATUS = 0
BEGIN
    IF OBJECT_ID(N'tempdb..#Parents') IS NOT NULL DROP TABLE #Parents;
    CREATE TABLE #Parents (Id INT);

    SET @ids = NULL;
    SET @isRoot = 0;
    SET @flag = 0;
    SET @j = @i;
    INSERT INTO #Parents (Id) VALUES (@j);

    WHILE (1=1)
    BEGIN
        SELECT
            @j = ParentId,
            @isRoot = CASE WHEN ParentId = Id THEN 1 ELSE 0 END
        FROM MyTable
        WHERE Id = @j;

        IF (@isRoot = 1)
        BEGIN
            SET @flag = 0;
            BREAK;
        END        

        IF EXISTS (SELECT 1 FROM #Parents WHERE Id = @j)
        BEGIN
            INSERT INTO #Parents (Id) VALUES (@j);
            SET @flag = 1;
            SELECT @ids = COALESCE(@ids + ' < ', '') + CAST(Id AS VARCHAR) FROM #Parents;
            BREAK;
        END
        ELSE
        BEGIN
            INSERT INTO #Parents (Id) VALUES (@j);
        END        
    END

    INSERT INTO #Results (Id, HasParentalCycle, Cycle) VALUES (@i, @flag, @ids);

    FETCH NEXT FROM MyCursor INTO @i;
END
CLOSE MyCursor;
DEALLOCATE MyCursor;

SELECT Id, Cycle
FROM #Results
WHERE HasParentalCycle = 1;
cubetwo1729
sumber
The 0 > 0tidak harus dianggap siklus?
ypercubeᵀᴹ
1
Tidak, 0 adalah simpul root, karena ParentIdsama dengan simpulnya Id, jadi ini bukan siklus untuk skenario ini.
cubetwo1729

Jawaban:

30

Ini panggilan untuk CTE rekursif:

WITH FindRoot AS
(
    SELECT Id,ParentId, CAST(Id AS NVARCHAR(MAX)) Path
    FROM dbo.MyTable

    UNION ALL

    SELECT C.Id, P.ParentId, C.Path + N' > ' + CAST(P.Id AS NVARCHAR(MAX))
    FROM dbo.MyTable P
    JOIN FindRoot C
    ON C.ParentId = P.Id AND P.ParentId <> P.Id AND C.ParentId <> C.Id
 )
SELECT *
FROM FindRoot R
WHERE R.Id = R.ParentId 
  AND R.ParentId <> 0;

Lihat beraksi di sini: SQL Fiddle


Memperbarui:

Menambahkan jarak untuk dapat mengecualikan semua siklus diri (lihat komentar ypercube):

WITH FindRoot AS
(
    SELECT Id,ParentId, CAST(Id AS NVARCHAR(MAX)) Path, 0 Distance
    FROM dbo.MyTable

    UNION ALL

    SELECT C.Id, P.ParentId, C.Path + N' > ' + CAST(P.Id AS NVARCHAR(MAX)), C.Distance + 1
    FROM dbo.MyTable P
    JOIN FindRoot C
    ON C.ParentId = P.Id AND P.ParentId <> P.Id AND C.ParentId <> C.Id
 )
SELECT *
FROM FindRoot R
WHERE R.Id = R.ParentId 
  AND R.ParentId <> 0
  AND R.Distance > 0;

SQL Fiddle

Yang mana yang harus Anda gunakan tergantung pada kebutuhan Anda.

Sebastian Meine
sumber
Ini harus diperbaiki. Saat ini juga menunjukkan 1-siklus, seperti 6 > 6, asalkan tidak 0 > 0.
ypercubeᵀᴹ
Saya mengerti OP bahwa hanya siklus root node sendiri yang harus dikecualikan. Namun Anda dapat dengan mudah menambahkan persyaratan itu dengan memeriksa R.Path seperti '%>%' di klausa final where. Atau Anda bisa menambahkan kolom hitungan panjang siklus di dalam CTE rekursif.
Sebastian Meine
2
Anda bisa menambahkan WHERE Id <> ParentIddi bagian pertama CTE.
ypercubeᵀᴹ
AND C.ParentId <> C.Idtidak cukup. Jika sebuah jalur mengarah ke lingkaran yang lebih panjang ( A->B, B->C, C->B), Anda masih akan mendapatkan rekursi tak terbatas untuk membangun jalur yang dimulai A. Anda benar-benar perlu memeriksa seluruh jalur.
Bergi
2
SELECT RC.CONSTRAINT_NAME FK_Name
, KF.TABLE_SCHEMA FK_Schema
, KF.TABLE_NAME FK_Table
, KF.COLUMN_NAME FK_Column
, RC.UNIQUE_CONSTRAINT_NAME PK_Name
, KP.TABLE_SCHEMA PK_Schema
, KP.TABLE_NAME PK_Table
, KP.COLUMN_NAME PK_Column
, RC.MATCH_OPTION MatchOption
, RC.UPDATE_RULE UpdateRule
, RC.DELETE_RULE DeleteRule
FROM INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS RC
JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KF ON RC.CONSTRAINT_NAME = KF.CONSTRAINT_NAME
JOIN INFORMATION_SCHEMA.KEY_COLUMN_USAGE KP ON RC.UNIQUE_CONSTRAINT_NAME = KP.CONSTRAINT_NAME
WHERE KF.TABLE_NAME = KP.TABLE_NAME
StuntThumper
sumber
1
Dan bagaimana cara kerjanya? Biasanya penjelasan itulah yang membuat jawaban yang bagus. Posting hanya kode disukai di sini (biasanya, setidaknya).
dezso
2
Ini sepertinya menjawab pertanyaan yang serupa tetapi berbeda.
ypercubeᵀᴹ