First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys

Summary: Extends consistent query answering under key dependencies to schemas allowing multiple keys per relation, focusing on self-join-free Boolean conjunctive queries. Proves decidability of FO-rewritability and provides an effective procedure to construct an FO rewriting when one exists. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h26748c79c75cc3df
Venue: PODS
Year: 2020
Pagerank: 5.1976693e-05
Overall Rank: 9,305 | 37.44%
DOI: 10.1145/3375395.3387654

Incoming Non-self Citations Over Time

Authors

1. Paraschos Koutris (University of Wisconsin)
2. Jef Wijsen (University of Mons)

BibTeX Citation

@inproceedings{koutris_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3387654},
        doi = {10.1145/3375395.3387654},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koutris, Paraschos and Wijsen, Jef},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
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

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.00049349003
1,361	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010917917
1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.7545681e-05
2,613	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.2260448e-05
5,892	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS	5.956925e-05
7,230	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	5.5795492e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,793	Charting the Tractability Frontier of Certain Conjunctive Query Answering	2013	PODS
2	897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
3	7,230	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS
4	1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
5	12,501	Certain Query Answering in Partially Consistent Databases	2014	VLDB
6	11,833	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS
7	11,469	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
8	7,705	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS
9	5,892	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS
10	11,093	Rewriting Consistent Answers on Annotated Data	2025	PODS