column

Consistent Query Answering for Primary Keys

Authors:

Paraschos Koutris,

Jef WijsenAuthors Info & Claims

ACM SIGMOD Record, Volume 45, Issue 1

Pages 15 - 22

https://doi.org/10.1145/2949741.2949746

Published: 02 June 2016 Publication History

Abstract

We study the complexity of consistent query answering with respect to primary key violations, for self-join-free conjunctive queries. A repair of a possibly inconsistent database is obtained by selecting a maximal number of tuples without selecting two distinct tuples with the same primary key value. For any Boolean query q, CERTAINTY(q) is the problem that takes a database as input, and asks whether q is true in every repair of the database. The complexity of this problem has been extensively studied for q ranging over the class of self-join-free Boolean conjunctive queries. A research challenge is to determine, given q, whether CERTAINTY(q) belongs to complexity classes FO, P, or coNP-complete. We show that for any self-join-free Boolean conjunctive query q, it can be decided whether or not CERTAINTY(q) is in FO. Further, CERTAINTY(q) is either in P or coNP-complete, and the complexity dichotomy is effective. This settles a research question of practical relevance that has been open for ten years.

References

[1]

M. Arenas, L. E. Bertossi, and J. Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68--79. ACM Press, 1999.

Digital Library

[2]

C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes. J. ACM, 30(3):479--513, 1983.

Digital Library

[3]

L. E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.

Digital Library

[4]

A. A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4):24, 2011.

Digital Library

[5]

J. Chomicki, J. Marcinkowski, and S. Staworko. Hippo: A system for computing consistent answers to a class of SQL queries. In E. Bertino et al., editors, EDBT, volume 2992 of Lecture Notes in Computer Science, pages 841--844. Springer, 2004.

[6]

G. Fontaine. Why is it hard to obtain a dichotomy for consistent query answering? In LICS, pages 550--559. IEEE Computer Society, 2013.

Digital Library

[7]

A. Fuxman, E. Fazli, and R. J. Miller. ConQuer: Efficient management of inconsistent databases. In F. Özcan, editor, SIGMOD Conference, pages 155--166. ACM, 2005.

Digital Library

[8]

A. Fuxman and R. J. Miller. First-order query rewriting for inconsistent databases. In T. Eiter and L. Libkin, editors, ICDT, volume 3363 of Lecture Notes in Computer Science, pages 337--351. Springer, 2005.

Digital Library

[9]

G. Greco, S. Greco, and E. Zumpano. A logical framework for querying and repairing inconsistent databases. IEEE Trans. Knowl. Data Eng., 15(6):1389--1408, 2003.

Digital Library

[10]

P. G. Kolaitis and E. Pema. A dichotomy in the complexity of consistent query answering for queries with two atoms. Inf. Process. Lett., 112(3):77--85, 2012.

Digital Library

[11]

P. G. Kolaitis, E. Pema, and W. Tan. Efficient querying of inconsistent databases with binary integer programming. PVLDB, 6(6):397--408, 2013.

Digital Library

[12]

P. Koutris and D. Suciu. A dichotomy on the complexity of consistent query answering for atoms with simple keys. In Schweikardt et al. {19}, pages 165--176.

[13]

P. Koutris and J. Wijsen. The data complexity of consistent query answering for self-join-free conjunctive queries under primary key constraints. In T. Milo and D. Calvanese, editors, PODS, pages 17--29. ACM, 2015.

Digital Library

[14]

P. Koutris and J. Wijsen. A trichotomy in the data complexity of certain query answering for conjunctive queries. CoRR, abs/1501.07864, 2015.

[15]

L. Libkin. Elements of Finite Model Theory. Springer, 2004.

Digital Library

[16]

D. Maslowski and J. Wijsen. A dichotomy in the complexity of counting database repairs. J. Comput. Syst. Sci., 79(6):958--983, 2013.

Digital Library

[17]

D. Maslowski and J. Wijsen. Counting database repairs that satisfy conjunctive queries with self-joins. In Schweikardt et al. {19}, pages 155--164.

[18]

G. J. Minty. On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory, Ser. B, 28(3):284--304, 1980.

[19]

N. Schweikardt, V. Christophides, and V. Leroy, editors. Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014. OpenProceedings.org, 2014.

[20]

J. Wijsen. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In J. Paredaens and D. V. Gucht, editors, PODS, pages 179--190. ACM, 2010.

Digital Library

[21]

J. Wijsen. A remark on the complexity of consistent conjunctive query answering under primary key violations. Inf. Process. Lett., 110(21):950--955, 2010.

Digital Library

[22]

J. Wijsen. Certain conjunctive query answering in first-order logic. ACM Trans. Database Syst., 37(2):9, 2012.

Digital Library

[23]

J. Wijsen. A survey of the data complexity of consistent query answering under key constraints. In C. Beierle and C. Meghini, editors, FoIKS, volume 8367 of Lecture Notes in Computer Science, pages 62--78. Springer, 2014.

Digital Library

Cited By

Dixit AKolaitis P(2022)Consistent Answers of Aggregation Queries via SAT2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00074(924-937)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00074
Dixit ABoncz PManegold SAilamaki ADeshpande AKraska T(2019)CAvSATProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3300095(1823-1825)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3300095
Greco SMolinaro CTrubitsyna I(2019)Approximation algorithms for querying incomplete databasesInformation Systems10.1016/j.is.2019.03.010Online publication date: Apr-2019
https://doi.org/10.1016/j.is.2019.03.010
Show More Cited By

Consistent Query Answering for Primary Keys
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys
PODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We study consistent query answering with respect to key dependencies. Given a (possibly inconsistent) database instance and a set of key dependencies, a repair is an inclusion-maximal subinstance that satisfies all key dependencies. Consistent query ...
Consistent Query Answering for Primary Keys on Path Queries
PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal consistent subset of the database. For a Boolean query q, the problem CERTAINTY(q) takes a database as ...
A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys
PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Since 2005, significant progress has been made in the problem of Consistent Query Answering (CQA) with respect to primary keys. In this problem, the input is a database instance that may violate one or more primary key constraints. A repair is defined ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 45, Issue 1

March 2016

73 pages

ISSN:0163-5808

DOI:10.1145/2949741

Editors:
Yanlei Diao
University of Massachusetts Amherst
,
Vanessa Braganholo
Universidade Federal Fluminense
,
Marco Brambilla
Politecnico di Milano
,
Chee Yong Chan
National University of Singapore
,
Rada Chirkova
North Carolina State University
,
Zackary Ives
University of Pennsylvania
,
Anastasios Kementsietsidis
Google Research
,
Jeffrey Naughton
University of Wisconsin-Madison
,
Olga Papaemmanoui
Brandeis Univesity
,
Aditya Parameswaran
University of Illinois
,
Anish Das Sarma
Google Research
,
Alkis Simitsis
HP Labs
,
Wang-Chiew Tan
University of California Santa Cruz
,
Nesime Tatbul
MIT CSAIL
,
Marianne Winslett
University of Illinois
,
Jun Yang
Duke University

Issue’s Table of Contents

Copyright © 2016 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2016

Published in SIGMOD Volume 45, Issue 1

Check for updates

Qualifiers

Column

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
137
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dixit AKolaitis P(2022)Consistent Answers of Aggregation Queries via SAT2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00074(924-937)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00074
Dixit ABoncz PManegold SAilamaki ADeshpande AKraska T(2019)CAvSATProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3300095(1823-1825)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3300095
Greco SMolinaro CTrubitsyna I(2019)Approximation algorithms for querying incomplete databasesInformation Systems10.1016/j.is.2019.03.010Online publication date: Apr-2019
https://doi.org/10.1016/j.is.2019.03.010
Balamuralikrishna NJiang YKoehler HLeck ULink SPrade H(2019)Possibilistic keysFuzzy Sets and Systems10.1016/j.fss.2019.01.008Online publication date: Jan-2019
https://doi.org/10.1016/j.fss.2019.01.008
Dixit AKolaitis P(2019)A SAT-Based System for Consistent Query AnsweringTheory and Applications of Satisfiability Testing – SAT 201910.1007/978-3-030-24258-9_8(117-135)Online publication date: 29-Jun-2019
https://doi.org/10.1007/978-3-030-24258-9_8
Koutris PWijsen J(2017)Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key ConstraintsACM Transactions on Database Systems10.1145/306833442:2(1-45)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1145/3068334
Geerts FPijcke FWijsen J(2017)First-order under-approximations of consistent query answersInternational Journal of Approximate Reasoning10.1016/j.ijar.2016.10.00583:C(337-355)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1016/j.ijar.2016.10.005
Koehler HLink SMukhopadhyay SZhai CBertino ECrestani FMostafa JTang JSi LZhou XChang YLi YSondhi P(2016)Qualitative Cleaning of Uncertain DataProceedings of the 25th ACM International on Conference on Information and Knowledge Management10.1145/2983323.2983679(2269-2274)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2983323.2983679

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents