Name
Abstract | ||
|---|---|---|
© 2016, CEUR-WS. All rights reserved. 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. |
Year | Venue | Field |
|---|---|---|
2016 | Description Logics | Data mining,Ontology,Conjunctive query,Computer science,Theoretical computer science,Constraint satisfaction problem,Predicate (grammar) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| André Hernich | 1 | 87 | 8.30 |
| Julio Lemos | 2 | 0 | 1.01 |
| Frank Wolter | 3 | 4454 | 266.99 |