A Sound and Complete Backward Chaining Algorithm for Existential Rules

Mélanie König 1 Michel Leclère 1 Marie-Laure Mugnier 1, * Michaël Thomazo 1
* Corresponding author
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 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.
Document type :
Reports
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00713182
Contributor : Mélanie König <>
Submitted on : Thursday, November 7, 2013 - 10:56:31 AM
Last modification on : Wednesday, June 5, 2019 - 11:58:13 AM
Long-term archiving on : Monday, February 10, 2014 - 11:23:17 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00713182, version 3

Collections

Citation

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⟩

Share

Metrics

Record views

526

Files downloads

741