Luca Grieco
ABSTRACT
Research in consistent query answering studies the definition and computation of "meaningful" answers to queries posed to inconsistent databases, i.e., databases whose data do not satisfy the integrity constraints (ICs) declared on their schema. Computing consistent answers to conjunctive queries is generally coNP-hard in data complexity, even in the presence of very restricted forms of ICs (single, unary keys). Recent studies on consistent query answering for database schemas containing only key dependencies have analyzed the possibility of identifying classes of queries whose consistent answers can be obtained by a first-order rewriting of the query, which in turn can be easily formulated in SQL and directly evaluated through any relational DBMS. In this paper we study consistent query answering in the presence of key dependencies and exclusion dependencies. We first prove that even in the presence of only exclusion dependencies the problem is coNP-hard in data complexity, and define a general method for consistent answering of conjunctive queries under key and exclusion dependencies, based on the rewriting of the query in Datalog with negation. Then, we identify a subclass of conjunctive queries that can be first-order rewritten in the presence of key and exclusion dependencies, and define an algorithm for computing the first-order rewriting of a query belonging to such a class of queries. Finally, we compare the relative efficiency of the two methods for processing queries in the subclass above mentioned. Experimental results, conducted on a real and large database of the computer science engineering degrees of the University of Rome "La Sapienza", clearly show the computational advantage of the first-order based technique.
- Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In Proc. of PODS'99, pages 68--79, 1999. Google Scholar
Digital Library
- Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2003. Google ScholarDigital Library
- Loreto Bravo and Leopoldo Bertossi. Logic programming for consistently querying data integration systems. In Proc. of IJCAI 2003, pages 10--15, 2003. Google ScholarDigital Library
- Andrea Calì, Domenico Lembo, and Riccardo Rosati. On the decidability and complexity of query answering over inconsistent and incomplete databases. In Proc. of PODS 2003, pages 260--271, 2003. Google ScholarDigital Library
- Andrea Calì, Domenico Lembo, and Riccardo Rosati. Query rewriting and answering under constraints in data integration systems. In Proc. of IJCAI 2003, pages 16--21, 2003. Google ScholarDigital Library
- Jan Chomicki and Jerzy Marcinkowski. On the computational complexity of minimal-change integrity maintenance in relational databases. In Inconsistency Tolerance, pages 119--150, 2005. Google ScholarDigital Library
- Jan Chomicki, Jerzy Marcinkowski, and Slawomir Staworko. Computing consistent query answers using conflict hypergraphs. In Proc. of CIKM 2004, pages 417--426, 2004. Google ScholarDigital Library
- Chiara Cumbo, Wolfgang Faber, Gianluigi Greco, and Nicola Leone. Enhancing the magic-set method for disjunctive datalog programs. In Proc. ICLP 2004), pages 371--385, 2004.Google ScholarCross Ref
- Thomas Eiter, Michael Fink, Gianluigi Greco, and Domenico Lembo. Efficient evaluation of logic programs for querying data integration systems. In Proc. of ICLP'03, pages 163--177, 2003.Google ScholarCross Ref
- Thomas Eiter, Georg Gottlob, and Heikki Mannilla. Disjunctive Datalog. ACM Trans. on Database Systems, 22(3):364--418, 1997. Google ScholarDigital Library
- Wolfgang Faber, Gianluigi Greco, and Nicola Leone. Magic sets and their application to data integration. In Proc. of ICDT 2005, pages 306--320, 2005. Google ScholarDigital Library
- Ariel Fuxman, Elham Fazli, and Renée J. Miller. Conquer: Efficient management of inconsistent databases. In Proc. of SIGMOD 2005, pages 155--166, 2005. Google ScholarDigital Library
- Ariel Fuxman and Renée J. Miller. First-order query rewriting for inconsistent databases. In Proc. of ICDT 2005, pages 337--351, 2005. Google ScholarDigital Library
- Gianluigi Greco, Sergio Greco, and Ester Zumpano. A logical framework for querying and repairing inconsistent databases. IEEE Trans. on Knowledge and Data Engineering, 15(6):1389--1408, 2003. Google ScholarDigital Library
- Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, and Francesco Scarcello. The DLV system for knowledge representation and reasoning. ACM Trans. on Computational Logic, 2005. To appear. Google ScholarDigital Library
Index Terms
- Consistent query answering under key and exclusion dependencies: algorithms and experiments
Recommendations
Inclusion Dependency Discovery: An Experimental Evaluation of Thirteen Algorithms
Inclusion dependencies are an important type of metadata in relational databases, because they indicate foreign key relationships and serve a variety of data management tasks, such as data linkage, query optimization, and data integration. The discovery ...
Comments