LIPIcs.ICDT.2020.2.pdf
- Filesize: 0.56 MB
- 20 pages
Document
What Makes a Variant of Query Determinacy (Un)Decidable? (Invited Talk)
Author
-
Part of:
Volume:
23rd International Conference on Database Theory (ICDT 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Database Theory (ICDT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-03-11
File
Document Identifiers
Acknowledgements
The author would not have been in a position to write this invited paper had he not been first blessed with the opportunity to work with extraordinary students: Tomasz Gogacz, Grzegorz Głuch and Piotr Ostropolski-Nalewaja.
Cite As Get BibTex
Jerzy Marcinkowski. What Makes a Variant of Query Determinacy (Un)Decidable? (Invited Talk). In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICDT.2020.2
Abstract
This paper was written as the companion paper of the ICDT 2020 invited tutorial. Query determinacy is a broad topic, with literally hundreds of papers published since late 1980s. This paper is not going to be a "survey" but rather a personal perspective of a person somehow involved in the recent developments in the area. First I explain how, in the last 30+ years, the question of determinacy was formalized. There are many parameters here: obviously one needs to choose the query language of the available views and the query language of the query itself. But - surprisingly - there is also some choice regarding what the word "to compute" actually means in this context. Then I concentrate on certain variants of the decision problem of determinacy (for each choice of parameters there is one such problem) and explain how I understand the mechanisms rendering such variants of determinacy decidable or undecidable. This is on a rather informal level. No really new theorems are presented, but I show some improvements of existing theorems and also simplified proofs of some of the earlier results.
Subject Classification
ACM Subject Classification
- Theory of computation → Database theory
Keywords
- database theory
- query
- view
- determinacy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Foto N. Afrati. Determinacy and query rewriting for conjunctive queries and views. Theoretical Computer Science, 412(11):1005-1021, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.031.
-
Michael Benedikt, Stanislav Kikot, Piotr Ostropolski-Nalewaja, and Miguel Romero Orth. Unpublished manuscript, 2019.
- Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. What is View-Based Query Rewriting? In Proceedings of the 7th International Workshop on Knowledge Representation meets Databases (KRDB 2000), Berlin, Germany, August 21, 2000, pages 17-27, 2000. URL: http://ceur-ws.org/Vol-29/02-cdlv.ps.
- Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Lossless Regular Views. In Proceedings of the Twenty-first ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '02, pages 247-258, New York, NY, USA, 2002. ACM. URL: https://doi.org/10.1145/543613.543646.
-
Wenfei Fan, Floris Geerts, and Lixiao Zheng. View determinacy for preserving selected information in data transformations. Inf. Syst., 37:1-12, 2012.
- Grzegorz Gluch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja. Can One Escape Red Chains?: Regular Path Queries Determinacy is Undecidable. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '18, pages 492-501, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3209108.3209120.
- Grzegorz Gluch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja. The First Order Truth Behind Undecidability of Regular Path Queries Determinacy. In 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, pages 15:1-15:18, 2019. URL: https://doi.org/10.4230/LIPIcs.ICDT.2019.15.
- Tomasz Gogacz and Jerzy Marcinkowski. The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable. In Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), LICS '15, pages 281-292, Washington, DC, USA, 2015. IEEE Computer Society. URL: https://doi.org/10.1109/LICS.2015.35.
- Tomasz Gogacz and Jerzy Marcinkowski. Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '16, pages 121-134, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2902251.2902288.
- Per-Åke Larson and H. Z. Yang. Computing Queries from Derived Relations. In Proceedings of the 11th International Conference on Very Large Data Bases - Volume 11, VLDB '85, pages 259-269. VLDB Endowment, 1985. URL: http://dl.acm.org/citation.cfm?id=1286760.1286784.
-
Alan Nash, Luc Segoufin, and Victor Vianu. Determinacy and Rewriting of Conjunctive Queries Using Views: A Progress Report. In Thomas Schwentick and Dan Suciu, editors, Database Theory - ICDT 2007, pages 59-73, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
- Daniel Pasailă. Conjunctive Queries Determinacy and Rewriting. In Proceedings of the 14th International Conference on Database Theory, ICDT '11, pages 220-231, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1938551.1938580.
- Luc Segoufin and Victor Vianu. Views and queries: determinacy and rewriting. In Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 13-15, 2005, Baltimore, Maryland, USA, pages 49-60, 2005. URL: https://doi.org/10.1145/1065167.1065174.