Ontology-Mediated Queries with Closed Predicates
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 3120-3125.
Abstract
In the context of ontology-based data access with description logics (DLs), we study ontology-mediated queries in which selected predicates can be closed (OMQCs). In particular, we contribute to the classification of the data complexity of such queries in several relevant DLs. For the case where only concept names can be closed, we tightly link this question to the complexity of surjective CSPs. When also role names can be closed, we show that a full complexity classification is equivalent to classifying the complexity of all problems in coNP, thus currently out of reach. We also identify a class of OMQCs based on ontologies formulated in DL-LiteR that are guaranteed to be tractable and even FO-rewritable.
@inproceedings{ijcai2015p440,
title = {Ontology-Mediated Queries with Closed Predicates},
author = {Lutz, Carsten and Seylan, Inanç and Wolter, Frank},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {3120--3125},
year = {2015},
month = {7},
note = {Special Track on Knowledge Representation and Reasoning},
url = {https://ijcai.org/proceedings/2015/440},
}
TY - CPAPER TI - Ontology-Mediated Queries with Closed Predicates AU - Lutz, Carsten AU - Seylan, Inanç AU - Wolter, Frank T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 3120 EP - 3125 UR - https://ijcai.org/proceedings/2015/440 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
