Affiliations: Department of Computer Science, University of Oxford, UK. E-mail: markus.kroetzsch@cs.ox.ac.uk | Institute of Artificial Intelligence, Technische Universität Dresden, Germany. E-mail: sebastian.rudolph@tu-dresden.de | Institute for Theoretical Computer Science, Karlsruhe Institute of Technology, Germany. E-mail: pschmitt@ira.uka.de
Note: [] Corresponding author.
Note: [] An earlier version of this paper, entitled “On the Semantic Relationship between Datalog and Description Logics,” has been published in the proceedings of the 4th International Conference on Web Reasoning and Rule Systems (RR 2010), Springer 2010.
Abstract: Translations to (first-order) Datalog have been used in a number of inferencing techniques for description logics (DLs), yet the relationship between the semantic expressivities of function-free Horn logic and DL is understood only poorly. Although Description Logic Programs (DLP) have been described as DLs in the “expressive intersection” of DL and Datalog, it is unclear what an intersection of two syntactically incomparable logics is, even if both have a first-order logic semantics. In this work, we offer a characterisation for DL fragments that can be expressed, in a concrete sense, in Datalog. We then determine the largest such fragment for the DL 𝒜ℒ𝒞, and provide an outlook on the extension of our methods to more expressive DLs.
