🚀 go-pugleaf

Here is another embarrasingly simple problem. I'm fairly clear that there
is a simple solution... but I don't know what it is.

I am writing code to interface prolog (as it happens, Quintus) to an
external database running on a remote machine. When making a query on the
remote database, it is essential to form the best joins, because joining
the database is computationally expensive. 

The geography of the database can be seen as a messy graph. Each table can
be joined to at least one other, and this possibility, together with the
fields that make it possible, is represented in prolog by the symmetrical
relation:

	canJoin( [ Table1, Key1], [ Table2, Key2]).

Furthermore, we can be sure that there is at least one possible path from
any table to any other. However, joins may have to connect an arbitrary
number of tables. The rules for this are:

*	A continuous join path must be found which visits every table
	in the list;
*	The path must not cycle;
*	The path may branch.

In other words, the smallest possible tree must be formed such that it
visits all the nodes on the target list.

What I want is a predicate of the form:

	findBestJoins( +TableSet, -JoinSet).

where TableSet is a set of tables to be joined, and JoinSet is a list of
join specifications (ideally in the form [ [ Table1, Key1], [ Table2, Key2]])
which describe the tree.

After looking at this ugly monster for a while, I have come up with an
English description of a procedural algorithm to tackle it, and this I
intend to code over the next few days. But that misses the point. Prolog
is supposed to be a declarative language, and this problem can easily be
described in declarative terms [look, I've done it up there :-)]. But I
can't for the life of me work out how to write it, declaratively, in
prolog. Can you?

T'anx

** Simon Brooke *********************************************************
*  e-mail : simon@uk.ac.lancs.comp                                      *
*  surface: Dept of Computing, University of Lancaster,  LA 1 4 YW, UK. *
*  PS 2   : Yesterday's technology, today. OS 2 : Yesterday's software, *
*********** real soon now. **********************************************