A Generic Querying Algorithm for Greedy Sets of Existential Rules

Michaël Thomazo 1 Jean-François Baget 1 Marie-Laure Mugnier 1 Sebastian Rudolph 2
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 : Answering queries in information systems that allow for ex- pressive inferencing is currently a field of intense research. This problem is often referred to as ontology-based data ac- cess (OBDA). We focus on conjunctive query entailment un- der logical rules known as tuple-generating dependencies, existential rules or Datalog+/-. One of the most expressive decidable classes of existential rules known today is that of greedy bounded treewidth sets (gbts). We propose an algo- rithm for this class, which is worst-case optimal for data and combined complexities, with or without bound on the pred- icate arity. A beneficial feature of this algorithm is that it allows for separation between offline and online processing steps: the knowledge base can be compiled independently from queries, which are evaluated against the compiled form. Moreover, very simple adaptations of the algorithm lead to worst-case-optimal complexities for specific subclasses of gbts which have lower complexities, such as guarded rules.
Type de document :
Communication dans un congrès
KR: Principles of Knowledge Representation and Reasoning, Jun 2012, Rome, Italy. 13th International Conference on Principles of Knowledge Representation and Reasoning pp.096-106, 2012, 〈http://www.dis.uniroma1.it/~kr12/〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00763518
Contributeur : Thomazo Michaël <>
Soumis le : mardi 11 décembre 2012 - 08:57:18
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 12 mars 2013 - 03:52:56

Fichier

kr12-tbmr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00763518, version 1

Collections

Citation

Michaël Thomazo, Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph. A Generic Querying Algorithm for Greedy Sets of Existential Rules. KR: Principles of Knowledge Representation and Reasoning, Jun 2012, Rome, Italy. 13th International Conference on Principles of Knowledge Representation and Reasoning pp.096-106, 2012, 〈http://www.dis.uniroma1.it/~kr12/〉. 〈lirmm-00763518〉

Partager

Métriques

Consultations de la notice

433

Téléchargements de fichiers

320