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: 1817
Venue: PODS
Year: 2020
Pagerank: 5.3169677e-05
Overall Rank: 9,133 | 37.34%
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,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
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

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.00049907763
1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010893312
1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.9625097e-05
2,565	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.4116912e-05
5,773	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS	6.0926349e-05
7,088	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	5.7068548e-05

Semantically Similar Papers

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