A cost-based model and effective heuristic for repairing constraints by value modification

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.

REFERENCES

• 1: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Consistent query answers in inconsistent databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.68-79, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303983]
• 2: L. Bertossi and J. Chomicki, Query Answering in Inconsistent Databases. In J. Chomicki, R. van der Meyden, and G. Saake, editors, Logics for Emerging Applications of Databases, Springer, 2003.
• 3: L. Bravo and L. Bertossi. Logic programs for consistently querying data integration systems. In IJCAI, 2003.
• 4: Peter Buneman , Sanjeev Khanna , Wang-Chiew Tan, On propagation of deletions and annotations through views, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543633]
• 5: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 6: A. Cali, D. Lembo, and R. Rosati. Query rewriting and answering under constraints in data integration systems. In IJCAI, 2003.
• 7: J. Chomicki and J. Marcinkowski. On the Computational Complexity of Minimal-Change Integrity Maintenance in Relational Databases. In L. Bertossi, A. Hunter, and T. Schaub, editors, Integrity Tolerance. Springer, 2004.
• 8: Jan Chomicki , Jerzy Marcinkowski, Minimal-change integrity maintenance using tuple deletions, Information and Computation, v.197 n.1/2, p.90-121, February 25, 2005/March 15, 2005 [doi>10.1016/j.ic.2004.04.007]
• 9: W. Cohen, P. Ravikumar, and S. Feinberg. A comparison of string-distance metrics for name-matching tasks. In IIWeb, 2003.
• 10: M. G. Elfeky. V. S. Verykios, and A. K. Elmagarmid. TAILOR: A record linkage toolbox. In ICDE, 2002.
• 11: Enrico Franconi , Antonio Laureti Palma , Nicola Leone , Simona Perri , Francesco Scarcello, Census Data Repair: a Challenging Application of Disjunctive Logic Programming, Proceedings of the Artificial Intelligence on Logic for Programming, p.561-578, December 03-07, 2001
• 12: Helena Galhardas , Daniela Florescu , Dennis Shasha , Eric Simon, AJAX: an extensible data cleaning tool, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.590, May 15-18, 2000, Dallas, Texas, United States
• 13: Helena Galhardas , Daniela Florescu , Dennis Shasha , Eric Simon , Cristian-Augustin Saita, Declarative Data Cleaning: Language, Model, and Algorithms, Proceedings of the 27th International Conference on Very Large Data Bases, p.371-380, September 11-14, 2001
• 14: M. Gertz and U. Lipeck. A diagnostic approach to repairing constraint violations in databases. In DX, 1995.
• 15: Gianluigi Greco , Sergio Greco , Ester Zumpano, A Logical Framework for Querying and Repairing Inconsistent Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1389-1408, November 2003 [doi>10.1109/TKDE.2003.1245280]
• 16: Mauricio A. Hernández , Salvatore J. Stolfo, Real-world Data is Dirty: Data Cleansing and The Merge/Purge Problem, Data Mining and Knowledge Discovery, v.2 n.1, p.9-37, January 1998 [doi>10.1023/A:1009761603038]
• 17: International Standard ISO/IEC 9075-2:2003(E). Information technology: Database languages, SQL Part 2 (Foundation, 2nd edition), 2003.
• 18: M. Jaro. Advances in record-linkage methodology as applied to matching the 1985 census of tampa florida. Journal of the American Statistical Association, 89:414--420, 1989.
• 19: Lavastorm. Making the Case for Automated Revenue Assurance Solutions. http://www.lavastormtech.com.
• 20: Lucent Technologies. Revenue Assurance Products. http://www.lucent.com/solutions/revenue.html.
• 21: A. Monge. Matching algorithm within a duplicate detection system. IEEE Data Engineering Bulletin, 23(4), 2000.
• 22: A. Monge and C. Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database records. In DKMD, 1997.
• 23: Network Resource Management: Inventory Takes Stage. Rhk research, July 2002. RHK Market Report.
• 24: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 25: E. Rahm and H. H. Do. Data cleaning: Problems and current approaches. IEEE Data Engineering Bulletin, 23(4), 2000.
• 26: Vijayshankar Raman , Joseph M. Hellerstein, Potter's Wheel: An Interactive Data Cleaning System, Proceedings of the 27th International Conference on Very Large Data Bases, p.381-390, September 11-14, 2001
• 27: Transaction Processing Performance Council. TPC-H Benchmark. http://www.tpc.org.
• 28: Jef Wijsen, Condensed Representation of Database Repairs for Consistent Query Answering, Proceedings of the 9th International Conference on Database Theory, p.378-393, January 08-10, 2003
• 29: W. Winkler. Advanced methods for record linkage. Technical report. Statistical Research Division, U.S. Bureau of the Census., 1994.