Article

Why is it Hard to Obtain a Dichotomy for Consistent Query Answering?

Author:

Gaelle FontaineAuthors Info & Claims

LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

Pages 550 - 559

https://doi.org/10.1109/LICS.2013.62

Published: 25 June 2013 Publication History

Abstract

A database may for various reasons become inconsistent with respect to a given set of integrity constraints. To overcome the problem, a formal approach to querying such inconsistent databases has been proposed and since then, a lot of efforts have been spent to classify the complexity of consistent query answering under various classes of constraints. It is known that for the most common constraints and queries, the problem is in coNP and might be coNP-hard, yet several relevant tractable classes have been identified. Additionally, the results that emerged suggested that given a set of key constraints and a conjunctive query, the problem of consistent query answering is either in PTime or is coNP-complete. However, despite all the work, as of today this dichotomy remains a conjecture. The main contribution of this paper is to explain why it appears so difficult to obtain a dichotomy result in the setting of consistent query answering. Namely, we prove that such a dichotomy w.r.t.~common classes of constraints and queries, is harder to achieve than a dichotomy for the constraint satisfaction problem, which is a famous open problem since the 1990s.

References

[1]

F. N. Afrati and P. G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In ICDT, pages 31-41, 2009.

Digital Library

[2]

M. Arenas, P. Barcelo, L. Libkin, and F. Murlak. Relational and XML Data Exchange. Morgan and Claypool Publishers, 2010.

Digital Library

[3]

M. Arenas and L. E. Bertossi. On the decidability of consistent query answering. In AMW, 2010.

[4]

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

Digital Library

[5]

L. Barto. The dichotomy for conservative constraint satisfaction problems revisited. In LICS, pages 301-310, 2011.

Digital Library

[6]

L. E. Bertossi. Consistent query answering in databases. SIGMOD Record, 35(2):68-76, 2006.

Digital Library

[7]

A. A. Bulatov. Tractable conservative constraint satisfaction problems. In LICS, pages 321-, 2003.

Digital Library

[8]

A. A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, 2006.

Digital Library

[9]

A. A. Bulatov, A. A. Krokhin, and P. Jeavons. Constraint satisfaction problems and finite algebras. In ICALP, pages 272- 282, 2000.

Digital Library

[10]

D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi. View-based query processing and constraint satisfaction. In LICS, pages 361-371, 2000.

Digital Library

[11]

J. Chomicki. Consistent query answering: Five easy pieces. In ICDT, pages 1-17, 2007.

Digital Library

[12]

J. Chomicki and J. Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Inf. Comput., 197(1-2):90- 121, 2005.

Digital Library

[13]

R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. In ICDT, pages 207-224, 2003.

Digital Library

[14]

T. Feder and M. Y. Vardi. Monotone monadic snp and constraint satisfaction. In STOC, pages 612-622, 1993.

Digital Library

[15]

P. Jeavons, D. A. Cohen, and M. Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, 1997.

Digital Library

[16]

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

[17]

P. G. Kolaitis and M. Y. Vardi. Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci., 61(2):302-332, 2000.

Digital Library

[18]

R. E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, 1975.

Digital Library

[19]

M. Lenzerini. Data integration: A theoretical perspective. In PODS, pages 233-246, 2002.

Digital Library

[20]

T. J. Schaefer. The complexity of satisfiability problems. In STOC, pages 216-226, 1978.

Digital Library

[21]

S. Staworko. Declarative Inconsistencies Handling in Relational and Semi-structured Databases. PhD thesis, State University of New York at Buffalo, 2007.

Digital Library

[22]

S. Staworko and J. Chomicki. Consistent query answers in the presence of universal constraints. Information Systems, 35(1):1- 22, 2010.

Digital Library

[23]

B. ten Cate, G. Fontaine, and P. G. Kolaitis. On the data complexity of consistent query answering. In ICDT, pages 22-33, 2012.

Digital Library

[24]

J. Wijsen. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In PODS, pages 179-190, 2010.

Digital Library

Cited By

Koutris PWijsen JVan den Bussche JArenas M(2018)Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated AtomsProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196982(209-224)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196982
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
Koutris PWijsen J(2016)Consistent Query Answering for Primary KeysACM SIGMOD Record10.1145/2949741.294974645:1(15-22)Online publication date: 2-Jun-2016
https://dl.acm.org/doi/10.1145/2949741.2949746
Show More Cited By

Why is it Hard to Obtain a Dichotomy for Consistent Query Answering?
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

Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering?

A database may for various reasons become inconsistent with respect to a given set of integrity constraints. In the late 1990s, the formal approach of consistent query answering was proposed in order to query such databases. Since then, a lot of efforts ...
A dichotomy in the complexity of consistent query answering for queries with two atoms

We establish a dichotomy in the complexity of computing the consistent answers of a Boolean conjunctive query with exactly two atoms and without self-joins. Specifically, we show that the problem of computing the consistent answers of such a query ...
On the tractability and intractability of consistent conjunctive query answering
PhD '11: Proceedings of the 2011 Joint EDBT/ICDT Ph.D. Workshop

The consistent query answering framework has received considerable attention since it was first introduced as an alternative to coping with inconsistent databases. The framework was defined based on two notions: repairs and consistent query answers. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

June 2013

597 pages

ISBN:9780769550206

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

IEEE Computer Society

United States

Publication History

Published: 25 June 2013

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 215 of 622 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
29
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Koutris PWijsen JVan den Bussche JArenas M(2018)Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated AtomsProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196982(209-224)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196982
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
Koutris PWijsen J(2016)Consistent Query Answering for Primary KeysACM SIGMOD Record10.1145/2949741.294974645:1(15-22)Online publication date: 2-Jun-2016
https://dl.acm.org/doi/10.1145/2949741.2949746
Combi CSala P(2016)Mining approximate interval-based temporal dependenciesActa Informatica10.1007/s00236-015-0246-x53:6-8(547-585)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00236-015-0246-x
Pfandler ASallinger E(2015)Distance-bounded consistent query answeringProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832415.2832563(2262-2269)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832415.2832563
Koutris PWijsen JMilo TCalvanese D(2015)The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key ConstraintsProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2745754.2745769(17-29)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2745754.2745769
Fagin RKimelfeld BKolaitis PMilo TCalvanese D(2015)Dichotomies in the Complexity of Preferred RepairsProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2745754.2745762(3-15)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2745754.2745762
Fontaine G(2015)Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering?ACM Transactions on Computational Logic10.1145/269991216:1(1-24)Online publication date: 24-Mar-2015
https://dl.acm.org/doi/10.1145/2699912
Wijsen J(2014)A Survey of the Data Complexity of Consistent Query Answering under Key ConstraintsProceedings of the 8th International Symposium on Foundations of Information and Knowledge Systems - Volume 836710.1007/978-3-319-04939-7_2(62-78)Online publication date: 3-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-319-04939-7_2

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 Table of Contents