Counting Database Repairs under Primary Keys Revisited

Summary: Refines the data complexity of counting database repairs under primary keys: known #P-complete under Cook reductions but potentially "hard-to-count-easy-to-decide" and not #P-complete under standard many-one logspace reductions. Performs a finer-grained classification by seeking membership and completeness in natural subclasses of #P under parsimonious (logspace many-one) reductions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1765
Venue: PODS
Year: 2019
Pagerank: 5.5481038e-05
Overall Rank: 5,360 | 62.72%
DOI: 10.1145/3294052.3319703

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,739	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9449088e-05
7,667	Fast Detection of Denial Constraint Violations	2022	VLDB	4.683767e-05
7,703	Uniform Operational Consistent Query Answering	2022	PODS	4.673644e-05
8,132	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5784634e-05
8,145	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5761263e-05
8,261	Counting Problems over Incomplete Databases	2020	PODS	4.5483999e-05
9,748	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2897489e-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,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 2 of 2 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
627	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018959005

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,705	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9549359e-05
7,703	Uniform Operational Consistent Query Answering	2022	PODS	4.673644e-05
6,739	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9449088e-05
10,928	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS	4.1945683e-05
9,748	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2897489e-05
8,132	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5784634e-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
11,325	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS	4.1945683e-05
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05
7,069	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8438319e-05