Title: Computing Joins via Fractional Edge Covers

Abstract:
We consider the fundamental problem of computing the natural join of a
sequence of relations. We show that a simple linear program, which
describes the so-called fractional edge cover number of a hypergraph
associated with the join expression, gives nontrivial bounds on the
size of such joins. Using linear programming duality, we can also show
that these bounds are optimal.

This gives us better cost estimates to optimize join queries, which
lead to better algorithms. We show that a straightforward query plan
obtained by interleaving joins with projections is asymptotically
optimal, and that it can be exponentially better than any query plan
that only uses joins (even for queries that do not contain any
projections).

This is joint work with Albert Atserias and Daniel Marx.