Query Answering in DL-Lite with Datatypes: A Non-Uniform Approach

Hernich, Andre, Lemos, Julio and Wolter, Frank ORCID: 0000-0002-4470-606X (2017) Query Answering in DL-Lite with Datatypes: A Non-Uniform Approach. In: AAAI, 2017-2-4 - 2017-2-9, San Francisco.

Text AAAI17-full.pdf - Author Accepted Manuscript Download (291kB)

Abstract

<jats:p> Adding datatypes to ontology-mediated queries (OMQs) often makes query answering hard. As a consequence, the use of datatypes in OWL 2 QL has been severely restricted. In this paper we propose a new, non-uniform, way of analyzing the data-complexity of OMQ answering with datatypes. Instead of restricting the ontology language 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. To this end we establish a close link between OMQ answering with datatypes and constraint satisfaction problems over the datatypes. In a case study we apply this link to prove a P/coNP-dichotomy for OMQs over DL-Lite extended with the datatype (Q,&lt;=). The proof employs a recent dichotomy result by Bodirsky and Kára for temporal constraint satisfaction problems. </jats:p>

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	datatypes, conjunctive queries, data complexity, dichotomy
Depositing User:	Symplectic Admin
Date Deposited:	19 Dec 2016 16:38
Last Modified:	15 Mar 2024 19:11
DOI:	10.1609/aaai.v31i1.10689
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3004936