On the Parameterised Complexity of Tree-Shaped Ontology-Mediated Queries in OWL 2 QL

Meghyn Bienvenu 1 Stanislav Kikot 2 Roman Kontchakov 2 Vladislav Ryzhikov 3 Michael Zakharyaschev 2
1 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 : We discuss the parameterised complexity of answering tree-shaped ontology-mediated queries (OMQs) in OWL 2 QL under various restrictions on their ontologies and conjunctive queries (CQs). In particular, we construct an ontology T such that answering OMQs (T , q) with tree-shaped CQs q is W[1]-hard if the number of leaves in q is regarded as the parameter. The number of leaves has previously been identified as an important characteristic of CQs as bounding it leads to tractable OMQ answering. Our result shows that treating it as a parameter does not make the problem fixed-parameter tractable, even for a fixed ontology.
Type de document :
Communication dans un congrès
30th International Workshop on Description Logics, Jul 2017, Montpellier, France
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01632925
Contributeur : Meghyn Bienvenu <>
Soumis le : vendredi 10 novembre 2017 - 17:27:57
Dernière modification le : jeudi 11 janvier 2018 - 17:01:56

Fichier

BieKikKonRyzZak-DL17-Param.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01632925, version 1

Citation

Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladislav Ryzhikov, Michael Zakharyaschev. On the Parameterised Complexity of Tree-Shaped Ontology-Mediated Queries in OWL 2 QL. 30th International Workshop on Description Logics, Jul 2017, Montpellier, France. 〈hal-01632925〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

15