| Resumé |
Au cours des 50 dernières années, la quantité et la complexité des informations stockées dans les bases de données ont augmenté et les besoins des utilisateurs ont évolué. Ces changements ont conduit à la création de nouveaux modèles tels que XML, les bases de données clés-valeurs, de séries temporelles, etc. Le sujet de cette thèse est l'un de ces modèles : la base de données graphe. Dans une base de données graphe, les données sont stockées sous la forme d'un graphe, ou d'une collection de noeuds, représentant les entités, reliés entre eux par des arêtes, représentant les relations entre les entités. Des informations supplémentaires sur les entités et leurs relations peuvent être attachées aux noeuds et aux arêtes. Ce modèle puissant, popularisé par Neo4j en 2010, est aujourd'hui incontournable dans divers secteurs tels que la biologie, les réseaux sociaux et la banque. En mettant en avant les liens entre les données, les bases de données de graphes permettent aux utilisateurs de raisonner non seulement sur les éléments individuels, mais aussi sur la structure du graphe entier. En conséquence, l'objectif d'une requête de graphe typique est de trouver un chemin reliant des noeuds spécifiques. Comme les traversées de graphes reposent intrinsèquement sur la transitivité, les langages de requête traditionnels ne sont pas adaptés au contexte des graphes, et de nouveaux langages ont donc été créés. Dans la communauté théorique, les éléments de base d'un langage de graphe sont les requêtes de chemins réguliers (RPQ), qui définissent les contraintes de chemin au moyen d'expressions régulières. Le pouvoir d'expression et la complexité des RPQ et de leurs extensions (par l'union, la conjonction, la navigation bidirectionnelle, les comparaisons de valeurs de données et les propriétés de chemin, par exemple) sont étudiés depuis les années 1990, mais leurs propriétés commencent à peine à être comprises. Le langage graphe pratique le plus populaire aujourd'hui est Cypher de Neo4j. Dans Cypher, un chemin peut être décrit par une expression régulière, mais il comprend également de nombreuses autres fonctionnalités, notamment l'agrégation, différentes sémantiques de chemin, la projection, les sous-requêtes et les mises à jour. Ces éléments diffèrent de ceux d'autres langages, comme GSQL de Tigergraph ou PGQL d'Oracle, mais tous les systèmes de graphes partagent le même noyau : le pattern matching. En 2019, un nouveau groupe de l'Organisation internationale de normalisation (ISO) a été créé pour superviser la normalisation des langages graphes pratiques. Cela a donné lieu à deux nouvelles normes : SQL/PGQ et GQL. L'idée de SQL/PGQ est d'ajouter un mécanisme de pattern matching basé sur les vues à SQL et d'interpréter les données relationnelles en tant que graphe uniquement lorsque cela est nécessaire, tandis que GQL est autonome et stocke les données en tant que graphe natif. Bien que ce travail de normalisation soit un pas dans la bonne direction, il manque un ingrédient crucial : un modèle théorique correspondant. L'objectif de cette thèse est de définir un langage théorique pour les bases de données de graphes, semblable à l'algèbre relationnelle pour SQL, qui reflète les aspects essentiels de GQL et de SQL/PGQ tout en étant suffisamment simple pour une étude théorique. Nous commençons par présenter en détail les caractéristiques de pattern matching partagées par SQL/PGQ et GQL. Nous identifions et formalisons ensuite le noyau de ce langage. Ensuite, nous positionnons nos formalisations de SQL/PGQ et GQL par rapport à l'algèbre relationnelle, ce qui nous permet de mettre en évidence leurs styles distincts, tout en prouvant leur équivalence. Enfin, nous explorons l'impact de l'extension du pattern matching avec des fonctions de liste et montrons que cet ajout n'est pas seulement dangereux en théorie, mais qu'il échoue également en pratique. |