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

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)
Number of pages56
Publication statusAccepted/In press - 20 Nov 2022
EventThe 26th International Conference on Database Theory, 2023 - Ioannina, Greece
Duration: 28 Mar 202331 Mar 2023
Conference number: 26
http://edbticdt2023.cs.uoi.gr/

Conference

ConferenceThe 26th International Conference on Database Theory, 2023
Abbreviated titleICDT 2023
Country/TerritoryGreece
CityIoannina
Period28/03/2331/03/23
Internet address

Keywords

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

Fingerprint

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

Cite this