• Langue : Anglais
• Discipline : Informatique et applications
• Identifiant : 2026ULILB006
• Type de thèse : Doctorat
• Date de soutenance : 11/03/2026

Résumé en langue originale

L'évaluation et l'accès efficaces aux réponses des requêtes sur les bases de données constituent un enjeumajeur dans le cadre de la gestion des données. Cette problématique revêt une importance croissante avec l'augmentation constante des volumes de données et la complexité croissante des requêtes plus complexes. Dans le modèle des bases de données relationnelles, l'évaluation des requêtes s'avère complexe en raison de la présence des jointures. Ces dernières peuvent engendrer des résultats intermédiaires de grande taille et occasionner des frais de calcul substantiels. Dans le cadre de cette thèse, une exploration approfondie de divers aspects inhérents à l'évaluation des requêtes et à leur complexité computationnelle respective est entreprise.L'analyse se concentre en premier lieu sur les algorithmes de jointure optimaux dans le pire des cas. Cesalgorithmes ont pour objectif de renvoyer l'ensemble des réponses à une requête sur une base de données, tout en offrant des garanties solides quant au temps d'évaluation, qui doit rester proportionnel à la taille maximale de la sortie. Dans le présent manuscrit, nous proposons une exposition d'un algorithme de jointure simple, qui peut être démontré comme étant optimal dans le pire des cas, de manière simple etmodulaire.Dans cette thèse, nous avons exploré deux tâches d'évaluation principales : l'accès direct et l'échantillonnage uniforme. Dans le cadre de l'échantillonnage uniforme, nous montrons comment utiliser la trace d'exécution de notre algorithme de jointure pour échantillonner uniformément, sans pour autant énumérer tous les résultats. Afin d'assurer l'accès direct, nous avons exploité une structure de circuits relationnels. Cette méthode permet une navigation efficace dans l'espace des réponses et la récupération des réponses à des positions arbitraires pour un ordre fixé. Nous montrons également que notre méthode permet d'étendre les résultats présents dans la littérature à des classes plus larges de requêtes, et notamment les requêtes avec négation.Dans les deux cas, l'objectif des algorithmes développés est de construire l'ensemble des réponses auxrequêtes de manière incrémentale. Les structures employées, à base de circuits et de branchements, nouspermettent de réduire la complexité des méthodes employées.

Résumé traduit

Efficiently evaluating and accessing the answers of queries over databases is a central problem in datamanagement, particularly as data volumes continue to grow and queries become more complex. In therelational database model, query evaluation is complicated by the presence of joins, which may inducelarge intermediate results and lead to prohibitive computational costs. This thesis explores several aspectsof query evaluation and their respective computational complexity.The first aspect we consider is that of worst-case optimal join algorithms. These algorithms aim toreturn the answer set of a query over a database, while providing strong guarantees ensuring that theevaluation runs in time proportional to the maximum possible output size. In this manuscript, we presenta join algorithm that can be shown to be worst-case optimal in a simple and modular way. One ofthe advantages of our approach is the implicit data representation it induces. By improving on thisrepresentation of the answers of a query, we are able to work on finer algorithmic problems.The two main evaluation tasks we consider in this thesis are direct access and uniform sampling. Foruniform sampling, we show how the execution trace of our worst-case optimal join algorithm can beleveraged to sample query answers according to a uniform distribution without enumerating the fullresult set. For direct access, we exploit relational circuits to navigate the answer space efficiently andretrieve answers at arbitrary positions in a fixed order, extending existing approaches to broader classesof queries, including queries with negation.In both cases, the aim of our algorithms is to build the answer set of queries incrementally. We also usethe structure of relational circuits to improve on the complexity of these methods.