Acyclic Query Answering under Guarded Disjunctive Existential Rules and Consequences to DLs

ABSTRACT. The complete picture of the complexity of conjunctive query answering under guarded disjunctive existential rules has been recently settled. However, in the case of acyclic (unions of) conjunctive queries there are some fundamental questions which are still open. It is the precise aim of the present paper to close those questions. Our main result states that acyclic conjunctive query answering under a fixed set of guarded disjunctive existential rules is EXPTIME-hard. This result together with an EXPTIME upper bound obtained by exploiting classical results on guarded first-order logic, gives us the complete picture of the complexity of our problem. As an immediate consequence, we get that answering acyclic unions of conjunctive queries under DL-Lite_{bool}^{H}, one of the most expressive languages of the DL-Lite family of DLs, is EXPTIME-complete, even in the case of a fixed TBox. In fact, the EXPTIME-hardnees holds even for DL-Lite_{bool}, that is, the DL obtained from DL-Lite_{bool}^{H} after forbidding role hierarchies.