What data structure should I use to track dependency?

Question

I have a bunch of tables in a relational database which, obviously, are dependent upon one another due to foreign key relationships. I want to build a dependency tree, traverse it, and output INSERT SQL statements. I need to first output SQL for foreign key tables in my dependency tree first because parent tables will depend on values from their foreign key identifier tables.

Does a binary tree, traversed in postorder, seem suitable for this task?

Answer 1

If a table can be dependent on more than two tables, a binary tree will be insufficient. Let table A be dependent on tables B, C and D. Then you would have to insert into B, C and D first, i.e. A should have three child nodes in your tree.

I think you need to use a more general tree structure which allows an arbitrary number of child nodes. Traversing this tree structure in post-order should yield the desired results, as you suggested.

Things will start to get messy when your dependency graph contains cycles and you need to defer constraint checking ;)

Answer 2

Take a look at the following:

Microsoft.SqlServer.Management.Smo.Server
Microsoft.SqlServer.Management.Smo.Database
Microsoft.SqlServer.Management.Smo.Scripter

Microsoft.SqlServer.Management.Smo.DependencyTree
Microsoft.SqlServer.Management.Smo.DependencyWalker
Microsoft.SqlServer.Management.Smo.DependencyCollection
Microsoft.SqlServer.Management.Smo.DependencyCollectionNode

There's examples on MSDN on how to use all this.

Essentially you want something like

Server server = new Server(SOURCESERVER);
Database database = server.Databases[SOURCEDATABASE];
Scripter sp = new Scripter(server);

...

UrnCollection col = new UrnCollection();

foreach (Table table in database.Tables)
{
    col.Add(table.Urn);
}

....

DependencyTree tree = sp.DiscoverDependencies(col, DependencyType.Parents);
DependencyWalker walker = new DependencyWalker(server);
DependencyCollection depends = walker.WalkDependencies(tree);

//Iterate over each table in DB in dependent order...
foreach (DependencyCollectionNode dcn in depends)

...