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

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

Sponsored by
Published by

Copyright © 2021 International Joint Conferences on Artificial Intelligence Organization

Parallelisable Existential Rules: a Story of Pieces

  1. Maxime Buron(University of Oxford, United Kingdom)
  2. Marie-Laure Mugnier(LIRMM, Inria, University of Montpellier, CNRS, France)
  3. Michaël Thomazo(Inria, DI ENS, ENS, CNRS, PSL University, France)


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


In this paper, we consider existential rules, an expressive formalism well adapted to the representation of ontological knowledge, as well as data-to-ontology mappings in the context of ontology-based data integration.

The chase is a fundamental tool to do reasoning with existential rules as it computes all the facts entailed by the rules from a database instance. We introduce parallelisable sets of existential rules, for which the chase can be computed in a single breadth-first step from any instance. The question we investigate is the characterization of such rule sets. We show that parallelisable rule sets are exactly those rule sets both bounded for the chase and belonging to a novel class of rules, called pieceful. The pieceful class includes in particular frontier-guarded existential rules and (plain) datalog. We also give another characterization of parallelisable rule sets in terms of rule composition based on rewriting.