Containment of Regular Path Queries under Description Logic Constraints

Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI 2011). 2011.

Query containment has been studied extensively in KR and DBs, for different kinds of query languages and domain constraints. We address the longstanding open problem of containment under expressive description logic (DL) constraints for two-way regular path queries (2RPQs) and their conjunctions, which generalize conjunctive queries with the ability to express regular navigation. We show that, surprisingly, functionality constraints alone make containment of 2RPQs already ExpTime-hard. By employing automata-theoretic techniques, we also provide a matching upper bound that extends to very expressive DL constraints. For conjunctive 2RPQs we prove a further exponential jump in complexity, and provide again a matching upper bound for expressive DLs. 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.

@inproceedings{IJCAI-2011-c2rpq,
   title = "Containment of Regular Path Queries under Description Logic
Constraints",
   year = "2011",
   author = "Diego Calvanese and Magdalena Ortiz and Mantas Simkus",
   booktitle = "Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence
(IJCAI 2011)",
   pages = "805--812",
}