Pushing the Boundaries of Tractable Ontology Reasoning

On the theoretical side, we introduce a class of Horn ontologies, namely RSA ontologies, for which standard reasoning tasks are tractable. This class is general enough to include the OWL 2 EL, QL, and RL profiles. Furthermore, we extend existing combined approaches to solve CQ answering over RSA ontologies, which we show to be feasible in NP. On the practical side, we show that many real-world ontologies that are not included in any OWL 2 profile are indeed RSA, and thus that polynomial time reasoning is possible for these. We also implement a rather efficient reasoner for RSA ontologies making use of existing Datalog engines. See the following for more information: http://www.cs.ox.ac.uk/ian.horrocks/Publications/download/2014/CarralFGHH14.pdf