Doctorant – Langages de requête pour l’analyse de graphes – Verigraph

Le doctorant sera membre du laboratoire et aura accès à ses ressources. Les financements mis à disposition des deux encadrants (dont le projet ANR Verigraph) couvriront les tâches du doctorant, ainsi que tout matériel informatique nécessaire au bon déroulement de la thèse.

Langages de requête pour l’analyse de graphiques.

Les bases de données relationnelles sont devenues l’épine dorsale de notre infrastructure informatique quotidienne, avec SQL figurant parmi les 5 langages les plus courants et un paysage de 65 milliards de dollars par an dominé par les géants de l’industrie. Cette domination a été contestée à plusieurs reprises, notamment au cours de la dernière décennie par les bases de données graphiques. Ils gèrent 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 Property Graphs (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 (actuel leader du marché) avec son langage Cypher, et de nombreux noms connus (Oracle, Amazon, IBM, Redis, SAP).

Le nouveau paysage a également contraint les grands acteurs industriels à normaliser un nouveau langage pour les données graphiques (connu sous le nom de GQL ; version 1 à paraître en 2024), à l’instar de SQL devenu le langage des bases de données relationnelles il y a environ 35 ans.

Dans ce scénario, le plus grand débat est de savoir si des représentations graphiques natives des PG sont nécessaires ou si des 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), ajoutant les requêtes PG à SQL, Datalog (ses implémentations de pointe telles que Soufflé [3]) et des alternatives SQL modernes et puissantes, telles que Rel. .

Une grande partie de la recherche de la communauté universitaire continue de se concentrer sur les bases de données de graphes natives, laissant un énorme vide dans la recherche indispensable sur des applications pratiques déjà en cours, avec peu de bases scientifiques derrière elles.

Il est donc urgent de comprendre les fondements des modèles et des langages d’interrogation relationnelle des PG, pour disposer d’une base théorique solide sur cet aspect, bientôt dominant, de la gestion des données graphiques.

Cette thèse abordera en particulier la question cruciale de l’introduction de l’analyse de graphes dans les langages pour les PG. L’analyse graphique, cruciale dans de nombreuses charges de ML et applications industrielles, est centrée sur des tâches telles que la recherche de chemin, la centralité et la détection de communauté [4]. Ils ne sont pas correctement pris en charge par les langages de requête de graphes basés principalement sur la correspondance de modèles pour la recherche de chemin, obligeant les fournisseurs à fournir des extensions telles que GDS dans Neo4j et MAGE dans Memgraph pour combler le fossé. Cependant, il est bien plus intéressant de fusionner les requêtes et les analyses dans un seul langage. Une direction théorique prometteuse consiste à ajouter des points fixes à la récursivité et à la correspondance de modèles [2].

Dans l’industrie, les langages graphiques visent à atteindre le même objectif en utilisant la récursion pour différents types de représentations graphiques (le langage Rel mentionné ci-dessus), ou une puissante combinaison d’agrégation et de récursivité (SQL/PGQ [1]) pour capturer de nombreux algorithmes graphiques.

Le principal défi est de trouver l’équilibre entre l’expressivité du langage, sa complexité théorique et pratique et le degré d’utilisabilité dans l’analyse graphique. Nous envisageons d’étudier cet équilibre sur différents langages (SQL, extension PGQ, Rel, etc.). Pour SQL, cela signifie étudier des éléments qui échappaient jusqu’alors à l’attention des théoriciens tout en étant largement utilisés dans la pratique (par exemple, les agrégations complexes via les fonctions de fenêtre). De même, lorsque nous traitons de langages complets de Turing, nous devons nous concentrer sur des restrictions syntaxiques à la fois correctes et expressives.

Nous irons au-delà des investigations 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. Correspondance de modèles de graphiques dans GQL et SQL/PGQ. Dans SIGMOD, 2022.

[2] A. Hogan, JLReutter et A. Soto. Analyse graphique dans la base de données avec SPARQL récursif. Dans ISWC, novembre 2020.

[3] H. Jordan, B. Scholz et P. Subotic. Soufflé : Sur la synthèse des analyseurs de programmes. Dans CAV, pages 422 à 430. Springer, 2016.

[4] M. Needham et A. Hodler. Algorithmes graphiques : exemples pratiques dans Apache Spark et Neo4j. 2019.