Dialogue entre la procédure du chase et la réécriture sur les mots

Graphs are a framework that is used to represent data of many different applications: transport, social network, proteins interaction, open data diffusion and its underlying structure.To manage these graphs, the user needs to express queries to extract data and to express properties to enforce integrity constraints or knowledge/ontology used to represent missing data in the graph.In this PhD thesis, we focus on two different questions: how to evaluate efficiently queries over graph and how to complete graphs to satisfy the properties?Our approach to optimize the evaluation of queries is to find a query semantically equal to the initial one but easier to evaluate. We focus at a useful subclass of queries: regular path queries. Indeed, path queries are the core of the classical queries over graphs, for example: “which are the cities reachable from each other by an exclusive bus travel ?”In the logical optimisation of queries, one of the core problems is the problem of inclusion of a query into another. This problem is well studied for different classes of queries and paths queries; however, there are few works that took account integrity constraints satisfied by the graphs. In practice, this could lead to a very efficient optimisation: for the path query x.a^+.y and the integrity constraints which impose that the set of edges labelled by a is closed under transitivity, we can prove that under the graphs satisfying this constraints, the queries xa+y and x.a.y are equivalent. One can remark that it is very efficient to answer this query. Our approach is to reduce the inclusion problem where integrity constraints are expressed by word constraints, to a problem of containment of regular languages by using string rewriting systems following the approach introduced by Grahne and Thomo. After proving that this reduction of Grahne and Thomo is partially wrong for finite graphs, we introduce a restriction over the rewriting systems guaranteeing the correctness of this reduction and the decidability of the inclusion. The key idea of our restriction is to bound the number of “parallel steps” for every derivation by a constant. We prove that checking if a system is uniformly-bounded by k is pspace-complete.The second problem is to complete the graph to satisfy the properties. This problem is well studied in the context of relational databases by diverse variants of a same procedure: the chase. Unfortunately, this procedure does create a possibly infinite model and not a finite one as we wish.The classical approach in this context is to check whenever the chase procedure terminates for every instance. However, this question is undecidable in general. Inspired by our uniform-bounded notion for rewriting systems developed in the previous part and a similar notion recently introduced for some chase procedures, we study different definitions of uniform boundedness for different kind of chases and we compare them to each other. Finally, we establish that the notions of uniform boundedness for the chase and the uniform boundedness for string rewriting systems are equivalent for a subclass of word constraints reinforcing the links between reasoning over graphs and reasoning over rewriting systems.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