Extending the SPARQL Algebra for the optimization of Property Paths

Louis Jachiet 1 Pierre Genevès 1 Nils Gesbert 1 Nabil Layaïda 1
1 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : sparql is the w3c standard language for querying rdf graphs. Since its 1.1 version, sparql allows queries with Property Paths. They correspond to a form of regular path queries over graphs that raises new challenges for sparql evaluators and rdf stores. Property Paths can be recursive and the optimization of recursive queries remains a challenge both in the relational world and in the semantic web world. In this paper, we present µ-algebra, a variation of the sparql Algebra that allows for the optimization of sparql especially with Property Paths. Similarly to the sparql Algebra , sparql 1.1 queries can be translated into our algebra but the obtained µ-algebra terms can be rewritten into multiple equivalent terms. Each of these terms is a possible execution plan of the initial sparql query. We then show that our method generates terms corresponding to execution plans that are not considered by existing methods. We experimentally demonstrate the advantages of our approach. We have implemented a prototype that translates, optimizes and evaluates sparql queries using our algebra. Experiments show that our prototype outperforms other existing methods on recursive queries.
Type de document :
Pré-publication, Document de travail
2017
Domaine :
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01673025
Contributeur : Tyrex Equipe <>
Soumis le : jeudi 28 décembre 2017 - 10:59:31
Dernière modification le : mercredi 16 mai 2018 - 11:18:50

Fichier

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

Identifiants

  • HAL Id : hal-01673025, version 1

Collections

Citation

Louis Jachiet, Pierre Genevès, Nils Gesbert, Nabil Layaïda. Extending the SPARQL Algebra for the optimization of Property Paths. 2017. 〈hal-01673025〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

89