How to list tables in their dependency order (based on foreign keys)?

Question

This question was originally asked by @PrateekGupta

---

Background

@PrateekGupta wanted to perform bulk insert operation on multiple tables.
The tables have foreign key relationships between themselves.
If an INSERT operation is done on a table with a foreign key before the referenced table is being inserted to, the operation might fail due to violation of the foreign key.

Requirement

Produce a list of tables within a database ordered according to their dependencies.
Tables with no dependencies (no foreign keys) will be 1st.
Tables with dependencies only in the 1st set of tables will be 2nd.
Tables with dependencies only in the 1st or 2nd sets of tables will be 3rd.
and so on...

Baun

Answer 1

    example:

    create table t1 (i int primary key,j int unique)
    create table t2 (i int primary key references t1 (i));
    create table t3 (i int,j int,primary key (i,j));
    create table t4 (i int,j int,  foreign key (i,j) references t3 (i,j));
    create table t5 (i int references t1 (i),j int,foreign key (i,j) references t3 (i,j));
    create table t6 (i int references t2 (i));

---

with        cte (lvl,object_id,name)
            as 
            (
                select      1
                           ,object_id
                           ,name

                from        sys.tables

                where       type_desc       = 'USER_TABLE'
                        and is_ms_shipped   = 0

                union all

                select      cte.lvl + 1
                           ,t.object_id
                           ,t.name
                from                    cte

                            join        sys.tables  as t

                            on          exists
                                        (
                                            select      null

                                            from        sys.foreign_keys    as fk

                                            where       fk.parent_object_id     = t.object_id 
                                                    and fk.referenced_object_id = cte.object_id
                                        )

                                    and t.object_id <> cte.object_id
                                    and cte.lvl < 30

                where       t.type_desc     = 'USER_TABLE'      
                        and t.is_ms_shipped = 0
            )


select      name
           ,max (lvl)   as dependency_level

from        cte

group by    name

order by    dependency_level
           ,name
;

Baun

I want to rewrite this query using another DB, but it does not support recursive queries, maybe there is another way of doing this? – Farrar

Answer 2

The above answers won't work with circular references. You can use this stored procedure instead.

EXEC sp_msdependencies @flags = 8

Can see the flag options here

EXEC sp_msdependencies '?'

Unfortunately this is not available on SQL Azure.

Sentry

This executes very quickly even with a very large, complicated schema, and was very helpful: thank you, Pigeon. – Absorption

This should be valid answer. Very fast, efficient and clever! – Pegeen

Answer 3

Thanks for David.

I've just added the schema name to his query if anyone needed

WITH cte (lvl, object_id, name, schema_Name) AS
  (SELECT 1, object_id, sys.tables.name, sys.schemas.name as schema_Name
   FROM sys.tables Inner Join sys.schemas on sys.tables.schema_id = sys.schemas.schema_id
   WHERE type_desc = 'USER_TABLE'
     AND is_ms_shipped = 0
   UNION ALL SELECT cte.lvl + 1, t.object_id, t.name, S.name as schema_Name
   FROM cte
   JOIN sys.tables AS t ON EXISTS
     (SELECT NULL FROM sys.foreign_keys AS fk
      WHERE fk.parent_object_id = t.object_id
        AND fk.referenced_object_id = cte.object_id )
   JOIN sys.schemas as S on t.schema_id = S.schema_id
   AND t.object_id <> cte.object_id
   AND cte.lvl < 30
   WHERE t.type_desc = 'USER_TABLE'
     AND t.is_ms_shipped = 0 )
SELECT schema_Name, name, MAX (lvl) AS dependency_level
FROM cte
GROUP BY schema_Name, name
ORDER BY dependency_level,schema_Name, name;

Peaceful

Answer 4

The Oracle version of the script:

with 
    foreign_keys as (
        select
          src_cc.owner as src_owner,
          src_cc.table_name as src_table,
          src_cc.column_name as src_column,
          dest_cc.owner as dest_owner,
          dest_cc.table_name as dest_table,
          dest_cc.column_name as dest_column,
          c.constraint_name
        from
          all_constraints c
        inner join all_cons_columns dest_cc on
          c.r_constraint_name = dest_cc.constraint_name
          and c.r_owner = dest_cc.owner
        inner join all_cons_columns src_cc on
          c.constraint_name = src_cc.constraint_name
          and c.owner = src_cc.owner
        where
          c.constraint_type = 'R'
          and dest_cc.owner = :owner),
    cte (lvl,table_name) as (
        select 1, table_name
        from all_tables
        where 
            owner = :owner
        union all
        select cte.lvl + 1, t.table_name
        from cte
        join all_tables t on exists (
            select null 
            from foreign_keys fk 
            where 
                fk.src_table = t.table_name
                and fk.dest_table = cte.table_name
        )
        and t.table_name <> cte.table_name
            AND cte.lvl < 30
    )
select table_name, max (lvl)   as dependency_level
from        cte
group by    table_name
order by    dependency_level desc, table_name
;

Ghyll

Answer 5

I needed to do this myself and was hoping someone had already done it for Postgres, but didn't find anything, so I'll just leave this here:

WITH RECURSIVE t AS (
    SELECT relnamespace as nsp, oid as tbl, null::regclass as source, 1 as level
    FROM pg_class
    WHERE relkind = 'r'
        AND relnamespace not in ('pg_catalog'::regnamespace, 'information_schema'::regnamespace)
UNION ALL
    SELECT c.connamespace as nsp, c.conrelid as tbl, c.confrelid as source, p.level + 1
    FROM pg_constraint c
    INNER JOIN t p ON (c.confrelid = p.tbl AND c.connamespace = p.nsp)
    WHERE c.contype = 'f'
        AND c.connamespace not in ('pg_catalog'::regnamespace, 'information_schema'::regnamespace)
)
SELECT nsp::regnamespace, tbl::regclass
FROM t
GROUP BY nsp, tbl
ORDER BY max(level) DESC;

This is a bit of a hybrid query between two use cases. You may remove the GROUP BY and SELECT source::regclass instead, if you need to see to which table the foreign key refers.

Juxon