Database repairing using updates

ABSTRACT

Repairing a database means bringing the database in accordance with a given set of integrity constraints by applying some minimal change. If a database can be repaired in more than one way, then the consistent answer to a query is defined as the intersection of the query answers on all repaired versions of the database.Earlier approaches have confined the repair work to deletions and insertions of entire tuples. We propose a theoretical framework that also covers updates as a repair primitive. Update-based repairing is interesting in that it allows rectifying an error within a tuple without deleting the tuple, thereby preserving consistent values in the tuple. Another novel idea is the construct of nucleus: a single database that yields consistent answers to a class of queries, without the need for query rewriting. We show the construction of nuclei for full dependencies and conjunctive queries. Consistent query answering and constructing nuclei is generally intractable under update-based repairing. Nevertheless, we also show some tractable cases of practical interest.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: 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]
• 3: 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]
• 4: 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]
• 5: Marcelo Arenas , Leopoldo E. Bertossi , Michael Kifer, Applications of Annotated Predicate Calculus to Querying Inconsistent Databases, Proceedings of the First International Conference on Computational Logic, p.926-941, July 01, 2000
• 6: Ofer Arieli, An Algorithmic Approach to Recover Inconsistent Knowledge-Bases, Proceedings of the European Workshop on Logics in Artificial Intelligence, p.148-162, October 02, 2000
• 7: Arieli, O., Denecker, M., Nuffelen, B. V., and Bruynooghe, M. 2002. Repairing inconsistent databases: A model-theoretic approach and abductive reasoning. In Paraconsistent Computational Logic. Datalogiske Skrifter, vol. 95. Roskilde University, Roskilde, Denmark, 51--65.
• 8: Arieli, O., Denecker, M., Nuffelen, B. V., and Bruynooghe, M. 2004. Database repair by signed formulae. In Proceedings of the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2004). LNCS, vol. 2942. Springer, 14--30.
• 9: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 10: Bertossi, L. E. and Chomicki, J. 2003. Query answering in inconsistent databases. In Logics for Emerging Applications of Databases, J. Chomicki, R. van der Meyden, and G. Saake, Eds. Springer, Chapter 2, 43--83.
• 11: Leopoldo E. Bertossi , Camilla Schwind, Analytic Tableaux and Database Repairs: Foundations, Proceedings of the Second International Symposium on Foundations of Information and Knowledge Systems, p.32-48, February 20-23, 2002
• 12: Leopoldo Bertossi , Camilla Schwind, Database Repairs and Analytic Tableaux, Annals of Mathematics and Artificial Intelligence, v.40 n.1-2, p.5-35, January 2004 [doi>10.1023/A:1026153912205]
• 13: Bravo, L. and Bertossi, L. E. 2003. Logic programs for consistently querying data integration systems. In Proceedings of the 18th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 10--15.
• 14: Loreto Bravo , Leopoldo Bertossi, Consistent query answering under inclusion dependencies, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.202-216, October 04-07, 2004, Markham, Ontario, Canada
• 15: François Bry, Query Answering in Information Systems with Integrity Constraints, Proceedings of the IFIP TC11 Working Group 11.5, First Working Conference on Integrity and Internal Control in Information Systems: Increasing the confidence in Information Systems, p.113-130, December 04-05, 1997
• 16: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Data integration under integrity constraints, Information Systems, v.29 n.2, p.147-163, April 2004 [doi>10.1016/S0306-4379(03)00050-4]
• 17: 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]
• 18: Calì, A., Lembo, D., and Rosati, R. 2003b. Query rewriting and answering under constraints in data integration systems. In Proceedings of the 18th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 16--21.
• 19: Alexander Celle , Leopoldo E. Bertossi, Querying Inconsistent Databases: Algorithms and Implementation, Proceedings of the First International Conference on Computational Logic, p.942-956, July 01, 2000
• 20: 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]
• 21: Chomicki, J. and Marcinkowski, J. 2005b. On the computational complexity of minimal-change integrity maintenance in relational databases. In Inconsistency Tolerance. LNCS, vol. 3300. Springer, 119--150.
• 22: Jan Chomicki , Jerzy Marcinkowski , Slawomir Staworko, Computing consistent query answers using conflict hypergraphs, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031254]
• 23: Chomicki, J., Marcinkowski, J., and Staworko, S. 2004b. Hippo: A system for computing consistent answers to a class of SQL queries. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT 2004). LNCS, vol. 2992. Springer, 841--844.
• 24: Sandra de Amo , Walter Alexandre Carnielli , João Marcos, A Logical Framework for Integrating Inconsistent Information in Multiple Databases, Proceedings of the Second International Symposium on Foundations of Information and Knowledge Systems, p.67-84, February 20-23, 2002
• 25: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 26: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.90-101, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773163]
• 27: 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
• 28: Fuxman, A. D. and Miller, R. J. 2005. First-order rewriting for inconsistent databases. In Proceedings of the 10th International Conference on Database Theory (ICDT 2005). LNCS, vol. 3363. Springer, 337--351.
• 29: John Grant , V. s. Subrahmanian, Reasoning in Inconsistent Knowledge Bases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.1, p.177-189, February 1995 [doi>10.1109/69.368510]
• 30: 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]
• 31: Greco, S., Sirangelo, C., Trubitsyna, I., and Zumpano, E. 2003b. Preferred repairs for inconsistent databases. In 7th International Database Engineering and Applications Symposium (IDEAS 2003). IEEE Computer Society, 202--211.
• 32: Pavol Hell , Xuding Zhu, The Existence of Homomorphisms to Oriented Cycles, SIAM Journal on Discrete Mathematics, v.8 n.2, p.208-222, May 1995 [doi>10.1137/S0895480192239992]
• 33: Lembo, D., Lenzerini, M., and Rosati, R. 2002. Source inconsistency and incompleteness in data integration. In Proceedings of the 9th International Workshop on Knowledge Representation Meets Databases (KRDB 2002). Number 54 in CEUR Workshop Proceedings. Technical University of Aachen (RWTH).
• 34: Lin, J. and Mendelzon, A. O. 1998. Merging databases under constraints. Int. J. Cooperative Inf. Syst. 7, 1, 55--76.
• 35: Nair, M. 1982a. A new method in elementary prime number theory. J. London Math. Soc. 25, 385--391.
• 36: Nair, M. 1982b. On Chebyshev-type inequalities for primes. Amer. Math. Monthly 89, 126--129.
• 37: Plotkin, G. D. 1969. A note on inductive generalization. In Machine Intelligence 5, B. Meltzer and D. Michie, Eds. Edinburgh University Press, Edinburgh, 153--163.
• 38: Edward Sciore, Inclusion dependencies and the universal instance, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588066]
• 39: 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
• 40: Wijsen, J. 2004. Making more out of an inconsistent database. In Proceedings of the 8th East European Conference on Advances in Databases and Information Systems (ADBIS 2004). LNCS, vol. 3255. Springer, 291--305.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Theory

Keywords:
Consistent query answering, database repairing