Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Tyrex Equipe Connect in order to contact the contributor
Submitted on : Thursday, December 28, 2017 - 10:59:31 AM
Last modification on : Tuesday, October 19, 2021 - 11:29:14 AM


Files produced by the author(s)


  • HAL Id : hal-01673025, version 1



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



Record views


Files downloads