Abstract
Consistent query answering (CQA) is an approach to querying inconsistent databases without repairing them first. This invited talk introduces the basics of CQA, and discusses selected issues in this area. The talk concludes with a summary of other relevant work and an outline of potential future research topics.
Research supported by NSF grant IIS-0119186.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Andritsos, P., Fuxman, A., Miller, R.: Clean Answers over Dirty Databases. In: IEEE International Conference on Data Engineering (ICDE) (2006)
Arenas, M., Bertossi, L., Chomicki, J.: Consistent Query Answers in Inconsistent Databases. In: ACM Symposium on Principles of Database Systems (PODS), pp. 68–79 (1999)
Arenas, M., Bertossi, L., Chomicki, J.: Answer Sets for Consistent Query Answering in Inconsistent Databases. Theory and Practice of Logic Programming 3(4–5), 393–424 (2003)
Arenas, M., Bertossi, L., Chomicki, J., He, X., Raghavan, V., Spinrad, J.: Scalar Aggregation in Inconsistent Databases. Theoretical Computer Science 296(3), 405–434 (2003)
Baral, C., Kraus, S., Minker, J., Subrahmanian, V.S.: Combining Knowledge Bases Consisting of First-Order Theories. Computational Intelligence 8, 45–71 (1992)
Batini, C., Scannapieco, M.: Data Quality: Concepts, Methodologies and Techniques. Springer, Heidelberg (2006)
Bertossi, L.: Consistent Query Answering in Databases. SIGMOD Record 35(2) (June 2006)
Bertossi, L., Bravo, L.: Consistent Query Answers in Virtual Data Integration Systems. In: Bertossi, et al. (eds.) [12], pp. 42–83
Bertossi, L., Bravo, L., Franconi, E., Lopatenko, A.: Complexity and Approximation of Fixing Numerical Attributes in Databases Under Integrity Constraints. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 262–278. Springer, Heidelberg (2005)
Bertossi, L., Chomicki, J.: Query Answering in Inconsistent Databases. In: Chomicki, J., van der Meyden, R., Saake, G. (eds.) Logics for Emerging Applications of Databases, pp. 43–83. Springer, Heidelberg (2003)
Bertossi, L., Hunter, A., Schaub, T. (eds.): Inconsistency Tolerance. Springer, Heidelberg (2004)
Bille, P.: A Survey on Tree Edit Distance and Related Problems. Theoretical Computer Science 337(1-3), 217–239 (2003)
Bohannon, P., Flaster, M., Fan, W., Rastogi, R.: A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification. In: ACM SIGMOD International Conference on Management of Data, pp. 143–154 (2005)
Borgida, A.: Language Features for Flexible Handling of Exceptions in Information Systems. ACM Transactions on Database Systems 10(4), 565–603 (1985)
Bravo, L., Bertossi, L.: Logic Programs for Consistently Querying Data Integration Systems. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 10–15 (2003)
Bravo, L., Bertossi, L.: Semantically Correct Query Answers in the Presence of Null Values. In: EDBT Workshops (IIDB), Springer, Heidelberg (2006)
Bry, F.: Query Answering in Information Systems with Integrity Constraints. In: IFIP WG 11.5 Working Conference on Integrity and Control in Information Systems, pp. 113–130. Chapman and Hall, Boca Raton (1997)
Calì, A., Lembo, D., Rosati, R.: On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases. In: ACM Symposium on Principles of Database Systems (PODS), pp. 260–271 (2003)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Inconsistency Tolerance in P2P Data Integration: An Epistemic Logic Approach. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 90–105. Springer, Heidelberg (2005)
Celle, A., Bertossi, L.: Querying Inconsistent Databases: Algorithms and Implementation. In: Palamidessi, C., Moniz Pereira, L., Lloyd, J.W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Sagiv, Y., Stuckey, P.J. (eds.) CL 2000. LNCS (LNAI), vol. 1861, pp. 942–956. Springer, Heidelberg (2000)
Chakravarthy, U.S., Grant, J., Minker, J.: Logic-Based Approach to Semantic Query Optimization. ACM Transactions on Database Systems 15(2), 162–207 (1990)
Chandra, A., Merlin, P.: Optimal Implementation of Conjunctive Queries in Relational Databases. In: ACM SIGACT Symposium on the Theory of Computing (STOC), pp. 77–90 (1977)
Chomicki, J.: Consistent Query Answering: Opportunities and Limitations. In: DEXA Workshops (LAAIC), pp. 527–531. IEEE Computer Society Press, Los Alamitos (2006)
Chomicki, J., Marcinkowski, J.: On the Computational Complexity of Minimal-Change Integrity Maintenance in Relational Databases. In: Bertossi, et al. (eds.) [12], pp. 119–150
Chomicki, J., Marcinkowski, J.: Minimal-Change Integrity Maintenance Using Tuple Deletions. Information and Computation 197(1-2), 90–121 (2005)
Chomicki, J., Marcinkowski, J., Staworko, S.: Computing Consistent Query Answers Using Conflict Hypergraphs. In: International Conference on Information and Knowledge Management (CIKM), pp. 417–426. ACM Press, New York (2004)
Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and Expressive Power of Logic Programming. ACM Computing Surveys 33(3), 374–425 (2001)
Eiter, T., Fink, M., Greco, G., Lembo, D.: Efficient Evaluation of Logic Programs for Querying Data Integration Systems. In: International Conference on Logic Programming (ICLP), pp. 163–177 (2003)
Embury, S.M., Brandt, S.M., Robinson, J.S., Sutherland, I., Bisby, F.A., Gray, W.A., Jones, A.C., White, R.J.: Adapting Integrity Enforcement Techniques for Data Reconciliation. Information Systems 26(8), 657–689 (2001)
Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data Exchange: Semantics and Query Answering. Theoretical Computer Science 336(1), 89–124 (2005)
Fan, W., Simeon, J.: Integrity Constraints for XML. Journal of Computer and System Sciences 66(1), 201–254 (2003)
Fazzinga, B., Flesca, S., Furfaro, F., Parisi, F.: DART: a Data Acquisition and Repairing Tool. In: EDBT Workshops (IIDB), Springer, Heidelberg (2006)
Flesca, S., Furfaro, F., Greco, S., Zumpano, E.: Querying and Repairing Inconsistent XML Data. In: Ngu, A.H.H., Kitsuregawa, M., Neuhold, E.J., Chung, J.-Y., Sheng, Q.Z. (eds.) WISE 2005. LNCS, vol. 3806, pp. 175–188. Springer, Heidelberg (2005)
Flesca, S., Furfaro, F., Parisi, F.: Consistent Query Answers on Numerical Databases under Aggregate Constraints. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 279–294. Springer, Heidelberg (2005)
Franconi, E., Palma, A.L., Leone, N., Perri, S., Scarcello, F.: Census Data Repair: a Challenging Application of Disjunctive Logic Programming. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol. 2250, pp. 561–578. Springer, Heidelberg (2001)
Fuxman, A., Miller, R.J.: ConQuer: Efficient Management of Inconsistent Databases. In: ACM SIGMOD International Conference on Management of Data, pp. 155–166 (2005)
Fuxman, A., Miller, R.J.: First-Order Query Rewriting for Inconsistent Databases. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 337–351. Springer, Heidelberg (2004)
Greco, G., Greco, S., Zumpano, E.: A Logical Framework for Querying and Repairing Inconsistent Databases. IEEE Transactions on Knowledge and Data Engineering 15(6), 1389–1408 (2003)
Greco, S., Sirangelo, C., Trubitsyna, I., Zumpano, E.: Preferred Repairs for Inconsistent Databases. In: International Conference on Database and Expert Systems Applications (DEXA), pp. 44–55 (2004)
Grieco, L., Lembo, D., Rosati, R., Ruzzi, M.: Consistent Query Answering under Keys and Exclusion Dependencies: Algorithms and Experiments. In: International Conference on Information and Knowledge Management (CIKM), pp. 792–799. ACM Press, New York (2005)
Imieliński, T., Lipski, W.: Incomplete Information in Relational Databases. Journal of the ACM 31(4), 761–791 (1984)
Imieliński, T., Naqvi, S., Vadaparty, K.: Incomplete Objects - A Data Model for Design and Planning Applications. In: ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 1991, pp. 288–297 (1991)
Johnson, D.S., Klug, A.: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. Journal of Computer and System Sciences 28(1), 167–189 (1984)
Lipski Jr., W.: On Semantic Issues Connected with Incomplete Information Databases. ACM Transactions on Database Systems 4(3), 262–296 (1979)
Kanellakis, P.C.: Elements of Relational Database Theory. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, ch. 17, pp. 1073–1158. Elsevier/MIT Press (1990)
Lembo, D., Rosati, R., Ruzzi, M.: On the First-Order Reducibility of Unions of Conjunctive Queries over Inconsistent Databases. In: EDBT Workshops (IIDB) (2006)
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV System for Knowledge Representation and Reasoning. ACM Transactions on Computational Logic (to appear, 2006)
Lin, J., Mendelzon, A.O.: Merging Databases under Constraints. International Journal of Cooperative Information Systems 7(1), 55–76 (1996)
Lopatenko, A., Bertossi, L.: Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics. In: International Conference on Database Theory (ICDT) (to appear, 2007)
Melton, J., Simon, A.R.: SQL:1999 Understanding Relational Language Components. Morgan Kaufmann, San Francisco (2002)
Simons, P., Niemelä, I., Soininen, T.: Extending and Implementing the Stable Model Semantics. Artificial Intelligence 138(1-2), 181–234 (2002)
Staworko, S., Chomicki, J.: Consistent Query Answers in the Presence of Universal Constraints (October 2006) manuscript
Staworko, S., Chomicki, J.: Validity-Sensitive Querying of XML Databases. In: EDBT Workshops (dataX), Springer, Heidelberg (2006)
Staworko, S., Chomicki, J., Marcinkowski, J.: Priority-Based Conflict Resolution in Inconsistent Relational Databases. In: EDBT Workshops (IIDB), Springer, Heidelberg (2006)
van der Meyden, R.: Logical Approaches to Incomplete Information: A Survey. In: Chomicki, J., Saake, G. (eds.) Logics for Databases and Information Systems, ch. 10, pp. 307–356. Kluwer Academic Publishers, Boston (1998)
Vardi, M.Y.: The Complexity of Relational Query Languages. In: ACM Symposium on Theory of Computing (STOC), pp. 137–146 (1982)
Wijsen, J.: Database Repairing Using Updates. ACM Transactions on Database Systems 30(3), 722–768 (2005)
Wijsen, J.: Project-Join Repair: An Approach to Consistent Query Answering Under Functional Dependencies. In: International Conference on Flexible Query Answering Systems (FQAS) (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chomicki, J. (2006). Consistent Query Answering: Five Easy Pieces. In: Schwentick, T., Suciu, D. (eds) Database Theory – ICDT 2007. ICDT 2007. Lecture Notes in Computer Science, vol 4353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11965893_1
Download citation
DOI: https://doi.org/10.1007/11965893_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69269-0
Online ISBN: 978-3-540-69270-6
eBook Packages: Computer ScienceComputer Science (R0)