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
2 Birkbeck College [University of London]
3 Free University of Bozen-Bolzano
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download
https://hal.inria.fr/hal-01632925
Contributor : Meghyn Bienvenu <>
Submitted on : Friday, November 10, 2017 - 5:27:57 PM
Last modification on : Wednesday, March 13, 2019 - 5:22:02 PM
Long-term archiving on : Sunday, February 11, 2018 - 2:46:26 PM

File

BieKikKonRyzZak-DL17-Param.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01632925, version 1

Collections

GRAPHIK | LIRMM | INRIA | MIPS | UNIV-MONTPELLIER

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. DL: Description Logics, Jul 2017, Montpellier, France. ⟨hal-01632925⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

693

Files downloads

49

Contact


archive-ouverte@inria.fr