Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2
Magdalena Ortiz, Sebastian Rudolph, Mantas Šimkus · 2010
Horn fragments of Description Logics (DLs) have gained popularity because they provide a beneficial trade-off be-tween expressive power and computational complexity and, more specifically, are usually tractable w.r.t. data complexity. Despite their potential, and partly due to the intricate inter-action of nominals (O), inverses (I) and counting (Q), such fragments had not been studied so far for the DLs SHOIQ and SROIQ that underly OWL1 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 com-pleteness of full SHOIQ. Thereby, Horn-SHOIQ stands out as the first EXPTIME complete DL that allows simultane-ously forO, I, andQ. In addition, we show that standard rea-soning in Horn-SROIQ is 2-EXPTIME complete. Despite their high expressiveness, both Horn-SHOIQ and Horn-SROIQ have polynomial data complexity. This makes them particularly attractive for reasoning in semantically en-riched 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.