Basically, you want to find the path connecting two tables. As the total number of tables is likely very finite (I suspect less than 4000, to pull a number out of my ass), and the number of joins likely also is very finite (let's say, each table links to two other tables, so roughly 8000 links) you can use brute force to enumerate all paths between two tables.

As you likely want to find a shortest connection according to some metric, you will have to enumerate them all and then select one of the shortest paths. There can be obviously more than one shortest path.

For generic and relatively efficient path finding, see the A_Star algorithm.

If you want to get ambitious, you can use AI::Prolog or just Prolog directly to let it tell you the links between two tables.

Of course, you can also program the search directly, but this is untested code I write off my cuff, so caveat emptor:

use strict;
use Data::Dumper;

my @links = map { [/^(\w+)\s+(\w+)/] } split /\n/, <<LINKS;
apple bug unid1 unid2 
apple cat unid1 unid3 
bug dog unid2 unid4 
apple dog unid1 unid4
LINKS

# All links work both ways:
my %links;
for (@links) {
    my ($left,$right) = @$_;
    # We store all links in arrays
    $links{$left} ||= [];
    $links{$right} ||= [];

    # Links work both ways
    push @{$links{$left}}, $right;
    push @{$links{$right}}, $left;
};

sub find_joins {
    my ($start, $goal, $prefix, $visited) = @_;

    $visited ||= {}; # our breadcrumb trail so we don't run around in 
+circles
    $prefix ||= [];  # the path so far
    my $curr = $start;

    warn "[@$prefix] $start => $goal";

    my @results; # All the paths that lead from $start to $end
    $visited->{$start} = 1;

    for my $link (grep { ! $visited->{$_} } @{$links{$start}}) {
        if ($link eq $goal) {
            push @results, [@$prefix,$start,$goal];
        } else {
            my %v = %$visited;
            push @results, find_joins($link,$goal,[@$prefix,$start],\%
+v);
        };
    };

    # Sort by length, then asciibetically
    @results = sort { scalar @$a <=> scalar @$b or $a->[0] cmp $b->[0]
+ } @results;

    return @results;
};

print Dumper find_joins( apple => 'bug' );
print Dumper find_joins( apple => 'dog' );
print Dumper find_joins( cat => 'dog' );

__END__
[] apple => bug at tmp.pl line 31.
[apple] cat => bug at tmp.pl line 31.
[apple] dog => bug at tmp.pl line 31.
$VAR1 = [
          'apple',
          'bug'
        ];
$VAR2 = [
          'apple',
          'dog',
          'bug'
        ];
[] apple => dog at tmp.pl line 31.
[apple] bug => dog at tmp.pl line 31.
[apple] cat => dog at tmp.pl line 31.
$VAR1 = [
          'apple',
          'dog'
        ];
$VAR2 = [
          'apple',
          'bug',
          'dog'
        ];
[] cat => dog at tmp.pl line 31.
[cat] apple => dog at tmp.pl line 31.
[cat apple] bug => dog at tmp.pl line 31.
$VAR1 = [
          'cat',
          'apple',
          'dog'
        ];
$VAR2 = [
          'cat',
          'apple',
          'bug',
          'dog'
        ];

[download]

An interesting invariant that you should maybe check in the code would be that the joins must be symmetric, that is, all paths which are found for getting from $x to $y need also be found when getting from $y to $x. I haven't checked that my brute force solution returns symmetric results.

Conversion of the output into SQL statements is left as an exercise.

In reply to Re: Advise on sql table mapping. by Corion
in thread Advise on sql table mapping. by dbmathis

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.