  Description Logics are knowledge representation formalisms that provide, for
example, the logical underpinning of the W3C OWL standards. Conjunctive
queries, the standard query language in databases, have recently gained
significant attention as an expressive formalism for querying Description Logic
knowledge bases. Several different techniques for deciding conjunctive query
entailment are available for a wide range of DLs. Nevertheless, the combination
of nominals, inverse roles, and number restrictions in OWL 1 and OWL 2 DL
causes unsolvable problems for the techniques hitherto available. We tackle
this problem and present a decidability result for entailment of unions of
conjunctive queries in the DL ALCHOIQb that contains all three problematic
constructors simultaneously. Provided that queries contain only simple roles,
our result also shows decidability of entailment of (unions of) conjunctive
queries in the logic that underpins OWL 1 DL and we believe that the presented
results will pave the way for further progress towards conjunctive query
entailment decision procedures for the Description Logics underlying the OWL
standards.
