12 septembre 2022
Florent Foucaud (Clermont Ferrand (LIMOS))Certaines requêtes de bases de données peuvent être modélisées par des homomorphismes de structures relationnelles. Les bases de données graphes sont de plus en plus utilisées dans l’industrie. Une telle base de données peut être modélisée par un (grand) graphe orienté et étiqueté. Certaines requêtes “locales” peuvent être vues comme de (petits) graphes orientés et étiquetés, et la requête est satisfaite s’il existe un homomorphisme du graphe de la requête vers le graphe de la base de données.
Dans les applications modernes, des requêtes plus expressives, dites “navigationnelles”, sont communément utilisées. Nous montrerons comment définir la notion correspondante d’homomorphisme navigationnel, concept défini en 2017 par Barcelo, Romero et Vardi. Nous nous focaliserons sur les requêtes dites “à chemins réguliers”, définies par des langages réguliers, et nous présenterons quelques résultats algorithmiques théoriques dans ce domaine. Nous montrerons le lien entre cette thématique et celles de la théorie des homomorphismes de graphes et des problèmes de satisfaction de contraintes. Il s’agit de travaux réalisés avec Laurent Beaudou, Florent Madelaine, Lhouari Nourine et Gaétan Richard.