The Not-So-Easy Task of Computing Class Subsumptions in OWL RL


Jump to: navigation, search

Markus Krötzsch

The Not-So-Easy Task of Computing Class Subsumptions in OWL RL

Abstract. The lightweight ontology language OWL RL is used for reasoning with large amounts of data. To this end, the W3C standard provides a simple system of deduction rules, which operate directly on the RDF syntax of OWL. Several similar systems have been studied. However, these approaches are usually complete for instance retrieval only. This paper asks if and how such methods could also be used for computing entailed subclass relationships. Checking entailment for arbitrary OWL RL class subsumptions is co-NP-hard, but tractable rule-based reasoning is possible when restricting to subsumptions between atomic classes. Surprisingly, however, this cannot be achieved in any RDF-based rule system, i.e., the W3C calculus cannot be extended to compute all atomic class subsumptions. We identify syntactic restrictions to mitigate this problem, and propose a rule system that is sound and complete for many OWL RL ontologies.

Published at ISWC2012, nominated for Best Paper award (Conference paper)

Download PDF (last update: Nov 13 2012)

Citation details


This paper got nominated for the Best Paper award in the research track of ISWC 2012. Congratulations to Rahul Parundekar, Craig Knoblock and José Luis Ambite whose paper Discovering Concept Coverings in Ontologies of Linked Data Sources received the award.

The linked PDF is the extended technical report. There is also an abridged conference version without the proofs.

See also the slide set for the talk given at ISWC 2012.


Semantic Web, Description logics

Personal tools