Skip to Main content Skip to Navigation
Journal articles

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 2
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 repre-sented 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 any rewriting operator as a parameter, and de-fine properties of rewriting operators that ensure the correctness of the algorithm. Then, we focus on piece-unifiers, which provide a rewriting operator with the de-sired properties. Finally, we propose an implementation of this framework and report some experiments.
Document type :
Journal articles
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Michel Leclère <>
Submitted on : Thursday, December 4, 2014 - 5:43:06 PM
Last modification on : Thursday, January 7, 2021 - 2:30:03 PM
Long-term archiving on: : Saturday, April 15, 2017 - 2:30:39 AM


Files produced by the author(s)




Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo. Sound, Complete and Minimal UCQ-Rewriting for Existential Rules. Semantic Web – Interoperability, Usability, Applicability, IOS Press, 2015, 6 (5), pp.451-475. ⟨10.3233/SW-140153⟩. ⟨lirmm-01090370⟩



Record views


Files downloads