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: 1829
Venue: PODS
Year: 2021
Pagerank: 4.8438319e-05
Overall Rank: 7,069 | 50.83%
DOI: 10.1145/3452021.3458334

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,112	A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join	2024	PODS	5.2048658e-05
10,357	Rewriting Consistent Answers on Annotated Data	2025	PODS	4.1945683e-05
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05
10,928	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS	4.1945683e-05
11,178	LinCQA: Faster Consistent Query Answering with Linear Time Guarantees	2023	SIGMOD	4.1945683e-05
11,325	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
2,566	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5243847e-05
3,524	Efficient Querying of Inconsistent Databases with Binary Integer Programming	2013	VLDB	7.0087032e-05
4,361	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.2559141e-05
4,937	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8187108e-05
7,063	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS	4.8461152e-05
8,970	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	4.4188963e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,739	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9449088e-05
8,970	First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys	2020	PODS	4.4188963e-05
9,748	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2897489e-05
7,703	Uniform Operational Consistent Query Answering	2022	PODS	4.673644e-05
12,012	Certain Query Answering in Partially Consistent Databases	2014	VLDB	4.1945683e-05
5,360	Counting Database Repairs under Primary Keys Revisited	2019	PODS	5.5481038e-05
6,112	A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join	2024	PODS	5.2048658e-05
11,325	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS	4.1945683e-05
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05