Source-linked AI summary
Guided Data Repair
Mohamed Yakout, Ahmed K. Elmagarmid, Jennifer Neville, Mourad Ouzzani, Ihab F. Ilyas
TL;DR
Poor data quality makes fully automated repair risky, while exhaustive user verification is costly. GDR combines constraint-based repair, selective user feedback, VOI-based group ranking, and active learning to improve databases with limited effort. Experiments report rapid quality improvement with minimal user involvement, including about 90% improvement for Dataset 1 with 20% effort and about 94% for Dataset 2 with 30% effort.
Problem
Fully automated repairs can make risky update choices, but users cannot efficiently verify the large number of possible updates.
Method
GDR combines constraint-based repair, selective user feedback, VOI-based group ranking, and active learning to guide repairs and train models for update correctness.
Results
90% improvement was achieved for Dataset 1 with 20% effort, while 94% quality improvement was achieved for Dataset 2 with 30% effort.
Takeaways & Limitations
Experiments show fast convergence to a better-quality database with minimal user intervention.
Takeaways & Limitations
GDR's learned classifiers do not inherently guarantee correct repairs; users decide whether classifier accuracy is sufficient while inspecting suggestions.
Abstract
from arXiv · showhide
In this paper we present GDR, a Guided Data Repair framework that incorporates user feedback in the cleaning process to enhance and accelerate existing automatic repair techniques while minimizing user involvement. GDR consults the user on the updates that are most likely to be beneficial in improving data quality. GDR also uses machine learning methods to identify and apply the correct updates directly to the database without the actual involvement of the user on these specific updates. To rank potential updates for consultation by the user, we first group these repairs and quantify the utility of each group using the decision-theory concept of value of information (VOI). We then apply active learning to order updates within a group based on their ability to improve the learned model. User feedback is used to repair the database and to adaptively refine the training set for the model. We empirically evaluate GDR on a real-world dataset and show significant improvement in data quality using our user guided repairing process. We also, assess the trade-off between the user efforts and the resulting data quality.
1. INTRODUCTION
GDR addresses the tension between risky fully automated repairs and costly user verification by selectively involving users and learning from their feedback. It ranks update groups by expected benefit and orders updates to improve data quality with minimal user effort.
- Motivation: Existing repair methods can introduce risky changes, while verifying the many possible updates manually is expensive.The paper motivates selecting only the most useful updates for user presentation, especially for critical data.
- Motivation: Update groups share contextual information, making feedback easier to provide and supplying correlated examples for learning.Grouping can improve handling by users and prediction accuracy compared with unrelated examples.
- Motivation: GDR interactively combines automatic cleaning with user guidance to achieve better data quality quickly.The framework continuously consults users on updates expected to be most beneficial.
- Contributions: The framework uses data-quality rules to generate candidate updates for violating tuples and applies learned models to reduce direct user involvement.This paper considers Conditional Functional Dependencies as its data-quality rules.
- Contributions: GDR uses VOI to estimate the benefit of consulting users on update groups and active learning to order updates within groups.The framework selectively acquires feedback and trains models to decide the correctness of additional suggested updates.
- Contributions: Experiments on real datasets show fast convergence to a better-quality database with minimal user intervention.The evaluation specifically assesses effectiveness and the trade-off between user effort and resulting data quality.
3. GENERATING CANDIDATE UPDATES
GDR identifies dirty tuples through rule violations, discovers candidate attribute-value updates, and maintains consistency as confirmed updates change the database. It groups related updates to ease user feedback and support machine learning.
- Dirty tuple identification: A tuple is considered dirty when it violates at least one Conditional Functional Dependency in the rule set.Dirty tuples are identified after the rule set Σ is defined and stored for processing.
- Candidate update discovery: An on-demand discovery process generates candidate updates for dirty tuples and their attributes, initially and after user feedback.The consistency manager can trigger discovery when feedback creates new dirty tuples or changes the repair context.
- Candidate update representation: Each candidate update records a tuple, attribute, suggested value, and score representing repair certainty.The score lies between 0 and 1 and is assigned by an update evaluation function.
- Consistency management: Confirmed updates are immediately applied, which can create new violations and invalidate previously suggested updates.The consistency manager triggers further discovery and removes or revises inconsistent suggestions as needed.
- Online monitoring: GDR can monitor online data entries and suggest updates immediately, although this issue is not discussed further.The consistency manager would need notifications such as database triggers for newly added or modified tuples.
- Update grouping: Grouping gives users related updates to process and gives learning algorithms correlated training examples that can improve prediction accuracy.The grouping function is intended to make feedback easier and more informative than random examples.
4. RANKING AND DISPLAYING SUGGESTED UPDATES
GDR ranks groups of suggested repairs by their estimated value for reducing data-quality loss, then uses user feedback and learned correctness estimates to guide update selection. Its ranking combines VOI-based utility estimation with assumptions about update independence and machine-learned user feedback.
- VOI and active learning jointly rank suggested-update groups and determine how updates should be presented to the user.VOI estimates the benefit of consulting on a group, while learning components support principled ranking and feedback acquisition.
- Data quality loss is defined inversely to rule satisfaction and weighted according to the importance of satisfying each rule.Rule-specific loss compares satisfying tuples in the current database with those in the desired clean database; rule weights can reflect contextual importance.
- GDR models update correctness from user feedback, initially using each repairing algorithm’s certainty score when no feedback is available.The prediction probability approximates the probability that a suggested update is correct and is refined as feedback is collected.
- The ranking approximation assumes updates within a group are independent, because modeling full joint probabilities would be computationally infeasible.Under this assumption, the method evaluates alternatives in which an individual update is correct or incorrect and aggregates their expected losses.
- The estimated benefit of a repair group is based on expected changes in rule violations, weighted by the model’s predicted probability that each update is correct.The method compares violation reduction after applying updates and uses predicted correctness because the true clean database and update correctness are unknown.
- GDR delegates some update decisions to learned classifiers, but users determine whether those classifiers are accurate while inspecting suggestions.This delegation enables automatic repairing without providing an inherent guarantee that every delegated repair is correct.
5. EXPERIMENTS
GDR combines VOI-based group ranking with active learning to improve data quality while reducing the feedback required from users. Across two real-world datasets, it achieved faster quality improvement than comparison approaches, while learning introduced a possibility of incorrect automatic updates.
- Experimental setup: GDR was evaluated on two real-world datasets of about 20,000 records each, using simulated feedback determined by ground truth and loss relative to the desired clean database.The experiments assessed both ranking effectiveness and the trade-off between user effort and data quality.
- GDR Overall Evaluation: GDR achieved about 90% quality improvement on Dataset 1 with 20% effort, or about 1,000 verified updates.Feedback was measured relative to 6,000 initially identified dirty tuples in Dataset 1.
- GDR Overall Evaluation: GDR achieved about 94% quality improvement on Dataset 2 with 30% effort, or about 1,000 verified updates.Feedback was measured relative to 3,000 initially identified dirty tuples in Dataset 2.
- GDR Overall Evaluation: Active learning was comparable to GDR only early on Dataset 1, while GDR-S-Learning surpassed it after about 45% user effort.Learning methods were less successful on Dataset 2 because its errors were more random and offered fewer correlations for the model to learn.
- GDR Overall Evaluation: Grouping helps GDR learn locally within a beneficial update group, avoiding the overfitting problem observed when active learning considers a broad mixture of cases.Selecting uncertain updates strengthens model predictions, whereas random within-group inspection wastes effort on less informative updates.
- GDR Overall Evaluation: Combining VOI-based ranking with active learning improved over traditional active learning, but automatic learning allowed mistakes, so 100% accuracy might not be reached.Without learning, GDR-NoLearning is suited to settings where every suggested update must be verified before application.
6. RELATED WORK
Related work spans automated minimal-change repairs, user-directed cleaning, reference matching, and decision-theoretic or active-learning methods. GDR differs by combining repair certainty with learner uncertainty and interactively grouping and ranking updates for efficient user involvement.
- Automated repair: Most existing repair techniques automatically seek a consistent database with minimal changes, often using heuristics to select updates.GDR instead focuses on selectively involving domain experts while retaining automatic repair capabilities.
- User-guided repair: Prior user-in-the-loop repair work may add constraints or require manual updates, whereas GDR interactively generates and groups updates without using machine learning only for the cleaning process.GDR requires data quality rules, rather than the reference data and pre-specified editing rules assumed by another related approach.
- Cleaning systems: Earlier cleaning systems emphasize exploration and transformation, with repair actions explicitly specified by users, and do not efficiently leverage user feedback with automatic repair.Examples include declarative duplicate elimination and transformation systems that detect irregularities.
- Feedback and learning: Other work solicits feedback for reference matching or model improvement, but those methods target matching or query-response quality rather than constrained relational-database repair.Selective supervision combines decision theory and active learning for learned-model benefit, while GDR applies related ideas to data repair.
- GDR distinction: GDR combines repair certainty from an automatic repair evaluation function with learner uncertainty to rank updates for faster data-quality improvement.This mechanism balances the confidence of candidate repairs with their value for improving predictions.
7. CONCLUSION AND FUTURE WORK
GDR combines constraint-based repair with user feedback, using decision-theoretic update selection and active learning to improve database quality with minimal user involvement. Future work extends the framework to additional data quality rules and rule discovery.
- GDR combines constraint-based repair techniques with user feedback through an interactive process.Its decision-theoretic mechanism identifies useful updates for feedback, while active learning supports the interactive repair process.
- The framework aims to move database quality to a better state with respect to the data quality rules.
- Experiments show promising progress in data quality with minimal user involvement.
- Future work will extend GDR beyond CFDs to CINDs, matching dependencies, and matching rules, while investigating guided rule discovery from dirty data.The paper also identifies challenges in handling different rule types and their interactions.
A.1 CFD: Overview
Conditional Functional Dependencies combine functional dependencies with tuple patterns that restrict where those dependencies apply. Their satisfaction depends on whether matching tuples obey the specified constant or variable dependency.
- A CFD is represented as φ : (X →Y, tp), where X and Y are attribute sets and tp assigns constants or variables to attributes.X and Y are called LHS(φ) and RHS(φ), respectively.
- Tuple matching requires each left-hand-side value either equal the pattern value or correspond to its variable marker ‘−’.For example, (Sherden RD, Fort Wayne, IN) matches (−, Fort Wayne, −).
- Constant CFDs require matching tuples to equal the constant right-hand-side value, whereas variable CFDs require matching tuples to agree with one another.The two cases differ in whether the RHS pattern specifies a constant or ‘−’.
A.2 Resolving CFD Violations
CFD violations arise when a tuple conflicts with a constant pattern value or disagrees with another matching tuple under a variable CFD. Repairs can modify either dependent attributes or determinant attributes to remove the violation.
- A dirty tuple violates a constant CFD when its left-hand side matches the pattern but its dependent value differs from the specified constant.
- A dirty tuple violates a variable CFD when another tuple shares its matching left-hand-side values but has a different dependent value.This resembles a standard functional-dependency violation.
- Repairs resolve violations by changing a right-hand-side value or altering left-hand-side attributes so the tuple no longer matches the conflicting pattern.For variable CFDs, the right-hand-side values may instead be made equal across the conflicting tuples.
- The normal form decomposes a CFD with multiple right-hand-side attributes into separate CFDs.For example, ZIP → CT, STT becomes one CFD for CT and another for STT.
- For φ1,1, t2 can be repaired by changing CT from ‘Westville’ to ‘Michigan City’ or ZIP from ‘46360’ to ‘46391’.The example illustrates alternative repairs through RHS or LHS changes.
- For φ5, t5 can be repaired by changing ZIP to ‘46825’ or by changing a left-hand-side attribute such as STR or CT.
A.3 Update Evaluation Function
GDR generates candidate attribute-value repairs for dirty tuples and evaluates them by similarity between current and suggested values. Its update procedure searches constant-CFD, variable-CFD, and determinant-attribute scenarios while tracking rejected values and changeability.
- Generating Updates: Candidate repairs are represented as ⟨t, B, v, s⟩, pairing a dirty tuple and attribute with a suggested value and repair score.
- Generating Updates: Rejected suggestions are stored in preventedList, and Changeable is set false when an attribute-value pair should no longer be modified.These records prevent previously confirmed-wrong values from being suggested again.
- Generating Updates: Initially, every attribute value in a dirty tuple is treated as incorrect, and the procedure searches for the highest-scoring replacement.Algorithm 1 is applied across dirty tuples and their attributes.
- Generating Updates: The procedure searches three scenarios: constant-CFD RHS values, variable-CFD RHS values from related tuples, and LHS values maximizing similarity.For LHS repairs, it first uses CFD values and then searches tuples matching the remaining pattern attributes.
- Generating Updates: Each generated repair is inserted into PossibleUpdates after excluding values listed as prevented.
- Generating Updates: The examples produce ‘Westville’ for a constant-CFD repair, 46825 for a variable-CFD repair, and ‘Sherden RD’ for an LHS repair.
A.5 Updates Consistency Manager
The consistency manager keeps repairs synchronized with database changes by tracking dirty tuples and revisiting updates whose dependencies may have changed. Confirmed, rejected, and retained feedback trigger different update, prevention, or stopping actions.
- Consistency invariants: The manager maintains two invariants: violating tuples are dirty, and possible updates do not depend on modified values.These invariants align repair candidates with the current database instance.
- Feedback handling: Retaining a value marks its tuple-attribute pair unchangeable, stopping further update generation for that value.
- Feedback handling: Rejecting an update records the prevented value and searches for another update for the same tuple-attribute pair.
- Feedback handling: Confirming an update applies it immediately, marks the value unchangeable, and refreshes structures for rules involving the modified attribute.The refresh reflects both removed violations and newly emerging violations.
- Dependency propagation: When repairs can alter other rule decisions, affected tuple-attribute pairs enter RevisitList and obsolete possible updates are removed.Variable CFDs can additionally add related tuples to DirtyTuples and revisit their candidate attributes.
- Online consistency: The manager supports online databases by processing newly added tuples and modified values as updates, while maintaining dirty-tuple consistency after repairs.
B. EXPERIMENTS SETTINGS
The experiments use a real-world emergency-room dataset and the UCI adult dataset, with manually repaired or assumed-clean records providing ground truth. The evaluation runs on a Java/MySQL implementation in a specified server environment.
- Datasets: Dataset 1 integrates anonymized emergency-room visits from 74 hospitals and contains selected patient, address, and visit attributes.The multiple data sources and data-entry operators produce diverse data-quality issues.
- Datasets: Dataset 2 is the UCI adult dataset, used alongside Dataset 1 in the experiments.
- Ground truth: Ground truth for Dataset 1 comes from manually repairing 20,000 patient records using address and ZIP-code lookup websites.
- Ground truth: Dataset 2 contains about 23,000 records and is assumed clean for use as ground truth, with synthetic attribute errors introduced for evaluation.
- Implementation setting: Experiments ran on Linux using a 3 GHz processor, 32 GB RAM, Java implementations, and MySQL storage and queries.
B.1 Additional Experiments: User Efforts vs. Repair Accuracy
The additional experiments measure how increasing user verification effort affects repair precision and recall. Across both datasets, greater user effort generally improves repair accuracy, though Dataset 1 performs better than Dataset 2.
- Experimental procedure: GDR asks the user to verify selected updates within repair groups until the allowed feedback effort F is reached, then decides the remaining updates automatically.
- Results: Precision and recall generally improve as verified feedback F increases, with F measured as a percentage of dirty tuples.
- Results: Dataset 1 consistently achieves higher precision than Dataset 2 as user effort increases.The paper attributes Dataset 2’s lower precision to its learning component’s lower accuracy under randomly introduced errors.
- Conclusion: The results illustrate a trade-off in which increasing user feedback effort is associated with increasing repair accuracy.