caa a22 4500 463182898 CHVBK 20180406164844.0 cr unu---uuuuu 170326e20071001xx s 000 0 eng 10.1007/s10817-007-9080-3 doi (NATIONALLICENCE)springer-10.1007/s10817-007-9080-3 Reasoning in Description Logics by a Reduction to Disjunctive Datalog [Elektronische Daten] [Ullrich Hustadt, Boris Motik, Ulrike Sattler] As applications of description logics proliferate, efficient reasoning with knowledge bases containing many assertions becomes ever more important. For such cases, we developed a novel reasoning algorithm that reduces a $\mathcal{SHIQ}$ knowledge base to a disjunctive datalog program while preserving the set of ground consequences. Queries can then be answered in the resulting program while reusing existing and practically proven optimization techniques of deductive databases, such as join-order optimizations or magic sets. Moreover, we use our algorithm to derive precise data complexity bounds: we show that $\mathcal{SHIQ}$ is data complete for NP, and we identify an expressive fragment of $\mathcal{SHIQ}$ with polynomial data complexity. Springer Science+Business Media B.V., 2007 Description logics nationallicence Disjunctive datalog nationallicence Data complexity nationallicence Hustadt Ullrich Department of Computer Science, University of Liverpool, Liverpool, UK aut Motik Boris Department of Computer Science, University of Manchester, Manchester, UK aut Sattler Ulrike Department of Computer Science, University of Manchester, Manchester, UK aut Journal of Automated Reasoning Springer Netherlands 39/3(2007-10-01), 351-384 0168-7433 39:3<351 2007 39 10817 https://doi.org/10.1007/s10817-007-9080-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10817-007-9080-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hustadt Ullrich Department of Computer Science, University of Liverpool, Liverpool, UK aut NATIONALLICENCE 700 1- Motik Boris Department of Computer Science, University of Manchester, Manchester, UK aut NATIONALLICENCE 700 1- Sattler Ulrike Department of Computer Science, University of Manchester, Manchester, UK aut NATIONALLICENCE 773 0- Journal of Automated Reasoning Springer Netherlands 39/3(2007-10-01), 351-384 0168-7433 39:3<351 2007 39 10817 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer