Amela Fejza

Les graphes contenant des masses d'information interreliées sont des structures de données omniprésentes de nos jours. 

Les requêtes récursives constituent un moyen puissant pour extraire des informations potentiellement précieuses de ces graphes. Par exemple, en permettant la navigation le long de séquences d'arêtes de longueur arbitraire, les requêtes de chemins réguliers permettent d'analyser les relations entre des entités distantes du graphe. Cependant, la récursivité rend souvent la réponse aux requêtes très coûteuse, parfois même difficilement réalisable en pratique. 

Les méthodes d'optimisation des requêtes récursives sont cruciales. La difficulté du problème de l'optimisation des requêtes en présence de récursion est notoirement connue. 

Cette thèse décrit les fondements théoriques et pratiques du graphe acyclique dirigé logique récursif de requêtes (RLQDAG) pour énumérer efficacement les plans de requêtes récursives dans les optimiseurs basés sur le principe de transformation ; ainsi qu'une application pour extraire de l'information de graphes de propriétés. Le RLQDAG étend les techniques précédemment développées pour les requêtes non récursives ainsi que les derniers développements en algèbre relationnelle récursive, dans le but d'optimiser la phase d'énumération de plans dans les optimiseurs de requêtes. Cette phase est cruciale car elle peut produire des plans d'évaluation qui sont drastiquement plus efficaces, avec un impact direct sur la faisabilité et l'efficacité de l'évaluation de requêtes récursives en pratique.

Cette thèse commence par une étude approfondie de la littérature sur les langages de requêtes pour les graphes, les méthodes d'optimisation de requêtes et leurs limites en présence de récursion. Ensuite, dans une partie de contribution, le RLQDAG est introduit en formalisant et en étendant des concepts importants tels que le partage de sous-termes afin de capturer et de permettre des transformations groupées de sous-plans de requêtes récursives. Un chapitre suivant étudie l'application du RLQDAG pour l'évaluation de requêtes récursives avec des graphes de propriétés. Un prototype d'implémentation du RLQDAG permet d'obtenir des gains de performance significatifs par rapport à l'état de l'art.