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

TitleDescription Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
Publication TypeConference Paper
Year of Publication2008
AuthorsSebastian Rudolph, Markus Krotzsch, Pascal Hitzler
Conference NameThe Semantic Web - ISWC 2008, 7th International Semantic Web Conference, 2008
Pagination435-450
PublisherThe Semantic Web - ISWC 2008, 7th International Semantic Web Conference
Conference LocationKarlsruhe, Germany
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.

Full Text

Sebastian Rudolph, Markus Krotzsch, Pascal Hitzler, 'Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog' The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, 2008,pp. 435-450.

hasEditor: Pascal Hitzler
hasBookTitle: Lecture Notes in Computer Science Vol. 5318

Related Files: