2008 | OriginalPaper | Chapter
Query Answering in the Description Logic Horn-
Authors : Thomas Eiter, Georg Gottlob, Magdalena Ortiz, Mantas Šimkus
Published in: Logics in Artificial Intelligence
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We provide an
ExpTime
algorithm for answering conjunctive queries (CQs) in
Horn
-
$\mathcal{SHIQ}$
, a Horn fragment of the well-known Description Logic
$\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
-
$\mathcal{SHIQ}$
; the queries are answered by reasoning over the domino system. Our algorithm not only shows that CQ answering in
Horn
-
$\mathcal{SHIQ}$
is not harder than satisfiability testing, but also that it is polynomial in data complexity, making
Horn
-
$\mathcal{SHIQ}$
an attractive expressive Description Logic.