Wie schreibe ich eine Abfrage, die alle Zirkelverweise findet, wenn eine Tabelle auf sich selbst verweist?

26

Ich habe das folgende Schema (Namen geändert), das ich nicht ändern kann:

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

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

Das heißt, jeder Datensatz ist einem anderen Datensatz untergeordnet. Wenn der Wert eines Datensatzes ParentIdgleich dem Wert seines ist Id, wird der Datensatz als Stammknoten betrachtet.

Ich möchte eine Abfrage ausführen, die alle Zirkelverweise findet. Zum Beispiel mit den Daten

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

Die Abfrage sollte zurückkehren

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

Ich habe die folgende Abfrage für SQL Server 2008 R2 geschrieben und frage mich, ob diese Abfrage verbessert werden kann:

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
quelle
Das 0 > 0sollte nicht als Zyklus angesehen werden?
Ypercubeᵀᴹ
1
Nein, 0 ist ein Wurzelknoten, da sein ParentIdWert gleich seinem Idist. In diesem Szenario handelt es sich also nicht um einen Zyklus.
Cubetwo1729

Antworten:

30

Dies erfordert einen rekursiven CTE:

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;

Sehen Sie es hier in Aktion: SQL Fiddle


Aktualisieren:

Entfernung hinzugefügt, um alle Selbstzyklen ausschließen zu können (siehe Kommentar von 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-Geige

Welches Sie verwenden sollten, hängt von Ihrer Anforderung ab.

Sebastian Meine
quelle
Dies sollte korrigiert werden. Derzeit zeigt es auch 1-Zyklen, wie 6 > 6lange es nicht ist 0 > 0.
Ypercubeᵀᴹ
Ich habe das OP so verstanden, dass nur der eigentliche Wurzelknotenselbstzyklus ausgeschlossen werden soll. Sie können diese Anforderung jedoch leicht hinzufügen, indem Sie in der letzten where-Klausel prüfen, ob R.Path wie '%>%' ist. Sie können auch eine Spalte für die Zykluslängenzählung in den rekursiven CTE einfügen.
Sebastian Meine
2
Sie könnten nur WHERE Id <> ParentIdim ersten Teil des CTE hinzufügen .
Ypercubeᵀᴹ
AND C.ParentId <> C.Idist nicht genug. Führt ein Pfad in einen längeren Kreis ( A->B, B->C, C->B), erhalten Sie immer noch eine unendliche Rekursion für die Erstellung der Pfade, die mit beginnen A. Sie müssten wirklich den gesamten Pfad überprüfen.
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
quelle
1
Und wie funktioniert das? Es ist normalerweise die Erklärung, die eine gute Antwort gibt. Nur-Code-Posts werden hier verpönt (normalerweise zumindest).
Dezso
2
Dies scheint eine ähnliche, aber unterschiedliche Frage zu beantworten.
ypercubeᵀᴹ