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.7499517e-05
Overall Rank
1,737 | 88.33%
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,614 Database Repairs and Consistent Query Answering: Origins and Further Developments 2019 PODS 8.2221507e-05
4,342 Possible and Certain SQL Keys 2015 VLDB 6.6478954e-05
4,750 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 6.4344094e-05
5,743 An Operational Approach to Consistent Query Answering 2018 PODS 6.0079668e-05
5,866 Properties of Inconsistency Measures for Databases 2021 SIGMOD 5.96357e-05
5,892 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS 5.9541051e-05
5,967 A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join 2024 PODS 5.9297752e-05
6,068 ACID: A System for Computing Approximate Certain Query Answers over Incomplete Databases 2018 SIGMOD 5.8949741e-05
6,814 Benchmarking Approximate Consistent Query Answering 2021 PODS 5.6736541e-05
7,711 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4711392e-05
7,874 Uniform Operational Consistent Query Answering 2022 PODS 5.4338536e-05
8,202 Counting and Enumerating (Preferred) Database Repairs 2017 PODS 5.3774362e-05
8,286 The Computation of Optimal Subset Repairs 2020 VLDB 5.361078e-05
8,396 CAvSAT: A System for Query Answering over Inconsistent Databases 2019 SIGMOD 5.3385571e-05
9,314 First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys 2020 PODS 5.1952088e-05
9,668 CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving 2021 SIGMOD 5.142891e-05
10,108 Combined Approximations for Uniform Operational Consistent Query Answering 2024 PODS 5.0765311e-05
11,102 Rewriting Consistent Answers on Annotated Data 2025 PODS 4.9769913e-05
11,475 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9769913e-05
11,500 Computing Range Consistent Answers to Aggregation Queries via Rewriting 2024 PODS 4.9769913e-05
11,705 LinCQA: Faster Consistent Query Answering with Linear Time Guarantees 2023 SIGMOD 4.9769913e-05
11,839 A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys 2022 PODS 4.9769913e-05
12,273 Dichotomies in Ontology-Mediated Querying with the Guarded Fragment 2017 PODS 4.9769913e-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