DBScholar

Back to papers

On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases

Summary: Characterize when CERTAINTY(q) is FO-expressible for Boolean conjunctive queries over key-violating (uncertain) databases, giving a necessary syntactic condition for queries without self‑join. For acyclic CQs the condition is also sufficient, yielding a decision procedure and a constructive FO‑rewriting (hence AC0). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
ha7435113564f3692
Venue
PODS
Year
2010
Pagerank
5.5769079e-05
Overall Rank
7,232 | 51.40%
DOI
10.1145/1807085.1807111

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{wijsen_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807111},
        doi = {10.1145/1807085.1807111},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Wijsen, Jef},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank Citing Paper Year Venue Pagerank
1,737 The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints 2015 PODS 9.7499517e-05
4,870 Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers 2019 SIGMOD 6.3718189e-05
5,892 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS 5.9541051e-05
7,711 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS 5.4711392e-05
8,396 CAvSAT: A System for Query Answering over Inconsistent Databases 2019 SIGMOD 5.3385571e-05
8,435 Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds 2021 SIGMOD 5.3324907e-05
8,801 Charting the Tractability Frontier of Certain Conjunctive Query Answering 2013 PODS 5.2735778e-05
9,314 First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys 2020 PODS 5.1952088e-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,507 Certain Query Answering in Partially Consistent Databases 2014 VLDB 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.

Rank Cited Paper Year Venue Pagerank
33 Consistent Query Answers in Inconsistent Databases 1999 PODS 0.00049326063
595 ConQuer: Efficient Management of Inconsistent Databases 2005 SIGMOD 0.00015791577
2,806 MayBMS: A Probabilistic Database Management System 2009 SIGMOD 7.9800849e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,711 Consistent Query Answering for Primary Keys on Path Queries 2021 PODS
2 11,839 A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys 2022 PODS
3 11,102 Rewriting Consistent Answers on Annotated Data 2025 PODS
4 5,370 Certain Answers Meet Zero-One Laws 2018 PODS
5 9,314 First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys 2020 PODS
6 11,475 Consistent Query Answering for Primary Keys on Rooted Tree Queries 2024 PODS
7 5,892 Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms 2018 PODS
8 1,737 The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints 2015 PODS
9 8,801 Charting the Tractability Frontier of Certain Conjunctive Query Answering 2013 PODS
10 12,507 Certain Query Answering in Partially Consistent Databases 2014 VLDB