Document Open Access Logo

Rewriting with Acyclic Queries: Mind Your Head

Authors Gaetano Geck, Jens Keppeler, Thomas Schwentick, Christopher Spinrath

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICDT.2022.8.pdf
  • Filesize: 0.72 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Data integration
  • Theory of computation → Database query processing and optimization (theory)
Keywords
  • rewriting
  • acyclic rewriting
  • acyclic conjunctive queries
  • free-connex queries
  • hierarchical queries
  • NP-hardness

Metrics

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

Abstract

The paper studies the rewriting problem, that is, the decision problem whether, for a given conjunctive query Q and a set 𝒱 of views, there is a conjunctive query Q' over 𝒱 that is equivalent to Q, for cases where the query, the views, and/or the desired rewriting are acyclic or even more restricted.
It shows that, if Q itself is acyclic, an acyclic rewriting exists if there is any rewriting. An analogous statement also holds for free-connex acyclic, hierarchical, and q-hierarchical queries.
Regarding the complexity of the rewriting problem, the paper identifies a border between tractable and (presumably) intractable variants of the rewriting problem: for schemas of bounded arity, the acyclic rewriting problem is NP-hard, even if both Q and the views in 𝒱 are acyclic or hierarchical. However, it becomes tractable, if the views are free-connex acyclic (i.e., in a nutshell, their body is (i) acyclic and (ii) remains acyclic if their head is added as an additional atom).

Cite As Get BibTex

Gaetano Geck, Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Rewriting with Acyclic Queries: Mind Your Head. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICDT.2022.8

Author Details

Gaetano Geck
  • TU Dortmund University, Germany
Jens Keppeler
  • TU Dortmund University, Germany
Thomas Schwentick
  • TU Dortmund University, Germany
Christopher Spinrath
  • TU Dortmund University, Germany

Supplementary Materials

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
  2. Foto N. Afrati and Rada Chirkova. Answering Queries Using Views, Second Edition. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2019. URL: https://doi.org/10.2200/S00884ED2V01Y201811DTM054.
  3. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes in Computer Science, pages 208-222. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74915-8_18.
  4. Nurzhan Bakibayev, Tomás Kociský, Dan Olteanu, and Jakub Zavodny. Aggregation and ordering in factorised databases. Proc. VLDB Endow., 6(14):1990-2001, 2013. URL: https://doi.org/10.14778/2556549.2556579.
  5. Pablo Barceló, Andreas Pieris, and Miguel Romero. Semantic optimization in tractable classes of conjunctive queries. SIGMOD Rec., 46(2):5-17, 2017. URL: https://doi.org/10.1145/3137586.3137588.
  6. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 303-318. ACM, 2017. URL: https://doi.org/10.1145/3034786.3034789.
  7. Johann Brault-Baron. De la pertinence de l'énumération : complexité en logiques propositionnelle et du premier ordre. Theses, Université de Caen, April 2013. URL: https://hal.archives-ouvertes.fr/tel-01081392.
  8. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. View-based query processing: On the relationship between rewriting, answering and losslessness. In Thomas Eiter and Leonid Libkin, editors, Database Theory - ICDT 2005, 10th International Conference, Edinburgh, UK, January 5-7, 2005, Proceedings, volume 3363 of Lecture Notes in Computer Science, pages 321-336. Springer, 2005. URL: https://doi.org/10.1007/978-3-540-30570-5_22.
  9. Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison, editors, Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 77-90. ACM, 1977. URL: https://doi.org/10.1145/800105.803397.
  10. Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theor. Comput. Sci., 239(2):211-229, 2000. URL: https://doi.org/10.1016/S0304-3975(99)00220-0.
  11. Rada Chirkova and Jun Yang. Materialized views. Found. Trends Databases, 4(4):295-405, 2012. URL: https://doi.org/10.1561/1900000020.
  12. Nilesh N. Dalvi and Dan Suciu. The dichotomy of conjunctive queries on probabilistic structures. In Leonid Libkin, editor, Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China, pages 293-302. ACM, 2007. URL: https://doi.org/10.1145/1265530.1265571.
  13. Robert Fink and Dan Olteanu. A dichotomy for non-repeating queries with negation in probabilistic databases. In Richard Hull and Martin Grohe, editors, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22-27, 2014, pages 144-155. ACM, 2014. URL: https://doi.org/10.1145/2594538.2594549.
  14. Robert Fink and Dan Olteanu. Dichotomies for queries with negation in probabilistic databases. ACM Trans. Database Syst., 41(1):4:1-4:47, 2016. URL: https://doi.org/10.1145/2877203.
  15. Gaetano Geck, Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Rewriting with acyclic queries: Mind your head, 2022. URL: http://arxiv.org/abs/2201.05129.
  16. Georg Gottlob, Nicola Leone, and Francesco Scarcello. The complexity of acyclic conjunctive queries. J. ACM, 48(3):431-498, 2001. URL: https://doi.org/10.1145/382780.382783.
  17. Gang Gou, Maxim Kormilitsin, and Rada Chirkova. Query evaluation using overlapping views: completeness and efficiency. In Surajit Chaudhuri, Vagelis Hristidis, and Neoklis Polyzotis, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, USA, June 27-29, 2006, pages 37-48. ACM, 2006. URL: https://doi.org/10.1145/1142473.1142479.
  18. Alon Y. Halevy. Answering queries using views: A survey. VLDB J., 10(4):270-294, 2001. URL: https://doi.org/10.1007/s007780100054.
  19. Xiao Hu and Ke Yi. Instance and output optimal parallel algorithms for acyclic joins. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 450-463. ACM, 2019. URL: https://doi.org/10.1145/3294052.3319698.
  20. Muhammad Idris, Martín Ugarte, and Stijn Vansummeren. The dynamic yannakakis algorithm: Compact and efficient query processing under updates. In Semih Salihoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu, editors, Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017, pages 1259-1274. ACM, 2017. URL: https://doi.org/10.1145/3035918.3064027.
  21. Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Trade-offs in static and dynamic evaluation of hierarchical queries. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 375-392. ACM, 2020. URL: https://doi.org/10.1145/3375395.3387646.
  22. Jens Keppeler. Answering Conjunctive Queries and FO+MOD Queries under Updates. PhD thesis, Humboldt University of Berlin, Germany, 2020. URL: http://edoc.hu-berlin.de/18452/22264.
  23. Benny Kimelfeld and Yehoshua Sagiv. Incrementally computing ordered answers of acyclic conjunctive queries. In Opher Etzion, Tsvi Kuflik, and Amihai Motro, editors, Next Generation Information Technologies and Systems, 6th International Workshop, NGITS 2006, Kibbutz Shefayim, Israel, July 4-6, 2006, Proceedings, volume 4032 of Lecture Notes in Computer Science, pages 141-152. Springer, 2006. URL: https://doi.org/10.1007/11780991_13.
  24. Paraschos Koutris and Dan Suciu. Parallel evaluation of conjunctive queries. In Maurizio Lenzerini and Thomas Schwentick, editors, Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pages 223-234. ACM, 2011. URL: https://doi.org/10.1145/1989284.1989310.
  25. Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. Answering queries using views. In Mihalis Yannakakis and Serge Abiteboul, editors, Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California, USA, pages 95-104. ACM Press, 1995. URL: https://doi.org/10.1145/212433.220198.
  26. Alan Nash, Luc Segoufin, and Victor Vianu. Views and queries: Determinacy and rewriting. ACM Trans. Database Syst., 35(3):21:1-21:41, 2010. URL: https://doi.org/10.1145/1806907.1806913.
  27. Dan Olteanu and Jakub Závodný. Size bounds for factorised representations of query results. ACM Trans. Database Syst., 40(1):2:1-2:44, 2015. URL: https://doi.org/10.1145/2656335.
  28. Rachel Pottinger and Alon Y. Halevy. Minicon: A scalable algorithm for answering queries using views. VLDB J., 10(2-3):182-198, 2001. URL: https://doi.org/10.1007/s007780100048.
  29. Maximilian Schleich, Dan Olteanu, and Radu Ciucanu. Learning linear regression models over factorized joins. In Fatma Özcan, Georgia Koutrika, and Sam Madden, editors, Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 3-18. ACM, 2016. URL: https://doi.org/10.1145/2882903.2882939.
  30. Mihalis Yannakakis. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings, pages 82-94. IEEE Computer Society, 1981. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact