Skip to Main content Skip to Navigation
Conference papers

Capturing Homomorphism-Closed Decidable Queries with Existential Rules

Camille Bourgaux 1 David Carral 2 Markus Krötzsch 3 Sebastian Rudolph 3 Michaël Thomazo 1
1 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
2 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
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. 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.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03345614
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Wednesday, September 15, 2021 - 4:40:47 PM
Last modification on : Friday, October 15, 2021 - 1:41:28 PM

File

BCKRT-terminating-chase-KR2021...
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-03345614, version 1
  • ARXIV : 2107.07811

Citation

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. To appear. ⟨lirmm-03345614⟩

Share

Metrics

Record views

63

Files downloads

14