Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Thomazo Michaël Connect in order to contact the contributor
Submitted on : Thursday, March 1, 2012 - 2:23:13 PM
Last modification on : Friday, August 5, 2022 - 3:03:00 PM
Long-term archiving on: : Wednesday, December 14, 2016 - 9:47:47 AM


Files produced by the author(s)


  • HAL Id : lirmm-00675560, version 1
  • PRODINRA : 245482



Michaël Thomazo, Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph. A Generic Querying Algorithm for Greedy Sets of Existential Rules. RR-12006, 2012. ⟨lirmm-00675560⟩



Record views


Files downloads