Conjunctive Queries with Free Access Patterns under Updates

Ahmet Kara; Milos Nikolic; Dan Olteanu; Haozhe Zhang

doi:10.4230/LIPIcs.ICDT.2023.17

Conjunctive Queries with Free Access Patterns under Updates

Ahmet Kara, Milos Nikolic, Dan Olteanu, Haozhe Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Proceedings of the 26th International Conference on Database Theory (ICDT 2023)
Editors	Floris Geerts, Brecht Vandevoort
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	17:1-17:20
Number of pages	56
Volume	255
ISBN (Electronic)	9783959772709
DOIs	https://doi.org/10.4230/LIPIcs.ICDT.2023.17
Publication status	Published - 17 Mar 2023
Event	The 26th International Conference on Database Theory, 2023 - Ioannina, Greece Duration: 28 Mar 2023 → 31 Mar 2023 Conference number: 26 http://edbticdt2023.cs.uoi.gr/

Publication series

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

Conference

Conference	The 26th International Conference on Database Theory, 2023
Abbreviated title	ICDT 2023
Country/Territory	Greece
City	Ioannina
Period	28/03/23 → 31/03/23
Internet address	http://edbticdt2023.cs.uoi.gr/

Keywords / Materials (for Non-textual outputs)

fully dynamic algorithm
enumeration delay
complexity trade-of
dichotomy

Access to Document

10.4230/LIPIcs.ICDT.2023.17Licence: Creative Commons: Attribution (CC-BY)

Conjunctive Queries_KARA_DOA20112022_AFVAccepted author manuscript, 1.12 MBLicence: Creative Commons: Attribution (CC-BY)
Conjunctive Queries_KARA_DOA20112022_VOR_CC-BYFinal published version, 909 KBLicence: Creative Commons: Attribution (CC-BY)

https://drops.dagstuhl.de/opus/volltexte/2023/17759Licence: Creative Commons: Attribution (CC-BY)

Cite this

Kara, A., Nikolic, M., Olteanu, D., & Zhang, H. (2023). Conjunctive Queries with Free Access Patterns under Updates. In F. Geerts, & B. Vandevoort (Eds.), Proceedings of the 26th International Conference on Database Theory (ICDT 2023) (Vol. 255, pp. 17:1-17:20). (LIPIcs – Leibniz International Proceedings in Informatics). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICDT.2023.17

Kara, Ahmet ; Nikolic, Milos ; Olteanu, Dan et al. / Conjunctive Queries with Free Access Patterns under Updates. Proceedings of the 26th International Conference on Database Theory (ICDT 2023). editor / Floris Geerts ; Brecht Vandevoort. Vol. 255 Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 17:1-17:20 (LIPIcs – Leibniz International Proceedings in Informatics).

@inproceedings{542d44c5f19a4220a17e1dabdc7481f7,

title = "Conjunctive Queries with Free Access Patterns under Updates",

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.",

keywords = "fully dynamic algorithm, enumeration delay, complexity trade-of, dichotomy",

author = "Ahmet Kara and Milos Nikolic and Dan Olteanu and Haozhe Zhang",

note = "This project has received funding from the European Union{\textquoteright}s Horizon 2020 research and innovation programme under grant agreement No 682588; The 26th International Conference on Database Theory, 2023, ICDT 2023 ; Conference date: 28-03-2023 Through 31-03-2023",

year = "2023",

month = mar,

day = "17",

doi = "10.4230/LIPIcs.ICDT.2023.17",

language = "English",

volume = "255",

series = "LIPIcs – Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "17:1--17:20",

editor = "Floris Geerts and Brecht Vandevoort",

booktitle = "Proceedings of the 26th International Conference on Database Theory (ICDT 2023)",

url = "http://edbticdt2023.cs.uoi.gr/",

}

Kara, A, Nikolic, M, Olteanu, D & Zhang, H 2023, Conjunctive Queries with Free Access Patterns under Updates. in F Geerts & B Vandevoort (eds), Proceedings of the 26th International Conference on Database Theory (ICDT 2023). vol. 255, LIPIcs – Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 17:1-17:20, The 26th International Conference on Database Theory, 2023, Ioannina, Greece, 28/03/23. https://doi.org/10.4230/LIPIcs.ICDT.2023.17

Conjunctive Queries with Free Access Patterns under Updates. / Kara, Ahmet; Nikolic, Milos; Olteanu, Dan et al.
Proceedings of the 26th International Conference on Database Theory (ICDT 2023). ed. / Floris Geerts; Brecht Vandevoort. Vol. 255 Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. p. 17:1-17:20 (LIPIcs – Leibniz International Proceedings in Informatics).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Conjunctive Queries with Free Access Patterns under Updates

AU - Kara, Ahmet

AU - Nikolic, Milos

AU - Olteanu, Dan

AU - Zhang, Haozhe

N1 - Conference code: 26

PY - 2023/3/17

Y1 - 2023/3/17

N2 - 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.

AB - 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.

KW - fully dynamic algorithm

KW - enumeration delay

KW - complexity trade-of

KW - dichotomy

U2 - 10.4230/LIPIcs.ICDT.2023.17

DO - 10.4230/LIPIcs.ICDT.2023.17

M3 - Conference contribution

VL - 255

T3 - LIPIcs – Leibniz International Proceedings in Informatics

SP - 17:1-17:20

BT - Proceedings of the 26th International Conference on Database Theory (ICDT 2023)

A2 - Geerts, Floris

A2 - Vandevoort, Brecht

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl, Germany

T2 - The 26th International Conference on Database Theory, 2023

Y2 - 28 March 2023 through 31 March 2023

ER -

Kara A, Nikolic M, Olteanu D, Zhang H. Conjunctive Queries with Free Access Patterns under Updates. In Geerts F, Vandevoort B, editors, Proceedings of the 26th International Conference on Database Theory (ICDT 2023). Vol. 255. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. p. 17:1-17:20. (LIPIcs – Leibniz International Proceedings in Informatics). doi: 10.4230/LIPIcs.ICDT.2023.17

Conjunctive Queries with Free Access Patterns under Updates

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this