On the Parameterised Complexity of Tree-Shaped Ontology-Mediated Queries in OWL 2 QL - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

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

Résumé

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.
Fichier principal
Vignette du fichier
BieKikKonRyzZak-DL17-Param.pdf (382.01 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01632925 , version 1 (10-11-2017)

Identifiants

  • HAL Id : hal-01632925 , version 1

Citer

Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladislav Ryzhikov, Michael Zakharyaschev. On the Parameterised Complexity of Tree-Shaped Ontology-Mediated Queries in OWL 2 QL. DL: Description Logics, Jul 2017, Montpellier, France. ⟨hal-01632925⟩
695 Consultations
54 Téléchargements

Partager

Gmail Facebook X LinkedIn More