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,… [88] 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 ㄷ 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 ㄷ 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, …).
Contraintes de mots et traduction
Définition 77
Une contrainte de mots est une règle tgd B → H telle que B et H sont de la forme :
— B est de la forme {A1(x1,x2), A2(x2,x3),…, An(xn,xn+1)}
— H est de la forme {B1(y1, y2),B2(y2, y3),…,Bm(ym, ym+1)}
— les variables communes de B et H sont x1 et xn+1 avec x1 = y1 et xn+1 = ym+1.
— Les variables x1,…,xn+1 sont distinctes les variables y1,…, ym+1 sont distinctes.
Exemple 78
Les règles suivantes sont des contraintes de mots
— A(x, y), A(y, z) → A(x, z)
— A(x, y),B(y, z) → B(x,t),C(t, z)
Et les règles suivantes n’en sont pas :
— A(x, y), A(x, z) → A(x, z)
— B(x,x) → A(x,x)
— A(x, y) → A(x, z),B(x, y)
Nous allons maintenant relier trois notions :
— Les contraintes de mots (sous formes tgd)
— Les contraintes de mots (sous formes RPQ)
— Les systèmes de réécriture
On commence par introduire une transformation entre les prédicats et les lettres d’un alphabet. Très souvent, les prédicats sont désignés par des lettresmajuscules, nous noterons alors par la minuscule correspondante la transformation en lettre d’un alphabet.
Définition 79
Soit r une contrainte de mot. Soit M = A1(x1,x2), A2(x2,x3),…, An(xn,xn+1) la tête ou le corps de r . On associe à M le mot a1a2…an.
À chaque règle tgd nous pouvons donc associer deux mots, et donc associer une contrainte de mots (forme RPQ) ou une règle d’un système de réécriture.
Définition 80
À toute contrainte de mots (en tant que tgd) r = B → H on associe le mot u à B et v à H on peut donc associer à r :
— La contrainte de mots xuy v xv y
— La règle de réécriture (u, v)
À toute instance I dont tous les prédicats sont d’arité 2 on peut associer une base de données graphes G :
— N = Dom(I)
— E = {(x,a, y), A(x, y) ∈ I}
Pour tout ensemble de contraintes de mots C en tant que tgd, si C’ désigne les contraintes de mots en tant que RPQ on a :
I |= C si et seulement si G |= C’
Ainsi, nous préférons confondre les termes de contraintes de mots tgd et RPQ. De même nous confondons une instance d’arité 2 et la base de données graphe associée.
|
Table des matières
0 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
Télécharger le rapport complet