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
1653
Venue
PODS
Year
2015
Pagerank
9.9625097e-05
Overall Rank
1,707 | 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,565 Database Repairs and Consistent Query Answering: Origins and Further Developments 2019 PODS 8.4116912e-05
4,303 Possible and Certain SQL Keys 2015 VLDB 6.7711902e-05
4,670 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 6.5734205e-05
5,619 An Operational Approach to Consistent Query Answering 2018 PODS 6.1483242e-05
5,773 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS 6.0926349e-05
5,844 A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join 2024 PODS 6.0687501e-05
5,943 ACID: A System for Computing Approximate Certain Query Answers over Incomplete Databases 2018 SIGMOD 6.0331149e-05
6,544 Properties of Inconsistency Measures for Databases 2021 SIGMOD 5.8461093e-05
6,674 Benchmarking Approximate Consistent Query Answering 2021 PODS 5.8066263e-05
7,558 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.5993651e-05
7,712 Uniform Operational Consistent Query Answering 2022 PODS 5.5612056e-05
8,038 Counting and Enumerating (Preferred) Database Repairs 2017 PODS 5.502256e-05
8,103 The Computation of Optimal Subset Repairs 2020 VLDB 5.4867244e-05
8,228 CAvSAT: A System for Query Answering over Inconsistent Databases 2019 SIGMOD 5.4621278e-05
9,133 First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys 2020 PODS 5.3169677e-05
9,480 CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving 2021 SIGMOD 5.2634238e-05
9,921 Combined Approximations for Uniform Operational Consistent Query Answering 2024 PODS 5.1955087e-05
10,650 Rewriting Consistent Answers on Annotated Data 2025 PODS 5.093636e-05
11,121 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS 5.093636e-05
11,146 Computing Range Consistent Answers to Aggregation Queries via Rewriting 2024 PODS 5.093636e-05
11,384 LinCQA: Faster Consistent Query Answering with Linear Time Guarantees 2023 SIGMOD 5.093636e-05
11,524 A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys 2022 PODS 5.093636e-05
11,969 Dichotomies in Ontology-Mediated Querying with the Guarded Fragment 2017 PODS 5.093636e-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