KR2021Proceedings of the 18th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning

Online event. November 3-12, 2021.

Edited by
  1. Meghyn Bienvenu
  2. Gerhard Lakemeyer
  3. Esra Erdem

ISSN: 2334-1033
ISBN: 978-1-956792-99-7

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

Capturing Homomorphism-Closed Decidable Queries with Existential Rules

  1. Camille Bourgaux(DIENS, ENS, CNRS, PSL University & Inria)
  2. David Carral(LIRMM, Inria, University of Montpellier, CNRS)
  3. Markus Krötzsch(TU Dresden)
  4. Sebastian Rudolph(TU Dresden)
  5. Michaël Thomazo(Inria, DIENS, ENS, CNRS, PSL University)
PDF
BibTeX
https://doi.org/10.24963/kr.2021/14

Keywords

  1. Computational aspects of knowledge representation
  2. Knowledge representation languages
  3. Ontology-based data access, integration, and exchange

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.