%0 Journal Article %1 Eiter %A Eiter, T. %A Lutz, C. %A Ortiz, M. %A Simkus., M. %D 2009 %E Boutilier, C. %J Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press/IJCAI, 2009. %K description logics ontologies ontorule query roles %P 759-764 %T Query answering in description logics with transitive roles %U http://ijcai.org/papers09/Papers/IJCAI09-131.pdf %X 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 2-EXPTIME-hardness, and transitive roles alone which result in CO-NEXPTIME-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2-EXPTIME-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.

@article{Eiter, 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 2-EXPTIME-hardness, and transitive roles alone which result in CO-NEXPTIME-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2-EXPTIME-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. }, added-at = {2010-03-29T16:36:31.000+0200}, author = {Eiter, T. and Lutz, C. and Ortiz, M. and Simkus., M.}, biburl = {https://www.bibsonomy.org/bibtex/2a45cb2dad294a430afd315b47276837c/ontorule}, editor = {Boutilier, C.}, interhash = {600cd75bdcacad18fc4eb95d38aadf00}, intrahash = {a45cb2dad294a430afd315b47276837c}, journal = {Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press/IJCAI, 2009.}, keywords = {description logics ontologies ontorule query roles}, month = {July}, pages = {759-764}, timestamp = {2010-03-29T16:36:32.000+0200}, title = {Query answering in description logics with transitive roles}, url = {http://ijcai.org/papers09/Papers/IJCAI09-131.pdf}, year = 2009 }