Sound, Complete, and Minimal Query Rewriting for Existential Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2013

Sound, Complete, and Minimal Query Rewriting for Existential Rules

Mélanie König
Michel Leclère
Michaël Thomazo


We address the issue of Ontology-Based Data Access which consists of exploiting the semantics expressed in ontologies while querying data. Ontologies are represented in the framework of existential rules, also known as Datalog+/-. We focus on the backward chaining paradigm, which involves rewriting the query (assumed to be a conjunctive query, CQ) into a set of CQs (seen as a union of CQs). The proposed algorithm accepts any set of existential rules as input and stops for so-called finite unification sets of rules (fus). The rewriting step relies on a graph notion, called a piece, which allows to identify subsets of atoms from the query that must be processed together. We first show that our rewriting method computes a minimal set of CQs when this set is finite, i.e., the set of rules is a fus. We then focus on optimizing the rewriting step. First experiments are reported in the associated technical report.
Fichier principal
Vignette du fichier
konig.pdf (186.32 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00838791 , version 1 (26-06-2013)


  • HAL Id : lirmm-00838791 , version 1


Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo. Sound, Complete, and Minimal Query Rewriting for Existential Rules. IJCAI: International Joint Conference on Artificial Intelligence, Aug 2013, Beijing, China. ⟨lirmm-00838791⟩
239 View
217 Download


Gmail Mastodon Facebook X LinkedIn More