SpringerLink
Log in

An Incremental Algorithm for Computing All Repairs in Inconsistent Knowledge Bases

  • Conference paper
  • First Online:
Ontologies and Concepts in Mind and Machine (ICCS 2020)

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

Included in the following conference series:

  • 399 Accesses

Abstract

Repair techniques are used for reasoning in presence of inconsistencies. Such techniques rely on optimisations to avoid the computation of all repairs while certain applications need the generation of all repairs. In this paper, we show that the problem of all repair computation is not trivial in practice. To account for a scalable solution, we provide an incremental approach for the computation of all repairs when the conflicts have a cardinality of at most three. We empirically study its performance on generated knowledge bases (where the knowledge base generator could be seen as a secondary contribution in itself).

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 EPUB and 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

Similar content being viewed by others

Notes

  1. 1.

    The algorithms avoid the problem of derivation loss [19] which is important for the completeness of our approach. Note that in Hecham et al. [19] the authors discuss how finding all derivations for an atom is practically feasible despite the problem being exponential for combined complexity but polynomial for data complexity.

  2. 2.

    The set of restricted conflicts by a set U is the set containing each intersection of a conflict with U. Namely, it is equal to \(\{ X \cap U \mid X \in Conflict(\mathcal {K})\}.\)

  3. 3.

    The computational problem of finding a single repair of \(\mathcal {F}\) w.r.t. a set \(Y \subseteq 2^{\mathcal {F}}\) is only in the NC complexity class when every \(y \in Y\) is such that \(|y| \le 3\), otherwise it has been proven to be in the RNC complexity class [6, 20].

  4. 4.

    A subrepair of U w.r.t. \(\mathcal {A}\) is a subset of a repair of U w.r.t. \(\mathcal {A}\).

References

  1. Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent databases. In: Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, USA, 31 May–2 June 1999, pp. 68–79 (1999). https://doi.org/10.1145/303976.303983

  2. Arioua, A., Croitoru, M., Buche, P.: DALEK: a tool for dialectical explanations in inconsistent knowledge bases. In: Computational Models of Argument - Proceedings of COMMA 2016, Potsdam, Germany, 12–16 September 2016, pp. 461–462 (2016). https://doi.org/10.3233/978-1-61499-686-6-461

  3. Baget, J.F., et al.: A general modifier-based framework for inconsistency-tolerant query answering. In: Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference, KR 2016, Cape Town, South Africa, 25–29 April 2016, pp. 513–516 (2016)

    Google Scholar 

  4. Baget, J.F., Gutierrez, A., Leclère, M., Mugnier, M.L., Rocher, S., Sipieter, C.: DLGP: An extended Datalog Syntax for Existential Rules and Datalog\(\pm \) Version 2.0, June 2015

    Google Scholar 

  5. Baget, J.F., Leclère, M., Mugnier, M.L., Salvat, E.: On rules with existential variables: walking the decidability line. Artif. Intell. 175(9–10), 1620–1654 (2011)

    Article  MathSciNet  Google Scholar 

  6. Beame, P., Luby, M.: Parallel search for maximal independence given minimal dependence. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, USA, 22–24 January 1990, pp. 212–218 (1990)

    Google Scholar 

  7. Benferhat, S., Bouraoui, Z., Croitoru, M., Papini, O., Tabia, K.: Non-objection inference for inconsistency-tolerant query answering. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9–15 July 2016, pp. 3684–3690 (2016)

    Google Scholar 

  8. Bienvenu, M.: On the complexity of consistent query answering in the presence of simple ontologies. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, 22–26 July 2012 (2012). http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4928

  9. Boros, E., Elbassioni, K.M., Gurvich, V., Khachiyan, L.: An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Process. Lett. 10(4), 253–266 (2000)

    Article  MathSciNet  Google Scholar 

  10. Bourgaux, C.: Inconsistency Handling in Ontology-Mediated Query Answering. Ph.D. thesis, Université Paris-Saclay, Paris, September 2016. https://tel.archives-ouvertes.fr/tel-01378723

  11. Calì, A., Gottlob, G., Lukasiewicz, T., Marnette, B., Pieris, A.: Datalog\(\pm \): a family of logical knowledge representation and query languages for new applications. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, Edinburgh, United Kingdom, 11–14 July 2010, pp. 228–242 (2010). https://doi.org/10.1109/LICS.2010.27

  12. Croitoru, M., Vesic, S.: What can argumentation do for inconsistent ontology query answering? In: Liu, W., Subrahmanian, V.S., Wijsen, J. (eds.) SUM 2013. LNCS (LNAI), vol. 8078, pp. 15–29. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40381-1_2

    Chapter  Google Scholar 

  13. Dahlhaus, E., Karpinski, M., Kelsen, P.: An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3. Inf. Process. Lett. 42(6), 309–313 (1992). https://doi.org/10.1016/0020-0190(92)90228-N

    Article  MathSciNet  MATH  Google Scholar 

  14. Gallo, G., Longo, G., Pallottino, S.: Directed hypergraphs and applications. Discrete Appl. Math. 42(2), 177–201 (1993). https://doi.org/10.1016/0166-218X(93)90045-P

    Article  MathSciNet  MATH  Google Scholar 

  15. Goldberg, M.K., Spencer, T.H.: A new parallel algorithm for the maximal independent set problem. SIAM J. Comput. 18(2), 419–427 (1989). https://doi.org/10.1137/0218029

    Article  MathSciNet  MATH  Google Scholar 

  16. Grégoire, É., Mazure, B., Piette, C.: Boosting a complete technique to find MSS and MUS thanks to a local search oracle. In: IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 6–12 January 2007, pp. 2300–2305 (2007). http://ijcai.org/Proceedings/07/Papers/370.pdf

  17. Grégoire, É., Mazure, B., Piette, C.: Using local search to find MSSes and MUSes. Eur. J. Oper. Res. 199(3), 640–646 (2009). https://doi.org/10.1016/j.ejor.2007.06.066

    Article  MATH  Google Scholar 

  18. Hecham, A.: Defeasible reasoning for existential rules. (Raisonnement defaisable dans les règles existentielles). Ph.D. thesis (2018). https://tel.archives-ouvertes.fr/tel-01904558

  19. Hecham, A., Bisquert, P., Croitoru, M.: On the chase for all provenance paths with existential rules. In: Proceedings of the Rules and Reasoning - International Joint Conference, RuleML+RR 2017, London, UK, 12–15 July 2017, pp. 135–150 (2017)

    Google Scholar 

  20. Kelsen, P.: On the parallel complexity of computing a maximal independent set in a hypergraph. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 4–6 May 1992, pp. 339–350 (1992). https://doi.org/10.1145/129712.129745

  21. Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Inconsistency-tolerant semantics for description logics. In: Hitzler, P., Lukasiewicz, T. (eds.) RR 2010. LNCS, vol. 6333, pp. 103–117. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15918-3_9

    Chapter  Google Scholar 

  22. Poggi, A., Lembo, D., Calvanese, D., Giacomo, G.D., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. Data Semant. 10, 133–173 (2008)

    MATH  Google Scholar 

  23. Rocher, S.: Interrogation tolérante aux incohérences, Technical report. Université de Montpellier (2013)

    Google Scholar 

  24. Tamani, N., et al.: Eco-efficient packaging material selection for fresh produce: industrial session. In: Hernandez, N., Jäschke, R., Croitoru, M. (eds.) ICCS 2014. LNCS (LNAI), vol. 8577, pp. 305–310. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08389-6_27

    Chapter  Google Scholar 

  25. Yun, B., Bisquert, P., Buche, P., Croitoru, M.: Arguing about end-of-life of packagings: preferences to the rescue. In: Garoufallou, E., Subirats Coll, I., Stellato, A., Greenberg, J. (eds.) MTSR 2016. CCIS, vol. 672, pp. 119–131. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49157-8_10

    Chapter  Google Scholar 

  26. Yun, B., Vesic, S., Croitoru, M., Bisquert, P.: Inconsistency measures for repair semantics in OBDA. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, 13–19 July 2018, pp. 1977–1983 (2018). https://doi.org/10.24963/ijcai.2018/273

Download references

Acknowledgement

The second author acknowledges the support of the Docamex project, funded by the French Ministry of Agriculture.

Author information

Authors and Affiliations

  1. University of Aberdeen, Aberdeen, UK

    Bruno Yun

  2. University of Montpellier, Montpellier, France

    Madalina Croitoru

Authors
  1. Bruno Yun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Madalina Croitoru
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bruno Yun .

Editor information

Editors and Affiliations

  1. FIZ Karlsruhe – Leibniz Institute for Information Infrastructure, Karlsruhe, Germany

    Mehwish Alam

  2. Institute of Information Systems, University of Lübeck, Lübeck, Germany

    Tanya Braun

  3. Department of Computing Science, University of Aberdeen, Aberdeen, UK

    Bruno Yun

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Yun, B., Croitoru, M. (2020). An Incremental Algorithm for Computing All Repairs in Inconsistent Knowledge Bases. In: Alam, M., Braun, T., Yun, B. (eds) Ontologies and Concepts in Mind and Machine. ICCS 2020. Lecture Notes in Computer Science(), vol 12277. Springer, Cham. https://doi.org/10.1007/978-3-030-57855-8_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-57855-8_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-57854-1

  • Online ISBN: 978-3-030-57855-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation