Query Answering in Description Logics with Transitive Roles
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 759-763.
Abstract
We study the computational complexity of conjunctive query answering w.r.t. ontologies formulated in fragments of the description logic SHIQ. Our main result is the identification of two new sources of complexity: the combination of transitive roles and role hierarchies which results in 2ExpTime-hardness, and transitive roles alone which result in coNExpTime-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2ExpTime-hard. We also show that conjunctive query answering with transitive roles, but without inverse roles and role hierarchies, remains in ExpTime if the ABox is tree-shaped.Thomas Eiter, Carsten Lutz, Magdalena Ortiz, Mantas Simkus
@inproceedings{ijcai2009p131,
title = {Query Answering in Description Logics with Transitive Roles},
author = {Eiter, Thomas and Lutz, Carsten and Ortiz, Magdalena and Simkus, Mantas},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {759--763},
year = {2009},
url = {https://ijcai.org/proceedings/2009/131},
}
TY - CPAPER TI - Query Answering in Description Logics with Transitive Roles AU - Eiter, Thomas AU - Lutz, Carsten AU - Ortiz, Magdalena AU - Simkus, Mantas T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 759 EP - 763 UR - https://ijcai.org/proceedings/2009/131 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
