Data integrated from multiple sources may contain inconsistencies that violate integrity constraints. The constraint repair problem attempts to find "low cost" changes that, when applied, will cause the constraints to be satisfied. While in most previous work repair cost is stated in terms of tuple insertions and deletions, we follow recent work to define a database repair as a set of value modifications. In this context, we introduce a novel cost framework that allows for the application of techniques from record-linkage to the search for good repairs. We prove that finding minimal-cost repairs in this model is NP-complete in the size of the database, and introduce an approach to heuristic repair-construction based on equivalence classes of attribute values. Following this approach, we define two greedy algorithms. While these simple algorithms take time cubic in the size of the database, we develop optimizations inspired by algorithms for duplicate-record detection that greatly improve scalability. We evaluate our framework and algorithms on synthetic and real data, and show that our proposed optimizations greatly improve performance at little or no cost in repair quality.
Description
A cost-based model and effective heuristic for repairing constraints by value modification
%0 Conference Paper
%1 bohannon05.repaire
%A Bohannon, Philip
%A Fan, Wenfei
%A Flaster, Michael
%A Rastogi, Rajeev
%B SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data
%C New York, NY, USA
%D 2005
%I ACM
%K ic repair
%P 143--154
%R http://doi.acm.org/10.1145/1066157.1066175
%T A cost-based model and effective heuristic for repairing constraints by value modification
%U http://homepages.inf.ed.ac.uk/wenfei/papers/sigmod05.pdf
%X Data integrated from multiple sources may contain inconsistencies that violate integrity constraints. The constraint repair problem attempts to find "low cost" changes that, when applied, will cause the constraints to be satisfied. While in most previous work repair cost is stated in terms of tuple insertions and deletions, we follow recent work to define a database repair as a set of value modifications. In this context, we introduce a novel cost framework that allows for the application of techniques from record-linkage to the search for good repairs. We prove that finding minimal-cost repairs in this model is NP-complete in the size of the database, and introduce an approach to heuristic repair-construction based on equivalence classes of attribute values. Following this approach, we define two greedy algorithms. While these simple algorithms take time cubic in the size of the database, we develop optimizations inspired by algorithms for duplicate-record detection that greatly improve scalability. We evaluate our framework and algorithms on synthetic and real data, and show that our proposed optimizations greatly improve performance at little or no cost in repair quality.
%@ 1-59593-060-4
@inproceedings{bohannon05.repaire,
abstract = {Data integrated from multiple sources may contain inconsistencies that violate integrity constraints. The constraint repair problem attempts to find "low cost" changes that, when applied, will cause the constraints to be satisfied. While in most previous work repair cost is stated in terms of tuple insertions and deletions, we follow recent work to define a database repair as a set of value modifications. In this context, we introduce a novel cost framework that allows for the application of techniques from record-linkage to the search for good repairs. We prove that finding minimal-cost repairs in this model is NP-complete in the size of the database, and introduce an approach to heuristic repair-construction based on equivalence classes of attribute values. Following this approach, we define two greedy algorithms. While these simple algorithms take time cubic in the size of the database, we develop optimizations inspired by algorithms for duplicate-record detection that greatly improve scalability. We evaluate our framework and algorithms on synthetic and real data, and show that our proposed optimizations greatly improve performance at little or no cost in repair quality.},
added-at = {2008-10-11T20:57:22.000+0200},
address = {New York, NY, USA},
author = {Bohannon, Philip and Fan, Wenfei and Flaster, Michael and Rastogi, Rajeev},
biburl = {https://www.bibsonomy.org/bibtex/2969d1c5ad08447790dabf51c91e6c887/ljiang},
booktitle = {SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data},
description = {A cost-based model and effective heuristic for repairing constraints by value modification},
doi = {http://doi.acm.org/10.1145/1066157.1066175},
interhash = {a11a60319a51e54438fd36b349cb9f76},
intrahash = {969d1c5ad08447790dabf51c91e6c887},
isbn = {1-59593-060-4},
keywords = {ic repair},
location = {Baltimore, Maryland},
pages = {143--154},
publisher = {ACM},
timestamp = {2009-02-24T16:45:22.000+0100},
title = {A cost-based model and effective heuristic for repairing constraints by value modification},
url = {http://homepages.inf.ed.ac.uk/wenfei/papers/sigmod05.pdf},
year = 2005
}