Nos partenaires

CNRS

Rechercher





Accueil du site > Français > Evénements > Soutenances > Soutenances de thèses

Soutenances de thèses

 

 

Méthodes d'optimisation pour le traitement de requêtes réparties à grande échelle sur des données liées
Optimization Methods for Large-scale Distributed Query Processing on Linked Data

Damla DEMIRTAS - Equipe PYRAMIDE - IRIT

Mercredi 28 Juin 2017, 10h00
UT3 Paul Sabatier, IRIT, Salle des Thèses
Version PDF :

Jury

M. Djamal BENSLIMANE, Professeur à l'Université Claude Bernard Lyon 1, France (Rapporteur)
M. Onur DEMIRÖRS, Professeur à l'Université Technique du Moyen-Orient, Turquie (Rapporteur)
M. Ladjel BELLATRECHE, Professeur à l'ENSMA Poitiers, France (Examinateur)
M. Abdelkader HAMEURLAIN, Professeur à l'Université Toulouse III - Paul Sabatier, France (Directeur de Thèse)
Mme Belgin ERGENC, Professeur Associé à l'Institut des Technologies d'Izmir, Turquie (co-Directeur de Thèse)
Mme Shaoyi YIN, Maître de Conférences à l'Université Toulouse III - Paul Sabatier, France (Encadrant)

Mots clés

Traitement de requêtes distribuées, optimisation de requêtes, optimisation de requêtes adaptative, Données Liées, fédération de requêtes, évaluation de performances

Keywords

Distributed Query Processing, Query Optimization, Adaptive Query Optimization, Linked Data, Query Federation, Performance Evaluation

Résumé

"Données Liées" est un terme pour définir un ensemble de meilleures pratiques pour la publication et l'interconnexion des données structurées sur le Web. A mesure que le nombre de fournisseurs de Données Liées augmente, le Web devient un vaste espace de données global. La fédération de requêtes est l'une des approches permettant d'interroger efficacement cet espace de données distribué. Il est utilisé via un moteur de requêtes fédéré qui vise à minimiser le temps de réponse du premier tuple du résultat et le temps d'exécution pour obtenir tous les tuples du résultat.
Il existe trois principales étapes dans un moteur de requêtes fédéré qui sont la sélection de sources de données, l'optimisation de requêtes et l'exécution de requêtes. La plupart des études sur l'optimisation de requêtes dans ce contexte se concentrent sur l'optimisation de requêtes statique qui génère des plans d'exécution de requêtes avant l'exécution et nécessite des statistiques. Cependant, l'environnement des Données Liées a plusieurs caractéristiques spécifiques telles que les taux d'arrivée de données imprévisibles et les statistiques peu fiables. En conséquence, l'optimisation de requêtes statique peut provoquer des plans d'exécution inefficaces. Ces contraintes montrent que l'optimisation de requêtes adaptative est une nécessité pour le traitement de requêtes fédéré sur les données liées.
Dans cette thèse, nous proposons d'abord un opérateur de jointure adaptatif qui vise à minimiser le temps de réponse et le temps d'exécution pour les requêtes fédérées sur les endpoints SPARQL. Deuxièmement, nous étendons notre première proposition afin de réduire encore le temps d'exécution. Nos deux propositions peuvent changer la méthode de jointure et l'ordre de jointures pendant l'exécution en utilisant une optimisation de requêtes adaptative. Nos opérateurs adaptatifs proposés peuvent gérer différents taux d'arrivée des données et le manque de statistiques sur des relations.
L'évaluation de performances dans cette thèse montre l'efficacité de nos opérateurs adaptatifs proposés. Ils offrent des temps d'exécution plus rapides et presque les mêmes temps de réponse, comparé avec une jointure par hachage symétrique. Par rapport à bind join, nos propositions se comportent beaucoup mieux en ce qui concerne le temps de réponse et peuvent également offrir des temps d'exécution plus rapides. En outre, notre deuxième proposition obtient un temps de réponse considérablement plus rapide que la bind-bloom join et peut également améliorer le temps d'exécution. Comparant nos deux propositions, la deuxième offre des temps d'exécution plus rapides que la première dans toutes les conditions. En résumé, nos opérateurs de jointure adaptatifs présentent le meilleur compromis entre le temps de réponse et le temps d'exécution. Même si notre objectif principal est de gérer différents taux d'arrivée des données, l'évaluation de performance révèle qu'ils réussissent à la fois avec des taux d'arrivée de données fixes et variés.

Abstract

Linked Data is a term to define a set of best practices for publishing and interlinking structured data on the Web. As the number of data providers of Linked Data increases, the Web becomes a huge global data space. Query federation is one of the approaches for efficiently querying this distributed data space. It is employed via a federated query engine which aims to minimize the response time and the completion time. Response time is the time to generate the first result tuple, whereas completion time refers to the time to provide all result tuples.
There are three basic steps in a federated query engine which are data source selection, query optimization, and query execution. This thesis contributes to the subject of query optimization for query federation. Most of the studies focus on static query optimization which generates the query plans before the execution and needs statistics. However, the environment of Linked Data has several difficulties such as unpredictable data arrival rates and unreliable statistics. As a consequence, static query optimization can cause inefficient execution plans. These constraints show that adaptive query optimization should be used for federated query processing on Linked Data.
In this thesis, we first propose an adaptive join operator which aims to minimize the response time and the completion time for federated queries over SPARQL endpoints. Second, we extend our first proposal to further reduce the completion time. Both our proposals can change the join method and the join order during the execution by using adaptive query optimization. Our proposed operators can handle different data arrival rates of relations and the lack of statistics about them.
The performance evaluation of this thesis shows the efficiency of our proposed adaptive operators. They provide faster completion times and almost the same response times, compared to symmetric hash join. Compared to bind join, our proposals perform substantially better with respect to the response time and can also provide faster completion times. In addition, our second proposal provides considerably faster response time than bind-bloom join and can improve the completion time as well. Our second proposal also provides faster completion times than our first proposal in all conditions. In conclusion, our adaptive join operators provide the best trade-off between the response time and the completion time. Even though our main objective is to manage different data arrival rates of relations, the performance evaluation reveals that they are successful in both fixed and different data arrival rates.

 

Retour