Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog

Sebastian RudolphSebastian Rudolph, Markus KrötzschMarkus Krötzsch, Pascal HitzlerPascal Hitzler

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 International Semantic Web Conference (ISWC 2008), volume 5318 of LNCS, 435-450, 2008. Springer

Details
Bibtex

KurzfassungAbstract
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.
Bemerkung: Note: Please refer to the more comprehensive journal paper Type-elimination-based Reasoning for the Description Logic SHIQbs using Decision Diagrams and Disjunctive Datalog instead.
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-88564-1_28.

/* Please refer to the 2012 journal paper instead */
@inproceedings{RKH2008,
  author    = {Sebastian Rudolph and Markus Kr{\"{o}}tzsch and Pascal Hitzler},
  title     = {Description Logic Reasoning with Decision Diagrams: Compiling
               {SHIQ} to Disjunctive Datalog},
  editor    = {Amit Sheth and Steffen Staab and Mike Dean and Massimo Paolucci
               and Diana Maynard and Timothy Finin and Krishnaprasad
               Thirunarayan},
  booktitle = {Proceedings of the International Semantic Web Conference (ISWC
               2008)},
  series    = {LNCS},
  volume    = {5318},
  publisher = {Springer},
  year      = {2008},
  pages     = {435-450},
  doi       = {10.1007/978-3-540-88564-1_28}
}