We provide an
ExpTime algorithm for answering conjunctive queries (CQs) in
Horn-
SHIQ\mathcal{SHIQ}
, a Horn fragment of the well-known Description Logic
SHIQ\mathcal{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\mathcal{SHIQ}
; the queries are answered by reasoning over the domino system. Our algorithm not only shows that CQ answering in
Horn-
SHIQ\mathcal{SHIQ}
is not harder than satisfiability testing, but also that it is polynomial in data complexity, making
Horn-
SHIQ\mathcal{SHIQ}
an attractive expressive Description Logic.
This work was partially supported by the Austrian Science Fund (FWF) grant P20840, Wolfgang Pauli Institute (WPI), and the
Mexican National Council for Science and Technology (CONACYT) grant 187697.