Description Logic Reasoning with Decision Diagrams
Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler
Description Logic Reasoning with Decision Diagrams – Compiling SHIQ to Disjunctive Datalog
Abstract. We propose a novel method for reasoning in the description logic SHIQ. After a satisfiability preserving transformation from SHIQ to the description logic ALCIb, the obtained ALCIb Tbox T is converted into an ordered binary decision diagram (OBDD) which represents a canonical model for T. This OBDD is turned into a disjunctive datalog program that can be used for Abox reasoning. The algorithm is worst-case optimal w.r.t. data complexity, and admits easy extensions with DL-safe rules and ground conjunctive queries.
Published at ISWC2008 (Conference paper)
Download PDF (last update: July 10 2008)
Citation details
- Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Description Logic Reasoning with Decision Diagrams – Compiling SHIQ to Disjunctive Datalog. 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. 435–450. SpringerProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2008.
author = {Sebastian Rudolph and Markus Kr\"{o}tzsch
and Pascal Hitzler},
title = {Description Logic Reasoning with Decision
Diagrams: Compiling $\mathcal{SHIQ}$ to
Disjunctive Datalog},
pages = {435--450},
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
This work extends our earlier work on using binary decision diagrams for terminological DL reasoning with a datalog translation that allows for Aboxes to be incorporated.
A much simpler datalog-based reasoning procedure that requires only a syntactic translation has been given for the expressive light-weight description logic ELP.
