  Efficient join processing is one of the most fundamental and well-studied
tasks in database research. In this work, we examine algorithms for natural
join queries over many relations and describe a novel algorithm to process
these queries optimally in terms of worst-case data complexity. Our result
builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size
of a full conjunctive query in terms of the sizes of the individual relations
in the body of the query. These bounds, however, are not constructive: they
rely on Shearer's entropy inequality which is information-theoretic. Thus, the
previous results leave open the question of whether there exist algorithms
whose running time achieve these optimal bounds. An answer to this question may
be interesting to database practice, as it is known that any algorithm based on
the traditional select-project-join style plans typically employed in an RDBMS
are asymptotically slower than the optimal for some queries. We construct an
algorithm whose running time is worst-case optimal for all natural join
queries. Our result may be of independent interest, as our algorithm also
yields a constructive proof of the general fractional cover bound by Atserias,
Grohe, and Marx without using Shearer's inequality. This bound implies two
famous inequalities in geometry: the Loomis-Whitney inequality and the
Bollob\'as-Thomason inequality. Hence, our results algorithmically prove these
inequalities as well. Finally, we discuss how our algorithm can be used to
compute a relaxed notion of joins.
