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 [2007-2015]
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 metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01673025
Contributor : Tyrex Equipe <>
Submitted on : Thursday, December 28, 2017 - 10:59:31 AM
Last modification on : Friday, July 3, 2020 - 4:51:38 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • 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-01673025v1⟩

Share

Metrics

Record views

330

Files downloads

194