Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!mcsun!hp4nl!star.cs.vu.nl!bagron
From: bagron@cs.vu.nl (Rene Baart)
Newsgroups: comp.databases
Subject: Automatic Query Generation
Keywords: Query, automatic, SQL, join
Message-ID: <5668@star.cs.vu.nl>
Date: 24 Feb 90 11:03:23 GMT
Sender: news@cs.vu.nl
Lines: 43


I am faced with an intruiging yet difficult problem. I'm working on
a user-friendly front-end to a relational database that's supposed
to isolate the user from the underlying data model of the database.

The user should be able to just list the attributes he or she wants
in a report (such as EMPLOYEE_NAME and SALARY) and have the system
generate the appropriate SQL query. Since the listed attributes may
be in different relations, the system has to figure out how to join
the involved tables. This is where things get difficult.

The information available to the program is the set of tables in the
database (T1..Tn), the set of tables from which attributes are being
queried (Q1..Qm, with m<n) and a list of "arrows" which indicate
that a certain table has a foreign key in another table (Tx-->Ty).

Graphically, the problem can be represented like this:

                                      +-------  SALARY
                                      |
                                      v
    CHILD  <---  EMPLOYEE  --->  POSITION  <--  TITLE
                                      ^
                                      |
                                      +-------  DEPARTMENT

I am in need of a general algorithm for finding the set of tables that
is needed to perform the join. What's more, if there is more than one
possible join, the system should provide a list of alternatives for the
user to choose from. So far, I haven't been able to come up with a
solution that handles every possible situation correctly, and I'm
starting to wonder if there exist one at all.

So, if there's anyone out there in NetLand who has thought about this
problem before and who knows of a solution, I'd love to hear about it.
Or if anyone could point me towards some books or articles dealing with
this kind of problem, I'd be grateful too. (I suppose every existing
natural-language front-end faces a similar task?) Thanks in advance!

+--------------+  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