Note ABES Branching and circuits : algorithmic techniques for efficient query evaluation Branchements et circuits : techniques algorithmiques pour l’évaluation efficace de requêtes Compilation de connaissances Agrégation Requêtes de jointure Requêtes conjonctives Knowledge compilation Databases Aggregation Join queries Conjunctive queries Bases de données -- Interrogation Bases de données relationnelles Représentation des connaissances 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. 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. Electronic Thesis or Dissertation Text en PDF 2078933 https://pepite-depot.univ-lille.fr/LIBRE/EDMADIS/2026/2026ULILB006.pdf https://theses.fr/2026ULILB006/abes https://theses.hal.science/tel-05762022 https://theses.hal.science/tel-05762022 Irwin Oliver Irwin 1997-04-28 FR 298986108 https://theses.fr/2026ULILB006 2026ULILB006 https://doi.org/10.70675/fffb9da0z3514z425czb7d5z4591cedc18d4 2026-03-11 Informatique et applications Université de Lille (2022-....) 259265152 Doctorat Docteur es non oui Salvati Sylvain MADS_DIRECTEUR_DE_THESE_1 090492420 Capelli Florent MADS_DIRECTEUR_DE_THESE_2 233183213 Sirangelo Cristina MADS_PRESIDENT_DU_JURY 190258713 Carmeli Nofar MADS_MEMBRE_DU_JURY_1 27563969X Kimelfeld Benny MADS_RAPPORTEUR_1 233183019 Figueira Diego MADS_RAPPORTEUR_2 162394039 École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) MADS_ECOLE_DOCTORALE_1 258621362 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 410272 18388695X Centre Inria de l'Université de Lille MADS_PARTENAIRE_DE_RECHERCHE_2 104752 185432247 Agence nationale de la recherche (France ; 2005-....) MADS_PARTENAIRE_DE_RECHERCHE_3 121892174 ddc:004 Salvati Sylvain Capelli Florent Sirangelo Cristina Carmeli Nofar Kimelfeld Benny Figueira Diego École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) Centre de Recherche en Informatique, Signal et Automatique de Lille Centre Inria de l'Université de Lille Agence nationale de la recherche (France ; 2005-....) PDF 2078933