Name
Abstract | ||
|---|---|---|
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, <=). The proof employs a recent dichotomy result by Bodirsky and Kara for temporal constraint satisfaction problems. |
Year | Venue | Field |
|---|---|---|
2017 | THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE | Data mining,Programming language,Computer science,Artificial intelligence,Machine learning |
DocType | Citations | PageRank |
Conference | 4 | 0.40 |
References | Authors | |
16 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| André Hernich | 1 | 87 | 8.30 |
| Julio Lemos | 2 | 4 | 0.40 |
| Frank Wolter | 3 | 4454 | 266.99 |