Skip to Main content Skip to Navigation
Theses

On the foundations for the compilation of web data queries: optimization and distributed evaluation of SPARQL.

Louis Jachiet 1
1 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble [2007-2015]
Résumé : Ma thèse porte sur la compilation des langages de requêtes orientés web des données. Plus particulièrement, ma thèse s’intéresse à l’analyse, l’optimisation et l’évaluation distribuée d’un tel langage : SPARQL. Ma contribution principale est l’élaboration d’une méthode nouvelle particulièrement in- téressante pour des requêtes contenant de la récursion ou dans le cadre d’une évaluation distribuée. Cette nouvelle méthode s’appuie sur un nouvel outil que nous introduisons : la μ-algèbre. C’est une variation de l’algèbre relationnelle équipée d’un opérateur de point fixe. Nous présentons sa syntaxe et sémantique ainsi qu’une traduction vers la μ-algèbre depuis SPARQL avec Property Paths (une fonctionnalité introduite dans le dernier standard SPARQL qui autorise une forme de récursion). Nous présentons ensuite un système de types et nous montrons comment les termes de la μ-algèbre peuvent être réécrits en d’autres termes (de sémantique équivalente) en utilisant soit des règles de réécriture provenant de l’algèbre relationnelle soit des règles nouvelles, spécifiques à la μ-algèbre. Nous démontrons la correction des nouvelles règles qui sont intro- duites pour réécrire les points fixes : elles permettent de pousser les filtres, les jointures ou les projections à l’intérieur des points fixes (dépendant des certaines conditions sur le terme). Nous présentons ensuite comment ces termes peuvent être évalués, d’abord de manière générale, puis en considérant le cas particulier d’une évaluation sur une plateforme distribuée. Nous présentons aussi un modèle de coût pour l’évaluation des termes. À l’aide du modèle de coût et de l’évaluateur, plusieurs termes qui sont équivalents d’un point de vue sémantiques peuvent maintenant être vus comme différentes manières d’évaluer les termes avec différents coûts estimés. Nous montrons alors que les termes qui sont considérés grâce aux nouvelles règles de réécritures que nous avons introduites, permettent une exécution plus efficace que ce qui était possible dans les autres approches existantes. Nous confirmons ce résultat théorique par une expérimentation comparant plusieurs exécuteurs sur des requêtes SPARQL contenant de la récursion. Nous avons investigué comment utiliser une plateforme de calcul distribuée (Apache Spark) pour produire un évaluateur efficace de requêtes SPARQL. Cet évaluateur s’appuie sur un fragment de la μ-algèbre, limité aux opérateurs qui ont une traduction en code Spark efficace. Le résultat de ces investigations à résultat en l’implémentation de SPAR- QLGX, un évaluateur SPARQL distribué en pointe par rapport à l’état de l’art. Pour finir, ma dernière contribution concerne l’estimation de la cardinalité des solutions à un terme de la μ-algèbre. Ces estimateurs sont particulièrement utiles pour l’optimisation. En effet, les modèles de coût reposent généralement sur de telles estimations pour choisir quel sera le terme le plus efficace parmi plusieurs termes équivalents. Pour cette estimation nous nous intéressons tout particulièrement au fragment conjonctif de la μ-algèbre (ce qui correspond au fragment bien connu Basic Graph Pattern de SPARQL). Notre nouvelle estimation de cardinalité s’appuie sur des statistiques sur les données et a été implémenté dans SPARQLGX. Nos expériences montrent que cette méthode permet de grandement accélérer l’évaluation de SPARQL sur SPARQLGX.
Complete list of metadatas

Cited literature [158 references]  Display  Hide  Download

https://hal.inria.fr/tel-01891444
Contributor : Tyrex Equipe <>
Submitted on : Tuesday, October 9, 2018 - 3:44:02 PM
Last modification on : Thursday, July 9, 2020 - 9:44:52 AM

File

these-Louis-Jachiet-2018 (1).p...
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01891444, version 1

Collections

CNRS | INRIA | LIG | UGA

Citation

Louis Jachiet. On the foundations for the compilation of web data queries: optimization and distributed evaluation of SPARQL.. Web. Communauté Université Grenoble Alpes, 2018. English. ⟨tel-01891444v1⟩

Share

Metrics

Record views

330

Files downloads

291