Hernich, A, Lemos, J and Wolter, F
(2016)
Constraint patterns for tractable ontology-mediated queries with datatypes.
.
Text
dljulio.pdf - Author Accepted Manuscript Download (414kB) |
Abstract
Adding datatypes to ontology-mediated conjunctive queries (OMQs) often makes query answering hard. This applies, in particular, to datatypes with non-unary predicates. In this paper we propose a new, non-uniform way, of analysing the data-complexity of OMQ answering with datatypes containing higher-arity predicates. We aim at a classification of the patterns of datatype atoms in OMQs into those that can occur in non-tractable OMQs and those that only occur in tractable OMQs. Our main result is a P/coNP-dichotomy for OMQs over DL-Lite TBoxes and rooted CQs using the datatype (ℚ, ≤). The proof employs a recent dichotomy result by Bodirsky and Kara for temporal constraint satisfaction problems.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Depositing User: | Symplectic Admin |
Date Deposited: | 31 May 2016 08:19 |
Last Modified: | 19 Jan 2023 07:36 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3001405 |