A Sound and Complete Backward Chaining Algorithm for Existential Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports Year : 2012

A Sound and Complete Backward Chaining Algorithm for Existential Rules

Abstract

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.
Fichier principal
Vignette du fichier
main.pdf (217.71 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00713182 , version 1 (19-07-2012)
lirmm-00713182 , version 2 (10-09-2012)
lirmm-00713182 , version 3 (07-11-2013)

Identifiers

  • HAL Id : lirmm-00713182 , version 3

Cite

Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo. A Sound and Complete Backward Chaining Algorithm for Existential Rules. RR-12016, 2012. ⟨lirmm-00713182v3⟩
356 View
808 Download

Share

More