Is it ok to have cyclic foreign key dependencies in a relational database?

Question

I'm writing a code to backup a MySQL database into a binary file. I'm aware of mysqldump but for some reasons I can't use trivial methods. What I'm currently doing:

read schema definition
sort tables by foreign key dependencies
select rows in all tables (100 rows each time) and write them in a binary file

Definition of Dependency: A table T1 depends on existence of table T2 if and only if at least there is one foreign key in T1 pointing to T2's key.

A numeric value is assigned to each table. This value specifies order of tables. For tables with no dependency, this value is 0 for others it's maximum value of tables that current table depends on them; plus one. If there is a -1 in the set of values of depended tables, value of current table remains undefined (-1). Initially value of all tables is -1 which means unspecified.

This is C++ code:

// tablesQueue: Queue of all tables
// orderedQueue: Resulting order

while(! tablesQueue.isEmpty())
{
    bool satisfied = true;
    foreach(TableNode* parent, tablesQueue.head()->referencedTables)
    {
        if(parent->degreeOfFreedom == -1)
        {
            satisfied = false;
            break;
        }
        else
           // handle error blah blah ... 
    }
    if(satisfied)
    {
        int max =0;
        foreach(TableNode* parent, tablesQueue.head()->referencedTables)
        max = (max < parent->degreeOfFreedom+1) ? 
                  parent->degreeOfFreedom+1 : max;
        tablesQueue.head()->degreeOfFreedom = max;
        orderedQueue.enqueue(tablesQueue.dequeue());
    }
    else
    {
        tablesQueue.enqueue(tablesQueue.dequeue());
    }
}

If there is a cycle in dependency graph of tables, this algorithm does not terminate.

Normally is this OK to have such a design for tables? For example two tables having foreign key to each other. Surprisingly I found that example databases provided by Oracle for MySQL (sakila) have a lot of such cycles. I'm supposing that it's possible to remove all that cycles by adding a third table [?]

I don't see a problem with cyclic foreign key dependencies as long as there is at least one link in the cycle that is allowed to be null (i.e. _not_ declared `NOT NULL`). — Ian Roberts, Feb 09 '13 at 20:39
@IanRoberts Problem occurs when you try to write all data into a file and restore it again. Suppose that you're reading data from you'r backup file for table `A` at row `n`. It's depended on existence of corresponding row in `B`; say row number `m`. You need to have wrote `m`th row of `B` before `n`th row of `A`. But in the case that `m-i`th row of `B` have a key pointing to `n+j`th key of `A` you have no valid order of tables to restore your database. — sorush-r, Feb 09 '13 at 20:49

score 8 · Accepted Answer · edited May 23 '17 at 12:01

8

Circular dependencies are fairly common. Some examples:

A table references itself when implementing the "adjacency list" hierarchy.
Two tables reference each other when implementing the 1:1^* relationship.
Two tables referencing each other is one of the possible implementations for the 1:N relationship (where one of the rows on the "N" side is "special").
Furthermore, I've seen situations with multiple tables forming a "ring"...

So yes, it is "OK" to to have circular dependencies.

^* Strictly, a true 1:1 requires deferred constraints to solve the chicken-and-egg problem (which are not supported in MySQL), otherwise you can only have 1:0..1 or 0..1:0..1. But in all these cases, you have two tables referencing each other.

edited May 23 '17 at 12:01

Community

1
1

answered Feb 09 '13 at 22:42

Branko Dimitrijevic

50,809
10
93
167

1

In this situation, backup and restore wont work. I'm going to disable foreign key checks before restore and enable it again. (two queries with `SET FOREIGN_KEY_CHECKS = 0;` and `SET FOREIGN_KEY_CHECKS = 1;`) – sorush-r Feb 10 '13 at 08:25
1

EXEC sp_msforeachtable "ALTER TABLE ? NOCHECK CONSTRAINT all" – Lzh May 05 '14 at 15:25
http://stackoverflow.com/questions/159038/can-foreign-key-constraints-be-temporarily-disabled-using-t-sql – Lzh May 05 '14 at 15:27
...AND disabling checks doesn't work to gen scripts. – Lzh May 05 '14 at 15:28

Is it ok to have cyclic foreign key dependencies in a relational database?

1 Answers1