TL;DR
This paper introduces REPLACE, a novel framework that unifies entity resolution (deduplication) and data repairing (consistency enforcement) within a single logical system. By treating these data quality issues holistically, REPLACE offers a more comprehensive approach to cleaning "dirty" databases, enabling more robust query answering over imperfect data.
What Problem Does This Paper Address?
Data quality is a critical challenge in data management, encompassing issues like multiple representations of the same entity (entity resolution or ER) and conflicting or erroneous information (data repairing or consistency). While these problems have been studied extensively, they've often been tackled in isolation. Existing approaches, like pipelines, can miss synergistic benefits. For instance, resolving an entity might automatically fix a data inconsistency, or removing erroneous facts might enable previously blocked entity merges. This paper addresses the need for a unified framework that can jointly handle both ER and repairing, allowing for more effective data cleaning and more reliable query answering.
Methods
The core of the REPLACE framework is a declarative approach using logical rules and constraints. It builds upon the LACE framework for collective entity resolution, which uses hard and soft rules to define mandatory and potential merges of constants (e.g., merging two author IDs if they share the same email and institution). REPLACE extends this by incorporating denial constraints to specify consistency requirements.
A key innovation is the definition of "solutions" which now consist of not only a set of merges (represented by an equivalence relation) but also a set of facts to be deleted from the database. This allows for a more complete representation of data cleaning actions. The framework defines three notions of "optimal" solutions based on prioritizing maximizing merges (MER), minimizing deletions (DEL), or a Pareto approach (PAR). To handle the potential multiplicity of optimal solutions, REPLACE adopts concepts from Consistent Query Answering (CQA), defining "certain" (answers true in all optimal solutions) and "possible" (answers true in at least one optimal solution) query answers. Furthermore, it introduces "most informative" answers to provide a more compact and user-friendly presentation of query results.
Datasets
Not discussed in the paper. The paper uses a running example to illustrate its concepts, but no formal datasets are described for training or evaluation.
Key Insights and Ideas
- Holistic Approach is Crucial: Treating entity resolution and data repairing together unlocks synergies that isolated approaches miss, leading to better data quality outcomes.
- Solutions as Merges + Deletions: The novel definition of a "solution" as a pair of merges and deletions provides a richer model for data cleaning than just one or the other.
- Multiple Optimality Criteria: Recognizing that different applications might prioritize different aspects of data cleaning (more merges vs. fewer deletions) by introducing MER, DEL, and PAR optimality notions is practical.
- Querying the Space of Solutions: Instead of committing to a single "cleaned" database, querying the space of optimal solutions (via certain/possible answers) offers a robust way to handle uncertainty.
- "Most Informative" Answers: The introduction of "most informative" answers is a significant step towards making query results over uncertain data more digestible and useful for end-users.
Key Results
The paper focuses on the data complexity of various reasoning tasks within the REPLACE framework. Key findings include:
- Solution Recognition: Checking if a given set of merges and deletions constitutes a valid solution is P-complete.
- Optimal Solution Recognition: Determining if a solution is optimal (under MER, DEL, or PAR criteria) is coNP-complete.
- Query Answering Complexity:
- Certain answers are $\Pi_2^P$-complete.
- Possible answers are $\Sigma_2^P$-complete for MER/DEL and NP-complete for PAR.
- Restricted Specifications: Using restricted denial constraints (without inequality atoms) can reduce the complexity of some tasks, particularly for DEL and PAR optimality, bringing them down to P-complete or NP-complete.
- Most Informative Answers: Introducing "most informative" answers leads to higher complexity, with X-MICERTANS being DP$_2^P$-complete and X-MIPOSSANS being DP$_2^P$-complete or DP-complete, depending on the optimality criterion.
Limitations and Future Work
- Complexity: The computational complexity of reasoning tasks, especially for certain and possible answers, can be high, particularly for general specifications.
- Future Work:
- Other Reasoning Tasks: Exploring the complexity of identifying certain/possible merges and deletions.
- Quantitative Information: Extending the framework to handle weighted rules and facts for approximate weighted solutions.
- Prototype Development: Building an efficient prototype, potentially using Answer Set Programming (ASP), to handle the complexities, especially for "most informative" answers.
- More Informative Similarity Measures: Integrating machine learning-based similarity measures to enhance entity resolution.
Summary updated