# Parallelisable Existential Rules: a Story of Pieces

arXiv: https://arxiv.org/abs/2107.06054 · HTML: https://mlsanity.com/paper/2107.06054/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 40 references that are in the map.
- First posted on arXiv 13 Jul 2021.

## Builds on (most cited first, 6 of 6)

- [The Vadalog System: Datalog-based Reasoning for Knowledge Graphs](https://mlsanity.com/paper/1807.08709/) (2018)
- [Sound, Complete and Minimal UCQ-Rewriting for Existential Rules](https://mlsanity.com/paper/1311.3198/) (2013)
- [Oblivious and Semi-Oblivious Boundedness for Existential Rules](https://mlsanity.com/paper/2006.08467/) (2020)
- [Extending Acyclicity Notions for Existential Rules (long version)](https://mlsanity.com/paper/1407.6885/) (2014)
- [Worst-case Optimal Query Answering for Greedy Sets of Existential Rules and Their Subclasses](https://mlsanity.com/paper/1412.4485/) (2014)
- [Characterizing Boundedness in Chase Variants](https://mlsanity.com/paper/2004.10030/) (2020)

## Built on by (most cited first, 1 of 1)

- [Query Rewriting with Disjunctive Existential Rules and Mappings](https://mlsanity.com/paper/2306.05973/) (2023)

## Abstract (arXiv)

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.