I'm looking for a loose algorithm, not code but is there a way in a
query building scenario to determine if relationships in a SQL FROM
clause are in conflict without actually executing the SQL?



For example, 3 tables may be joined in a triangle and changing the
direction of one join may invalidate the other relationships. Many
commercial query builing interfaces seem to accomplish this (like MS SQL
Server) although I don't need all the extra functionality they provide
(like automatic conflict corrections etc...). Thx...


--
Posted via http://dbforums.com

"bill_dev" <member38341 (AT) dbforums (DOT) com> wrote

What do you mean by "changing the direction" ? Joins are symmetric.

I mean changing a left outer join into a right outer join... or I mean,
in the course of creating a query, the user adds a join of a type that
conflicts with the joins that are already configured.



E.g. Assuming a query exists like this....



SELECT TableA.*

FROM TableB INNER JOIN

TableA ON TableB.id1 = TableA.id1 INNER JOIN

TableC ON TableB.id3 = TableC.id3 AND TableA.id3 =
TableC.id3



...which is just 3 tables inner joined in a triangle. If the user then
tries to change the relationship between A and B to make sure all
records of A appear in the result, then the query builder software needs
to somehow report a conflict in the relationships because the
relationship between A and C must change as well.



I hope I explained that properly...


--
Posted via http://dbforums.com

...and just to confuse you further, my thoughts were that some recursive
function would be needed to traverse all existing relationships with the
participating tables of any newly proposed relationship. And the purpose
of that would be to verify that the newly proposed relationship would
coexist with existing ones without conflict.



I've been told this may involve heavy network modeling algorithms (that
would be beyond my understanding - entirely possible) and the best
course of action may be to let the user's query fail and put the
responsibility on them. But I'm not ready to give up on this yet. So any
assistance would be appreciated....Thx


--
Posted via http://dbforums.com

The software would need human intelligence. Maybe the single "reversal" is
what is needed to be done to get the "correct/desired" results. How would
the software be able to interpret the semantics of the data/query?


"bill_dev" <member38341 (AT) dbforums (DOT) com> wrote

I don't want my software to do any more than what commercially available
query builders currently do. Basically they allow users to choose tables
and fields and relationships but spare users from knowing SQL syntax.



When users of SQL Server try to configure a relationship in the above
example, SQL Server just does the reversal. In MS Access' query
builder, it won't make corrections on the user's behalf. It just reports
an error - that is what I'm trying to achieve.



Errors should be uncovered during the translation of tables, fields, and
relationships (however presented - graphically or otherwise) into SQL
syntax. I felt that query builders were a pretty common tool so I
thought maybe someone in this group could point me towards some
reference material that tells how this is done.



Originally posted by Alan




--
Posted via http://dbforums.com

bill_dev wrote:
It's not very simple, but also not very complicated. Just think of the join
as a graph: nodes are the relations, edges are join conditions. You start
from the node/relation that has to be fully in the result. If there is a
simple path (no cycles) that starts in this node and ends with the edge
(R1,R2) then the join between R1 and R2 should be an outer join on the side
of R1.

-- Jan Hidders

Originally posted by Jan Hidders

Awesome. I'm just on the verge of comprehending I was thinking
nodes are tables but no, they're relations. That makes more sense. I
found some algorithms for processing graphs but not for applying them to
this situation.



So in my above example I'd have 3 nodes...A is related to B, B is
related to C, and C is related to A and 3 edges. That would be a cycle
(#edges > (#nodes-1)), is that right? I assume verifying a cycle would
be harder than verfying the simple path you describe above. Do you know
of any documentation that describes this further? Thanks again!


--
Posted via http://dbforums.com

...or are you saying only cycles have potential for conflict and my
software should evaluate the simple path leading up to the last edge -
then if the last edge works as you describe then no conflict?

Thx


--
Posted via http://dbforums.com

bill_dev wrote:
It does? Because actually I meant "tables" when I said relations. :-)

Yes, it is. And as a conseqence you need a full outer join between B and C.

You could simply do a depth-first traversal with a recursive function
that checks if the node that it is about to visit is not already in the
path that it used to get to the node where it is at the moment. The
function looks roughly like this:

FUNCTION check_all( current_path, current_node )
/* current path is a list of nodes that describes the path */
/* to the current_node */
BEGIN
FOR ALL edges (R1,R2) with R1 = current_node DO
IF R2 is not in current_path
THEN
Check if the join condition that corresponds with the edge
is "outer" on the side of R1;
check_all( current_path ++ [ current_node ], R2 );
/* ++ = list append */
FI
OD
END

If table A is the one that has to be fully in the result then the
initial call is: check_all( [A], A)

Note that I didn't say what to do when the check fails, you can probably
figure that out for yourself.

If you look at the algorithm you will see that if there is a cycle then
it will walk around the cycle in both ways, which means that all the
join conditions have to be full on both sides, i.e., they have to be
*full* outer joins. All other join conditions only have to full on one side.

-- Jan Hidders