Background to avoid the X-Y problem: I'm building a database migration system that needs to resolve foreign key constraints (see here for full background). I need to determine what order I can execute create table/modify table operations so as to not violate any foreign key constraints. A topological sort is a natural starting place, except that a database can have circular constraints that a typical topological sorting algorithm can't handle.
There are some questions along those lines already here, and the most common suggestion I see here is to simply remove foreign key constraints and add them separately afterwards. That is not the solution I'm looking for, because doing so results in twice as many table alteration operations, which is especially important to avoid for large tables. As much as possible I would like to minimize the total number of CREATE/ALTER commands needed to migrate the database, which requires being smart about it.
Obviously though, in the case of circular foreign key constraints, the only option is to add the foreign keys separately. As a result the general approach I'm looking for is a two part approach: identify circular constraints and "break" them by flagging the foreign key constraints to be added afterward, perform a standard topological sort on the remaining operations, update the database in topological order, and finally apply any outstanding constraints that were reserved for later. I've found plenty of examples of topological sort algorithms, and references to algorithms that can help identify edges to be "broken" to enable a standard topological sort algorithm, but no actual algorithms for the latter.
Any direction would be appreciated, both for my specific problem and the general problem.
1 Month later: Update
A few weeks in, and I've learned that I do indeed need to solve this problem. I went with the general suggestion of just migrating with the foreign key checks off, especially given suggestions that it will improve overall performance. We've now been using this internally for a few weeks.
Unfortunately, it isn't a bullet-proof solution. It turns out that there are edge cases where MySQL will throw a 1215 error even with foreign key checks off. I've always had a plan to add in a MySQL linter on the table definitions, and that will prevent this edge case from being encountered. They primarily happen as a result of adjusting the structure to fix items that were caused by developers not being careful enough when initially creating the tables. Regardless, I now know that there are cases where order matters even when transaction checks are off. While we are implementing institutional fixes on our end to avoid those cases, I want this to be a general purpose tool for others. Others may run into these same edge cases, which means I need to implement a proper topological sorting, and I can't do that without identifying and breaking cycles. To be clear, in this case breaking cycles means simply flagging foreign key constraints to be added after everything else. It doesn't have to be smart. It just has to identify when the addition of an
add foreign key operation to the migration plan will result in a cycle, and defer that add operation until after everything else.