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

Magdalena OrtizMagdalena Ortiz, Sebastian RudolphSebastian Rudolph, Mantas SimkusMantas Simkus

Download

Magdalena Ortiz, Sebastian Rudolph, Mantas Simkus
Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ
In Toby Walsh, eds., Proceedings of the 22nd International Joint Conference on Artificial Intelligence, 1039-1044, July 2011. IJCAI/AAAI

Details
Bibtex

KurzfassungAbstract
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 nontrivial 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.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{ORS2011,
  author    = {Magdalena Ortiz and Sebastian Rudolph and Mantas Simkus},
  title     = {Query Answering in the Horn Fragments of the Description Logics
               {SHOIQ} and {SROIQ}},
  editor    = {Toby Walsh},
  booktitle = {Proceedings of the 22nd International Joint Conference on
               Artificial Intelligence},
  publisher = {IJCAI/AAAI},
  year      = {2011},
  month     = {July},
  pages     = {1039-1044}
}