Computing consistent query answers using conflict hypergraphs

ABSTRACT

A consistent query answer in a possibly inconsistent database is an answer which is true in every (minimal) repair of the database. We present here a practical framework for computing consistent query answers for large, possibly inconsistent relational databases. We consider relational algebra queries without projection, and denial constraints. Because our framework handles union queries, we can effectively (and efficiently) extract indefinite disjunctive information from an inconsistent database. We describe a number of novel optimization techniques applicable in this context and summarize experimental results that validate our approach.

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: Pablo Barceló , Leopoldo E. Bertossi, Logic Programs for Querying Inconsistent Databases, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.208-222, January 13-14, 2003
• 7: L. Bertossi and J. Chomicki. Query Answering in Inconsistent Databases. In J. Chomicki, R. van der Meyden, and G. Snake, editors, Logics for Emerging Applications of Databases, pages 43--83. Springer-Verlag, 2003.
• 8: Leopoldo E. Bertossi , Jan Chomicki , Alvaro Cortés , Claudio Gutiérrez, Consistent Answers from Integrated Data Sources, Proceedings of the 5th International Conference on Flexible Query Answering Systems, p.71-85, October 27-29, 2002
• 9: L. Bravo and L. Bertossi. Logic Programs for Consistently Querying Data Integration Systems. In International Joint Conference on Artificial Intelligence (IJCAI), pages 10--15, 2003.
• 10: 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
• 11: 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]
• 12: 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
• 13: J. Chomicki and J. Marcinkowski. Minimal-Change Integrity Maintenance Using Tuple Deletions. Information and Computation, 2004. To appear. Earlier version: Technical Report cs.DB/0212004, arXiv.org e-Print archive.
• 14: Thomas Eiter , Wolfgang Faber , Nicola Leone , Gerald Pfeifer, Declarative problem-solving using the DLV system, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
• 15: T. Eiter, M. Fink, G. Greco, and D. Lembo. Efficient Evaluation of Logic Programs for Querying Data Integration Systems. In International Conference on Logic Programming (ICLP), pages 163--177, 2003.
• 16: 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
• 17: A. Fuxman and R. Miller. Towards Inconsistency Management in Data Integration Systems. In IJCAI-03 Workshop on Information Integration on the Web (IIWeb-03), 2003.
• 18: 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
• 19: 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]
• 20: 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]
• 21: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 22: Davy Van Nieuwenborgh , Dirk Vermeir, Preferred Answer Sets for Ordered Logic Programs, Proceedings of the European Conference on Logics in Artificial Intelligence, p.432-443, September 23-26, 2002
• 23: 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

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Languages, Theory

Keywords:
inconsistency, integrity constraints, query processing