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

https://hal.inria.fr/hal-01098979
Contributor : Inria Links <>
Submitted on : Tuesday, December 30, 2014 - 12:16:09 PM
Last modification on : Thursday, January 7, 2021 - 2:30:03 PM
Long-term archiving on: : Tuesday, March 31, 2015 - 10:17:06 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01098979, version 1

Citation

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⟩

Share

Metrics

Record views

330

Files downloads

223