Base de données orientée graphe

Base de graphe

Cette section reprend in extenso le contenu de la fiche Wikipedia décrivant le concept de base de graphe

Qu'est ce qu'une base de données orientée graphe ?

Par définition, une base de données orientée graphe correspond à un système de stockage capable de fournir une adjacence entre éléments voisins : chaque voisin d'une entité est accessible grâce à un pointeur physique.

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

Exemple d'illustration :

En base de donnée relationnelle traditionnelle :

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 Dupont Jean 96 rue des lilas 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 Entreprise D automobile".

La relation entre les tables se nomme a_pour_client, et bien évidemment Entreprise D a pour client Jean.

En base de donnée orientée graphe, la table client sera représentée par un ensemble de nœuds pour chaque instance, donc le même client sera représenté par un nœud suivant :

• "Client :
  • identifiant : id01
  • nom : Dupont
  • prénom : Jean
  • adresse : 96 rue des lilas
  • numéro client : 010203".

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

• "Entreprise :
  • siret : 1221
  • nom : Entreprise D
  • domaine : automobile"

Et la relation entre les deux sera matérialisée par un arc partant du nœud Entreprise Entreprise D vers le nœud Dupont Jean, nommée "a_pour_client".

Aussi, l'entreprise aura autant de pointeurs que de clients (chaque arc partant de l'entreprise vers le nœud correspondant avec comme nom a_pour_client).

De la même manière, le nœud client pourra pointer vers un nœud véhicule, lequel véhicule pourra pointer vers un nœud type Pneu, par exemple.

Intérêt : il sera ainsi beaucoup plus facile d'accéder au type de pneu du client n^o id01 par le biais du graphe puisqu'en parcourant les arcs on retrouvera directement le client, puis son véhicule, et enfin son type de pneus. En base de donnée relationnelle traditionnelle, en revanche, il aurait fallu faire des jointures entre la table Client, la table Véhicule, et la table Pneus 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 nœud 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. Il est cependant possible en base de données orientées graphes d'effectuer des recherches de ce dernier type, en utilisant un système d'indexation qui pourra selon les cas être interne au graphe (super-nœuds servant à l'indexation) ou au-dessus du graphe (via Apache Lucene par exemple).

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 nœuds.

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.

Il existe différents type de graphes permettant le stockage des données tels que :

• le graphe non-orienté "single-type" ,
• l'hypergraphe,
• les Graph Property
• etc...

Une telle base 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 nœuds et des arcs

·       Lecture et parcours des données sans recours à un index, en utilisant les arcs pour passer d'un nœud à l'autre

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

·       Intégration d'une API utilisant des algorithmes classique de la Théorie des graphes (plus-court-chemin, Algorithme de Dijkstra, calcul de centralité…) permettant une exploitation différente des bases de données relationnelles.

Avantages des bases de données orientées graphe

Les bases de données orientées graphes apportent des avantages non négligeables :

·       permettre une modélisation parfois plus naturelle et plus lisible selon le cas d'utilisation

·       traiter des données fortement connectées en évitant les multiples jointures très coûteuses qu'il faudrait mettre en œuvre dans les bases de données relationnelles traditionnelles et ainsi permettre des mises à jour très performantes, même pour un très grand ensemble de données

·       gérer facilement un modèle complexe puisque la base de données ne s'appuie pas sur un schéma rigide

·       offrir des performances exceptionnelles en termes de rapidité de temps de réponse pour les lectures locales, par parcours de graphe

Comparaison avec les bases de données relationnelles

Les bases de données relationnelles sont plus adaptées à des requêtes de type "trouver toutes les entités de type X" grâce aux structures internes des tables. Cela est d'autant plus vrai lorsqu'il s'agit de réaliser des opérations d’agrégation sur toutes les lignes d'une table.

En revanche elles sont moins efficaces sur l'exploitation des relations car ceci nécessite une mise en place d'index. Comme cela a été dit plus tôt, les bases de données orientées graphes permettent de parcourir les relations grâce à des pointeurs physiques ce qui n'est pas le cas des clefs étrangères (bases relationnelles) qui offrent uniquement des pointeurs logiques.

Les bases de données graphes sont donc plus adaptées en termes de performance lorsqu'il s'agit de manipuler des volumes de données importants et une profondeur de graphe élevée.

Introduction aux SGBD OG

Fichier:Présentation Base de graphe Neo4J.pdf

Différence SGBDR et SGBD OG

David MEZA (NASA) :

Visualisation de graphe (ie. Cartographie espace informationnel)

Visualisation graphique de Mediawiki

• Wikipedia : https://www.sigmajs.org/demo/index.html
• Wiki du cours : https://viewer.komansamparle.fr/#/koman

ICIJ - Panama Papers

• Consortium de Journalisme ICIJ
• Affaire Panama Papers et utilisation des bases de données orientées graphe
• Panama Papers et visualisation de graphes

• https://www.icij.org/investigations/panama-papers/

Exploration multidimensionnelle de données d'ingénierie

• Une "Pierre de Rosette digitale" pour l’ingénierie d’installations : un portail web, oriente données, de publication CAO multidimensionnelle
  • démo minimaliste : http://efrei.komansamparle.fr/XDBrowser/index.html

Gestion des connaissances et graphe

https://neo4j.com/blog/david-meza-chief-knowledge-architect-nasa/