论文标题
与自结合的结合查询，朝着细粒的复杂性分析
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Complexity Analysis
论文作者
论文摘要
尽管查询评估是数据库中的一项基本任务，但通过其细粒度复杂性的已知共同查询分类仅适用于无自结合的查询。我们研究自加入如何影响枚举复杂性，目的是建立已知结果以实现一般分类。我们通过检查两个已知二分法的扩展：一个关于线性延迟的延伸，另一个相对于线性预处理后的恒定延迟。由于事实证明这是一项复杂的研究，因此本文作为示例驱动的讨论构成了启动此分析的示例讨论。我们展示的枚举算法依靠自加入来有效评估否则无法通过相同保证来回答的查询。由于这些额外的易处理情况，硬度证明比无自结合的情况更为复杂。我们展示如何利用已知的标记技术来证明与自结合的查询的硬度。我们的研究提供了足够的条件和必要条件，可以解决低位和查询的查询案例。然而，许多案件仍然开放。
Even though query evaluation is a fundamental task in databases, known classifications of conjunctive queries by their fine-grained complexity only apply to queries without self-joins. We study how self-joins affect enumeration complexity, with the aim of building upon the known results to achieve general classifications. We do this by examining the extension of two known dichotomies: one with respect to linear delay, and one with respect to constant delay after linear preprocessing. As this turns out to be an intricate investigation, this paper is structured as an example-driven discussion that initiates this analysis. We show enumeration algorithms that rely on self-joins to efficiently evaluate queries that otherwise cannot be answered with the same guarantees. Due to these additional tractable cases, the hardness proofs are more complex than the self-join-free case. We show how to harness a known tagging technique to prove hardness of queries with self-joins. Our study offers sufficient conditions and necessary conditions for tractability and settles the cases of queries of low arity and queries with cyclic cores. Nevertheless, many cases remain open.
