On the decidability and complexity of query answering over inconsistent and incomplete databases

ABSTRACT

In databases with integrity constraints, data may not satisfy the constraints. In this paper, we address the problem of obtaining consistent answers in such a setting, when key and inclusion dependencies are expressed on the database schema. We establish decidability and complexity results for query answering under different assumptions on data (soundness and/or completeness). In particular, after showing that the problem is in general undecidable, we identify the maximal class of inclusion dependencies under which query answering is decidable in the presence of key dependencies. Although obtained in a single database context, such results are directly applicable to data integration, where multiple information sources may provide data that are inconsistent with respect to the global view of the sources.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: C. E. Alchourrón, P. Gärdenfors, and D. Makinson. On the logic of theory change: Partial meet contraction and revision functions. J. of Symbolic Logic, 50:510--530, 1985.
• 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: M. Arenas, L. E. Bertossi, and J. Chomicki. Specifying and querying database repairs using logic programs with exceptions. In Proc. of the 4th Int. Conf. on Flexible Query Answering Systems (FQAS 2000), pages 27--41. Springer, 2000.
• 5: 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
• 6: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Accessing Data Integration Systems through Conceptual Schemas, Proceedings of the 20th International Conference on Conceptual Modeling: Conceptual Modeling, p.270-284, November 27-30, 2001
• 7: A. Calì, D. Calvanese, G. De Giacomo, and M. Lenzerini. Data integration under integrity constraints. Information Systems, 2003. To appear.
• 8: M. A. Casanova, R. Fagin, and C. H. Papadimitriou. Inclusion dependencies and their interaction with functional dependencies. J. of Computer and System Sciences, 28(1):29--59, 1984.
• 9: J. Chomicki and J. Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Technical Report arXiv:cs.DB/0212004v1, 2002.
• 10: J. Chomicki and J. Marcinkowski. On the computational complexity of consistent query answers. Technical Report arXiv:cs.DB/0204010v1, 2002.
• 11: Phan Minh Dung, Integrating data from possibly inconsistent databases, Proceedings of the First IFCIS International Conference on Cooperative Information Systems, p.58, June 19-21, 1996
• 12: Thomas Eiter , Georg Gottlob, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Artificial Intelligence, v.57 n.2-3, p.227-270, Oct. 1992 [doi>10.1016/0004-3702(92)90018-S]
• 13: Thomas Eiter , Georg Gottlob, The complexity of nested counterfactuals and iterated knowledge base revisions, Journal of Computer and System Sciences, v.53 n.3, p.497-512, Dec. 1996 [doi>10.1006/jcss.1996.0083]
• 14: 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
• 15: Ronald Fagin , Jeffrey D. Ullman , Moshe Y. Vardi, On the semantics of updates in databases, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588100]
• 16: Gianluigi Greco , Sergio Greco , Ester Zumpano, A Logic Programming Approach to the Integration, Repairing and Querying of Inconsistent Databases, Proceedings of the 17th International Conference on Logic Programming, p.348-364, November 26-December 01, 2001
• 17: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 18: D. S. Johnson and A. C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. J. of Computer and System Sciences, 28(1):167--189, 1984.
• 19: D. Lembo, M. Lenzerini, and R. Rosati. Source inconsistency and incompleteness in data integration. In Proc. of the 9th Int. Workshop on Knowledge Representation meets Databases (KRDB 2002). CEUR Electronic Workshop Proceedings, http://ceur-ws.org/Vol-54/, 2002.
• 20: Maurizio Lenzerini, Data integration: a theoretical perspective, 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.543644]
• 21: J. Lin and A. O. Mendelzon. Merging databases under constraints. Int. J. of Cooperative Information Systems, 7(1):55--76, 1998.
• 22: C. H. Papadimitriou. Computational Complexity. Addison Wesley Publ. Co., Reading, Massachussetts, 1994.
• 23: R. Reiter. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Databases, pages 119--140. Plenum Publ. Co., New York, 1978.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Experimentation, Theory