Containment of Regular Path Queries under Description Logic Constraints

Calvanese, Diego; Ortiz, Magdalena; Simkus, Mantas

doi:10.5591/978-1-57735-516-8/IJCAI11-141

Containment of Regular Path Queries under Description Logic Constraints

Diego Calvanese, Magdalena Ortiz, Mantas Simkus

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 805-811.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-141

Abstract

Query containment has been studied extensively in KR and databases, 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.

Diego Calvanese, Magdalena Ortiz, and Mantas Simkus. 2011. Containment of Regular Path Queries under Description Logic Constraints. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 805–811. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-141

@inproceedings{ijcai2011p141,
  title     = {Containment of Regular Path Queries under Description Logic Constraints},
  author    = {Calvanese, Diego and Ortiz, Magdalena and Simkus, Mantas},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {805--811},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-141},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-141},
}

TY  - CPAPER
TI  - Containment of Regular Path Queries under Description Logic Constraints
AU  - Calvanese, Diego
AU  - Ortiz, Magdalena
AU  - Simkus, Mantas
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 805
EP  - 811
DO  - 10.5591/978-1-57735-516-8/IJCAI11-141
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-141
ER  -