一句话：提出全动态求值方法支持所有带自由访问模式的合取查询，并刻画常数更新/延迟条件与复杂度权衡。
论文研究在更新下求值带自由访问模式的合取查询（CQAP）。自由访问模式将查询自由变量划分为输入和输出，给定输入值需返回输出变量上的元组。作者提出一种完全动态求值方法，对所有 CQAP 均适用，并对两类 CQAP 达到最优，同时恢复无访问模式合取查询的动态求值结果。首先给出语法刻画，精确识别那些支持单元组更新常数时间、且给定输入元组可常数延迟枚举输出的 CQAP。进一步刻画一类 CQAP 在预处理时间、更新时间和枚举延迟之间的复杂度权衡。对其中部分查询，方法达到最优但非恒定的更新时间和延迟，其最优性基于 Online Matrix-Vector Multiplication 猜想。最后将方法适配到概率数据库上可处理 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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{00020OZ23,
title = {Conjunctive Queries with Free Access Patterns under Updates},
author = {Ahmet Kara and Milos Nikolic and Dan Olteanu and Haozhe Zhang},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 2},
year = {2025},
doi = {10.46298/lmcs-21(2:23)2025}
}