Distance-Based Repairs of Databases | SpringerLink
Skip to main content
Springer Nature Link
Log in

Distance-Based Repairs of Databases

  • Conference paper
Logics in Artificial Intelligence (JELIA 2006)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 4160))

Included in the following conference series:

Abstract

We introduce a general framework for repairing inconsistent databases by distance-based considerations. The uniform way of representing repairs and their semantics clarifies the essence behind various approaches to consistency restoration in database systems, helps to compare the underlying formalisms, and relates them to existing methods of defining belief revision operators, merging data sets, and integrating information systems.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping 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. PODS 1999, pp. 68–79 (1999)

    Google Scholar 

  2. Arenas, M., Bertossi, L., Chomicki, J.: Answer sets for consistent query answering in inconsistent databases. Theory and Practice of Log. Prog. 3(4-5), 393–424 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  3. Arieli, O., Denecker, M., Van Nuffelen, B., Bruynooghe, M.: Coherent integration of databases by abductive logic programming. Artif. Intell. Res. 21, 245–286 (2004)

    MATH  Google Scholar 

  4. Arieli, O., Denecker, M., Van Nuffelen, B., Bruynooghe, M.: Computational methods for database repair by signed formulae. Annals Math. Artif. Intell. 46, 4–37 (2006)

    Article  MATH  Google Scholar 

  5. Bertossi, L.: Some research directions in consistent query answering: a vision. In: Pre-proc. of EDBT 2006 Workshop on Inconsistency in Databases, pp.109–113 (2006)

    Google Scholar 

  6. Bertossi, L., Chomicki, J., Cortés, A., Gutierrez, C.: Consistent answers from integrated data sources. In: Andreasen, T., Motro, A., Christiansen, H., Larsen, H.L. (eds.) FQAS 2002. LNCS, vol. 2522, pp. 71–85. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  7. Bertossi, L., Schwind, C.: Database repairs and analytic tableau. Annals of Mathematics and Artificial Intelligence 40(1-2), 5–35 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  8. Cali, A., Lembo, D., Rosati, R.: On the decidability and complexity of query answering over inconsistent and incomplete databases. In: Proc. PODS 2003, pp. 260–271 (2003)

    Google Scholar 

  9. Chomicki, J., Marcinkowski, J.: On the computational complexity of minimal-change integrity maintenance in relational databases. In: Bertossi, L., Hunter, A., Schaub, T. (eds.) Inconsistency Tolerance. LNCS, vol. 3300, pp. 119–150. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  10. Chomicki, J., Marchinkowski, J.: Minimal-change integrity maintenance using tuple deletion. Journal of Information and Computation 197(1-2), 90–121 (2005)

    Article  MATH  Google Scholar 

  11. Chomicki, J., Marchinkowski, J., Staworko, S.: Computing consistent query answers using conflict hypergraphs. In: Proc. CIKM 2004, pp. 417–426 (2004)

    Google Scholar 

  12. Dalal, M.: Investigations into a theory of knowledge base revision. In: Proc. AAAI 1998, pp. 475–479. AAAI Press, Menlo Park (1988)

    Google Scholar 

  13. de Amo, S., Carnielli, W.A., Marcos, J.: A logical framework for integrating inconsistent information in multiple databases. In: Eiter, T., Schewe, K.-D. (eds.) FoIKS 2002. LNCS, vol. 2284, pp. 67–84. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  14. Delgrande, J.: Preliminary considerations on the modelling of belief change operators by metric spaces. In: Proc. NMR 2004, pp. 118–125 (2004)

    Google Scholar 

  15. Dieudonné, J. (ed.): Foundations of Modern Analysis. Academic Press, London (1969)

    MATH  Google Scholar 

  16. Eiter, T.: Data integration and answer set programming. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS, vol. 3662, pp. 13–25. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  17. Eiter, T., Mannila, H.: Distance measure for point sets and their computation. Acta Informatica 34, 109–133 (1997)

    Article  MathSciNet  Google Scholar 

  18. Fazzinga, B., Flesca, S., Furfaro, F., Parisi, F.: DART: A data acquisition and repairing tool. In: Grust, T., Höpfner, H., Illarramendi, A., Jablonski, S., Mesiti, M., Müller, S., Patranjan, P.-L., Sattler, K.-U., Spiliopoulou, M., Wijsen, J. (eds.) EDBT 2006. LNCS, vol. 4254, pp. 2–16. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  19. Franconi, E., Palma, A., Leone, N., Perri, D., Scarcello, F.: Census data repair: A challenging application of disjunctive logic programming. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS, vol. 2250, pp. 561–578. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  20. Gelfond, N., Lifschitz, V.: The stable model semantics for logic programming. In: Proc. 5th Logic Programming Symposium, pp. 1070–1080. MIT Press, Cambridge (1988)

    Google Scholar 

  21. Greco, G., Greco, S., Zumpano, E.: A logic programming approach to the integration, repairing and querying of inconsistent databases. In: Codognet, P. (ed.) ICLP 2001. LNCS, vol. 2237, pp. 348–363. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  22. Greco, S., Zumpano, E.: Querying inconsistent databases. In: Parigot, M., Voronkov, A. (eds.) LPAR 2000. LNCS (LNAI), vol. 1955, pp. 308–325. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  23. Kifer, M., Lozinskii, E.L.: A logic for reasoning with inconsistency. Journal of Automated Reasoning 9(2), 179–215 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  24. Kleene, S.C.: Introduction to Metamathematics, Van Nostrand (1950)

    Google Scholar 

  25. Konieczny, S., Lang, J., Marquis, P.: Distance-based merging: A general framework and some complexity results. In: Proc KR 2002, pp. 97–108 (2002)

    Google Scholar 

  26. Konieczny, S., Pino Pérez, R.: Merging information under constraints: a logical framework. Journal of Logic and Computation 12(5), 773–808 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  27. Lehmann, D., Magidor, M., Schlechta, K.: Distance semantics for belief revision. Journal of Symbolic Logic 66(1), 295–317 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  28. Leone, N., Eiter, T., Faber, W., Fink, M., Gottlob, G., Greco, G.: Boosting information integration: The INFOMIX system. In: Proc. SEBD 2005, pp. 55–66 (2005)

    Google Scholar 

  29. Liberatore, P., Schaerf, M.: BReLS: A system for the integration of knowledge bases. In: Proc. KR 2000, pp. 145–152. Morgan Kaufmann Publishers, San Francisco (2000)

    Google Scholar 

  30. Nienhuys-Cheng, S.H.: Distance between Herbrand interpretations: A measure for approximations to a target concept. In: Džeroski, S., Lavrač, N. (eds.) ILP 1997. LNCS, vol. 1297, pp. 213–226. Springer, Heidelberg (1997)

    Google Scholar 

  31. Peppas, P., Chopra, S., Foo, N.: Distance semantics for relevance-sensitive belief revision. In: Proc. KR 2004, pp. 319–328. AAAI Press, Menlo Park (2004)

    Google Scholar 

  32. Ramon, J., Bruynooghe, M.: A polynomial time computable metric between point sets. Acta Informatica 37(10), 765–780 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  33. Reiter, R.: On closed world databases. In: Logic and Databases, pp. 55–76 (1978)

    Google Scholar 

  34. Wijsen, J.: Database repairing using updates. ACM Transactions on Database Systems 30(3), 722–768 (2005)

    Article  Google Scholar 

  35. Winslett, M.: Reasoning about action using a possible models approach. In: Proc. AAAI 1998, pp. 89–93. AAAI Press, Menlo Park (1988)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, The Academic College of Tel-Aviv, Israel

    Ofer Arieli

  2. Department of Computer Science, Katholieke Universiteit Leuven, Belgium

    Marc Denecker & Maurice Bruynooghe

Authors
  1. Ofer Arieli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marc Denecker
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maurice Bruynooghe
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Liverpool, Liverpool, U.K.

    Michael Fisher

  2. University of Liverpool, United Kingdom

    Wiebe van der Hoek

  3. University of Liverpool, Liverpool, UK

    Boris Konev

  4. Department of Computer Science, The University of Liverpool,  

    Alexei Lisitsa

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Arieli, O., Denecker, M., Bruynooghe, M. (2006). Distance-Based Repairs of Databases. In: Fisher, M., van der Hoek, W., Konev, B., Lisitsa, A. (eds) Logics in Artificial Intelligence. JELIA 2006. Lecture Notes in Computer Science(), vol 4160. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11853886_6

Download citation

  • DOI: https://doi.org/10.1007/11853886_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-39625-3

  • Online ISBN: 978-3-540-39627-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation