ELP: Tractable Rules for OWL 2
Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler
ELP: Tractable Rules for OWL 2
Abstract. We introduce ELP as a decidable fragment of the Semantic Web Rule Language (SWRL) that admits reasoning in polynomial time. ELP is based on the tractable description logic EL++, and encompasses an extended notion of the recently proposed DL rules for that logic. Thus ELP extends EL++ with a number of features introduced by the forthcoming OWL 2, such as disjoint roles, local reflexivity, certain range restrictions, and the universal role. We present a reasoning algorithm based on a translation of ELP to Datalog, and this translation also enables the seamless integration of DL-safe rules into ELP. While reasoning with DL-safe rules as such is already highly intractable, we show that DL-safe rules based on the Description Logic Programming (DLP) fragment of OWL 2 can be admitted in ELP without losing tractability.
Published at ISWC2008 (Conference paper)
Download PDF (last update: Oct 31 2008)
Citation details
- Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. ELP: Tractable Rules for OWL 2. In Amit Sheth, Steffen Staab, Mike Dean, Massimo Paolucci, Diana Maynard, Timothy Finin, Krishnaprasad Thirunarayan, eds.: Proceedings of the 7th International Semantic Web Conference (ISWC-08), pp. 649–664. SpringerProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2008.
author = {Markus Kr\"{o}tzsch and Sebastian Rudolph
and Pascal Hitzler},
title = {{ELP:} {Tractable} Rules for {OWL~2}},
pages = {649--664},
crossref = {iswc08}
}
@proceedings{iswc08,
editor = {Amit Sheth and Steffen Staab and Mike Dean
and Massimo Paolucci and Diana Maynard
and Timothy Finin and Krishnaprasad Thirunarayan},
title = {Proceedings of the 7th International Semantic Web
Conference (ISWC'08)},
booktitle = {Proceedings of the 7th International Semantic Web
Conference (ISWC'08)},
publisher = {Springer},
series = {LNCS},
volume = {5318},
year = {2008}
}
Remarks
A comprehensive treatment of description logic rules, including various updates on ELP, can be found in my dissertation.
The above PDF is the extended technical report. You can also download the camera ready ISWC paper which is a shortened version of the report.
You can also download the slides for the talk at ISWC.
