Skip to Main content Skip to Navigation

Worst-case Optimal Query Answering for Greedy Sets of Existential Rules and Their Subclasses

Sebastian Rudolph 1 Michael Thomazo 2, 1 Jean-François Baget 3 Marie-Laure Mugnier 3
1 International Center For Computational Logic [TU Dresden]
Institute of Artificial Intelligence [Dresden]
3 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 : The need for an ontological layer on top of data, associated with advanced reasoning mechanisms able to exploit the semantics encoded in ontologies, has been acknowledged both in the database and knowledge representation communities. We focus in this paper on the ontological query answering problem, which consists of querying data while taking ontological knowledge into account. More specifically, we establish complexities of the conjunctive query entailment problem for classes of existential rules (also called tuple-generating dependencies, Datalog+/- rules, or forall-exists-rules. Our contribution is twofold. First, we introduce the class of greedy bounded-treewidth sets (gbts) of rules, which covers guarded rules, and their most well-known generalizations. We provide a generic algorithm for query entailment under gbts, which is worst-case optimal for combined complexity with or without bounded predicate arity, as well as for data complexity and query complexity. Secondly, we classify several gbts classes, whose complexity was unknown, with respect to combined complexity (with both unbounded and bounded predicate arity) and data complexity to obtain a comprehensive picture of the complexity of existential rule fragments that are based on diverse guardedness notions. Upper bounds are provided by showing that the proposed algorithm is optimal for all of them.
Document type :
Complete list of metadata

Cited literature [76 references]  Display  Hide  Download
Contributor : Jean-François Baget <>
Submitted on : Tuesday, February 4, 2020 - 4:33:41 PM
Last modification on : Monday, February 15, 2021 - 10:39:04 AM
Long-term archiving on: : Tuesday, May 5, 2020 - 6:33:36 PM


Files produced by the author(s)


  • HAL Id : lirmm-01097137, version 1
  • ARXIV : 1412.4485


Sebastian Rudolph, Michael Thomazo, Jean-François Baget, Marie-Laure Mugnier. Worst-case Optimal Query Answering for Greedy Sets of Existential Rules and Their Subclasses. [Research Report] LIRMM. 2014. ⟨lirmm-01097137⟩



Record views


Files downloads