SQLServer: How to sort table names ordered by their foreign key dependency

Question

The following SQL separates tables according to their relationship. The problem is with the tables that sort under the 3000 series. Tables that are part of foreign keys and that use foreign keys. Anyone got some clever recursive CTE preferably or a stored procedure to do the necessary sorting?? Programs connectiong to the database are not considered a solution.

Edit: I posted the answer in the "answers" based on the first solution Free "right answer" to be had for anyone reposting my own "right" answer!

WITH 
 AllTables(TableName) AS
 (
 SELECT OBJECT_SCHEMA_NAME(so.id) +'.'+ OBJECT_NAME(so.id) 
 FROM dbo.sysobjects so 
 INNER JOIN sys.all_columns ac ON 
  so.ID = ac.object_id
 WHERE
  so.type = 'U'
 AND
  ac.is_rowguidcol = 1
 ),

  Relationships(ReferenceTableName, ReferenceColumnName, TableName, ColumnName)  AS
  (
  SELECT  
    OBJECT_SCHEMA_NAME (fkey.referenced_object_id) + '.' +  
    OBJECT_NAME (fkey.referenced_object_id) AS ReferenceTableName 
    ,COL_NAME(fcol.referenced_object_id, 
              fcol.referenced_column_id) AS ReferenceColumnName 
    ,OBJECT_SCHEMA_NAME (fkey.parent_object_id) + '.' +  
    OBJECT_NAME(fkey.parent_object_id) AS TableName 
    ,COL_NAME(fcol.parent_object_id, fcol.parent_column_id) AS ColumnName 
  FROM sys.foreign_keys AS fkey 
    INNER JOIN sys.foreign_key_columns AS fcol ON 
               fkey.OBJECT_ID = fcol.constraint_object_id 
  ),

 NotReferencedOrReferencing(TableName) AS
 (
 SELECT TableName FROM AllTables
 EXCEPT
 SELECT TableName FROM Relationships
 EXCEPT
 SELECT ReferenceTableName FROM Relationships
 ),

 OnlyReferenced(Tablename) AS
 (
 SELECT ReferenceTableName FROM Relationships
 EXCEPT
 SELECT TableName FROM Relationships
 ),
-- These need to be sorted based on theire internal relationships
 ReferencedAndReferencing(TableName, ReferenceTableName) AS
 (
 SELECT r1.Tablename, r2.ReferenceTableName FROM Relationships r1 
 INNER JOIN Relationships r2
 ON r1.TableName = r2.ReferenceTableName   
 ),

 OnlyReferencing(TableName) AS
 (
 SELECT Tablename FROM Relationships
 EXCEPT
 SELECT ReferenceTablename FROM Relationships
 )
SELECT TableName, 1000 AS Sorting FROM NotReferencedOrReferencing
UNION
SELECT TableName, 2000 AS Sorting FROM OnlyReferenced 
UNION
SELECT TableName, 3000 AS Sorting FROM ReferencedAndReferencing
UNION
SELECT TableName, 4000 AS Sorting FROM OnlyReferencing
ORDER BY Sorting

Answer 1

This causes problems with self-referencing tables. You'll need to manually exclude any foreign keys that point to self referencing tables.

INNER JOIN sys.foreign_keys  f 
  ON (f.parent_object_id = so.id AND f.parent_object_id != f.referenced_object_id)

  /* Manually exclude self-referencing tables - they cause recursion problems*/      
    and f.object_id  not in /*Below are IDs of foreign keys*/
        ( 1847729685,   
        1863729742,     
        1879729799      
        )   
INNER JOIN TablesCTE tt

Answer 2

My rendition with moderate tweaks: This one is SQL-2005+ and works on databases without the "rowguidcol":

WITH TablesCTE(SchemaName, TableName, TableID, Ordinal) AS
(
    SELECT
        OBJECT_SCHEMA_NAME(so.object_id) AS SchemaName,
        OBJECT_NAME(so.object_id) AS TableName,
        so.object_id AS TableID,
        0 AS Ordinal
    FROM
        sys.objects AS so
    WHERE
        so.type = 'U'
        AND so.is_ms_Shipped = 0
    UNION ALL
    SELECT
        OBJECT_SCHEMA_NAME(so.object_id) AS SchemaName,
        OBJECT_NAME(so.object_id) AS TableName,
        so.object_id AS TableID,
        tt.Ordinal + 1 AS Ordinal
    FROM
        sys.objects AS so
    INNER JOIN sys.foreign_keys AS f
        ON f.parent_object_id = so.object_id
        AND f.parent_object_id != f.referenced_object_id
    INNER JOIN TablesCTE AS tt
        ON f.referenced_object_id = tt.TableID
    WHERE
        so.type = 'U'
        AND so.is_ms_Shipped = 0
)

SELECT DISTINCT
        t.Ordinal,
        t.SchemaName,
        t.TableName,
        t.TableID
    FROM
        TablesCTE AS t
    INNER JOIN
        (
            SELECT
                itt.SchemaName as SchemaName,
                itt.TableName as TableName,
                itt.TableID as TableID,
                Max(itt.Ordinal) as Ordinal
            FROM
                TablesCTE AS itt
            GROUP BY
                itt.SchemaName,
                itt.TableName,
                itt.TableID
        ) AS tt
        ON t.TableID = tt.TableID
        AND t.Ordinal = tt.Ordinal
ORDER BY
    t.Ordinal,
    t.TableName

Answer 3

Thank you for a working solution NXC. You put me on the right track to solve the problem using a recursive CTE.

WITH 
  TablesCTE(TableName, TableID, Ordinal) AS
  (
  SELECT 
    OBJECT_SCHEMA_NAME(so.id) +'.'+ OBJECT_NAME(so.id) AS TableName,
    so.id AS TableID,
    0 AS Ordinal
  FROM dbo.sysobjects so INNER JOIN sys.all_columns ac ON so.ID = ac.object_id
  WHERE
    so.type = 'U'
  AND
    ac.is_rowguidcol = 1
  UNION ALL
  SELECT 
    OBJECT_SCHEMA_NAME(so.id) +'.'+ OBJECT_NAME(so.id) AS TableName,
    so.id AS TableID,
    tt.Ordinal + 1 AS Ordinal
  FROM 
    dbo.sysobjects so 
    INNER JOIN sys.all_columns ac ON so.ID = ac.object_id
    INNER JOIN sys.foreign_keys f 
      ON (f.parent_object_id = so.id AND f.parent_object_id != f.referenced_object_id)
    INNER JOIN TablesCTE tt ON f.referenced_object_id = tt.TableID
  WHERE
    so.type = 'U'
  AND
    ac.is_rowguidcol = 1
)  
SELECT DISTINCT 
  t.Ordinal,
  t.TableName
  FROM TablesCTE t
  INNER JOIN 
    (
    SELECT 
      TableName as TableName,
      Max (Ordinal) as Ordinal
    FROM TablesCTE
    GROUP BY TableName
    ) tt ON (t.TableName = tt.TableName  AND t.Ordinal = tt.Ordinal)
ORDER BY t.Ordinal, t.TableName

For thoose wondering what this is useable for: I will use it to safely empty a database without violating any foreign key relations. (By truncating in descending order) I will also be able to safely fill the tables with data from another database by filling the tables in ascending order.

Answer 4

You can use an iterative algorithm, which is probably less convoluted than a CTE. Here's an example that sorts according to depth:

declare @level int      -- Current depth
       ,@count int      

-- Step 1: Start with tables that have no FK dependencies
--  
if object_id ('tempdb..#Tables') is not null
    drop table #Tables

select s.name + '.' + t.name  as TableName
      ,t.object_id            as TableID
      ,0                      as Ordinal
  into #Tables
  from sys.tables t
  join sys.schemas s
    on t.schema_id = s.schema_id
 where not exists
       (select 1
          from sys.foreign_keys f
         where f.parent_object_id = t.object_id)

set @count = @@rowcount         
set @level = 0


-- Step 2: For a given depth this finds tables joined to 
-- tables at this given depth.  A table can live at multiple 
-- depths if it has more than one join path into it, so we 
-- filter these out in step 3 at the end.
--
while @count > 0 begin

    insert #Tables (
           TableName
          ,TableID
          ,Ordinal
    ) 
    select s.name + '.' + t.name  as TableName
          ,t.object_id            as TableID
          ,@level + 1             as Ordinal
      from sys.tables t
      join sys.schemas s
        on s.schema_id = t.schema_id
     where exists
           (select 1
              from sys.foreign_keys f
              join #Tables tt
                on f.referenced_object_id = tt.TableID
               and tt.Ordinal = @level
               and f.parent_object_id = t.object_id
               and f.parent_object_id != f.referenced_object_id)
                   -- The last line ignores self-joins.  You'll
                   -- need to deal with these separately

   set @count = @@rowcount
   set @level = @level + 1
end

-- Step 3: This filters out the maximum depth an object occurs at
-- and displays the deepest first.
--
select t.Ordinal
      ,t.TableID
      ,t.TableName
  from #Tables t
  join (select TableName     as TableName
              ,Max (Ordinal) as Ordinal
          from #Tables
         group by TableName) tt
    on t.TableName = tt.TableName
   and t.Ordinal = tt.Ordinal
 order by t.Ordinal desc