Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!star.cs.vu.nl!bagron
From: bagron@cs.vu.nl (Rene Baart)
Newsgroups: comp.databases
Subject: Re: RE:Automatic Query Generation
Keywords: Join, automatic generation, relational theory
Message-ID: <5709@star.cs.vu.nl>
Date: 28 Feb 90 18:35:16 GMT
References: <5668@star.cs.vu.nl> <774@dgis.dtic.dla.mil> <CIMSHOP!DAVIDM.90Feb27104331@uunet.UU.NET>
Sender: news@cs.vu.nl
Organization: Fac. Wiskunde & Informatica, VU, Amsterdam
Lines: 41

In article <CIMSHOP!DAVIDM.90Feb27104331@uunet.UU.NET> cimshop!davidm@uunet.UU.NET (David S. Masterson) writes:
>In article <774@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes:
[ some stuff from my original posting deleted..]
>
>Wait a second, now.  With a knowledge of the foreign key relationships between
>tables (his "arrows"), he has all the information he needs to get an answer.
>Its basically a variation on the traveling salesman problem: given a couple of
>points on a graph find all the routes between those points.  I was never any
>good at solving that problem, so I can't provide the algorithm for the
>original question, but all the information is there.  After all, he isn't
>asking for a single query to do this, but the general algorithm!
>

The join problem indeed seems similar to that Traveling Salesman problem,
but the big difference is that in solving the salesman problem you're
trying to find the cheapest or shortest path. With the joins, a shorter
path isn't neccesarily a better one. (Or the one the user intended.)

But then again, you couldn't present a user with ALL possible paths 
for a given query since that set of solutions will definitely explode
as the database gets more complex.

The "solution" (note the quotes) I came up with after looking at a lot
of output from a little program that prints all the possible paths
between any two nodes is that paths with the least number of relations
are more desireable. I define a relation in this context as a node that
has two arrows pointing inwards, like this: EMPL.--> POSITION <-- DEPT.

In my current implementation, I let the user choose between all paths
that have a minimum number of relations. This SEEMS to work well in 
practice. (It sure cuts down the number of paths)

But I don't have too much confidence in this emperical solution, hence
the reason for my posting. But by now I'm pretty convinced that the
problem cannot be solved without introducing extra semantics (like
a data dictionary). I'll have to look into that. 

+--------------+  Domain : bagron@cs.vu.nl, RBAART@neabbs.UUCP
|     Rene     |  Snail  : Wibautlaan 32, 1181 XW Amstelveen, The Netherlands
|     Baart    |  UUCP   : ..!mcvax!neabbs!rbaart, ..!mcvax!botter!bagron
+--------------+  Fido   : RENE BAART at 2:280/2    Voice  : (020)-454191