Consistent Answers to SQL Queries

This material is based upon work supported by the National Science Foundation under Grant No. IIS-0119186 Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).

Principal Investigator: Jan Chomicki, University at Buffalo

Title: Consistent Answers to SQL Queries

Abstract:

As the amount of information available in online data sources explodes, there is a growing concern about the consistency and quality of answers to user queries. This project addresses the issue of using logical integrity constraints to gauge the consistency and quality of query answers. Although it is impractical to enforce global integrity constraints across different data sources and correct integrity violations by updating individual sources, integrity constraints capture important semantic properties of data. This project studies the formal notions of database repair and consistent query answer: a consistent answer is true in every minimal repair of the database. The information about answer consistency serves as an important indication of its quality and reliability.

A variety of procedures for computing consistent query answers in the context of the relational data model and SQL are developed, and their computational complexity analyzed. The procedures exploit the properties of specific subsets of SQL and specific classes of integrity constraints. By providing information about query answer consistency, such procedures will enhance the functionality of existing DBMS in a non-intrusive way, particularly in the context of data integration applications.

Publications:

  1. Prioritized Repairing and Consistent Query Answering in Relational Databases. Annals of Mathematics and Artificial Intelligence, 64(2-3), March 2012, pp. 209-246 (with S. Staworko and J. Marcinkowski). Also preprint arXiv:0908.0464v1 [cs.DB], August 4, 2009.

  2. Consistent Query Answering in the Presence of Universal Constraints. Information Systems, 35(1), January 2010, pp. 1-22 (with Slawomir Staworko). Also UB CSE Technical Report 2008-15 and preprint arxiv: 0809.1551v1 [cs.DB], September 9, 2008.

  3. Disjunctive Databases for Representing Repairs. Annals of Mathematics and Artificial Intelligence, 57(2), October 2009, pp. 103-124 (with Cristian Molinaro and Jerzy Marcinkowski). Also preprint arxiv: 0811.2117v1 [cs.DB], November 13, 2008.

  4. S. Staworko. Declarative Inconsistency Handling in Relational and Semi-Structured Databases. Ph. D. dissertation. UB CSE TR 2008-03, February 2008.

  5. Consistent Query Answering: Five Easy Pieces. Proc. 11th International Conference on Database Theory (ICDT), January 2007, Barcelona, Spain, Springer, LNCS 4353, pp. 1-17. Keynote talk.

  6. Consistent Query Answering: Opportunities and Limitations. Proc. 2nd International Workshop on Logical Aspects and Applications of Integrity Constraints (LAAIC), DEXA Workshops, September 2006, Krakow, Poland, IEEE Computer Society Press. Keynote talk.

  7. Validity-Sensitive Querying of XML Databases. Proc. 2nd International Workshop on Database Technologies for Handling XML Information on the Web (dataX), March 2006, Munich, Germany (with S. Staworko).

  8. Preference-Driven Querying of Inconsistent Relational Databases. Proc. International Workshop on Inconsistency and Incompleteness in Databases, March 2006, Munich, Germany (with S. Staworko and J. Marcinkowski). Earlier version: UB CSE Technical Report 2005-11 and arXiv.org paper cs.DB/0506063, June 15, 2005.

  9. Computing Consistent Query Answers Using Conflict Hypergraphs. Proc. 13th ACM Conference on Information and Knowledge Management (CIKM), November 2004, Arlington, Virginia, ACM Press, pp. 417-426. Short version in Proc. Workshop on Information Integration on the Web, August 2004, Toronto, Canada, (with J. Marcinkowski and S. Staworko).

  10. Minimal-Change Integrity Maintenance Using Tuple Deletions. Information and Computation, 197 (1-2), February 2005, pp. 90-121 (with Jerzy Marcinkowski). Earlier version: arXiv.org paper cs.DB/0212004.

  11. Answer Sets for Consistent Query Answering in Inconsistent Databases. Theory and Practice of Logic Programming 3(4&5), 2003, 393-424 (with Marcelo Arenas and Leo Bertossi). arXiv.org paper cs.DB/0207094.

  12. Scalar Aggregation in Inconsistent Databases. Theoretical Computer Science, 296(3), March 2003, pp. 405-434 (special issue: selected papers from ICDT'01). With Marcelo Arenas, Leo Bertossi, Xin He, Vijay Raghavan and Jeremy Spinrad.

  13. Consistent Answers from Integrated Data Sources. Proc. 5th International Conference on Flexible Query Answering Systems, October 2002, Copenhagen, Denmark (with L. Bertossi, A. Cortes and C. Gutierrez).

  14. Scalar Aggregation in FD-Inconsistent Databases. Proc. 8th International Conference on Database Theory, January 2001, London, UK, Springer-Verlag, LNCS 1973, pp. 39-53 (with M. Arenas and L. Bertossi). Journal version.

  15. Specifying and Querying Database Repairs Using Logic Programs with Exceptions. Proc. 4th International Conference on Flexible Query Answering Systems, October 2000, Warsaw, Poland, Springer-Verlag, pp.27-41 (with M. Arenas and L. Bertossi). Journal version.

  16. Consistent Query Answers in Inconsistent Databases. Proc. 18th ACM Symposium on Principles of Database Systems, June 1999, Philadelphia, Pennsylvania, pp. 68-79 (with M. Arenas and L. Bertossi).

  17. Query Answering in Inconsistent Databases. In Logics for Emerging Applications of Databases, J. Chomicki, R. van der Meyden, G. Saake, editors, Springer-Verlag, 2003 (with Leopoldo Bertossi).

  18. Consistent Query Answering: Recent Developments and Future Directions. Proc. Sixth IFIP TC-11 WG 11.5 Working Conference on Integrity and Internal Control in Information Systems, November 2003, Lausanne, Switzerland, Kluwer Publishers.

  19. On the Computational Complexity of Minimal-Change Integrity Maintenance in Relational Databases. In Integrity Tolerance, L. Bertossi, A. Hunter, T. Schaub, editors, Springer-Verlag, 2005 (with J. Marcinkowski).

Talks:

  1. Consistent Query Answering: The First Ten Years. SUM'08, October 2008, Naples, Italy. Invited tutorial.

  2. Consistent Query Answering: Five Easy Pieces. ICDT'07, January 2007, Barcelona, Spain. Keynote talk.

  3. Consistent Query Answering: Opportunities and Limitations. LAAIC, September 2006, Cracow, Poland. Keynote talk.

  4. Consistent Query Answering: Recent Developments and Future Directions. Sixth IFIP TC-11 WG 11.5 Working Conference on Integrity and Internal Control in Information Systems, November 2003, Lausanne, Switzerland. Keynote talk.

  5. Consistent Answers to Quantifier-Free Queries. Dagstuhl Seminar 03241, June 2003.

  6. Consistent Query Answers in Inconsistent Databases. November 2001.

Systems:

Documents: 

http://www.cse.buffalo.edu/~chomicki/cqa.html