Consistent Query Answering for Primary Keys on Path Queries

Summary: Study data complexity of CERTAINTY(q) for Boolean path queries under primary-key violations with repairs as maximal consistent subsets. Show a tetrachotomy (FO, NL-complete, PTIME-complete, coNP-complete) when self-joins are allowed, and give a polynomial-time procedure to decide which case applies from the query. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1861
Venue: PODS
Year: 2021
Pagerank: 5.5993651e-05
Overall Rank: 7,558 | 48.15%
DOI: 10.1145/3452021.3458334

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@inproceedings{koutris_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Consistent Query Answering for Primary Keys on Path Queries}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458334},
        doi = {10.1145/3452021.3458334},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koutris, Paraschos and Ouyang, Xiating and Wijsen, Jef},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,844	A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join	2024	PODS	6.0687501e-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 10 of 10 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
636	Answering Conjunctive Queries under Updates	2017	PODS	0.0001551856
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,551	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	8.4290374e-05
2,565	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.4116912e-05
3,991	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.9695922e-05
4,670	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.5734205e-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
9,133	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	5.3169677e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,619	An Operational Approach to Consistent Query Answering	2018	PODS
2	9,921	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS
3	7,712	Uniform Operational Consistent Query Answering	2022	PODS
4	12,210	Certain Query Answering in Partially Consistent Databases	2014	VLDB
5	5,258	Counting Database Repairs under Primary Keys Revisited	2019	PODS
6	5,844	A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join	2024	PODS
7	5,773	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS
8	11,524	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS
9	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
10	11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS