The Not-So-Easy Task of Computing Class Subsumptions in OWL RL
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
- Markus Krötzsch. The Not-So-Easy Task of Computing Class Subsumptions in OWL RL. In Philippe Cudré-Mauroux, Jeff Heflin, Evren Sirin, Tania Tudorache, Jérôme Euzenat, Manfred Hauswirth, Josiane Xavier Parreira, Jim Hendler, Guus Schreiber, Abraham Bernstein, Eva Blomqvist, eds.: Proceedings of the 11th International Semantic Web Conference. SpringerProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2012.
author = {Markus Kr{\"o}tzsch},
title = {The Not-So-Easy Task of Computing Class
Subsumptions in {OWL RL}},
booktitle = {Proceedings of the 11th International Semantic
Web Conference (ISWC'12)},
editor = {Philippe Cudr{\'e}-Mauroux and
Jeff Heflin and Evren Sirin and
Tania Tudorache and J{\'e}r{\^o}me Euzenat and
Manfred Hauswirth and Josiane Xavier Parreira and
Jim Hendler and Guus Schreiber and
Abraham Bernstein and Eva Blomqvist},
publisher = {Springer},
series = {LNCS},
volume = {7649},
year = {2012},
pages = {279--294},
}
Remarks
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.
