Constraint patterns for tractable ontology-mediated queries with datatypes

Hernich, A, Lemos, J and Wolter, F ORCID: 0000-0002-4470-606X (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 Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	31 May 2016 08:19
Last Modified:	09 Jun 2025 14:35
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001405