Graph Theory problem
Date: Fri, 26 Oct 2001 18:05:08 -0700
Message-ID: <3BDA0844.FFE3EF11_at_vpservices.com>
I want to be able to evaluate the table relations implied by equijoins in a WHERE clause, for example, given somthing like:
WHERE a.foo = b.foo AND c.bar = d.bar AND d.baz = a.baz
I want to be able to place the tables in order for joining (at a low implementation level, not in an rdbms) such that each table is joined with one it has an equijoin to. In the example, if I start with table a, I can't immediately join table c to it, but must first join table d to table a and then join table c to those two.
From my (very) limited knowledge of graph theory, this can be stated as:
Given a graph containing an arbitrary number of paths each of which contains exactly two vertices, return the vertices in an order such that each vertex (except the first) shares an edge with at least one vertex prior to it but not necessarily adjacent to it or fail if that is not possible.
Is that a correct statement of the problem? Is there a name for that in graph theory? I know it shares some features with topological sort and transitive closure. Any suggestions on algorithims or resources that might help me out?
-- JeffReceived on Sat Oct 27 2001 - 03:05:08 CEST