Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ

Ortiz, Magdalena; Rudolph, Sebastian; Simkus, Mantas

doi:10.5591/978-1-57735-516-8/IJCAI11-178

Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ

Magdalena Ortiz, Sebastian Rudolph, Mantas Simkus

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1039-1043.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-178

Abstract

The high computational complexity of the expressive Description Logics (DLs) that underlie the OWL standard has motivated the study of their Horn fragments, which are usually tractable in data complexity and can also have lower combined complexity, particularly for query answering. In this paper we provide algorithms for answering conjunctive 2-way regular path queries (2CRPQs), a non-trivial generalization of plain conjunctive queries, in the Horn fragments of the DLs SHOIQ and SROIQ underlying OWL 1 and OWL 2. We show that the combined complexity of the problem is ExpTime-complete for Horn-SHOIQ and 2ExpTime-complete for the more expressive Horn-SROIQ, but is PTime-complete in data complexity for both. In contrast, even decidability of plain conjunctive queries is still open for full SHOIQ and SROIQ. These are the first completeness results for query answering in DLs with inverses, nominals, and counting, and show that for the considered logics the problem is not more expensive than standard reasoning.

Magdalena Ortiz, Sebastian Rudolph, and Mantas Simkus. 2011. Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1039–1043. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-178

@inproceedings{ijcai2011p178,
  title     = {Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ},
  author    = {Ortiz, Magdalena and Rudolph, Sebastian and Simkus, Mantas},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1039--1043},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-178},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-178},
}

TY  - CPAPER
TI  - Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ
AU  - Ortiz, Magdalena
AU  - Rudolph, Sebastian
AU  - Simkus, Mantas
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1039
EP  - 1043
DO  - 10.5591/978-1-57735-516-8/IJCAI11-178
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-178
ER  -