- Python code
- A CTE
- An execsql script.
All of these methods take, as input, a table of dependencies in which each row contains a pair of table names corresponding to a parent:child relationship. The Python code produces a Python list containing tables listed in dependency order, and the other two methods produce a table consisting of one column containing table names and another column containing integers that specify the dependency order. The first items in these lists are the tables that have no parents, and the last items in these lists are the tables with the longest chain of dependencies.
Getting the Dependencies
When using a DBMS that supports INFORMATION_SCHEMA tables, the following SQL can be used to obtain a table containing all direct parent:child pairs
Additional constraints may be used, or needed, in the WHERE clause to limit the set of tables returned--for example, to eliminate system tables, or to select only the tables in a particular schema. If there are cyclic dependency relationships among tables, this SQL will not complete, and so in those cases at least one of the tables in the cycle of mutual dependencies should be omitted using an appropriate specification in the WHERE clause.
The table produced by this SQL will include only those tables that are part of some foreign key relationship. Standalone tables that are neither a parent nor a child will not be included. Standalone tables and tables that are omitted because of cyclic dependency relationships can be added to the output of the dependency-ordering step.
Ordering Tables by Dependency
Converting the set of parent:child dependencies into a list of tables in dependency order requires an iterative or recursive traversal of the tree of relationships that is rooted at the tables that have no parents. The table-ordering routines that follow use different approaches:
- A loop over a list of unprocessed dependencies in Python, where that list is modified within the loop.
- A recursive traversal of the tree using a CTE, terminating when the farthest leaves of the tree have been reached.
- Looping using end recursion in the execsql script to traverse the tree in a manner similar to the CTE.
The algorithm used in the Python code is distinct, whereas the algorithms used with the recursive CTE and the execsql script are very similar. (The algorithm used by the Python code can also be implemented using an execsql script, but the code is considerably longer than the implementation shown below.)
The input for the Python code to generate a dependency-ordered list of tables is a table of dependencies consisting of a list of two-element lists or tuples, each containing a child table name and a parent table name. This list might be generated by querying the database (e.g., using the SQL above) or from static configuration data. Given this table of dependencies, a Python list of all of the tables in dependency order can be generated with the following function
For DBMSs that support them, a recursive CTE can be used to convert a table of parent:child dependencies into a list of tables in dependency order. The input for the following code should be a table of such dependencies; that table should be named "dependencies". The output of the recursive CTE contains all parent tables, and the remaining tables (that are not parents to any other table) are added in the SELECT statement that uses the CTE.
For DBMSs that don't support recursive CTEs, and when use of a client language like Python is not desired, the metacommands provided by execsql allow recursive traversal of the tree of dependencies, as shown in the following code. Explanations of the metacommands used in this code can be found in the on-line documentation.
As with the CTE implementation, the input for the following code should be a table of parent:child dependencies that is named "dependencies".
The following code increments a counter to track and assign the successive levels of recursion during traversal from the root to the leaves of the dependency tree. Because automatically-generated sequences and variables are DBMS-specific extensions to SQL, for the sake of generality, this implementation uses execsql counter variables and substitution variables. Thus, but for minor differences in SQL syntax, the following code should run in any DBMS.