# Can relational database tables always be topologically sorted by their FK reference relation?

Suppose I have some conceptual, not physical, E-R diagram describing a relational database. I want to sort all the tables in the database using a topological sort, where the partial ordering between tables is Table 1 has a foreign key onto Table 2.

When clearing out tables after putting test data in them, I would need to delete Table 1 above first, then Table 2, in order to not violate FK references. A topological sort on the FK relation gives me an ordering to clear the tables in.

It is possible to have a table with an FK to itself, providing a simple counter example where there is a cycle, and subsequently no topological sort. However, this self relationship could also be represented using a join table, which lists 2 rows of the table, where one refers to the other, and in this case there would be a topological sort.

By replacing direct FK references between tables with join tables, is it always possible to arrive at a structure that can be topologically sorted?

• What is the topological sort being used for? A scheduling problem? Also, I'm unclear what you mean by "topologically sorted by their FK relation." Are you sorting rows, or the tables themselves? How many tables are we talking about? Apr 23, 2015 at 15:56
• To order the database tables correctly, in order to remove tests data from them without violating FK referential integrity. An alternative might be to keep a stack as test data is inserted, the pop the stack till empty to remove it in exact reverse order. I'm just curious about the top-sort option. Apr 23, 2015 at 15:58
• PK ==> FK relations only go in one direction. You could always walk the tables through the relations until you get to the last one, and then delete them in reverse order. But yeah, it's probably simpler to just maintain a table containing the order. Apr 23, 2015 at 15:59
• I am talking about sorting the tables themselves. As I say, if a table holds a foreign key to another table, then those tables are in the 'partial ordering' that is going to be topologically sorted to arrive at a total ordering. Maybe 50 tables, perhaps many more. Apr 23, 2015 at 16:00
• Yeah, I knew what you meant. Apr 23, 2015 at 16:01

It seems to be me that you can trivially get rid of the cycles by moving all foreign keys to join tables.

Once you've move all foreign keys to join tables, none of the original tables have dependencies on anything. The join tables have dependencies on the original tables. Nothing has dependencies on the join tables. In consequence, you have a trivial topological sort: first the join, then the original tables.

Under no circumstances should you actually contemplate doing this. You are massively complicating your data model without much benefit.

When clearing out tables after putting test data in them, I would need to delete Table 1 above first, then Table 2, in order to not violate FK references. A topological sort on the FK relation gives me an ordering to clear the tables in.

If you really need to clear out test data like this, you can do the following:

1. Set all foreign keys to NULL
2. Delete everything

But you should consider some other alternatives:

1. Can you do everything inside a transaction that simply lets your rollback when you are done?
2. Can you create and populate a temporary database that you can simply throw away when the test is done?

Well, if I understood correctly, if there is a cycle somewhere along the path then you can't have a topological sort. Even if you solve the cycle problem in the case of a FK from table A to itself (I didn't understand what you meant exactly with the term "join table" though, but it's certainly because of my lack of experience with databases) you could always have a cycle among N tables.

In the last case you should consider the resources necessary to solve that particular case (assuming you go with the "join table" approach). You could do a topological sort of a subset of tables though where you don't have cycles.

• A join table is one that holds 2 FKs onto other tables. So if you have a one-to-many relationship, on the 'one' side you can put the FK directly in that table. If you have a many-to-many, you need a third table to list all the links, and that is called a 'join table'. You can use join tables for one-to-one, one-to-many and many-to-many, but they are only required for many-to-many. Apr 24, 2015 at 8:31
• Oh, OK. Didn't know it was called like that. Thanks. I understand now how it can be used in the case of a table referencing itself. What about the case where a cycle among N tables is present, how would you deal with it? Apr 24, 2015 at 8:46