LIPIcs.ICDT.2019.23.pdf
- Filesize: 0.62 MB
- 19 pages
Document
Consistent Query Answering for Primary Keys in Logspace
Authors
-
Part of:
Volume:
22nd International Conference on Database Theory (ICDT 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Database Theory (ICDT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-03-19
Cite AsGet BibTex
Paraschos Koutris and Jef Wijsen. Consistent Query Answering for Primary Keys in Logspace. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICDT.2019.23
https://doi.org/10.4230/LIPIcs.ICDT.2019.23
Abstract
We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q, CERTAINTY(q) is the problem that takes a database as input and asks whether q evaluates to true on every repair. In [Koutris and Wijsen, ACM TODS, 2017], the authors show that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either in P or coNP-complete, and it is decidable which of the two cases applies. In this paper, we sharpen this result by showing that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either expressible in symmetric stratified Datalog (with some aggregation operator) or coNP-complete. Since symmetric stratified Datalog is in L, we thus obtain a complexity-theoretic dichotomy between L and coNP-complete. Another new finding of practical importance is that CERTAINTY(q) is on the logspace side of the dichotomy for queries q where all join conditions express foreign-to-primary key matches, which is undoubtedly the most common type of join condition.
Subject Classification
ACM Subject Classification
- Information systems → Relational database model
- Information systems → Inconsistent data
- Information systems → Incomplete data
- Information systems → Integrity checking
Keywords
- conjunctive queries
- consistent query answering
- Datalog
- primary keys
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
- Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent Query Answers in Inconsistent Databases. In ACM PODS, pages 68-79, 1999. URL: http://dx.doi.org/10.1145/303976.303983.
- Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki, Xin He, Vijay Raghavan, and Jeremy P. Spinrad. Scalar aggregation in inconsistent databases. Theor. Comput. Sci., 296(3):405-434, 2003. URL: http://dx.doi.org/10.1016/S0304-3975(02)00737-5.
- Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. Inf. Process. Lett., 8(3):121-123, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90002-4.
- Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler. An Introduction to Description Logic. Cambridge University Press, 2017. URL: http://www.cambridge.org/de/academic/subjects/computer-science/knowledge-management-databases-and-data-mining/introduction-description-logic?format=PB#17zVGeWD2TZUeu6s.97.
- Pablo Barceló and Gaëlle Fontaine. On the data complexity of consistent query answering over graph databases. J. Comput. Syst. Sci., 88:164-194, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2017.03.015.
- Leopoldo E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. URL: http://dx.doi.org/10.2200/S00379ED1V01Y201108DTM020.
- Meghyn Bienvenu and Camille Bourgaux. Inconsistency-Tolerant Querying of Description Logic Knowledge Bases. In Jeff Z. Pan, Diego Calvanese, Thomas Eiter, Ian Horrocks, Michael Kifer, Fangzhen Lin, and Yuting Zhao, editors, Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering - 12th International Summer School 2016, Aberdeen, UK, September 5-9, 2016, Tutorial Lectures, volume 9885 of Lecture Notes in Computer Science, pages 156-202. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49493-7_5.
- Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4):24:1-24:66, 2011. URL: http://dx.doi.org/10.1145/1970398.1970400.
- László Egri, Benoit Larose, and Pascal Tesson. Symmetric Datalog and Constraint Satisfaction Problems in Logspace. In LICS, pages 193-202, 2007. URL: http://dx.doi.org/10.1109/LICS.2007.47.
- László Egri, Benoit Larose, and Pascal Tesson. Directed st-Connectivity Is Not Expressible in Symmetric Datalog. In ICALP, pages 172-183, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70583-3_15.
- Gaëlle Fontaine. Why is it Hard to Obtain a Dichotomy for Consistent Query Answering? In LICS, pages 550-559, 2013. URL: http://dx.doi.org/10.1109/LICS.2013.62.
- Ariel Fuxman and Renée J. Miller. First-Order Query Rewriting for Inconsistent Databases. In ICDT, pages 337-351, 2005. URL: http://dx.doi.org/10.1007/978-3-540-30570-5_23.
- Ariel Fuxman and Renée J. Miller. First-order query rewriting for inconsistent databases. J. Comput. Syst. Sci., 73(4):610-635, 2007. URL: http://dx.doi.org/10.1016/j.jcss.2006.10.013.
- Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, and Scott Weinstein. Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2007. URL: http://dx.doi.org/10.1007/3-540-68804-8.
- Sergio Greco, Fabian Pijcke, and Jef Wijsen. Certain Query Answering in Partially Consistent Databases. PVLDB, 7(5):353-364, 2014. URL: http://www.vldb.org/pvldb/vol7/p353-greco.pdf, URL: http://dx.doi.org/10.14778/2732269.2732272.
- Martin Grohe and Thomas Schwentick. Locality of order-invariant first-order formulas. ACM Trans. Comput. Log., 1(1):112-130, 2000. URL: http://dx.doi.org/10.1145/343369.343386.
- Phokion G. Kolaitis, Enela Pema, and Wang-Chiew Tan. Efficient Querying of Inconsistent Databases with Binary Integer Programming. PVLDB, 6(6):397-408, 2013. URL: http://www.vldb.org/pvldb/vol6/p397-tan.pdf, URL: http://dx.doi.org/10.14778/2536336.2536341.
- Paraschos Koutris and Jef Wijsen. The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. In PODS, pages 17-29, 2015. URL: http://dx.doi.org/10.1145/2745754.2745769.
- Paraschos Koutris and Jef Wijsen. Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. ACM Trans. Database Syst., 42(2):9:1-9:45, 2017. URL: http://dx.doi.org/10.1145/3068334.
- Paraschos Koutris and Jef Wijsen. Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms. In PODS, pages 209-224, 2018. URL: http://dx.doi.org/10.1145/3196959.3196982.
- Paraschos Koutris and Jef Wijsen. Consistent Query Answering for Primary Keys in Logspace. CoRR, abs/1810.03386, 2018. URL: http://arxiv.org/abs/1810.03386.
- Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant query answering in ontology-based data access. J. Web Sem., 33:3-29, 2015. URL: http://dx.doi.org/10.1016/j.websem.2015.04.002.
- Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-662-07003-1.
- Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. In ACM-SIAM SODA, pages 1236-1252, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.80.
- Carsten Lutz and Frank Wolter. On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems. In ICDT, pages 363-379, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2015.363.
- Mónica Caniupán Marileo and Leopoldo E. Bertossi. The consistency extractor system: Answer set programs for consistent query answering in databases. Data Knowl. Eng., 69(6):545-572, 2010. URL: http://dx.doi.org/10.1016/j.datak.2010.01.005.
- Dany Maslowski and Jef Wijsen. A dichotomy in the complexity of counting database repairs. J. Comput. Syst. Sci., 79(6):958-983, 2013. URL: http://dx.doi.org/10.1016/j.jcss.2013.01.011.
- Dany Maslowski and Jef Wijsen. Counting Database Repairs that Satisfy Conjunctive Queries with Self-Joins. In ICDT, pages 155-164, 2014. URL: http://dx.doi.org/10.5441/002/icdt.2014.18.
-
Fabian Pijcke. Theoretical and Practical Methods for Consistent Query Answering in the Relational Data Model. PhD thesis, University of Mons, 2018.
- Piotr Przymus, Aleksandra Boniewicz, Marta Burzanska, and Krzysztof Stencel. Recursive Query Facilities in Relational Databases: A Survey. In FGIT, pages 89-99, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17622-7_10.
- Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1-17:24, 2008. URL: http://dx.doi.org/10.1145/1391289.1391291.
- Jef Wijsen. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In PODS, pages 179-190, 2010. URL: http://dx.doi.org/10.1145/1807085.1807111.
- Jef Wijsen. Certain conjunctive query answering in first-order logic. ACM Trans. Database Syst., 37(2):9:1-9:35, 2012. URL: http://dx.doi.org/10.1145/2188349.2188351.
- Jef Wijsen. A Survey of the Data Complexity of Consistent Query Answering under Key Constraints. In FoIKS, pages 62-78, 2014. URL: http://dx.doi.org/10.1007/978-3-319-04939-7_2.