首页|Tight Fine-Grained Bounds for Direct Access on Join Queries
Tight Fine-Grained Bounds for Direct Access on Join Queries
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
Assoc Computing Machinery
We consider the task of lexicographic direct access to query answers. That is, we want to simulate an arraycontaining the answers of a join query sorted in a lexicographic order chosen by the user. A recent dichotomyshowed for which queries and orders this task can be done in polylogarithmic access time after quasilinearpreprocessing, but this dichotomy does not tell us how much time is required in the cases classified as hard.We determine the preprocessing time needed to achieve polylogarithmic access time for all join queries and alllexicographical orders. To this end, we propose a decomposition-based general algorithm for direct access onjoin queries.We then explore its optimality by proving lower bounds for the preprocessing time based on thehardness of a certain online Set-Disjointness problem, which shows that our algorithm’s bounds are tight forall lexicographic orders on join queries. Then, we prove the hardness of Set-Disjointness based on the Zero-Clique Conjecture, which is an established conjecture from fine-grained complexity theory. Interestingly,while proving our lower bound, we show that self-joins do not affect the complexity of direct access (upto logarithmic factors). Our algorithm can also be used to solve queries with projections and relaxed orderrequirements, though in these cases, its running time is not necessarily optimal. We also show that similartechniques to those used in our lower bounds can be used to prove that, for enumerating answers to Loomis-Whitney joins, it is not possible to significantly improve upon trivially computing all answers at preprocessing.This, in turn, gives further evidence (based on the Zero-Clique Conjecture) to the enumeration hardness ofself-join-free cyclic joins with respect to linear preprocessing and constant delay.
NETL
NSTL
Assoc Computing Machinery
