Acyclic Query Answering Under Guarded Disjunctive Existential Rules and Consequences to DLs

Pierre Bourhis 1, 2 Michael Morak 3 Andréas Pieris 3
1 LINKS - Linking Dynamic Data
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : The complete picture of the complexity of conjunctive query answer-ing under guarded disjunctive existential rules has been recently settled. However, in the case of (unions of) acyclic conjunctive queries ((U)ACQs) there are some fundamental questions which are still open. It is the precise aim of the present paper to close those questions, and to understand whether the acyclicity of the query has a positive impact on the complexity of query answering. Our main re-sult states that acyclic conjunctive query answering under a fixed set of guarded disjunctive existential rules is EXPTIME-hard. This result together with an EXP-TIME upper bound obtained by exploiting classical results on guarded first-order logic, gives us a complete picture of the complexity of our problem. We also show that our results can be used as a generic tool for establishing results on (U)ACQ answering under several central DLs. In fact, restricting the query lan-guage to UACQs improves the complexity to EXPTIME-complete for any DL between DL-Lite bool and ALCHI; this holds even for fixed TBoxes.
Type de document :
Communication dans un congrès
Informal Proceedings of the 27th International Workshop on Description Logics, Jul 2014, Vienne, Austria. 2014
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01098983
Contributeur : Inria Links <>
Soumis le : mardi 30 décembre 2014 - 12:21:39
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27
Document(s) archivé(s) le : mardi 31 mars 2015 - 10:20:13

Fichier

paper_22.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01098983, version 1

Citation

Pierre Bourhis, Michael Morak, Andréas Pieris. Acyclic Query Answering Under Guarded Disjunctive Existential Rules and Consequences to DLs. Informal Proceedings of the 27th International Workshop on Description Logics, Jul 2014, Vienne, Austria. 2014. 〈hal-01098983〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

134