Les graphes sont une manière de représenter les données et leur structure sous-jacente utilisée dans différentes applications : transport, réseaux sociaux, interaction de protéines, ... Pour gérer ces graphes, l’utilisateur a besoin d’interroger les données du graphe et d’exprimer des propriétés représentées par des contraintes satisfaites par le graphe ou des connaissances pour représenter les données manquantes du graphe. Dans cette thèse nous nous intéressons à deux questions particulières : comment évaluer efficacement des requêtes sur des graphes et comment compléter des graphes pour satisfaire les propriétés? Notre approche d’optimisation d’évaluation des requêtes consiste à déterminer d’autres requêtes sémantiquement égales à l’initiale mais plus faciles à évaluer, nous appliquons cette méthode sur les requêtes de chemin régulier (RPQ). Ces dernières sont au cœur des requêtes classiques de graphe comme : “quelles sont les villes reliées par un trajet uniquement en bus ?“ Pour l'optimisation de requêtes, un des problèmes essentiels est de décider l’inclusion d’une requête dans une autre. Ce problème a été largement étudié pour différentes classes de requêtes et de requêtes de chemin, toutefois peu de travaux ont pris en compte les contraintes d’intégrité satisfaites par les graphes. D’un point de vue pratique, cela peut conduire à des optimisations très efficaces : par exemple la requête xa+y pour les graphes qui satisfont la contrainte imposant que l’ensemble des arêtes étiquetées par a est close par transitivité est équivalente à la requête x.a.y, elle, très facile à évaluer. Notre approche est de réduire le problème d’inclusion dans le cadre des contraintes de mots au problème d’inclusion de langages réguliers modulo les systèmes de réécriture de mots comme proposé par l’approche de Grahne et Thomo. Après avoir prouvé que la réduction de Grahne et Thomo est partiellement fausse dans le cas des graphes finis, nous introduisons une restriction sur les systèmes de réécriture qui assurent la réduction et la décidabilité du problème d’inclusion. L’idée principale de notre restriction et de borner le nombre “d’étapes parallèles” de toute dérivation par une constante donnée. Nous prouvons que tester si un système est uniformément borné par k est pspace-complet. Le second problème consiste à savoir comment compléter efficacement les graphes afin de satisfaire les propriétés données. Ce problème a été largement étudié dans le contexte des bases de données relationnelles pour diverses variantes d’une même procédure : le chase. Malheureusement cette procédure construit des modèles possiblement infinis contrairement à ce que nous souhaitons. L’approche classique pour répondre à ce problème est de vérifier si la procédure du chase termine pour toute instance, cependant cette question est indécidable en générale. En nous inspirant de la notion de borne uniforme des systèmes de réécriture développée précédemment et d’une notion similaire récemment introduite précédemment, nous étudions différentes définitions de borne uniforme pour plusieurs variantes de chase et nous comparons les classes obtenues entre elles. Finalement nous montrons que les notions de borne uniforme pour le chase et de borne uniforme pour les systèmes de réécriture de mots sont équivalentes pour une certaine sous-classe de contrainte de mot renforçant les dialogues entre les raisonnements sur les graphes et les raisonnements sur les systèmes de réécritures.
Evelyne CONTEJEAN CNRS Université Paris-Sud Rapportrice Marie-Laure MUGNIER Université de Montpellier Examinatrice Thomas GENET Université de Rennes Rapporteur Sophie TISON Université de Lille Directeur de thèse Pierre BOURHIS CNRS, Université de Lille Co-directeur de thèse Rémi GILLERON Université de Lille Examinateur
Thèse de l'équipe LINKS soutenue le 19/12/2019
français
English