Comment écrire une requête qui trouve toutes les références circulaires quand une table se référence elle-même?

26

J'ai le schéma suivant (les noms ont changé), que je ne peux pas changer:

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

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

Autrement dit, chaque enregistrement est un enfant d'un autre enregistrement. Si un enregistrement ParentIdest égal à son Id, alors l'enregistrement est considéré comme un nœud racine.

Je veux exécuter une requête qui trouvera toutes les références circulaires. Par exemple, avec les données

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

la requête doit retourner

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

J'ai écrit la requête suivante pour SQL Server 2008 R2, et je me demande si cette requête peut être améliorée:

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
la source
Le 0 > 0ne devrait pas être considéré comme un cycle?
ypercubeᵀᴹ
1
Non, 0 est un nœud racine, car son ParentIdest égal à son Id, ce n'est donc pas un cycle pour ce scénario.
cubetwo1729

Réponses:

30

Cela nécessite un CTE récursif:

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;

Voyez-le en action ici: SQL Fiddle


Mise à jour:

Ajout d'une distance pour pouvoir exclure tous les auto-cycles (voir le commentaire de 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

Lequel vous devez utiliser dépend de vos besoins.

Sebastian Meine
la source
Cela devrait être corrigé. Actuellement, il affiche également 1 cycle, comme 6 > 6, tant qu'il ne l'est pas 0 > 0.
ypercubeᵀᴹ
J'ai compris l'OP que seul l'auto-cycle des nœuds racine réels doit être exclu. Vous pouvez cependant facilement ajouter cette exigence en vérifiant que R.Path comme «%>%» dans la dernière clause where. Ou vous pouvez ajouter une colonne de comptage de durée de cycle à l'intérieur du CTE récursif.
Sebastian Meine
2
Vous pouvez simplement ajouter WHERE Id <> ParentIdla première partie du CTE.
ypercubeᵀᴹ
AND C.ParentId <> C.Idn'est pas assez. A->B, B->C, C->BSi un chemin mène à un cercle plus long ( ), vous obtiendriez toujours une récursion infinie pour construire les chemins commençant par A. Vous auriez vraiment besoin de vérifier le chemin complet.
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
la source
1
Et comment ça marche? C'est généralement l'explication qui fait une bonne réponse. Les publications uniquement codées sont désapprouvées ici (généralement, au moins).
dezso
2
Il semble que cela réponde à une question similaire mais différente.
ypercubeᵀᴹ