Lutz, Carsten and Wolter, Frank
(2017)
THE DATA COMPLEXITY OF DESCRIPTION LOGIC ONTOLOGIES.
LOGICAL METHODS IN COMPUTER SCIENCE, 13 (4).
2017-.
Text
lmcs.pdf - Author Accepted Manuscript Download (457kB) |
Abstract
We analyze the data complexity of ontology-mediated querying where the ontologies are formulated in a description logic (DL) of the ALC family and queries are conjunctive queries, positive existential queries, or acyclic conjunctive queries. Our approach is non-uniform in the sense that we aim to understand the complexity of each single ontology instead of for all ontologies formulated in a certain language. While doing so, we quantify over the queries and are interested, for example, in the question whether all queries can be evaluated in polynomial time w.r.t. a given ontology. Our results include a PTime/coNP-dichotomy for ontologies of depth one in the description logic ALCFI, the same dichotomy for ALC- and ALCI-ontologies of unrestricted depth, and the non-existence of such a dichotomy for ALCF-ontologies. For the latter DL, we additionally show that it is undecidable whether a given ontology admits PTime query evaluation. We also consider the connection between PTime query evaluation and rewritability into (monadic) Datalog.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Description Logic, Ontology-Mediated Querying, Data Complexity |
Depositing User: | Symplectic Admin |
Date Deposited: | 29 Nov 2017 08:18 |
Last Modified: | 19 Jan 2023 06:49 |
DOI: | 10.23638/LMCS-13(4:7)2017 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3013081 |