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

BASES DE DONNEES

II.3.1. Comparaison avec les bases de données relationnelles

En règle générale, une base de données orientée-graphe permet l'exploitation des structures de type graphe ou dérivé, tels que les arbres, les arborescences, etc., plus particulièrement s'il s'agit d'exploiter les relations entre les données. Pour effectuer une recherche par exemple, il est possible de partir d'un ou plusieurs noeuds et effectuer les opérations de parcours d'un graphe. Il offre ainsi la possibilité d'effectuer des lectures qui permet de trouver toutes les entités d'un type.

Mais, il faut toutefois noter que les bases de données relationnelles sont très adaptées à de requêtes du genre trouver toutes les entités grâce aux structures internes des tables, d'autant plus s'il s'agit de réaliser des opérations d'agrégations sur toutes les lignes d'une table.

Malgré l'adjectif « relationnelle », il faut noter que les bases de données relationnelles sont vraiment moins efficaces pour l'exploitation des « relations», qui dans ce cas doit être par la mise en place des clés étrangères (qui ne sont que des pointeurs logiques). L'avantage est que nous utilisons des pointeurs physiques dans une base de données orientées-graphe pour les parcours de relations qui se représentent par des arêtes dans le cas des bases de données graphe.

A titre illustratif, on se réfère de l'exemple donné par Michel Domenjoud dans un article de blog posté le 18/07/2012 [Octo], dans lequel on modélise des sociétés, les personnes qui y travaillent et depuis combien de temps. On cherche par exemple à trouver les personnes qui travaillent chez Google.

En utilisant une modélisation relationnelle, on pourrait obtenir l'exécution décrite dans la figure 3.3, qui nécessite a priori 3 lookups d'index, optimisés en fonction des indexes et des clés étrangères déclarés.

Figure 3.3. Exemple de la modélisation d'une base de données relationnelle

Source : [Octo]

En utilisant une modélisation dans un graphe, la requête nécessitera un lookup d'index, puis un parcours par pointeurs physiques des relations dans le graphe.

Figure 3.4. Exemple de la modélisation d'une base de données graphe

Source : [Octo]

Il parait très clairement au travers de cet exemple que l'utilisation d'une base de données orientée-graphes est logiquement plus performante que l'utilisation d'une base de données relationnelle.

La différence de performances sera d'autant plus importante lorsque la quantité de données stockées augmente, car hormis le lookup d'index pour trouver le(s) noeud(s) de départ du parcours de graphe, la requête se fera en temps à peu près constant dans un graphe, au contraire de la base de données relationnelle dans laquelle chaque parcours d'index pour récupérer une clé étrangère coûtera O(log₂N) du point de vue algorithmique si l'index est stocké dans un  B-Tree (avec N le nombre d'enregistrements dans la table parcourue).

Une base de données orientées-graphe surpassera naturellement les performances en lecture d'une base de données relationnelle sur son domaine de prédilection, les traversals, et d'autant plus si la profondeur de ceux-ci est importante ou n'est pas déterminée à l'avance (il serait dans ce cas impossible d'optimiser le plan de la requête SQL à l'avance), ce que tendent à montrer les  quelques comparatifs existants sur le Web.