#!/usr/bin/perl -w

use strict;

my @links = map { [/^(\w+)\s+(\w+)\s+(\w+)\s+(\w+)/] } split /\n/, <<LINKS;
apple bug unid1 unid2
apple cat unid1 unid3
bug dog unid2 unid4
apple dog unid1 unid4
dog owl unid4 unid5
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 dont go 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];
            for my $i ( 0 .. $#results ) {
                for my $ii ( 0 .. $#{$results[$i]} ) {
                    if ( $ii == 0 ) {
                        print "$results[$i][$ii]\n";
                    } else {
                        my $keys;
                        for ( @links ) {
                            my ( $left, $right, $lid, $rid  ) = @$_;
                            if ( $left eq $results[$i][$ii - 1] && $right eq $results[$i][$ii] ) {
                                $keys = "on $lid = $rid";
                            }
                        }
                        print "inner join $results[$i][$ii] $keys\n";
                    }
                }
                print "\n";
            }
        } 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;

}
find_joins( 'apple' => 'owl' );

##</code><code>##

apple
inner join bug on unid1 = unid2
inner join dog on unid2 = unid4
inner join owl on unid4 = unid5

apple
inner join dog on unid1 = unid4
inner join owl on unid4 = unid5