Hernich, A, Lemos, J and Wolter, F
(2016)
Constraint patterns for tractable ontology-mediated queries with datatypes.
.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
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 |
Share
Share
