How to Best Nest Regular Path Queries
Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph
How to Best Nest Regular Path Queries
Abstract. Regular path queries (RPQs) define query patterns in terms of regular 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 conjunctions), 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 paper, we discuss several ways of introducing nesting to PRPQs, and show that they
lead to increasingly expressive query languages: CN2RPQs, which were studied 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 nesting of the transitive closure operator.
Published at DL 2014 (Workshop paper)
Download PDF (last update: July 3 2014)
Citation details
- Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph. How to Best Nest Regular Path Queries. In Meghyn Bienvenu, Magdalena Ortiz, Riccardo Rosati, Mantas Simkus, eds.: Proceedings of the 27th International Workshop on Description Logics (DL-14), pp. 404–415. CEUR Workshop ProceedingsProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2014.
author = {Pierre Bourhis and Markus Kr{\"o}tzsch and
Sebastian Rudolph},
title = {How to Best Nest Regular Path Queries},
pages = {404--415},
booktitle = {Proceedings of the 27th International Workshop
on Description Logics (DL'14)},
editors = {Meghyn Bienvenu and Magdalena Ortiz and
Riccardo Rosati and Mantas Simkus},
publisher = {CEUR-WS.org},
series = {CEUR Workshop Proceedings},
volume = {1193},
year = {2014}
}
