Description du sujet de thèse

Langages d'interrogation pour l'analyse des graphes.
Les bases de données relationnelles sont devenues l'épine dorsale de notre infrastructure informatique quotidienne, SQL figurant parmi les cinq langages les plus courants, et le marché de 65 milliards de dollars par an est dominé par les géants de l'industrie. Cette domination a été remise en question à plusieurs reprises, notamment au cours de la dernière décennie par les bases de données graphiques. Celles-ci traitent les données telles qu'elles sont perçues conceptuellement, ce qui les rend faciles à utiliser par les développeurs. Le modèle de base de données graphique dominant dans l'industrie est celui des graphes de propriété (PG), qui devrait connaître une croissance rapide et être utilisé dans plus de 80 % des tâches d'analyse de données.
Le domaine comprend Neo4j (leader actuel du marché) avec son langage Cypher, et de nombreux noms connus (Oracle, Amazon, IBM, Redis, SAP).
Ce nouveau paysage a également contraint les principaux acteurs industriels à normaliser un nouveau langage pour les données graphiques (connu sous le nom de GQL ; la version 1 sera publiée en 2024), à l'instar de SQL qui est devenu le langage à utiliser pour les bases de données relationnelles il y a environ 35 ans.
Dans ce scénario, le débat le plus important est de savoir s'il faut des représentations graphiques natives des PG ou si les bases de données relationnelles peuvent les interroger. Cette dernière approche est celle de langages tels que SQL/PGQ (version 1 publiée en 2023), qui ajoute l'interrogation des PG à SQL, Datalog (ses implémentations industrielles telles que Soufflé [3]) et des alternatives SQL modernes et puissantes, telles que Rel.
La plupart des recherches de la communauté universitaire continuent de se concentrer sur les bases de données de graphes natives, ce qui laisse un énorme vide dans le domaine des bases de données de graphes, qui ont un grand besoin d'être développées.
Une grande partie de la recherche de la communauté universitaire continue à se concentrer sur les bases de données de graphes natives, laissant un énorme vide dans la recherche très nécessaire pour les applications pratiques qui se produisent déjà, avec peu de base scientifique derrière elles.
Il est donc urgent de comprendre les fondements des modèles et des langages d'interrogation relationnelle des PG, afin de disposer d'une base théorique solide pour cet aspect, bientôt dominant, de la gestion des données graphiques.
Cette thèse abordera en particulier la question de l'introduction de l'analyse des graphes dans les langages pour les PGs. L'analyse de graphes, cruciale dans de nombreuses charges de ML et applications industrielles, est centrée sur des tâches telles que la recherche de chemins, la centralité, la détection de communautés [4]. Elles ne sont pas correctement prises en charge par les langages d'interrogation de graphes basés principalement sur la correspondance de motifs pour la recherche de chemins, ce qui oblige les fournisseurs à proposer des extensions telles que GDS dans Neo4j et MAGE dans Memgraph pour combler l'écart. Cependant, il est beaucoup plus intéressant de fusionner l'interrogation et l'analyse dans un seul langage. L'ajout de points fixes à la récursion et au filtrage est une voie théorique prometteuse [2].
Dans l'industrie, les langages de graphes visent à atteindre le même objectif en utilisant la récursivité pour différents types de représentations de graphes (le langage Rel mentionné ci-dessus), ou une puissante combinaison d'agrégation et de récursion (SQL/PGQ [1]) pour capturer de nombreux algorithmes de graphes.
Le principal défi consiste à trouver un équilibre entre l'expressivité du langage et sa complexité théorique et pratique
Le principal défi consiste à trouver un équilibre entre l'expressivité du langage, sa complexité théorique et pratique, et le degré d'utilisabilité dans l'analyse des graphes. Nous prévoyons d'étudier cet équilibre sur différents langages (SQL, PGQ extension, Rel, etc.). Pour SQL, cela signifie étudier des éléments qui ont échappé à l'attention des théoriciens tout en étant largement utilisés dans la pratique (par exemple, les agrégations complexes via des fonctions de fenêtre). De même, étant donné que nous traitons de langages Turing- complets, nous devons nous concentrer sur des restrictions syntaxiques bien gérées et néanmoins expressives.
Nous irons au-delà des études théoriques et expérimentales et rendrons nos résultats applicables à la fois aux produits industriels et aux nouvelles normes graphiques.

[1] A.Deutsch et al. Graph pattern matching in GQL and SQL/PGQ. In SIGMOD, 2022.
[2] A.Hogan, J.L.Reutter, et A.Soto. In-database graph analytics with recursive SPARQL. In ISWC, Nov.2020.
[3] H.Jordan,B. Scholz, et P.Subotic. Soufflé : On synthesis of program analyzers. In CAV, pages 422-430. Springer, 2016.
[4] M.Needham et A.Hodler. Graph Algorithms : Practical Examples in Apache Spark and Neo4j. 2019.

Contexte de travail

Le doctorat sera membre du laboratoire et aura accès à ses ressources. Les financements à disposition des deux encadrants (dont le projet ANR Verigraph) couvriront les missions du doctorant ainsi que l’éventuel materiel informatique nécessaire au bon déroulement de la thèse.

Contraintes et risques

Pas de risque identifiés