Sql-server – How to Traverse All Foreign Keys to Generate All Possible Paths

foreign keyjoin;sql server

I'm attempting to traverse all of the foreign keys in a SQL Server database to generate all of the possible paths between tables. The query below seems to mostly work for what I am needing except that it seems to run indefinitely. My goal is to be able to find the most efficient foreign key path between any two tables in the database by using the path with the least number of "hops" to my destination table. Is there a way to limit the query below so that it doesn't go beyond 20 hops?

WITH cte
AS
(
    SELECT 
        fk.create_date
        , fk.modify_date
        , fkc.constraint_object_id AS ConstraintId
        , OBJECT_NAME(fkc.constraint_object_id) AS ConstraintName
        --, fkc.referenced_object_id AS PrimaryKeyTableId
        , OBJECT_NAME(fkc.referenced_object_id) AS PrimaryKeyTableName
        --, fkc.referenced_column_id AS PrimaryKeyColumnId
        , rc.name AS PrimaryKeyColumnName
        --, fk.parent_object_id AS ForeignKeyTableId
        , OBJECT_NAME(fk.parent_object_id) AS ForeignKeyTableName
        --, fkc.parent_column_id AS ForeignKeyColumnId
        , lc.name AS ForeignKeyColumnName
    FROM sys.foreign_key_columns fkc
    INNER JOIN sys.columns rc 
        ON  rc.OBJECT_ID = fkc.referenced_object_id 
        AND fkc.referenced_column_id = rc.column_id
    INNER JOIN sys.foreign_keys fk 
        ON  fk.OBJECT_ID = fkc.constraint_object_id
    INNER JOIN sys.columns lc 
        ON  lc.OBJECT_ID = fk.parent_object_id
        AND fkc.parent_column_id = lc.column_id
)
, cte2(create_date, modify_date, ConstraintName
        , PrimaryKeyTableName, PrimaryKeyColumnName
        , ForeignKeyTableName, ForeignKeyColumnName
        , Hops, path ) AS 
    (
        SELECT
            create_date, modify_date, ConstraintName
            , PrimaryKeyTableName, PrimaryKeyColumnName
            , ForeignKeyTableName, ForeignKeyColumnName 
            , 1 , CAST(QUOTENAME(PrimaryKeyTableName + '.' + PrimaryKeyColumnName) AS VARCHAR(4000))
        FROM cte
    UNION ALL
        SELECT 
            cte.create_date, cte.modify_date, cte.ConstraintName
            , cte.PrimaryKeyTableName, cte.PrimaryKeyColumnName
            , cte.ForeignKeyTableName, cte.ForeignKeyColumnName
            , cte2.Hops +1, CAST(cte2.path + '-> ' +QUOTENAME(cte.PrimaryKeyTableName+ '.' + cte.PrimaryKeyColumnName) AS VARCHAR(4000))
        FROM cte2 INNER JOIN cte ON cte2.ForeignKeyTableName = cte.PrimaryKeyTableName
        AND cte2.ForeignKeyColumnName != cte.PrimaryKeyColumnName
    )
SELECT 
ConstraintName
        , PrimaryKeyTableName, PrimaryKeyColumnName
        , ForeignKeyTableName, ForeignKeyColumnName
        , Hops, path + '-> ' + QUOTENAME(ForeignKeyTableName + '.' + ForeignKeyColumnName) AS Path
FROM cte2

Best Answer

I would try one or both of the following:

  • You've already added a Hops counter column in the anchor. In the recursive part of the CTE, you can filter WHERE cte2.Hops<20

  • In the first cte common table expression, I would add WHERE fk.parent_object_id!=fk.referenced_object_id to exclude infinite self-referencing foreign keys (like parent-child hierarchies).

Related Question