On approximating optimum repairs for functional dependency violations

By Solmaz Kolahi, Laks V. S. Lakshmanan. 2009

209 citations recorded by the source corpus.

We study the problem of repairing an inconsistent database that violates a set of functional dependencies by making the smallest possible value modifications. For an inconsistent database, we define an optimum repair as a database that satisfies the functional dependencies, and minimizes, among all repairs, a distance measure that depends on the number of corrections made in the database and the weights of tuples modified. We show that like other versions of the repair problem, checking the existence of a repair within a certain distance of a database is NP-complete. We also show that finding a constant-factor approximation for the optimum repair for any set of functional dependencies is NP-hard. Furthermore, there is a small constant and a set of functional dependencies, for which finding an approximate solution for the optimum repair within the factor of that constant is also NP-hard. Then we present an approximation algorithm that for a fixed set of functional dependencies and an arbitrary input inconsistent database, produces a repair whose distance to the database is within a constant factor of the optimum repair distance. We finally show how the approximation algorithm can be used in data cleaning using a recent extension to functional dependencies, called conditional functional dependencies.

Subfields: Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Automated Machine Learning: State-of-The-Art and Open Challenges (2019, methodology): “Conflict Hypergraph [63] has been introduced as an approximation algorithm which can be used to clean, and repair inconsistencies of a fixed set of functional dependencies with the minimum number of modifications in databases.”
HoloClean: Holistic Data Repairs with Probabilistic Inference (2017, methodology): “To generate these groups we leverage conflict hypergraphs [34] which encode constraint violations in the original datasetD.”
BigDansing: A System for Big Data Cleansing (2015, background): “The system translates these operators along with a, generated or user-provided, BigDansing job into a logical plan .”
Effective Data Cleaning with Continuous Evaluation (2016, background): “Much work adopt other guidelines to suggest data repairs based on less-justiﬁed principles such as minimality of repairs [5, 13].”
Detecting Data Errors: Where are we and what needs to be done? (2016, methodology): “• Rule-based detection algorithms [1,6,15,16,25,33] that can be embedded into frameworks, such as Nadeef [8, 23], where a rule can vary from a simple “not null” constraint to multi-attribute functional dependencies (FDs) to user-defined functions.”
Trends in Cleaning Relational Data: Consistency and Deduplication (2015, background): “Integrity constraints (ICs), which are usually declared as part of the database schema, have been increasingly used as data quality rules, either through checking the validity of the data upon addition or update, or by cleaning the dirty data at various points during the processing pipeline [26, 77]”
Combining Quantitative and Logical Data Cleaning (2015, methodology): “We show that the problem of computing statistical distortion minimal repairs is NP-hard.”
Data Lifecycle Challenges in Production Machine Learning (2018, background): “In the literature, cost-based models [16, 42] and conﬂict hypergraphs [23] are proposed.”
NADEEF: a commodity data cleaning system (2013, methodology): “For comparison, we obtained the implementation of two algorithms for FD repairing, a cost-based heuristic method [5], referred to as HEU, and a vertex cover based approach [20], referred to as VER.”
Don't be SCAREd: use SCalable Automatic REpairing with maximal likelihood and bounded changes (2013, unknown): “The work in [18] uses FDs to map the repairing problem to hyper-graph optimization problem, where a heuristic vertex cover algorithm can help finding the minimal number of attributes values to modify in order to find a database consistent with the FDs.”