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.6690279e-05
Overall Rank: 7,701 | 46.48%
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,574	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5126812e-05
6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.013741e-05
8,148	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5717374e-05
8,839	The Cost of Representation by Subset Repairs	2025	VLDB	4.4346105e-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.00067607389
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013373177
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
2,864	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	7.9964194e-05
3,045	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.6618214e-05
4,973	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7882537e-05
5,137	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.6653126e-05
5,406	Cleaning Inconsistencies in Information Extraction via Prioritized Repairs	2014	PODS	5.5239588e-05
5,565	Determining the Currency of Data	2011	PODS	5.4298528e-05
8,088	Determining the Relative Accuracy of Attributes	2013	SIGMOD	4.5856065e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
12,020	Certain Query Answering in Partially Consistent Databases	2014	VLDB	4.1905499e-05
5,370	Counting Database Repairs under Primary Keys Revisited	2019	PODS	5.5427744e-05
8,014	The Computation of Optimal Subset Repairs	2020	VLDB	4.6020746e-05
2,830	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0515409e-05
8,839	The Cost of Representation by Subset Repairs	2025	VLDB	4.4346105e-05
268	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029739054
6,707	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9500448e-05
8,134	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5740737e-05
3,045	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.6618214e-05