Worst-case Optimal Reasoning for the Horn-DL Fragments of OWL 1 and 2

Magdalena OrtizMagdalena Ortiz, Sebastian RudolphSebastian Rudolph, Mantas SimkusMantas Simkus

Download

Magdalena Ortiz, Sebastian Rudolph, Mantas Simkus
Worst-case Optimal Reasoning for the Horn-DL Fragments of OWL 1 and 2
In Fangzhen Lin, Ulrike Sattler, Miroslaw Truszczynski, eds., Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference (KR-10), 269-279, May 2010. AAAI Press

Details
Bibtex

KurzfassungAbstract
Horn fragments of Description Logics (DLs) are popular due to their beneficial trade-off between expressive power and computational complexity. Despite their potential, and partly due to the intricate interaction of nominals (O), inverses (I) and counting (Q), such fragments had not been studied so far for the DLs SHOIQ and SROIQ that underly OWL 1 and 2.
In this paper, we present a polynomial and modular translation from Horn-SHOIQ knowledge bases into Datalog, which shows that standard reasoning tasks are feasible in deterministic single exponential time. This improves over the previously known upper bounds, and contrasts the known NExpTime completeness of full SHOIQ. Thereby Horn-SHOIQ stands out as the first ExpTime-complete DL that allows simultaneously for O, I, and Q. In addition, we show that standard reasoning in Horn-SROIQ is 2ExpTime-complete.
Despite their high expressiveness, both Horn-SHOIQ and Horn-SROIQ have polynomial data complexity. This makes them particularly attractive for reasoning in semantically enriched systems with large data sets. A promising first step in this direction could be achieved exploiting existing Datalog engines, along the lines of our translation.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{ORS2010,
  author    = {Magdalena Ortiz and Sebastian Rudolph and Mantas Simkus},
  title     = {Worst-case Optimal Reasoning for the Horn-DL Fragments of {OWL} 1
               and 2},
  editor    = {Fangzhen Lin and Ulrike Sattler and Miroslaw Truszczynski},
  booktitle = {Principles of Knowledge Representation and Reasoning: Proceedings
               of the Twelfth International Conference (KR-10)},
  publisher = {AAAI Press},
  year      = {2010},
  month     = {May},
  pages     = {269-279}
}