Query-Oriented Data Cleaning with Oracles
Authors:
Open Access
- 27 May 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1199-1214
Abstract
As key decisions are often made based on information contained in a database, it is important for the database to be as complete and correct as possible. For this reason, many data cleaning tools have been developed to automatically resolve inconsistencies in databases. However, data cleaning tools provide only best-effort results and usually cannot eradicate all errors that may exist in a database. Even more importantly, existing data cleaning tools do not typically address the problem of determining what information is missing from a database. To overcome the limitations of existing data cleaning techniques, we present QOCO, a novel query-oriented system for cleaning data with oracles. Under this framework, incorrect (resp. missing) tuples are removed from (added to) the result of a query through edits that are applied to the underlying database, where the edits are derived by interacting with domain experts which we model as oracle crowds. We show that the problem of determining minimal interactions with oracle crowds to derive database edits for removing (adding) incorrect (missing) tuples to the result of a query is NP-hard in general and present heuristic algorithms that interact with oracle crowds. Finally, we implement our algorithms in our prototype system QOCO and show that it is effective and efficient through a comprehensive suite of experiments.Keywords
Funding Information
- National Science Foundation (IIS-1450560,III-1302212)
- European Research Council (291071)
This publication has 48 references indexed in Scilit:
- Data Cleaning: A Practical PerspectiveSynthesis Lectures on Data Management, 2013
- An overview of the deco systemACM SIGMOD Record, 2013
- Foundations of Data Quality ManagementSynthesis Lectures on Data Management, 2012
- Galaxy Zoo: Exploring the Motivations of Citizen Science VolunteersAstronomy Education Review, 2010
- Evaluating ontologies: Towards a cognitive measure of qualityInformation Systems, 2010
- Provenance in Databases: Why, How, and WhereFoundations and Trends® in Databases, 2009
- Collective entity resolution in relational dataACM Transactions on Knowledge Discovery From Data, 2007
- Why and Where: A Characterization of Data Provenance2001
- Tracing the lineage of view data in a warehousing environmentACM Transactions on Database Systems, 2000
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972