Ahmet Kara ; Milos Nikolic ; Dan Olteanu ; Haozhe Zhang - Conjunctive Queries with Free Access Patterns under Updates

lmcs:13059 - Logical Methods in Computer Science, June 16, 2025, Volume 21, Issue 2 - https://doi.org/10.46298/lmcs-21(2:23)2025
Conjunctive Queries with Free Access Patterns under UpdatesArticle

Authors: Ahmet Kara ; Milos Nikolic ; Dan Olteanu ; Haozhe Zhang

    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.


    Volume: Volume 21, Issue 2
    Published on: June 16, 2025
    Accepted on: April 3, 2025
    Submitted on: February 15, 2024
    Keywords: Computer Science - Databases

    Consultation statistics

    This page has been seen 246 times.
    This article's PDF has been downloaded 100 times.