A Generic Querying Algorithm for Greedy Sets of Existential Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2012

A Generic Querying Algorithm for Greedy Sets of Existential Rules


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.
Fichier principal
Vignette du fichier
kr12-tbmr.pdf (508.73 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00763518 , version 1 (11-12-2012)


  • HAL Id : lirmm-00763518 , version 1


Michaël Thomazo, Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph. A Generic Querying Algorithm for Greedy Sets of Existential Rules. KR: Representation and Reasoning, Jun 2012, Rome, Italy. pp.096-106. ⟨lirmm-00763518⟩
216 View
196 Download


Gmail Mastodon Facebook X LinkedIn More