DBScholar

Back to papers

The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints

Summary: Effective complexity classification of CERTAINTY(q) for self-join-free Boolean conjunctive queries under primary-key constraints: FO-membership decidable and an effective P vs coNP-complete dichotomy. Settles a decade-old open problem by combining and extending prior techniques. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h3b86d6fae3949fab
Venue
PODS
Year
2015
Pagerank
9.7545681e-05
Overall Rank
1,735 | 88.34%
DOI
10.1145/2745754.2745769

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{koutris_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745769},
        doi = {10.1145/2745754.2745769},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koutris, Paraschos and Wijsen, Jef},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank Citing Paper Year Venue Pagerank
2,613 Database Repairs and Consistent Query Answering: Origins and Further Developments 2019 PODS 8.2260448e-05
4,342 Possible and Certain SQL Keys 2015 VLDB 6.6510065e-05
4,747 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 6.4374568e-05
5,742 An Operational Approach to Consistent Query Answering 2018 PODS 6.0108123e-05
5,864 Properties of Inconsistency Measures for Databases 2021 SIGMOD 5.9663944e-05
5,892 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS 5.956925e-05
5,965 A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join 2024 PODS 5.9325836e-05
6,067 ACID: A System for Computing Approximate Certain Query Answers over Incomplete Databases 2018 SIGMOD 5.897766e-05
6,808 Benchmarking Approximate Consistent Query Answering 2021 PODS 5.6763412e-05
7,705 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4737304e-05
7,869 Uniform Operational Consistent Query Answering 2022 PODS 5.4364271e-05
8,194 Counting and Enumerating (Preferred) Database Repairs 2017 PODS 5.379983e-05
8,280 The Computation of Optimal Subset Repairs 2020 VLDB 5.363617e-05
8,392 CAvSAT: A System for Query Answering over Inconsistent Databases 2019 SIGMOD 5.3410855e-05
9,305 First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys 2020 PODS 5.1976693e-05
9,661 CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving 2021 SIGMOD 5.1453267e-05
10,104 Combined Approximations for Uniform Operational Consistent Query Answering 2024 PODS 5.0789354e-05
11,093 Rewriting Consistent Answers on Annotated Data 2025 PODS 4.9793485e-05
11,469 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9793485e-05
11,494 Computing Range Consistent Answers to Aggregation Queries via Rewriting 2024 PODS 4.9793485e-05
11,699 LinCQA: Faster Consistent Query Answering with Linear Time Guarantees 2023 SIGMOD 4.9793485e-05
11,833 A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys 2022 PODS 4.9793485e-05
12,267 Dichotomies in Ontology-Mediated Querying with the Guarded Fragment 2017 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Previous Page 1 / 1 Next

Semantically Similar Papers