Click here to Skip to main content
Click here to Skip to main content

Sort Database Tables By Foreign Keys

, 10 Sep 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
How to sort tables so data can be retrieved for offline sychronization and not violate foreign key relationships.

Background

I’ve been looking into the new Microsoft Synchronization Framework, specifically, providers for databases.

Visual Studio 2008 has a new project item type, “Local Database Cache”, not to be confused with “Local Database” which is for the SQL Server Compact edition database synchronization. The compact database doesn’t allow foreign key relationships; therefore, it doesn’t suit my needs. While Microsoft is working on a designer for an Express edition, I plug on.

The data that is retrieved from the master table needs to be retrieved in an order that doesn’t violate foreign key constraints. The understanding is that we are working down the happy path of software development. The Synchronization Framework will handle the cases where there are errors due to other issues that don’t involve the order of the data retrieved.

The purpose of this article is to provide a way of sorting database tables based on the foreign key relationships that exist within the database.

Sorting Algorithm

The following is part of the AdventureWorks sample database from Microsoft. The diagram shows the basic fields and the foreign key relationships between some of the tables.

pic_1.jpg

After four attempts at trying to sort tables, I came up with an algorithm that I believe works well. It is based on the principle that each table falls into one of the following categories:

  1. None – The table is not reference by another table and it does not reference another table.
  2. Referenced By – The table is referenced by another table.
  3. Both – The table is referenced by tables and references other tables.
  4. References – The table only references other tables.

The following diagram shows a picture of the database tables above, using a class notation of the tables organized into the four classifications:

pic_2.jpg

Within each category, the tables are ordered by name as they don’t have a relationship with any other table within the category; the exception being category 3 (Both). Category 3 needs to be further sorted by which table references other tables.

The following fictitious database picture represents the final sorted order (D, B, E, C) of the tables within category 3. If you look at the arrows of the class, you will notice that all the arrows are flowing from right to left. This is the flow that we are looking for when performing the sort.

pic_3.jpg

Given the AdventureWorks database table and the class diagrams shown above, the tables should be sorted into the following order:

  1. dbo.ErrorLog
  2. Sales.SalesTerritory
  3. HumanResources.Employee
  4. Sales.SalesPerson
  5. Sales.SalesOrderHeader
  6. Sales.Store
  7. Sales.SalesPersonQuotaHistory
  8. Sales.SalesTerritoryHistory

Using the Code

The project is broken into the following files:

  1. Program.cs – Main driver and prints the results of the sort.
  2. TableInfo.cs – Retrieves database information, creates the table relationships, and performs the sort.
  3. TableInfoComparer.cs – Comparison algorithm.

The table information is retrieved from SQL Server using the following two SQL scripts:

Retrieve the fully qualified table names in the current database:

SELECT TABLE_SCHEMA + '.' + TABLE_NAME AS TableName
FROM INFORMATION_SCHEMA.Tables
WHERE TABLE_TYPE='BASE TABLE'
ORDER BY TableName

Retrieve the relationship between tables:

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 
ORDER BY ReferenceTableName, ReferenceColumnName, TableName, ColumnName

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Dave Elliott
Software Developer (Senior) Webbert Solutions
United States United States
Dave is an independent consultant working in a variety of industries utilizing Microsoft .NET technologies.

Comments and Discussions

 
QuestionCircular References PinmemberEvilpaule23-Oct-12 21:34 
AnswerRe: Circular References PinmemberDave Elliott24-Oct-12 1:02 
GeneralRe: Circular References PinmemberEvilpaule24-Oct-12 3:34 
GeneralMy vote of 5 PinmvpKanasz Robert26-Sep-12 7:35 
GeneralThanks for the article! PinmemberMember 87843443-Apr-12 8:29 
GeneralGood starting point Pinmembervgo19-Apr-09 7:27 
GeneralAlgorithm Pinmemberlos.15-Dec-08 8:15 
GeneralRe: Algorithm PinmemberDave Elliott9-Apr-09 16:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.141022.1 | Last Updated 10 Sep 2008
Article Copyright 2008 by Dave Elliott
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid