Base des données orientées-graphe: migration du relationnel vers le noSQL

I.3. IMPORTANCE DE LA THEORIE DES GRAPHES EN BASE DE DONNEES

Les graphes sont d'une importance en base de données, car une base de données orientées-graphe utilise les structures de graphes (noeuds, arêtes et propriétés) pour représenter et stocker les données.

Par définition, une base de données orientées-graphe correspond à un système de stockage correspondant à un graphe G=(X, U) tel que :

· X est l'ensemble des noeuds qui représentent les enregistrements ;

· U est l'ensemble des liens entre noeuds qui représentent les relations entre enregistrements.

C'est une base de données orientées-objet adaptée à l'exploitation des structures de données de type graphe ou dérivée, comme des arbres. [Wiki3]

Exemple 1.16:

En base de données relationnelle:

Table Client contient un identifiant, un nom, un prénom, une adresse, un numéro client, correspondant aux noms des colonnes respectives. Considérons le client « id01 Badibanga Trésor 96 quartier Ngufu 010203 »

Cette table client est rattachée à une table entreprise, avec un numéro de SIRET, un nom, et un domaine d'activité par exemple. Considérons l'entreprise « 1221 Bcorp TIC ».

La relation entre les tables se nomme a pour client, et bien évidemment Bcorp a pour client Trésor.

En base de données orientées-graphe, la table client sera représentée par un ensemble de noeuds pour chaque instance, donc le même client sera représenté par un noeud suivant :

"Client :

identifiant : id01

nom : Badibanga

prénom : Trésor

adresse : 96 quartier Ngufu

numéro client : 010203".

L'entreprise sera représentée de la même manière par un noeud :

"Entreprise :

siret : 1221

nom : Bcorp

domaine : TIC"

Et la relation entre les deux sera matérialisée par un arc partant du noeud Entreprise Bcorp vers le noeud Badibanga Trésor, nommée "a pour client".

Aussi, l'entreprise aura autant de pointeurs que de clients (chaque arc partant de l'entreprise vers le noeud correspondant avec comme nom a pour client).

De la même manière, le noeud client pourra pointer vers un noeud véhicule, lequel véhicule pourra pointer vers un noeud typeClavier, par exemple.

Il sera ainsi beaucoup plus facile d'accéder au type d'ordinateur du client n^o id01 par le biais du graphe puisqu'en parcourant les arcs on retrouvera directement le client, puis son ordinateur, et enfin son type de clavier. En base de données relationnelle, en revanche, il aurait fallu faire des jointures entre la table Client, la table Ordinateur, et la table Clavier ce qui aurait été très couteux.

L'intérêt de cette structure devient donc évident dans le cas de données complexes. C'est ainsi une structure idéale pour des recherches du type « partir d'un noeud et parcourir le graphe » plutôt que « trouver toutes les entités du type X », plus adaptées aux  bases de données relationnelles traditionnelles.

Elle est particulièrement appropriée lorsqu'il s'agit d'exploiter les relations entre les données (par exemple des connaissances entre des personnes, la description de l'ensemble des pièces d'une machine industrielle et de la manière dont elles sont liées entre elles).

Les bases de données orientées-graphes sont utilisées aujourd'hui dans la  modélisation des  réseaux sociaux : LinkedIn utilise par exemple ce système avec un graphe représentant les personnes et leur relations, et parvient ainsi facilement à afficher le degré de séparation entre chaque contact, qui n'est finalement que la distance entre les noeuds.

Elles sont de même utilisées dans le stockage de masse de données ou  Big data, avec ainsi un enjeu important à l'heure actuelle dans l'exploitation des données par leur structure adaptée.

Une telle base de données se caractérise donc par les critères suivants :

· stockage des données représentées sous forme d'un graphe, avec des noeuds et des arêtes;

· lecture et parcours des données sans recours à un index, en utilisant les arêtes pour passer d'un noeud à l'autre ;

· flexibilité du modèle de données ; il n'est pas nécessaire de créer une entité pour les noeuds ou les arêtes contrairement au modèle d'une base de données relationnelle ;

· intégration d'une  API utilisant des algorithmes classique de la  Théorie des graphes ( Algorithme de plus cours chemin (Dijkstra), A*, parcours en largeur, parcours en profondeur, calcul de centralité,...) permettant une exploitation différente des bases de données relationnelles.