Inconsistent Data Management
We develop fundamental approaches to managing data quality in inconsistent databases
Managing data quality, and particularly data inconsistency, has been one of the major challenges in the research and practice of database management. Sources of inconsistency include imprecise processes of data generation such as mistakes in manual form filling and noisy sensing equipment, as well as data integration where different source databases may contain conflicting information. This problem becomes even more important and central to data management in modern times, where data repositories are increasingly based on imprecise processes (e.g., crowdsourcing and information extraction from natural language) and integration of repositories with varying levels of reliability. In our research, we aim to develop fundamental approaches to managing data quality, including ways to clean, query, and measure the error level in inconsistent databases.
People
- Prof. Benny Kimelfeld
- Ester Livshits alumnus
- Muhammad Tibi alumnus
Publications
-
Analyzing Deviations from Monotonic Trends through Database Repair
SIGMOD 2026: 1-27
-
Stress-Testing Causal Claims via Cardinality Repairs
SIGMOD 2026: 1-24
-
Computing Inconsistency Measures Under Differential Privacy
SIGMOD 2025: 1-27
-
Repairing Databases over Metric Spaces with Coincidence Constraints
ICDT 2025
-
The Cost of Representation by Subset Repairs
VLDB 2025
-
A Unifying Framework for Incompleteness, Inconsistency, and Uncertainty in Databases
Communications of the ACM 67(3): 74-83 (2024)
-
Database Repairing with Soft Functional Dependencies
ACM TODS 2024
-
Counting Subset Repairs with Functional Dependencies
J. Comput. Syst. Sci. 117: 154-164 (2021)
-
Database Repairing with Soft Functional Dependencies
ICDT 2021
-
Properties of Inconsistency Measures for Databases
SIGMOD 2021: 1182-1194
-
The Shapley Value of Inconsistency Measures for Functional Dependencies
ICDT 2021
-
Approximate Denial Constraints
PVLDB 13: 1682-1695 (2020)
-
Counting and Enumerating Preferred Database Repairs
Theor. Comput. Sci. 2020
-
A Formal Framework For Probabilistic Unclean Databases
ICDT 2019
Abstract
Most theoretical frameworks that focus on data errors and inconsistencies follow logic-based reasoning. Yet, practical data cleaning tools need to incorporate statistical reasoning to be effective in real-world data cleaning tasks. Motivated by these empirical successes, we propose a formal framework for unclean databases, where two types of statistical knowledge are incorporated: The first represents a belief of how intended (clean) data is generated, and the second represents a belief of how noise is introduced in the actual observed database instance.
To capture this noisy channel model, we introduce the concept of a Probabilistic Unclean Database, a triple that consists of a probabilistic database that we call the intention, a probabilistic data transformator that we call the realization and captures how noise is introduced, and a dirty observed database instance that we call the observation. We define three computational problems in the PUD framework: cleaning (infer the most probable clean instance given a PUD), probabilistic query answering (compute the probability of an answer tuple over the unclean observed instance), and learning (estimate the most likely intention and realization models of a PUD given a collection of training data). We illustrate the PUD framework on concrete representations of the intention and realization, show that they generalize traditional concepts of repairs such as cardinality and value repairs, draw connection to consistent query answering, and prove tractability results. We further show that parameters can be learned in practical instantiations, and in fact, prove that under certain conditions we can learn a PUD directly from a single dirty database instance without any need for clean examples.
-
Computing Optimal Repairs for Functional Dependencies
PODS 2018: 225-237
Abstract
We investigate the complexity of computing an optimal repair of an inconsistent database, in the case where integrity constraints are Functional Dependencies (FDs). We focus on two types of repairs: an optimal subset repair (optimal S-repair) that is obtained by a minimum number of tuple deletions, and an optimal update repair (optimal U-repair) that is obtained by a minimum number of value (cell) updates. For computing an optimal S-repair, we present a polynomial-time algorithm that succeeds on certain sets of FDs and fails on others. We prove the following about the algorithm. When it succeeds, it can also incorporate weighted tuples and duplicate tuples. When it fails, the problem is NP-hard, and in fact, APX-complete (hence, cannot be approximated better than some constant). Thus, we establish a dichotomy in the complexity of computing an optimal Srepair. We present general analysis techniques for the complexity of computing an optimal U-repair, some based on the dichotomy for S-repairs. We also draw a connection to a past dichotomy in the complexity of finding a “most probable database” that satisfies a set of FDs with a single attribute on the left hand side; the case of general FDs was left open, and we show how our dichotomy provides the missing generalization and thereby settles the open problem.
-
Counting and Enumerating (Preferred) Database Repairs
PODS 2017: 289-301
Enumeration Algorithms Inconsistent Data Management
Abstract
In the traditional sense, a subset repair of an inconsistent database refers to a consistent subset of facts (tuples) that is maximal under set containment. Preferences between pairs of facts allow to distinguish a set of preferred repairs based on relative reliability (source credibility, extraction quality, recency, etc.) of data items. Previous studies explored the problem of categoricity, where one aims to determine whether preferences suffice to repair the database unambiguously, or in other words, whether there is precisely one preferred repair. In this paper we study the ability to quantify ambiguity, by investigating two classes of problems. The first is that of counting the number of subset repairs, both preferred (under various common semantics) and traditional. We establish dichotomies in data complexity for the entire space of (sets of) functional dependencies. The second class of problems is that of enumerating (i.e., generating) the preferred repairs. We devise enumeration algorithms with efficiency guarantees on the delay between generated repairs, even for constraints represented as general conflict graphs or hypergraphs.
-
Detecting Ambiguity in Prioritized Database Repairing
ICDT 2017: 17:1-17:20
Inconsistent Data Management Preference Data Management
Abstract
In its traditional definition, a repair of an inconsistent database is a consistent database that differs from the inconsistent one in a “minimal way.” Often, repairs are not equally legitimate, as it is desired to prefer one over another; for example, one fact is regarded more reliable than another, or a more recent fact should be preferred to an earlier one. Motivated by these considerations, researchers have introduced and investigated the framework of preferred repairs, in the context of denial constraints and subset repairs. There, a priority relation between facts is lifted towards a priority relation between consistent databases, and repairs are restricted to the ones that are optimal in the lifted sense. Three notions of lifting (and optimal repairs) have been proposed: Pareto, global, and completion. In this paper we investigate the complexity of deciding whether the priority relation suffices to clean the database unambiguously, or in other words, whether there is exactly one optimal repair. We show that the different lifting semantics entail highly different complexities. Under Pareto optimality, the problem is coNP-complete, in data complexity, for every set of functional dependencies (FDs), except for the tractable case of (equivalence to) one FD per relation. Under global optimality, one FD per relation is still tractable, but we establish Pi-2-p-completeness for a relation with two FDs. In contrast, under completion optimality the problem is solvable in polynomial time for every set of FDs. In fact, we present a polynomial-time algorithm for arbitrary conflict hypergraphs. We further show that under a general assumption of transitivity, this algorithm solves the problem even for global optimality. The algorithm is extremely simple, but its proof of correctness is quite intricate.