A Sound and Complete Backward Chaining Algorithm for Existential Rules - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2012

A Sound and Complete Backward Chaining Algorithm for Existential Rules

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00713182 , version 3

Citer

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⟩
303 Consultations
735 Téléchargements

Partager

Gmail Facebook X LinkedIn More