@techreport{NeumannMoerkotte2008,
TITLE = {Single phase construction of optimal {DAG}-structured {QEPs}},
AUTHOR = {Neumann, Thomas and Moerkotte, Guido},
LANGUAGE = {eng},
URL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2008-5-002},
NUMBER = {MPI-I-2008-5-002},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {2008},
DATE = {2008},
ABSTRACT = {Traditionally, database management systems use tree-structured query<br>evaluation plans. They are easy to implement but not expressive enough<br>for some optimizations like eliminating common algebraic subexpressions<br>or magic sets. These require directed acyclic graphs (DAGs), i.e.<br>shared subplans.<br><br>Existing approaches consider DAGs merely for special cases<br>and not in full generality.<br>We introduce a novel framework to reason about sharing of subplans<br>and, thus, DAG-structured query evaluation plans.<br>Then, we present the first plan generator capable<br>of generating optimal DAG-structured query evaluation plans.<br>The experimental results show that with no or only a modest<br>increase of plan generation time, a major reduction<br>of query execution time can be<br>achieved for common queries.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}