| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
On the Parameterised Complexity of Tree-Shaped Ontology-Mediated Queries in OWL 2 QL
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.
Cited literature [16 references]
https://hal.inria.fr/hal-01632925
Contributor : Meghyn Bienvenu Connect in order to contact the contributor
Submitted on : Friday, November 10, 2017 - 5:27:57 PM
Last modification on : Wednesday, October 27, 2021 - 10:18:50 AM
Long-term archiving on: : Sunday, February 11, 2018 - 2:46:26 PM
Contributor : Meghyn Bienvenu Connect in order to contact the contributor
Submitted on : Friday, November 10, 2017 - 5:27:57 PM
Last modification on : Wednesday, October 27, 2021 - 10:18:50 AM
Long-term archiving on: : Sunday, February 11, 2018 - 2:46:26 PM
File
BieKikKonRyzZak-DL17-Param.pdf
Files produced by the author(s)