Conjunctive Queries with Free Access Patterns under Updates

Ahmet Kara, Milos Nikolic, Dan Olteanu, Haozhe Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProceedings of the 26th International Conference on Database Theory (ICDT 2023)
EditorsFloris Geerts, Brecht Vandevoort
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages56
ISBN (Electronic)9783959772709
Publication statusPublished - 17 Mar 2023
EventThe 26th International Conference on Database Theory, 2023 - Ioannina, Greece
Duration: 28 Mar 202331 Mar 2023
Conference number: 26

Publication series

NameLIPIcs – Leibniz International Proceedings in Informatics
ISSN (Electronic)1868-8969


ConferenceThe 26th International Conference on Database Theory, 2023
Abbreviated titleICDT 2023
Internet address

Keywords / Materials (for Non-textual outputs)

  • fully dynamic algorithm
  • enumeration delay
  • complexity trade-of
  • dichotomy


Dive into the research topics of 'Conjunctive Queries with Free Access Patterns under Updates'. Together they form a unique fingerprint.

Cite this