Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel

Stockage Natif Stockage Natif Stockage Natif

Structures de Stockage : Matrice d’adjacence Structures de Stockage : Matrice d’adjacence

Gestion des Données Graphe

Stefania Dumbrava

ENSIIE

1 Mars 2021

Figure: Graphe orienté étiqueté

Figure: Graphe non-orienté non-étiqueté

1/36 2/36 3/36

Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Matrice d’adjacence : Atteignabilité (I) Matrice d’adjacence : Atteignabilité (II) Matrice d’adjacence : Isomorphisme de graphe (I)
Pour une matrice d’adjacence, A, A2 = A · A représente les chemins de
longeur 2 entre les nœuds (éléments) appartenant à A. Les graphes représentés par A1 et A2 sont isomorphes, s’il y a une
matrice de pérmutations P, tel que P · A1 · P 1 = A2 .

Figure: Atteignabilité selon un chemin de longeur 2

Figure: Example de graphes isomorphes

4/36
Figure: Atteignabilité selon un chemin de longeur 2 5/36 6/36

Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Matrice d’adjacence : Isomorphisme de graphe (II) Matrice d’adjacence Matrice d’adjacence

Les graphes représentés par A1 et A2 sont isomorphes, s’il y a une
matrice de pérmutations P, tel que P · A1 · P 1 = A2 .

Problèmes avec cette représentation matriciale

comment gèrer les graphes étiquetés ?
comment gèrer les graphes très grands ?
comment gèrer les graphes faiblement connectés ?

Figure: Example de graphes isomorphes

Figure: Example des représentations matriciales

Source: http://brainimaging.waisman.wisc.edu/ chung/graph/admatrix.jpg

7/36 8/36 8/36

 Stockage Matricial Stockage Matricial Stockage Matricial
Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Matrice d’adjacence Interlude : Cas d’usage (I) Interlude : Cas d’usage (II)
Réseaux Sociaux (Facebook)
environ 1.4 bilion d’utilisateurs Réseaux de Transport (GMaps)
...comme structure de stockage
un utilisateur a en moyenne approx. 350 amis
Avante en Californie, approx. 2 millions de jonctions
matrice de taille au moins 1.400.000.000 x 1.400.000.000
facilement implementable dans la plus part de langages de approx. 350 valeurs non-nulles par ligne 99% des jonctions avec au moins 6 routes
programmation à travers des tableaux. matrice de taille au moins 2.000.000 x 2.000.000
moins de 6 valeurs non-nulles par ligne !

Désavantajes
seulement représente la topologie du graphe
pas de propriétés
pas de typage (étiquétes)
peu adapté au cas d’usage de la vraie vie...

Source: https://writings.stephenwolfram.com/2013/04/data-science-of-the-facebook-world/

9/36 10/36 11/36

Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Défi Compression Matriciale Compression Matriciale

Comment compresser les données ?

12/36 13/36 14/36

Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Triple Table Triple Table Tables Nœuds et Arêtes

Une table avec trois colonnes : sujet, prédicat, objet Deux tables universelles pour les nœuds et les arêtes
Une table avec trois colonnes : sujet, prédicat, objet Avantages
approche générique, simple, et dirécte
peut être implementé dans des moteurs relationnels
pérmet l’ajout des indexes pour une recherche plus efficace

Désavantages
les valeurs NULL ont besoin d’un traitement spécial
Référence : Daniel J. Abadi et al. “Scalable Semantic Web Data Management Using Vertical les requêtes doivent opérer sur tous les triplets (comme c’est le cas pour les column stores)
Partitioning”. [VLDB 2007]
(pas de partionnement des données selon le schéma) les requêtes doivent opérer sur tous les nœuds et les arêtes
beaucoup de redondance (pas de partionnement des données selon le schéma).

15/36 16/36 17/36

 Stockage Matricial Stockage Matricial Stockage Matricial
Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Property Table Property Table Property Table

regrouper les propriétés qui ont tendance à être définis ensemble

dans une table
e.g., les propriétés “type”, “title”, et “copyright date” la table va Désavantages
stocker ensemble tous les triples qui ont une de ces propriétés la géstion des attributs qui ont plusieurs valeurs
plusieurs “property tables” avec des di⇤erents clusters des propriétés la géstion des requêtes qui ont des propriétés qui ne sont pas
peuvent être crées spécifiés
une propriété donnée peut seulement apparaı̂tre dans maximum un l’approche introduit des valeurs NULL
“property table”
les triples qui ne peuvent pas être regroupés dans un “property
table” vont être stockés dans une table spéciale (“left-over table”)

Figure: Exemple de stockage à base des “property tables”

18/36 19/36 20/36

Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Property Class Table Property Class Table Approches á base des Property Tables

des ensembles des sujets qui sont similaires sont regroupés

(dans la même table)
les propriétés des sujets sont céntrales
une propriété peut exister dans plusieurs “property class tables”
un sujet peut aussi exister dans plusiers “property class tables

Désavantages
la géstion des attributs qui ont plusieurs valeurs
la géstion des requêtes dont les propriétés sont non-spécifiés
l’approche introduit des valeurs NULL Figure: Exemple comparatif
Figure: Exemple de stockage à base des “property class tables”

21/36 22/36 23/36

Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Approches á base des Property Tables Stockage Vertical Stockage Vertical

une table par propriété et deux colonnes par table : sujet et objet
triage par sujet : recherche rapide et jointures efficaces (sort-merge)
permet d’avoir plusieurs valeurs per attribut
des méthodes de compression peuvent être appliqués
problèmes à gérér des requêtes dont les propriétés sont non-spécifiés

Figure: Exemple d’un column store

Figure: Exemple comparatif

24/36 25/36 26/36

 Stockage Matricial Stockage Matricial Stockage Matricial
Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Stockage Natif Stockage Natif Stockage Natif

27/36 28/36 29/36

Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Stockage Natif Stockage Natif Stockage Natif

30/36 31/36 32/36

Stockage Matricial Stockage Matricial Stockage Matricial

Stockage Relationnel Stockage Relationnel Stockage Relationnel
Stockage Natif Stockage Natif Stockage Natif

Stockage Natif Stockage Natif Stockage Natif

Désavantages
Avantages La chase des pointeurs pour des résultats intérmedières très larges
enregistrements de taille fixe “massive random memory access”
diréctement adressable byte par byte on peut rater plusieurs caches
pointeur vers le i-éme enregistrements e.g., plutôt que scanner for all points in X { do something
on peut le retrouver à la position s + i · l, ou s est la position du with the record} ... scanner
store et l est la taille fixé des enregistrements dans le store for all points in X { if position in X { do something
with the record }}
la structure du graphe peut être navigué facilement
est peut être plus e⇥cace
“pointer chasing” (chase des pointeurs)
Comment choisir quels pointeurs chaser ?
Besoin d’optimiser les requêtes

33/36 34/36 35/36

 Stockage Matricial
Stockage Relationnel
Stockage Natif

Résumé

Plusieurs solutions de stockage :

matricialles : matrice d’adjacence, CSR, CSC
relationnelles : triple table, property (class) table, column store
natives : cas de Neo4j (usage des pointeurs)

36/36