Sound, Complete, and Minimal Query Rewriting for Existential Rules

Mélanie König 1 Michel Leclère 1 Marie-Laure Mugnier 1 Michaël Thomazo 1
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 in the associated technical report.
Keywords : Ontology-Based Data Access Existential Rules
Type de document :
Communication dans un congrès
IJCAI: International Joint Conference on Artificial Intelligence, Aug 2013, Beijing, China. 23rd International Joint Conference on Artificial Intelligence, 2013, 〈http://ijcai-13.org〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00838791
Contributeur : Mélanie König <>
Soumis le : mercredi 26 juin 2013 - 15:41:37
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mercredi 5 avril 2017 - 04:38:57

Fichier

konig.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00838791, version 1

Collections

INRIA | GRAPHIK | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

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. 23rd International Joint Conference on Artificial Intelligence, 2013, 〈http://ijcai-13.org〉. 〈lirmm-00838791〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

291

Téléchargements de fichiers

304

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD