Capturing Homomorphism-Closed Decidable Queries with Existential Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2021

Capturing Homomorphism-Closed Decidable Queries with Existential Rules

Résumé

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. In this paper, 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.
Fichier principal
Vignette du fichier
BCKRT-terminating-chase-KR2021.pdf (509.67 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03345614 , version 1 (15-09-2021)

Identifiants

Citer

Camille Bourgaux, David Carral, Markus Krötzsch, Sebastian Rudolph, Michaël Thomazo. Capturing Homomorphism-Closed Decidable Queries with Existential Rules. KR 2021 - 18th International Conference on Principles of Knowledge Representation and Reasoning, Nov 2021, Virtual, Vietnam. pp.141-150, ⟨10.24963/kr.2021/14⟩. ⟨lirmm-03345614⟩
228 Consultations
143 Téléchargements

Altmetric

Partager

More