Inproceedings1805

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

Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler

Published: 2008 Oktober
Herausgeber: Amit Sheth and Steffen Staab and Mike Dean and Massimo Paolucci and Diana Maynard and Timothy Finin and Krishnaprasad Thirunarayan
Buchtitel: Proceedings of the International Semantic Web Cnference (ISWC 2008)
Ausgabe: 5318
Reihe: LNCS
Seiten: 435-450
Verlag: Springer

Referierte Veröffentlichung

BibTeX

Kurzfassung
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.

Weitere Informationen unter: Link, Link

Projekt

ReaSem, NeOn, Active

Forschungsgruppe

Wissensmanagement

Forschungsgebiet

Wissensrepräsentationssprachen, Beschreibungslogik, Deduktive Datenbanken, Logik, Semantic Web