We study full acyclic join queries with general join predicates that involve conjunctions and disjunctions of inequalities  , focusing on ranked enumeration where the answers are returned incrementally in an order dictated by a given ranking function. Our approach offers strong time and space complexity guarantees in the standard RAM model of computation, getting surprisingly close to those of equi-joins. With n denoting the number of tuples in the database, we guarantee  that for every value of k, the k top-ranked answers are returned in \mathcal{O (n polylog n + k  k) time and \mathcal{O n + k) space . This is within a polylogarithmic factor of the best-known guarantee for equi-joins and even  \mathcal{O}(n+k), the time it takes to look at the input and output k answers . The key ingredient is an \mathcal{O}(n \operatorname{polylog} n)-size factorized representation of the query output, which is constructed on-the-fly for a given query and database. As a side benefit, our techniques are also applicable to unranked enumeration (where answers can be returned in any order) for joins with inequalities, returning k answers in \mathcal{O(n }%DIFDELCMD < \operatorname{polylog} %%% n + k). This guarantee improves over the state of the art for large values of k. In an experimental study , we show that our ranked-enumeration approach is not only theoretically interesting, but also fast and memory-efficient in practice .
We study theta-joins in general and join predicates with conjunctions and disjunctions of inequalities in particular , focusing on ranked enumeration where the answers are returned incrementally in an order dictated by a given ranking function. Our approach achieves strong time and space complexity properties: with n denoting the number of tuples in the database, we guarantee for acyclic full join queries with inequality conditions that for every value of k, the k top-ranked answers are returned in O (n polylog n + k \log k) time . This is within a polylogarithmic factor of the best known complexity for equi-joins and even of \mathcal{O}(n+k), the time it takes to look at the input and return k answers in any order. Our guarantees extend to join queries with selections and many types of projections, such as the so-called free-connex queries. Remarkably, they hold even when the entire output is of size n^\ell for a join of \ell relations. The key ingredient is a novel \mathcal{O}(n \operatorname{polylog} n)-size factorized representation of the query output, which is constructed on-the-fly for a given query and database. (n }%DIFDELCMD < \operatorname{polylog} %%% In addition to providing the first non-trivial theoretical guarantees beyond equi-joins, we show in an experimental study that our ranked-enumeration approach is also memory-efficient and fast in practice, beating the running time of state-of-the-art database systems by orders of magnitude .
R
full acyclic join queries with general join predicates that involve
theta-joins in general and join predicates with
A
in particular
R
offers
achieves
R
guarantees in the standard RAM model of computation, getting surprisingly close to those of equi-joins. With
properties: with
A
for acyclic full join queries with inequality conditions
R
\mathcal{O
O
A
\log
D
and \mathcal{O
D
n + k) space
R
best-known guarantee
best known complexity
A
of
R
output k answers .
return k answers in any order. Our guarantees extend to join queries with selections and many types of projections, such as the so-called free-connex queries. Remarkably, they hold even when the entire output is of size n^\ell for a join of \ell relations.
R
an
a novel
D
As a side benefit, our techniques are also applicable to unranked enumeration (where answers can be returned in any order) for joins with inequalities, returning k answers in \mathcal{O
R
n + k). This guarantee improves over the state of the art for large values of k. In
In addition to providing the first non-trivial theoretical guarantees beyond equi-joins, we show in
D
, we show
R
not only theoretically interesting, but also fast and
also
R
in practice
and fast in practice, beating the running time of state-of-the-art database systems by orders of magnitude