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

author: Sebastian Rudolph, Dresden University of Technology
published: Nov. 24, 2008,   recorded: October 2008,   views: 4337
Categories

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Description

We propose a novel method for reasoning in the description logic $\mathcal{SHIQ}$ . After a satisfiability preserving transformation from $\mathcal{SHIQ}$ to the description logic $\mathcal{ALCI}b$ , the obtained $\mathcal{ALCI}b$ Tbox $\mathcal{T}$ is converted into an ordered binary decision diagram (OBDD) which represents a canonical model for $\mathcal{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. Supported by the European Commission under contracts 027595 NeOn and 215040 ACTIVE, and by the Deutsche Forschungsgemeinschaft (DFG) under the ReaSem project.