simon@comp.lancs.ac.uk (Simon Brooke) (03/25/88)
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. **********************************************
ok@quintus.UUCP (Richard A. O'Keefe) (03/26/88)
In article <489@dcl-csvax.comp.lancs.ac.uk>,
simon@comp.lancs.ac.uk (Simon Brooke) writes about finding "best joins".
Isn't the matrix chain problem a special case of this?