Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

How to Best Nest Regular Path Queries

Abstract : Regular path queries (RPQs) define query patterns in terms of regu-lar expressions and are therefore well-suited to query for paths over roles in DL. RPQs can be extended to 2-way RPQs (with converse), CRPQs (with conjunc-tions), or PRPQs (arbitrary positive Boolean combinations), all of which have been explored in DL research. Another natural extension of any query language is nesting, where query predicates can be defined in terms of subqueries. In this pa-per, we discuss several ways of introducing nesting to PRPQs, and show that they lead to increasingly expressive query languages: CN2RPQs, which were stud-ied in the context of DLs recently; nested P2RPQs; and positive queries with transitive closure on binary predicates. The latter is one of the most expressive languages for which query answering can still be decided over DL knowledge bases. We present initial complexity results that show query answering to be non-elementary in the worst case, with an exponential increase for each level of nest-ing of the transitive closure operator.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Inria Links Connect in order to contact the contributor
Submitted on : Tuesday, December 30, 2014 - 12:16:09 PM
Last modification on : Thursday, January 20, 2022 - 5:30:44 PM
Long-term archiving on: : Tuesday, March 31, 2015 - 10:17:06 AM


Files produced by the author(s)


  • HAL Id : hal-01098979, version 1


Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph. How to Best Nest Regular Path Queries. Informal Proceedings of the 27th International Workshop on Description Logics, Jul 2014, Vienne, Austria. ⟨hal-01098979⟩



Record views


Files downloads