Query Answering in the Description Logic Horn-SHIQ

We provide an EXPTIME algorithm for answering conjunctive queries (CQs) in Horn-SHIQ, a Horn fragment of the well-known Description Logic SHIQ underlying the OWL-Lite standard. The algorithm employs a domino system for model representation, which is constructed via a worst-case optimal tableau algorithm for Horn-SHIQ, the queries are answered by reasoning over the domino system. Our algorithm not only shows that CQ answering in Horn-SHIQ is not harder than satisfiability testing, but also that it is polynomial in data complexity, making Horn-SHIQ an attractive expressive Description Logic.