Skip to Main content Skip to Navigation

Sound, Complete and Minimal UCQ-Rewriting for Existential Rules

Mélanie König 1 Michel Leclère 1 Marie-Laure Mugnier 1 Michaël Thomazo 1
1 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
Abstract : We address the issue of Ontology-Based Data Access, with ontologies represented in the framework of existential rules, also known as Datalog+/-. A well-known approach involves rewriting the query using ontological knowledge. We focus here on the basic rewriting technique which consists of rewriting the initial query into a union of conjunctive queries. First, we study a generic breadth-first rewriting algorithm, which takes as input any rewriting operator, and define properties of rewriting operators that ensure the correctness of the algorithm. Then, we focus on piece-unifiers, which provide a rewriting operator with the desired properties. Finally, we propose an implementation of this framework and report some experiments.
Document type :
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Marie-Laure Mugnier <>
Submitted on : Tuesday, November 12, 2013 - 9:52:51 AM
Last modification on : Wednesday, June 5, 2019 - 11:58:12 AM
Long-term archiving on: : Thursday, February 13, 2014 - 12:05:35 PM


Files produced by the author(s)


  • HAL Id : lirmm-00903375, version 1



Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo. Sound, Complete and Minimal UCQ-Rewriting for Existential Rules. [Research Report] RR-13034, Lirmm. 2013, pp.29. ⟨lirmm-00903375⟩



Record views


Files downloads