Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!cimshop!davidm From: cimshop!davidm@uunet.UU.NET (David S. Masterson) Newsgroups: comp.databases Subject: Re: Automatic Query Generation Message-ID: Date: 27 Feb 90 18:43:31 GMT References: <5668@star.cs.vu.nl> <774@dgis.dtic.dla.mil> Sender: davidm@cimshop.UUCP Organization: Consilium Inc., Mountain View, California. Lines: 50 In-reply-to: jkrueger@dgis.dtic.dla.mil's message of 26 Feb 90 23:31:07 GMT In article <774@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: bagron@cs.vu.nl (Rene Baart) writes: >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 mthat a certain table has a foreign key in another table (Tx-->Ty). > >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. > Table definitions are generated from database design, you're trying to "decompile" the other way. You lack master-detail information, referential integrities, domains, etc. You can make some good guesses but in general you can't be sure. 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! This is as much a measure of the power of the relational model to ask interesting questions as it is of the poverty of commercial products to express them. Consider how aggregates aren't handled in typical forms-based canned query tools, and when they are, how much the user must know about the underlying database design. Or consider questions answerable only by queries involving self-joins: how will this possibility be spotted by your tool? But don't feel bad, most third-party front ends don't try anything of the sort; in general, they're tabular, not relational. Why the diatribe?!? The key to answering this query is not the front-end, but the back-end. Many newer relational systems are keeping information in the data dictionary that help the system understand the data model (things like referential integrity constraints, domains, etc.). Since the data dictionary of a relational database is queriable like any other part of the relational database (at least with any relational system worth its salt), answering questions about the data model of the database, though not exactly trivial, should be doable. -- =================================================================== David Masterson Consilium, Inc. uunet!cimshop!davidm Mt. View, CA 94043 =================================================================== "If someone thinks they know what I said, then I didn't say it!"