Document Open Access Logo

Conjunctive Queries with Free Access Patterns Under Updates

Authors Ahmet Kara , Milos Nikolic , Dan Olteanu , Haozhe Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.17.pdf
  • Filesize: 0.88 MB
  • 20 pages

Document Identifiers

Author Details

Ahmet Kara
  • Universität Zürich, Switzerland
Milos Nikolic
  • University of Edinburgh, UK
Dan Olteanu
  • Universität Zürich, Switzerland
Haozhe Zhang
  • Universität Zürich, Switzerland

Funding

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 682588.

Cite As Get BibTex

Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Conjunctive Queries with Free Access Patterns Under Updates. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICDT.2023.17

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database query processing and optimization (theory)
  • Information systems → Database views
  • Information systems → Data streams
Keywords
  • fully dynamic algorithm
  • enumeration delay
  • complexity trade-off
  • dichotomy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
  2. Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. FAQ: Questions Asked Frequently. In PODS, pages 13-28, 2016. Google Scholar
  3. Albert Atserias, Martin Grohe, and Dániel Marx. Size Bounds and Query Plans for Relational Joins. SIAM J. Comput., 42(4):1737-1767, 2013. Google Scholar
  4. Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. On the Desirability of Acyclic Database Schemes. J. ACM, 30(3):479-513, 1983. Google Scholar
  5. Michael Benedikt, Julien Leblay, and Efthymia Tsamoura. Querying with Access Patterns and Integrity Constraints. VLDB, 8(6):690-701, 2015. Google Scholar
  6. Michael Benedikt, Balder Ten Cate, and Efthymia Tsamoura. Generating Low-cost Plans from Proofs. In PODS, pages 200-211, 2014. Google Scholar
  7. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering Conjunctive Queries Under Updates. In PODS, pages 303-318, 2017. Google Scholar
  8. Bozhena Bidyuk and Rina Dechter. Cutset Sampling for Bayesian Networks. J. Artif. Intell. Res., 28:1-48, 2007. Google Scholar
  9. Rada Chirkova and Jun Yang. Materialized Views. Found. & Trends DB, 4(4):295-405, 2012. Google Scholar
  10. Shaleen Deep, Xiao Hu, and Paraschos Koutris. Space-Time Tradeoffs for Answering Boolean Conjunctive Queries. CoRR, abs/2109.10889, 2021. URL: http://arxiv.org/abs/2109.10889.
  11. Shaleen Deep and Paraschos Koutris. Compressed Representations of Conjunctive Query Results. In PODS, pages 307-322, 2018. Google Scholar
  12. Alin Deutsch, Bertram Ludäscher, and Alan Nash. Rewriting Queries using Views with Access Patterns under Integrity Constraints. Theor. Comput. Sci., 371(3):200-226, 2007. Google Scholar
  13. Arnaud Durand and Etienne Grandjean. First-order Queries on Structures of Bounded Degree are Computable with Constant Delay. TOCL, 8(4):21, 2007. Google Scholar
  14. Arnaud Durand and Yann Strozecki. Enumeration Complexity of Logical Query Problems with Second-order Variables. In CSL, pages 189-202, 2011. Google Scholar
  15. Daniela Florescu, Alon Levy, Ioana Manolescu, and Dan Suciu. Query Optimization in the Presence of Limited Access Patterns. SIGMOD Rec., 28(2):311-322, 1999. Google Scholar
  16. Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree Decompositions and Tractable Queries. In PODS, pages 21-32, 1999. Google Scholar
  17. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In STOC, pages 21-30, 2015. Google Scholar
  18. Muhammad Idris, Martín Ugarte, and Stijn Vansummeren. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In SIGMOD, pages 1259-1274, 2017. Google Scholar
  19. Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Counting Triangles under Updates in Worst-Case Optimal Time. In ICDT, pages 4:1-4:18, 2019. Google Scholar
  20. Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Maintaining Triangle Queries under Updates. TODS, 45(3):11:1-11:46, 2020. Google Scholar
  21. Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries. In PODS, pages 375-392, 2020. Google Scholar
  22. Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Conjunctive Queries with Free Access Patterns under Updates. CoRR, abs/2206.09032, 2022. URL: http://arxiv.org/abs/2206.09032.
  23. Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries. To appear in LMCS, 2023. Google Scholar
  24. Christoph Koch et al. DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views. VLDB J., 23(2):253-278, 2014. Google Scholar
  25. Daphne Koller and Nir Friedman. Probabilistic Graphical Models - Principles and Techniques. MIT Press, 2009. Google Scholar
  26. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Dynamic Set Intersection. In WADS, pages 470-481, 2015. Google Scholar
  27. Chen Li and Edward Chang. On Answering Queries in the Presence of Limited Access Patterns. In ICDT, pages 219-233, 2001. Google Scholar
  28. Alan Nash and Bertram Ludäscher. Processing First-Order Queries under Limited Access Patterns. In PODS, pages 307-318, 2004. Google Scholar
  29. Alan Nash and Bertram Ludäscher. Processing Unions of Conjunctive Queries with Negation under Limited Access Patterns. In EDBT, pages 422-440, 2004. Google Scholar
  30. Milos Nikolic and Dan Olteanu. Incremental View Maintenance with Triple Lock Factorization Benefits. In SIGMOD, pages 365-380, 2018. Google Scholar
  31. Dan Olteanu and Jakub Závodný. Size Bounds for Factorised Representations of Query Results. TODS, 40(1):2:1-2:44, 2015. Google Scholar
  32. Judea Pearl. Probabilistic Reasoning in Intelligent Systems - Networks of Plausible Inference. Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989. Google Scholar
  33. Todd L. Veldhuizen. Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In ICDT, pages 96-106, 2014. Google Scholar
  34. Ramana Yerneni, Chen Li, Jeffrey Ullman, and Hector Garcia-Molina. Optimizing Large Join Queries in Mediation Systems. In ICDT, pages 348-364, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact