Consistent query answering under primary keys: a characterization of tractable queries

ABSTRACT

This article deals with consistent query answering to conjunctive queries under primary key constraints. The repairs of an inconsistent database db are obtained by selecting a maximum number of tuples from db without ever selecting two tuples that agree on their primary key. For a Boolean conjunctive query q, we are interested in the following question: does there exist a Boolean first-order query &phis; such that for every database db, &phis; evaluates to true on db if and only if q evaluates to true on every repair of db? We address this problem for acyclic conjunctive queries in which no relation name occurs more than once. Our results improve previous solutions that are based on Fuxman-Miller join graphs.

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: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• 4: 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]
• 5: A. Calì, D. Lembo, and R. Rosati. Query rewriting and answering under constraints in data integration systems. In G. Gottlob and T. Walsh, editors, IJCAI, pages 16--21. Morgan Kaufmann, 2003.
• 6: J. Chomicki. Consistent query answering: Five easy pieces. In T. Schwentick and D. Suciu, editors, ICDT, volume 4353 of Lecture Notes in Computer Science, pages 1--17. Springer, 2007.
• 7: 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]
• 8: 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]
• 9: 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]
• 10: A. Fuxman and R. J. Miller. First-order query rewriting for inconsistent databases. In T. Eiter and L. Libkin, editors, ICDT, volume 3363 of Lecture Notes in Computer Science, pages 337--351. Springer, 2005.
• 11: 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]
• 12: G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579--627, 2002.
• 13: Luca Grieco , Domenico Lembo , Riccardo Rosati , Marco Ruzzi, Consistent query answering under key and exclusion dependencies: algorithms and experiments, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099742]
• 14: D. Lembo, R. Rosati, and M. Ruzzi. On the first-order reducibility of unions of conjunctive queries over inconsistent databases. In T. Grust, H. Höpfner, A. Illarramendi, S. Jablonski, M. Mesiti, S. Müller, P.-L. Patranjan, K.-U. Sattler, M. Spiliopoulou, and J. Wijsen, editors, EDBT Workshops, volume 4254 of Lecture Notes in Computer Science, pages 358--374. Springer, 2006.
• 15: Leonid Libkin, Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series), SpringerVerlag, 2004
• 16: J. Lin and A. O. Mendelzon. Merging databases under constraints. Int. J. Cooperative Inf. Syst., 7(1):55--76, 1998.
• 17: 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]
• 18: J. Wijsen. On the consistent rewriting of conjunctive queries under primary key constraints. In M. Arenas and M. I. Schwartzbach, editors, DBPL, volume 4797 of Lecture Notes in Computer Science, pages 112--126. Springer, 2007. An extended version will appear in Information Systems.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

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

General Terms:
Algorithms, Theory

Keywords:
conjunctive queries, consistent query answering, database repairing, primary key, query rewriting