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

A Sound and Complete Backward Chaining Algorithm for Existential Rules

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

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 (166.36 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00764341 , version 1 (12-12-2012)
lirmm-00764341 , version 2 (30-05-2013)
lirmm-00764341 , version 3 (07-11-2013)

Identifiers

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: Web Reasoning and Rule Systems, Sep 2012, Vienna, Austria. pp.122-138, ⟨10.1007/978-3-642-33203-6_10⟩. ⟨lirmm-00764341v3⟩
227 View
362 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More