数据库学术速递[1.10]
Update！H5支持摘要折叠，体验更佳！点击阅读原文访问arxivdaily.com，涵盖CS|物理|数学|经济|统计|金融|生物|电气领域，更有搜索、收藏等功能！
cs.DB数据库，共计1篇
【1】 Tight Fine-Grained Bounds for Direct Access on Join Queries
标题：连接查询直接访问的紧致细粒度界限
链接：https://arxiv.org/abs/2201.02401
摘要：We consider the task of lexicographic direct access to query answers. That
is, we want to simulate an array containing the answers of a join query sorted
in a lexicographic order chosen by the user. A recent dichotomy showed for
which queries and orders this task can be done in polylogarithmic access time
after quasilinear preprocessing, 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
self-join free queries and all lexicographical orders. To this end, we propose
a decomposition-based general algorithm for direct access on join queries. We
then explore its optimality by proving lower bounds for the preprocessing time
based on the hardness of a certain online Set-Disjointness problem, which shows
that our algorithm's bounds are tight for all lexicographic orders on self-join
free 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. We also show that similar techniques 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 of self-join free cyclic joins with respect to linear
preprocessing and constant delay.
机器翻译，仅供参考
点击“阅读原文”获取带摘要的学术速递