Worst-case optimal join algorithms have gained a lot of attention in the database literature. We now count with several different algorithms that have all been shown to be optimal in the worst case, and many of them have also been implemented and tested in practice. However, the implementation of these algorithms often requires an enhanced indexing structure: to achieve optimality we either need to build completely new indexes  or we must populate the database with several different instantiations of common indexes such as B+-trees. Either way, this means spending an extra amount of storage space that may be non-negligible. In this paper we show that optimal algorithms can be obtained directly from a representation that regards the relations as point sets in variable-dimensional grids, without the need of extra storage. Our representation is a compact quadtree for the static indexes  and a dynamic quadtree sharing subtrees (which we dub a Qdag ) for intermediate results. We develop a compositional algorithm to process full join queries when data is stored in said structures, and then show that the running time of this algorithm is worst-case optimal in data complexity. Remarkably, we can even extend our framework to compute more expressive queries in relational algebra using both unions and a form of limited negation, by introducing a lazy version of Qdags . Once again, we can show that the running time of our algorithms is worst-case optimal.
Worst-case optimal join algorithms have gained a lot of attention in the database literature. We now count with several algorithms that are optimal in the worst case, and many of them have been implemented and validated in practice. However, the implementation of these algorithms often requires an enhanced indexing structure: to achieve optimality we either need to build completely new indexes , or we must populate the database with several instantiations of indexes such as B+-trees. Either way, this means spending an extra amount of storage space that may be non-negligible. We show that optimal algorithms can be obtained directly from a representation that regards the relations as point sets in variable-dimensional grids, without the need of extra storage. Our representation is a compact quad tree for the static indexes , and a dynamic quadtree sharing subtrees (which we dub a qdag ) for intermediate results. We develop a compositional algorithm to process full join queries under this representation, and show that the running time of this algorithm is worst-case optimal in data complexity. Remarkably, we can extend our framework to evaluate more expressive queries from relational algebra by introducing a lazy version of qdags (lqdags) . Once again, we can show that the running time of our algorithms is worst-case optimal.
R
different algorithms that have all been shown to be
algorithms that are
D
also
R
tested
validated
A
,
R
different instantiations of common
instantiations of
R
In this paper we
We
R
quadtree
quad tree
A
,
R
Qdag
qdag
R
when data is stored in said structures, and then
under this representation, and
D
even
R
compute
evaluate
R
in relational algebra using both unions and a form of limited negation,
from relational algebra
R
Qdags
qdags (lqdags)