Size Bounds and Query Plans for Relational Joins

By Albert Atserias, Martin Grohe, Daniel Marx. 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

382 citations recorded by the source corpus.

Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimisers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model, and in an average-case model where the database is chosen according to a known probability distribution. In the former case, our first key observation is that the worst-case size of a query is characterised by the fractional edge cover number of its underlying hypergraph, a combinatorial parameter previously known to provide an upper bound. We complete the picture by proving a matching lower bound, and by showing that there exist queries for which the join-project plan suggested by the fractional edge cover approach may be substantially better than any join plan that does not use intermediate projections.

Subfields: Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/44cc1e932305f92dd75d2b560f6024de9f920c89

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

  1. Kunle Olukotun
  2. Christopher R'e
  3. Jakub Konecný

In Signal Processing

  1. Kunle Olukotun
  2. Christopher R'e
  3. Jakub Konecný

Citations in the corpus