Containment of Regular Path Queries under Description Logic Constraints
Diego Calvanese, Magdalena Ortiz and Mantas Simkus
Query containment is a fundamental problem studied extensively in KR and DBs, for different kinds of query languages, possibly in the presence of complex domain constraints. In this paper, we address query containment under expressive description logic (DL) constraints for two-way regular path queries (2RPQs) and their conjunctions, which have been introduced in the context of graph databases and which generalize conjunctive queries with the ability to express navigation through regular expressions over binary relations. While query containment has been solved separately for the case of 2RPQs and extensions thereof in the absence of constraints, and for plain conjunctive queries in the presence of expressive forms of constraints, the case of containment of variants of regular queries under constraints has been a longstanding open problem. We show that, surprisingly, the presence of functionality constraints alone makes containment of 2RPQs already Exptime-hard. We also provide a matching upper bound that extends to the case of very expressive DL constraints. For the case of conjunctive 2RPQs, we prove a further exponential jump in complexity, and provide again a matching upper bound for expressive constraints. The upper bounds are obtained using automata-theoretic techniques, by combining ideas used for 2RPQs without constraints, which rely on finite-word automata, with ideas for reasoning in very expressive DLs, which rely on infinite-tree automata. Our techniques provide also a solution to the problem of query entailment over DL knowledge bases in which individuals in the ABox may be related through regular role-paths.