[schlenk] 2005-12-16 : Using real databases and loading a datamodel i often have to resolve the creation order of the tables, because the SQL tables reference themselves via Foreign keys. 
For direct database access with for example Pgtcl this isn't much of a problem, 
as one can deferr constraints like foreign keys in a transaction.

Basically this is a quite generic dependency resolver, based on the tcllib graph package, 
customized for the tcldb::table objects.

======
package require struct::graph 2

# Resolving reference dependecies for tcldb tables
#
# Create a dependency graph first, 
# then walk from leaves to the root
#

proc createGraph {tableObjs} {
    set g [::struct::graph ]

    foreach table $tableObjs {
        set tablename [$table cget -table]
        set fields [$table fieldlist 0 1 1]

        $g set $tablename $table
        if {![$g node exists $tablename]} {
            $g node insert $tablename
        }
        puts "Table: $tablename"
        foreach {field type param} $fields {
            puts "$field"
            puts "$type"
            puts $param 
            array unset finfo 
            set finfo(reference) ""
            $g node set $tablename $field [list $type $param]
            array set finfo $param
            if {$finfo(reference) eq ""} {continue}
            set reftable [lindex $finfo(reference) 0]
            if {![$g node exists $reftable]} {
                $g node insert $reftable
            } 
            $g arc insert $tablename $reftable
        }
    }
    return $g
}

proc filterIsolated {g n} {
    if {[llength [$g arcs -out $n]]} {
        return 0
    } else {
        return 1
    } 
}

proc findOrder {graph} {
    set g [::struct::graph tempGraph = $graph]

    set order [list]

    set old [llength [$g nodes]]
    while {[llength [$g nodes]]} {
        set isolated [$g nodes -filter [namespace current]::filterIsolated]
        if {[llength $isolated]} {
            foreach node $isolated {
                lappend order [list $node [$g set $node]]
                $g node delete $node
            }
        } else {
            break
        }
    }
    if {[llength [$g nodes]]} {
        return -code error "Could not resolve reference conflicts, objects left [$g nodes]"
    } 
    $g destroy
    return $order
}
======

To use it, put all your tcldb::table objects into a list, then call:

======
set g [createGraph $tablelist]
puts [findOrder $g]
======
 
This returns the creation order for your table as a list of lists, 
each sublist is a tablename tableobject pair.
----
''[escargo] 16 Dec 2005'' - In terms of dependencies, would determining the order via a 
[topological sort] work as well?  Can the dependency graph be relied upon to have no cycles?
----
''[schlenk] 16 Dec 2005'' - I think a topological sort would work as well. 
If the dependency graph for this use case (sql table relations) would have cycles, 
this would be a clear indication that some database normalization could be a good idea.

<<categories>> Database