Skip to Main content Skip to Navigation
New interface
Conference papers

Parallelisable Existential Rules: a Story of Pieces

Maxime Buron 1, 2 Marie-Laure Mugnier 3, 4 Michaël Thomazo 5 
2 CEDAR - Rich Data Analytics at Cloud Scale
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
3 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
5 VALDA - Value from Data
DI-ENS - Département d'informatique - ENS Paris, Inria de Paris
Abstract : In this paper, we consider existential rules, an expressive formalism well suited to the representation of ontological knowledge and 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.
Complete list of metadata
Contributor : Michaël Thomazo Connect in order to contact the contributor
Submitted on : Wednesday, October 27, 2021 - 1:55:06 PM
Last modification on : Friday, August 5, 2022 - 3:03:00 PM
Long-term archiving on: : Friday, January 28, 2022 - 7:00:30 PM


Files produced by the author(s)


  • HAL Id : hal-03405745, version 1


Maxime Buron, Marie-Laure Mugnier, Michaël Thomazo. Parallelisable Existential Rules: a Story of Pieces. KR 2021 - 18th International Conference on Principles of Knowledge Representation and Reasoning, Nov 2021, Virtual, Vietnam. ⟨hal-03405745⟩



Record views


Files downloads