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.7180424e-05
Overall Rank
1,747 | 88.30%
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,610 Database Repairs and Consistent Query Answering: Origins and Further Developments 2019 PODS 8.2035758e-05
4,361 Possible and Certain SQL Keys 2015 VLDB 6.6271978e-05
4,769 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 6.4131333e-05
5,755 An Operational Approach to Consistent Query Answering 2018 PODS 5.9883541e-05
5,879 Properties of Inconsistency Measures for Databases 2021 SIGMOD 5.9438507e-05
5,907 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS 5.9344171e-05
5,980 A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join 2024 PODS 5.9101677e-05
6,083 ACID: A System for Computing Approximate Certain Query Answers over Incomplete Databases 2018 SIGMOD 5.8754816e-05
6,830 Benchmarking Approximate Consistent Query Answering 2021 PODS 5.6548934e-05
7,724 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4530482e-05
7,890 Uniform Operational Consistent Query Answering 2022 PODS 5.4158859e-05
8,217 Counting and Enumerating (Preferred) Database Repairs 2017 PODS 5.3599084e-05
8,301 The Computation of Optimal Subset Repairs 2020 VLDB 5.3433509e-05
8,415 CAvSAT: A System for Query Answering over Inconsistent Databases 2019 SIGMOD 5.3209056e-05
9,339 First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys 2020 PODS 5.1780302e-05
9,697 CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving 2021 SIGMOD 5.1258854e-05
10,144 Combined Approximations for Uniform Operational Consistent Query Answering 2024 PODS 5.0597449e-05
11,163 Rewriting Consistent Answers on Annotated Data 2025 PODS 4.9605343e-05
11,527 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 4.9605343e-05
11,552 Computing Range Consistent Answers to Aggregation Queries via Rewriting 2024 PODS 4.9605343e-05
11,751 LinCQA: Faster Consistent Query Answering with Linear Time Guarantees 2023 SIGMOD 4.9605343e-05
11,883 A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys 2022 PODS 4.9605343e-05
12,316 Dichotomies in Ontology-Mediated Querying with the Guarded Fragment 2017 PODS 4.9605343e-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