Posts Tagged: graph

Jan 14

Cyclical dependency detection in the database

We recently had a need to find cyclical dependencies in our database. This happens to be a rather straightforward graph algorithm issue. The database foreign key constraints form a directed graph. Finding a cycle in a directed graph is mostly detecting an already visited node in a DFS algorithm (back-edge). We mark nodes as visited and if the ancestor of a node in the tree is already visited, then a back-edge (cycle) exists.

In order to do this on our own, we’d have to read the metadata from the database for each table, construct a directed graph using the foreign keys and then run the algorithm discussed above, rather straightforward. Most of the complexity comes from the cross cutting concerns of database metadata munging. We can easily accomplish all of the above using sqlalchemy and its ability to perform a topological sort on the reflected tables. Topological sort fails in there is a cycle detected and the exception thrown includes the nodes that produce the back-edge. Using this simple trick, we allow sqlalchemy to detect the cycles for us.

You’ll need to install sqlalchemy (and your db driver), networkx and graphviz (for visualization).