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.5427744e-05
Overall Rank: 5,370 | 62.68%
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,740	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9401646e-05
7,666	Fast Detection of Denial Constraint Violations	2022	VLDB	4.6792751e-05
7,700	Uniform Operational Consistent Query Answering	2022	PODS	4.6691622e-05
8,134	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5740737e-05
8,148	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5717374e-05
8,256	Counting Problems over Incomplete Databases	2020	PODS	4.5440379e-05
9,747	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2856385e-05
10,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
10,931	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS	4.1905499e-05
11,327	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS	4.1905499e-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.00067607389
630	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018942778

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,707	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9500448e-05
7,700	Uniform Operational Consistent Query Answering	2022	PODS	4.6691622e-05
6,740	Benchmarking Approximate Consistent Query Answering	2021	PODS	4.9401646e-05
10,931	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS	4.1905499e-05
9,747	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS	4.2856385e-05
8,134	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5740737e-05
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
11,327	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS	4.1905499e-05
10,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
7,064	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8391823e-05