Capturing Homomorphism-Closed Decidable Queries with Existential Rules (Extended Abstract)

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Contributors

  • Camille Bourgaux - , Ecole Normale Superieure, INRIA - Institut national de recherche en informatique et en automatique (Author)
  • David Carral - , University of Montpellier (Author)
  • Markus Krötzsch - , Chair of Knowledge-based Systems (cfaed) (Author)
  • Sebastian Rudolph - , Chair of Computational Logic (Author)
  • Michaël Thomazo - , Ecole Normale Superieure, INRIA - Institut national de recherche en informatique et en automatique (Author)

Abstract

Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize properties that are preserved under homomorphisms. This paper is an extended abstract of our eponymous publication at KR 2021 where we show the converse: every decidable query that is closed under homomorphism can be expressed by an existential rule set for which the standard chase universally terminates. Membership in this fragment is not decidable, but we show via a diagonalisation argument that this is unavoidable.

Details

Original languageEnglish
Title of host publicationProceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
EditorsLuc De Raedt, Luc De Raedt
PublisherInternational Joint Conferences on Artificial Intelligence
Pages5269-5273
Number of pages5
ISBN (electronic)978-1-956792-00-3
Publication statusPublished - 2022
Peer-reviewedYes

Publication series

SeriesIJCAI International Joint Conference on Artificial Intelligence
ISSN1045-0823

Conference

Title31st International Joint Conference on Artificial Intelligence, IJCAI 2022
Duration23 - 29 July 2022
CityVienna
CountryAustria

Keywords

ASJC Scopus subject areas