2026-07-25T13:34:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17759 2024-03-06T11:00:25Z ddc:004 open_access

Conjunctive Queries with Free Access Patterns Under Updates Kara, Ahmet Nikolic, Milos Olteanu, Dan Zhang, Haozhe fully dynamic algorithm enumeration delay complexity trade-off dichotomy We study the problem of answering conjunctive queries with free access patterns 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 for such queries. We also give a syntactic characterisation of those queries that admit constant time per single-tuple update and whose output tuples can be enumerated with constant delay given an input tuple. Finally, we chart the complexity trade-off between the preprocessing time, update time and enumeration delay for such queries. For a class of queries, our approach achieves optimal, albeit non-constant, update time and delay. Their optimality is predicated on the Online Matrix-Vector Multiplication conjecture. Our results recover prior work on the dynamic evaluation of conjunctive queries without access patterns. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahmet Kara and Milos Nikolic and Dan Olteanu and Haozhe Zhang 2023 Is Part Of LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2023.17 urn:nbn:de:0030-drops-177599 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.17 eng https://creativecommons.org/licenses/by/4.0/legalcode