SpringerLink
Log in

Complexity of Consistent Query Answering in Databases Under Cardinality-Based and Incremental Repair Semantics

  • Conference paper
Database Theory – ICDT 2007 (ICDT 2007)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 4353))

Included in the following conference series:

  • 736 Accesses

Abstract

A database D may be inconsistent wrt a given set IC of integrity constraints. Consistent Query Answering (CQA) is the problem of computing from D the answers to a query that are consistent wrt IC. Consistent answers are invariant under all the repairs of D, i.e. the consistent instances that minimally depart from D. Three classes of repair have been considered in the literature: those that minimize set-theoretically the set of tuples in the symmetric difference; those that minimize the changes of attribute values, and those that minimize the cardinality of the set of tuples in the symmetric difference. The latter class has not been systematically investigated. In this paper we obtain algorithmic and complexity theoretic results for CQA under this cardinality-based repair semantics. We do this in the usual, static setting, but also in a dynamic framework where a consistent database is affected by a sequence of updates, which may make it inconsistent. We also establish comparative results with the other two kinds of repairs in the dynamic case.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Arenas, M., Bertossi, L., Chomicki, J.: Consistent Query Answers in Inconsistent Databases. In: Proc. ACM Symposium on Principles of Database Systems (PODS 1999), pp. 68–79. ACM Press, New York (1999)

    Chapter  Google Scholar 

  2. 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)

    Article  MATH  MathSciNet  Google Scholar 

  3. Arenas, M., Bertossi, L., Chomicki, J., He, X., Raghavan, V., Spinrad, J.: Scalar Aggregation in Inconsistent Databases. Theoretical Computer Science 296, 405–434 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bertossi, L., Bravo, L., Franconi, E., Lopatenko, A.: Fixing Numerical Attributes under Integrity Constraints. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 262–278. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  5. Bertossi, L., Chomicki, J.: Query Answering in Inconsistent Databases. In: Logics for Emerging Applications of Databases, pp. 43–83. Springer, Heidelberg (2003)

    Google Scholar 

  6. Buccafurri, F., Leone, N., Rullo, P.: Enhancing Disjunctive Datalog by Constraints. IEEE Transactions on Knowledge and Data Engineering 12(5), 845–860 (2000)

    Article  Google Scholar 

  7. Calì, A., Lembo, D., Rosati, R.: Complexity of Query Answering over Inconsistent and Incomplete Databases. In: Proc. ACM Symposium on Principles of Database Systems (PODS 2003), pp. 260–271. ACM Press, New York (2003)

    Google Scholar 

  8. Chen, J., Kanj, I., Jia, W.: Vertex Cover: Further Observations and Further Improvements. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, pp. 313–324. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  9. Chomicki, J., Marcinkowski, J.: Minimal-Change Integrity Maintenance using Tuple Deletions. Information and Computation 197(1-2), 90–121 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  10. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1999)

    Google Scholar 

  11. Eiter, T., Gottlob, G.: On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. Artificial Intelligence 57(2-3), 227–270 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  12. 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)

    Chapter  Google Scholar 

  13. Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, Heidelberg (2006)

    Google Scholar 

  14. Franconi, E., Laureti Palma, A., 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)

    Chapter  Google Scholar 

  15. Fuxman, A., Miller, R.: First-Order Query Rewriting for Inconsistent Databases. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 337–351. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  16. Garey, M., Johnson, D., Stockmeyer, L.: Some Simplified NP-Complete Graph Problems. Theoretical Computer Science 1(3), 237–267 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  17. Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing 9, 365–385 (1991)

    Article  Google Scholar 

  18. Greco, G., Scarcello, F.: On the Complexity of Computing Peer Agreements for Consistent Query Answering in Peer-to-Peer Data Integration Systems. In: Proc. International Conference on Information and Knowledge Management (CIKM 2005), pp. 36–43. ACM Press, New York (2005)

    Chapter  Google Scholar 

  19. Grohe, M.: Parameterized Complexity for the Data-base Theorist. SIGMOD Record 31(4), 86–96 (2002)

    Article  Google Scholar 

  20. Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, Heidelberg (1999)

    MATH  Google Scholar 

  21. Krentel, M.: The Complexity of Optimization Problems. J. Computer and Systems Sciences 36, 490–509 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  22. Lopatenko, A., Bertossi, L.: Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics. Corr Archiv paper cs.DB/0604002

    Google Scholar 

  23. Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity Models for Incremental Computation. Theoretical Computer Science 130(1), 203–236 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  24. Niedermeier, R., Rossmanith, P.: An Efficient Fixed-Parameter Algorithm for 3-Hitting Set. Journal of Discrete Algorithms 1(1), 89–102 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  25. Papadimitriou, C.H., Yannakakis, M.: On the Complexity of Database Queries. J. Comput. Syst. Sci. 58(3), 407–427 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  26. Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)

    MATH  Google Scholar 

  27. Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Eficiently Four-Coloring Planar Graphs. In: Proc. 28th ACM Symposium on the Theory of Computing (STOC 1996), pp. 571–575. ACM Press, New York (1996)

    Chapter  Google Scholar 

  28. Weber, V., Schwentick, T.: Dynamic Complexity Theory Revisited. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 256–268. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  29. Wijsen, J.: Condensed Representation of Database Repairs for Consistent Query Answering. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 378–393. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Computer Science, Free University of Bozen-Bolzano, Bozen-Bolzano, Italy

    Andrei Lopatenko

  2. School of Computer Science, Carleton University, Ottawa, Canada

    Leopoldo Bertossi

Authors
  1. Andrei Lopatenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leopoldo Bertossi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Technical University of Dortmund,  

    Thomas Schwentick

  2. Department of Computer Science and Engineering, University of Washington,  

    Dan Suciu

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lopatenko, A., Bertossi, L. (2006). Complexity of Consistent Query Answering in Databases Under Cardinality-Based and Incremental Repair Semantics. 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_13

Download citation

  • DOI: https://doi.org/10.1007/11965893_13

  • 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)

Publish with us

Policies and ethics

Search

Navigation