¿Cómo escribir una consulta que encuentre todas las referencias circulares cuando una tabla hace referencia a sí misma?

26

Tengo el siguiente esquema (nombres cambiados), que no puedo cambiar:

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

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

Es decir, cada registro es hijo de otro registro. Si un registro ParentIdes igual a su Id, entonces el registro se considera un nodo raíz.

Quiero ejecutar una consulta que encontrará todas las referencias circulares. Por ejemplo, con los datos

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

la consulta debe devolver

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

Escribí la siguiente consulta para SQL Server 2008 R2, y me pregunto si esta consulta se puede mejorar:

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
fuente
El 0 > 0no debe considerarse un ciclo?
ypercubeᵀᴹ
1
No, 0 es un nodo raíz, ya que es ParentIdigual a su Id, por lo que no es un ciclo para este escenario.
cubetwo1729

Respuestas:

30

Esto requiere un CTE recursivo:

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;

Véalo en acción aquí: SQL Fiddle


Actualizar:

Distancia añadida para poder excluir todos los ciclos personales (ver el comentario 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;

Violín de SQL

Cuál debe usar depende de sus requisitos.

Sebastian Meine
fuente
Esto debe ser corregido. Actualmente también muestra 1 ciclos, como 6 > 6, siempre que no lo sea 0 > 0.
ypercubeᵀᴹ
Comprendí el OP de que solo se debe excluir el ciclo propio de los nodos raíz. Sin embargo, puede agregar fácilmente ese requisito marcando que R.Path como '%>%' en la cláusula where final. O puede agregar una columna de conteo de longitud de ciclo dentro del CTE recursivo.
Sebastian Meine
2
Puede agregar WHERE Id <> ParentIdla primera parte del CTE.
ypercubeᵀᴹ
AND C.ParentId <> C.Idno es suficiente. Si un camino conduce a un círculo más largo ( A->B, B->C, C->B), aún obtendría una recursión infinita para construir los caminos desde el principio A. Realmente necesitaría verificar el camino completo.
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
fuente
1
¿Y cómo funciona esto? Por lo general, es la explicación la que da una buena respuesta. Las publicaciones de solo código están mal vistas aquí (por lo general, al menos).
dezso
2
Parece que responde una pregunta similar pero diferente.
ypercubeᵀᴹ