U. Hustadt and B. Motik (2005): ``Description Logics and Disjunctive Datalog - The Story so Far.'' In Ian Horrocks, Ulrike Sattler, and Frank Wolter, editors, Proceedings of the 2005 International Workshop on Description Logics (DL2005) (Edinburgh, Scotland, UK, July 26-28, 2005).
Abstract, BibTeX, PDF.

In this paper we present an overview of our recent work on the relationship between description logics and disjunctive datalog. In particular, we reduce satisfiability and instance checking in SHIQ to corresponding problems in disjunctive datalog. This allows us to apply practically successful deductive database optimization techniques, such as magic sets. Interestingly, the reduction also allows us to obtain novel theoretical results on description logics. In particular, we show that the data complexity of reasoning in SHIQ is in NP, and we define a fragment called Horn-SHIQ for which the data complexity is in P. Finally, the reduction provides a basis for query answering in an extension of SHIQ with so-called DL-safe rules. [an error occurred while processing this directive]