ConQuer: efficient management of inconsistent databases

ABSTRACT

Although integrity constraints have long been used to maintain data consistency, there are situations in which they may not be enforced or satisfied. In this paper, we present ConQuer, a system for efficient and scalable answering of SQL queries on databases that may violate a set of constraints. ConQuer permits users to postulate a set of key constraints together with their queries. The system rewrites the queries to retrieve all (and only) data that is consistent with respect to the constraints. The rewriting is into SQL, so the rewritten queries can be efficiently optimized and executed by commercial database systems.We study the overhead of resolving inconsistencies dynamically (at query time). In particular, we present a set of performance experiments that compare the efficiency of the rewriting strategies used by ConQuer. The experiments use queries taken from the TPC-H workload. We show that the overhead is not onerous, and the consistent query answers can often be computed within twice the time required to obtain the answers to the original (non-rewritten) query.

REFERENCES

• 1: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 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 E. Bertossi , Jan Chomicki, Scalar Aggregation in FD-Inconsistent Databases, Proceedings of the 8th International Conference on Database Theory, p.39-53, January 04-06, 2001
• 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: 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]
• 6: Jan Chomicki , Jerzy Marcinkowski , Slawomir Staworko, Computing consistent query answers using conflict hypergraphs, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031254]
• 7: J. Chomicki, J. Marcinkowski, and S. Staworko. Hippo: A System for Computing Consistent Answers to a Class of SQL Queries. In EDBT, pages 841--844, 2004.
• 8: N. Dalvi and D. Suciu. Efficient Query Evaluation on Probabilistic Databases. In VLDB, pages 864--875, 2004.
• 9: Tamraparni Dasu , Theodore Johnson, Exploratory Data Mining and Data Cleaning, John Wiley & Sons, Inc., New York, NY, 2003
• 10: T. Eiter, M. Fink, G. Greco, and D. Lembo. Efficient Evaluation of Logic Programs for Querying Data Integration Systems. In ICLP, pages 163--177, 2003.
• 11: A. Fuxman and R. J. Miller. First-Order Query Rewriting for Inconsistent Databases. In ICDT, pages 337--351, 2005.
• 12: D. Lembo, M. Lenzerini, and R. Rosati. Source Inconsistency and Incompleteness in Data Integration. In KRDB, 2002.