On approximating optimum repairs for functional dependency violations

ABSTRACT

We study the problem of repairing an inconsistent database that violates a set of functional dependencies by making the smallest possible value modifications. For an inconsistent database, we define an optimum repair as a database that satisfies the functional dependencies, and minimizes, among all repairs, a distance measure that depends on the number of corrections made in the database and the weights of tuples modified. We show that like other versions of the repair problem, checking the existence of a repair within a certain distance of a database is NP-complete. We also show that finding a constant-factor approximation for the optimum repair for any set of functional dependencies is NP-hard. Furthermore, there is a small constant and a set of functional dependencies, for which finding an approximate solution for the optimum repair within the factor of that constant is also NP-hard. Then we present an approximation algorithm that for a fixed set of functional dependencies and an arbitrary input inconsistent database, produces a repair whose distance to the database is within a constant factor of the optimum repair distance. We finally show how the approximation algorithm can be used in data cleaning using a recent extension to functional dependencies, called conditional functional dependencies.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Serge Abiteboul , Paris Kanellakis , Gösta Grahne, On the representation and querying of sets of possible worlds, Theoretical Computer Science, v.78 n.1, p.159-187, Jan. 21, 1991
• 3: 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]
• 4: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Answer sets for consistent query answering in inconsistent databases, Theory and Practice of Logic Programming, v.3 n.4, p.393-424, July 2003 [doi>10.1017/S1471068403001832]
• 5: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki , Xin He , Vijay Raghavan , Jeremy Spinrad, Scalar aggregation in inconsistent databases, Theoretical Computer Science, v.296 n.3, p.405-434, 14 March 2003 [doi>10.1016/S0304-3975(02)00737-5]
• 6: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 7: Leopoldo Bertossi, Consistent query answering in databases, ACM SIGMOD Record, v.35 n.2, June 2006 [doi>10.1145/1147376.1147391]
• 8: Leopoldo Bertossi , Loreto Bravo , Enrico Franconi , Andrei Lopatenko, The complexity and approximation of fixing numerical attributes in databases under integrity constraints, Information Systems, v.33 n.4-5, p.407-434, June, 2008 [doi>10.1016/j.is.2008.01.005]
• 9: Philip Bohannon, Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsietsidis. Conditional functional dependencies for data cleaning. In ICDE, pages 746--755, 2007.
• 10: Philip Bohannon , Wenfei Fan , Michael Flaster , Rajeev Rastogi, A cost-based model and effective heuristic for repairing constraints by value modification, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066175]
• 11: Jan Chomicki. Consistent query answering: Five easy pieces. In ICDT, pages 1--17, 2007.
• 12: 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]
• 13: Gao Cong , Wenfei Fan , Floris Geerts , Xibei Jia , Shuai Ma, Improving data quality: consistency and accuracy, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 14: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 15: Wenfei Fan, Dependencies revisited for improving data quality, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376940]
• 16: Sergio Flesca, Filippo Furfaro, and Francesco Parisi. Consistent query answers on numerical databases under aggregate constraints. In DBPL, pages 279--294, 2005.
• 17: 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
• 18: Filippo Furfaro , Sergio Greco , Cristian Molinaro, A three-valued semantics for querying and repairing inconsistent databases, Annals of Mathematics and Artificial Intelligence, v.51 n.2-4, p.167-193, December 2007 [doi>10.1007/s10472-008-9088-3]
• 19: Ariel Fuxman , Elham Fazli , Renée J. Miller, ConQuer: efficient management of inconsistent databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066176]
• 20: Ariel Fuxman , Renée J. Miller, First-order query rewriting for inconsistent databases, Journal of Computer and System Sciences, v.73 n.4, p.610-635, June, 2007 [doi>10.1016/j.jcss.2006.10.013]
• 21: Solmaz Kolahi , Leonid Libkin, On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142369]
• 22: Gabriel M. Kuper, Leonid Libkin, and Jan Paredaens, editors. Constraint Databases. Springer, 2000.
• 23: Andrei Lopatenko and Loreto Bravo. Efficient approximation algorithms for repairing inconsistent databases. In ICDE, pages 216--225, 2007.
• 24: Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425--440, 1991.
• 25: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 26: 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
• 27: Jef Wijsen, Database repairing using updates, ACM Transactions on Database Systems (TODS), v.30 n.3, p.722-768, September 2005 [doi>10.1145/1093382.1093385]
• 28: Jef Wijsen. Project-join-repair: An approach to consistent query answering under functional dependencies. In FQAS, pages 1--12, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Theory

Keywords:
approximation algorithm, functional dependency violation, inconsistent databases, repair