Counting and Enumerating (Preferred) Database Repairs

Summary: Establishes data-complexity dichotomies for counting subset repairs (traditional and preference-based under common semantics) across the entire space of functional dependencies. Provides delay-guaranteed enumeration algorithms for preferred repairs even under general conflict graphs/hypergraphs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1719
Venue: PODS
Year: 2017
Pagerank: 4.6736471e-05
Overall Rank: 7,702 | 46.42%
DOI: 10.1145/3034786.3056107

Incoming Non-self Citations Over Time

Authors

1. Ester Livshits
2. Benny Kimelfeld

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,566	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5243847e-05
6,546	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.0185588e-05
8,145	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5761263e-05
8,840	The Cost of Representation by Subset Repairs	2025	VLDB	4.4388652e-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
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013390321
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,857	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	8.0037703e-05
3,042	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.669374e-05
4,971	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7938195e-05
5,141	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.6673499e-05
5,398	Cleaning Inconsistencies in Information Extraction via Prioritized Repairs	2014	PODS	5.5295577e-05
5,557	Determining the Currency of Data	2011	PODS	5.435361e-05
8,086	Determining the Relative Accuracy of Attributes	2013	SIGMOD	4.5899469e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-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
7,605	The Computation of Optimal Subset Repairs	2020	VLDB	4.697534e-05
2,823	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0593894e-05
8,840	The Cost of Representation by Subset Repairs	2025	VLDB	4.4388652e-05
265	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029763412
6,705	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9549359e-05
8,132	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5784634e-05
3,042	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.669374e-05