Andrea Calì
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.
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley Publ. Co., Reading, Massachussetts, 1995. Google Scholar
Digital Library
- 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.Google ScholarCross Ref
- M. Arenas, L. E. Bertossi, and J. Chomicki. Consistent query answers in inconsistent databases. In Proc. of the 18th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS'99), pages 68--79, 1999. Google ScholarDigital Library
- 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.Google Scholar
- F. Bry. Query answering in information systems with integrity constraints. In IFIP WG 11.5 Working Conf. on Integrity and Control in Information System. Chapman & Hall, 1997. Google ScholarDigital Library
- A. Calì, D. Calvanese, G. De Giacomo, and M. Lenzerini. Accessing data integration systems through conceptual schemas. In Proc. of the 20th Int. Conf. on Conceptual Modeling (ER 2001), pages 270--284, 2001. Google ScholarDigital Library
- A. Calì, D. Calvanese, G. De Giacomo, and M. Lenzerini. Data integration under integrity constraints. Information Systems, 2003. To appear.Google Scholar
- 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.Google ScholarCross Ref
- J. Chomicki and J. Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Technical Report arXiv:cs.DB/0212004v1, 2002.Google Scholar
- J. Chomicki and J. Marcinkowski. On the computational complexity of consistent query answers. Technical Report arXiv:cs.DB/0204010v1, 2002.Google Scholar
- P. M. Dung. Integrating data from possibly inconsistent databases. In Proc. of the 4th Int. Conf. on Cooperative Information Systems (CoopIS'96), pages 58--65, 1996. Google ScholarDigital Library
- T. Eiter and G. Gottlob. On the complexity of propositional knowledge base revision, updates and counterfactuals. Artificial Intelligence, 57:227--270, 1992. Google ScholarDigital Library
- T. Eiter and G. Gottlob. The complexity of nested counterfactuals and iterated knowledge base revisions. J. of Computer and System Sciences, 53(3):497--512, 1996. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. In Proc. of the 9th Int. Conf. on Database Theory (ICDT 2003), pages 207--224, 2003. Google ScholarDigital Library
- R. Fagin, J. D. Ullman, and M. Y. Vardi. On the semantics of updates in databases. In Proc. of the 2nd ACM SIGACT SIGMOD Symp. on Principles of Database Systems (PODS'83), pages 352--365, 1983. Google ScholarDigital Library
- G. Greco, S. Greco, and E. Zumpano. A logic programming approach to the integration, repairing and querying of inconsistent databases. In Proc. of the 17th Int. Conf. on Logic Programming (ICLP'01), volume 2237 of Lecture Notes in Artificial Intelligence, pages 348--364. Springer, 2001. Google ScholarDigital Library
- A. Y. Halevy. Answering queries using views: A survey. Very Large Database J., 10(4):270--294, 2001. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- M. Lenzerini. Data integration: A theoretical perspective. In Proc. of the 21st ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS 2002), pages 233--246, 2002. Google ScholarDigital Library
- J. Lin and A. O. Mendelzon. Merging databases under constraints. Int. J. of Cooperative Information Systems, 7(1):55--76, 1998.Google ScholarCross Ref
- C. H. Papadimitriou. Computational Complexity. Addison Wesley Publ. Co., Reading, Massachussetts, 1994.Google Scholar
- 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.Google ScholarCross Ref
Index Terms
- On the decidability and complexity of query answering over inconsistent and incomplete databases
Recommendations
Probabilistic query answering over inconsistent databases
This paper presents a framework for querying inconsistent databases in the presence of functional dependencies. Most of the works dealing with the problem of extracting reliable information from inconsistent databases are based on the notion of repair, ...
Repair localization for query answering from inconsistent databases
Query answering from inconsistent databases amounts to finding “meaningful” answers to queries posed over database instances that do not satisfy integrity constraints specified over their schema. A declarative approach to this problem relies on the ...
Approximate Probabilistic Query Answering over Inconsistent Databases
ER '08: Proceedings of the 27th International Conference on Conceptual ModelingThe problem of managing and querying inconsistent databases has been deeply investigated in the last few years. Most of the approaches proposed so far rely on the notion of <em>repair</em>(a minimal set of delete/insert operations making the database ...
Comments