Worst-case Optimal Query Answering for Greedy Sets of Existential Rules and Their Subclasses - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports (Research Report) Year : 2014

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

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.
Fichier principal
Vignette du fichier
1412.4485.pdf (1.38 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01097137 , version 1 (04-02-2020)

Identifiers

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

Cite

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⟩
272 View
22 Download

Altmetric

Share

Gmail Facebook X LinkedIn More