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.
Type de document :
Communication dans un congrès
Informal Proceedings of the 27th International Workshop on Description Logics, Jul 2014, Vienne, Austria. 2014
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01098979
Contributeur : Inria Links <>
Soumis le : mardi 30 décembre 2014 - 12:16:09
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27
Document(s) archivé(s) le : mardi 31 mars 2015 - 10:17:06

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2014. 〈hal-01098979〉

Partager

Métriques

Consultations de la notice

197

Téléchargements de fichiers

119