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

Les données sont devenues omniprésentes dans notre société. Devant la masse de ces données, les méthodes pour les interroger et la diversité des structures pour les représenter ne cesse d’augmenter. Le développement rapide des réseaux sociaux, des données des transports en commun, de la représentation des interactions entre protéines, … ont rendu populaire la notion de base de données graphe. Une base de données graphe est un modèle pratique pour stocker les données sous forme de nœuds et les mettre en relation par des arcs étiquetés. Dans un réseau social, si Claudie est la mère de Marius, on représente Claudie et Marius comme deux nœuds reliés avec un arc étiqueté par « mère ».

Pour utiliser les données, nous devons pouvoir les interroger, dans le contexte des bases de données graphe il existe plusieurs langages comme SparQL, Cypher,… [87] Ces langages utilisent des requêtes particulières qui expriment des propriétés sur les chemins : les Regular Path Queries (RPQ). Ces requêtes permettent d’interroger le graphe avec des requêtes comme « Quels sont tous les trajets qui peuvent être effectués uniquement en bus ? ». Dans la syntaxe de SparQL ces requêtes s’écrivent sous la forme : SELECT?x,?y WHERE {?x r?y}

où r est une expression régulière. Cette requête retourne les paires de nœuds du graphe qui sont reliés avec un chemin étiqueté par un mot satisfaisant l’expression régulière. Par exemple si r est l’expression régulière bus+ , la requête renvoie toutes les paires de nœuds reliés par un chemin formé d’arêtes toutes étiquetées par « bus ». Malheureusement, les techniques classiques des bases de données relationnelles ne sont pas adaptées pour évaluer de façon optimisée ces requêtes. Une méthode consiste à les optimiser en évaluant une requête plus simple (par exemple une requête acyclique) équivalente à la première. Nous utilisons des connaissances sur nos bases de données graphes pour optimiser plus efficacement les requêtes mais aussi pour compléter des données afin que les modèles satisfassent certaines propriétés. Par exemple, si on considère la clôture transitive par la locution « les amis de mes amis sont mes amis » comme contrainte dans un réseau social, nous pouvons évaluer la requête x.ami.y au lieu de la requête x.ami+ .y car il suffit de vérifier avec qui x est directement ami au lieu de rechercher « les amis d’amis ». On représente ces connaissances par des contraintes d’intégrité. Les contraintes d’intégrité les plus largement utilisées sont les « tuple generating dependencies » ou tgd en abrégé. Elles sont formées d’une tête et d’un corps et correspondent à des contraintes logiques de la forme « corps implique tête ». Par exemple, les deux contraintes suivantes :
∀x,est(x) −→ ∃z,est(z),parent(z,x)
∀x, y, z,fille(x, y),sœur(y, z) → nièce(x, z)

Les contraintes de mots sont régulièrement utilisées pour l’optimisation de requêtes RPQ. Une contrainte de mots est une expression de la forme xuy v xv y, elle est satisfaite par une base de données graphe si pour tout chemin étiqueté par u entre deux nœuds, il existe un chemin entre ces mêmes nœuds étiqueté par v. Par exemple la contrainte « les amis de mes amis sont mes amis » est une contrainte de mots : dès que deux arcs étiquetés par « ami » se succèdent, il existe un arc étiqueté par « ami » qui relie ces nœuds.

Une des questions clés pour optimiser les requêtes est le problème d’inclusion sous contraintes : on teste si l’ensemble des réponses d’une requête RPQ est inclus dans l’ensemble des réponses d’une requête RPQ pour toute base de données qui satisfait les contraintes.

Il existe des cas où le problème d’inclusion est connu comme étant décidable par exemple si les requêtes sont appliquées à partir d’un nœud particulier (racine) [3, 7]. On souhaite généraliser dans le cas où les requêtes peuvent être appliquées depuis n’importe où. L’étude de l’inclusion et de l’optimisation de requêtes RPQ sous contraintes de mots a été peu étudiée dans la littérature. Il a été montré que le problème d’inclusion est indécidable en général mais peu de classes de contraintes de mots assurant la décidabilité ont été proposées. L’approche classique pour résoudre ce problème est de le réduire au problème d’inclusion de langages sous réécriture de mots [57]. À chaque contrainte de mots xuv v xv y on peut associer la règle de réécriture u → v. Les règles de réécriture permettent de construire des dérivations à partir d’un mot donné. À partir d’un mot x, si un des facteurs est le membre gauche d’une règle de réécriture, alors on peut remplacer ce facteur par le membre droit de la règle. Par exemple, si on considère la règle ab → bb, le mot aab contient le facteur ab qu’on peut remplacer par bb pour obtenir le nouveau mot abb, à nouveau ce mot présente un facteur ab et on peut donc réécrire le mot abb en bbb, puis la règle ne peut plus être appliquée. De nombreux problèmes sur les systèmes de réécriture ont été largement étudiés. Par exemple, le problème de terminaison « Est ce qu’il existe une dérivation infinie ? » est indécidable. Mais aussi, les problèmes de la préservation des réguliers (auquel nous portons une attention particulière) « Pour tout langage régulier, est ce que l’ensemble des descendants est régulier ?et « pour tout langage régulier, est ce que l’ensemble des ancêtres est régulier ? » sont indécidables. Il est possible de réduire le problème d’inclusion RPQ sous contraintes de mots au problème d’inclusion de langages réguliers [57], nous montrons que cette réduction dan le cas où les modèles sont finis n’est valable que sous hypothèse :

Sous cette hypothèse, une RPQ de langage L est incluse dans une RPQ de langage L’ sous contraintes de mots si, et seulement si le langage L est inclus dans les ancêtres de L’ par le système de réécriture associé aux contraintes de mots.

Ainsi, si les systèmes de réécriture d’une classe préservent les réguliers (pour les ancêtres) alors il suffit de tester l’inclusion de deux langages réguliers. En général, les requêtes ne sont pas évaluées sur des bases de données qui satisfont toujours les contraintes d’intégrité. On souhaite alors compléter ces bases de données par des faits supplémentaires pour les satisfaire. Cette complétion a été largement utilisée à travers la procédure du chase qui comporte de nombreuses variantes (oblivious, semi-oblivious, standard, …).

Le principe est d’ajouter une donnée lorsque celle-ci est manquante pour une contrainte en ajoutant la tête si le corps est vérifié. Par exemple, considérons la requête∀x, y, z,fille(x, y),sœur(y, z) → nièce(x, z), la base de données   contient  les faits fille(Claudie,Léonne) et sœur(Léonne,Danielle), on peut donc ajouter le fait nièce(Claudie,Danielle) à notre base de connaissance. Cette procédure présente un inconvénient majeur : elle ne termine pas toujours. Par exemple si on considère la contrainte ∀x,est(x) −→ ∃z,est(z),parent(z,x) sur la base de données constituée uniquement de est(Adrien) alors une donnée NEW est ajoutée avec les relations est(NEW) et parent(NEW,Adrien). Mais les contraintes ne sont toujours pas satisfaites : nous devons compléter à nouveau, on ajoute alors une nouvelle donnée NEW2 et les faits est(NEW2) et parent(NEW2,NEW). Les contraintes ne sont toujours pas satisfaites, et cette procédure continue indéfiniment.

Table des matières

Introduction
1 Préliminaires
1.1 Ensembles, relations et graphes
1.2 Langages
1.3 Système de réécriture et réécriture parallèle
1.4 Base de données graphes, requêtes RPQ et contraintes de mots
1.5 Schéma relationnel et instance
1.6 Tuple Generating Dependency et Datalog
1.7 Chase et dérivations
1.8 Contraintes de mots et traduction
2 État de l’art
2.1 Réécriture
2.2 Requêtes de graphes
2.3 Procédure du chase et borne uniforme
3 Inclusion de requêtes sous contraintes de mots
3.1 Résumé
3.2 Etude de la restriction vers les modèles finis
3.3 Dureté du problème d’inclusion sous contraintes
3.4 Conclusion
4 Complexité parallèle de la réécriture
4.1 Complexité parallèle
4.2 Systèmes à complexité parallèle bornée
4.2.1 Classe MBmax(k)
4.2.2 Classe BPar(k)
4.3 Décidabilité du problème R ∈ MBmax(k)?
4.3.1 Premiers algorithmes
4.3.2 Un algorithme PSPACE
4.3.3 Le problème R ∈ MBmax(k) est PSPACE-difficile
4.4 Conclusion
5 Classe de règles tgd bornées
5.1 Systèmes de règles tgd bornés
5.1.1 Résumé
5.1.2 Définitions générales
5.1.3 Comparaison des classes en O et SO
5.1.4 Problèmes de décision
5.2 Systèmes de règles tgd totales en oblivious
5.2.1 Résumé
5.2.2 Equivalence BF – all
5.2.3 Équivalence terminant – borné
5.3 Chase dans le cadre des contraintes de mots
5.3.1 Résumé
5.3.2 Préliminaires sur les chemins
5.3.3 Comparaison srs/tgd : cas général
5.3.4 Comparaison srs/tgd : cas total
5.4 Conclusion
6 Conclusion
Bibliographie

Télécharger le rapport complet