View Related Documents

Abstract

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.

Fulltext Preview

Image of the first page of the fulltext document