更新下的自由访问模式连接查询

Conjunctive Queries with Free Access Patterns under Updates

摘要 Abstract

我们研究了在更新条件下回答具有自由访问模式(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.