Constraint patterns for tractable ontology-mediated queries with datatypes



Hernich, A, Lemos, J and Wolter, F
(2016) Constraint patterns for tractable ontology-mediated queries with datatypes. .

[img] Text
dljulio.pdf - Accepted Version

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: 04 Apr 2021 06:10
URI: https://livrepository.liverpool.ac.uk/id/eprint/3001405