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 :
Reports
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01097137
Contributor : Jean-François Baget <>
Submitted on : Thursday, December 18, 2014 - 11:35:15 PM
Last modification on : Wednesday, December 12, 2018 - 2:38:02 PM

Links full text

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

571