Conjunctive query answering in the description logic SH using knots

AbstractAnswering conjunctive queries (CQs) has been recognized as an important task for the widening use of Description Logics (DLs) in a number of applications. The problem has been studied by many authors, who developed a number of different techniques for its solution. We present a novel approach to CQ answering that is based on knots, which are schematic trees of depth at most one that can be used to represent the terminological information represented in a TBox. They allow us to obtain an algorithm for the DL SH that has some advantages with respect to previous approaches, proceeding as follows. We build a compilation of an input knowledge base using knots, and then use this compilation to answer CQs in two stages. In the first stage we employ knots to rewrite the input query into a set of queries (a union of CQs, short UCQ) that incorporate the terminological constraints. In the next stage we answer the query over the full knowledge base, by answering the constructed UCQ over a set of relational structures that are obtained by enriching the assertional part of the knowledge base. Since in the first stage we process the query and the taxonomy, and the assertional part of the knowledge base is only processed in the second stage, parts of the computation can be reused; in particular, answering a query over changing assertional data amounts to re-executing the last step. Notably, the algorithm handles CQs with distinguished (i.e., output) variables in a direct manner and scales down nicely: while double exponential in general, it runs in single exponential time under various restrictions on transitive roles in queries, including the case of CQ answering in the DL ALCH. This is worst-case optimal, given that CQ answering is 2ExpTime-complete for SH and ExpTime-complete already for the core expressive DL ALC. Furthermore, the last step is amenable to a realization in disjunctive Datalog, which yields a worst-case optimal implementation under data complexity