Capturing Homomorphism-Closed Decidable Queries with Existential Rules

Camille BourgauxCamille Bourgaux, David CarralDavid Carral, Markus KrötzschMarkus Krötzsch, Sebastian RudolphSebastian Rudolph, Michaël ThomazoMichaël Thomazo

Camille Bourgaux, David Carral, Markus Krötzsch, Sebastian Rudolph, Michaël Thomazo
Capturing Homomorphism-Closed Decidable Queries with Existential Rules
In Meghyn Bienvenu, Gerhard Lakemeyer, Esra Erdem, eds., Proc. 18th International Conference on Principles of Knowledge Representation and Reasoning (KR'21), 141--150, 2021

Details
Bibtex

KurzfassungAbstract
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.
Bemerkung: Note: This publication has received the Ray Reiter Best Paper Award at KR 2021!
Projekt:Project: CPEC, DeciGUT, ScaDS.AI
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{BCKRT2021,
  author    = {Camille Bourgaux and David Carral and Markus Kr{\"{o}}tzsch and
               Sebastian Rudolph and Micha{\"{e}}l Thomazo},
  title     = {Capturing Homomorphism-Closed Decidable Queries with Existential
               Rules},
  editor    = {Meghyn Bienvenu and Gerhard Lakemeyer and Esra Erdem},
  booktitle = {Proc. 18th International Conference on Principles of Knowledge
               Representation and Reasoning (KR'21)},
  year      = {2021},
  pages     = {141--150}
}