论文标题
在更新下具有免费访问模式的连接查询
Conjunctive Queries with Free Access Patterns under Updates
论文作者
论文摘要
我们研究了更新下使用免费访问模式（CQAP）回答连接查询的问题。免费访问模式是查询的自由变量的分区，以输入和输出。查询将元素返回输出变量，给定一个值元组的输入变量。 我们引入了一种完全动态的评估方法，该方法适用于所有CQAP，对于两类CQAP来说是最佳的。这种方法恢复了对没有访问模式的连接查询的动态评估的先前工作。 我们首先给出了所有CQAP的句法表征，该表征允许每个单匹匹配更新恒定时间，并且可以用恒定的延迟来枚举其输出元素，并在输入变量上进行值元整数。 我们进一步列出了一类CQAP的预处理时间，更新时间和枚举延迟之间的复杂性权衡。对于其中一些CQAP，我们的方法实现了最佳的，尽管是非恒定的，但更新时间和延迟。该最优性基于在线矩阵矢量乘法猜想。 我们最终将方法调整为对更新下的概率数据库的可拖动CQAP的动态评估。
We study the problem of answering conjunctive queries with free access patterns (CQAPs) under updates. A free access pattern is a partition of the free variables of the query into input and output. The query returns tuples over the output variables given a tuple of values over the input variables. We introduce a fully dynamic evaluation approach that works for all CQAPs and is optimal for two classes of CQAPs. This approach recovers prior work on the dynamic evaluation of conjunctive queries without access patterns. We first give a syntactic characterisation of all CQAPs that admit constant time per single-tuple update and whose output tuples can be enumerated with constant delay given a tuple of values over the input variables. We further chart the complexity trade-off between the preprocessing time, update time and enumeration delay for a class of CQAPs. For some of these CQAPs, our approach achieves optimal, albeit non-constant, update time and delay. This optimality is predicated on the Online Matrix-Vector Multiplication conjecture. We finally adapt our approach to the dynamic evaluation of tractable CQAPs over probabilistic databases under updates.
