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

III.2. OUTILS DES BASES DE DONNEES ORIENTEES-GRAPHE

Comme pour les autres types de bases de données, notamment les bases de données relationnelles, les bases de données orientées-graphe (bien que pas encore normalisé) on distingue les outils de stockage (graph storage) et les outils de traitements (graph processing).

Une comparaison qu'on est amené à faire est celle des bases de données graphes par rapport aux outils de « large-scale graph processing » (traitement de graphe en grande échelle) comme Google's Pregel ou BSP.

Une première différence importante est qu'on a affaire à des outils aux objectifs assez différents, bien qu'ils partagent les mêmes modèles de données. Jim Webber de NeoTechnology donne un point de vue intéressant bien qu'assez partisan :

· Les outils de graph processing, comme leur nom l'indique, adressent uniquement des problématiques de calcul et d'analyse (OLAP), tandis que les graphs storages'adressent essentiellement des problématiques de stockage et de calculs transactionnels (OLTP).

· Les outils de graph processing impliquent, de la même manière que des outils comme Hadoop, une certaine latence dans les calculs (plusieurs secondes), tandis que le graph storage vise des lectures plutôt temps réel (de l'ordre de la ms).

· Les deux n'adressent pas la même échelle de calculs, et n'ont pas non plus les mêmes exigences matérielles: un outil de graph storage adresse essentiellement la problématique du volume par scale-in sur un seul serveur là où un outil comme Pregel l'adresse par scale-out en distribuant les traitements sur plusieurs machines.

· Les outils de graph processing sont entièrement distribués, possibilité que n'offrent pas la plupart des outils de graph storage.

On a donc affaire à deux familles d'outils qui adressent des types et des échelles de problèmes différents : en terme d'usages, on utilisera plus facilement un outil de graph storage pour la navigation dans le graphe ou une recherche de plus court chemin, tandis qu'un outil de graph processing adressera plutôt du  clustering de graphe, de la recherche de  centralité ou encore une recherche globale de tous les chemins (problème de cheminement, d'une manière générale).

Les bases des données orientées-graphe connaissent toutefois une limite liée à leur structure, celle de la taille : il est complexe de partitionner un graphe, particulièrement en tenant compte de la latence réseau, des patterns récurrents de parcours du graphe (quelles relations sont les plus parcourues) et surtout de l'évolution en temps réel du graphe. Certains systèmes de gestion de base de données graphes, OrientDB et InfiniteGraph, s'affichent comme facilement partitionnables, tandis que le SGBD comme de Neo4j n'offre pas encore cette possibilité. Les chercheurs travaillent encore sur ce sujet. Ce qui n'empêche pas que dans un avenir plus ou moins moyen qu'on introduise les notions comme la coloration des graphes (Algorithme de coloration, b-coloration, etc.), la connexité des graphes (Algorithme de Tarjan, Algorithme de Kusaraju).

Par ailleurs, on peut alors résumer (selon Marko Rodriguez) très bien le positionnement des différents outils de traitements de graphes dans ce graphique, en fonction de la taille des données à utiliser par rapport à l'objectif de vitesse des parcours du graphe : plus la taille du graphe à exploiter est grande (et surtout la portion du graphe à parcourir), moins les outils adaptés permettent un traitement en temps réel.

 Figure 3.2 : Classification des outils de traitement de graphes

Source : [Octo]