BT

Les Bases Orientées Graphes, NoSQL et Neo4j

Écrit par Peter Neubauer , traduit par Simon Baslé le 20 mai 2010 |

Introduction

Parmi les différents modèles de données, le modèle relationnel a dominé depuis les années 80, avec des implémentations telles qu'Oracle, MySQL et MSSQL - aussi connus sous le nom de Systèmes de Gestion de Bases de Données Relationnelles (SGBDR). Pourtant, ces derniers temps dans un nombre croissant de cas d'utilisations l'usage de bases de données relationnelles a rencontré des écueils à la fois à cause de problèmes et de manques dans la modélisation des données et à cause de contraintes de montée en charge horizontale, distribuée sur plusieurs serveurs et de gros volumes de données. Il y a deux tendances qui ont exposé ces problèmes à l'attention de la communauté internationale des développeurs:

Les bases de données relationnelles ont de plus en plus de mal à s'accommoder de ces tendances. Cela a conduit à l'apparition d'un certain nombre de technologies qui adressent des aspects spécifiques de ces problèmes, qui peuvent être utilisées avec les SGBDR existants ou en tant qu'alternatives - aussi connues sous le nom de Persistance Polyglotte. Les bases de données alternatives ne sont pas une nouveauté, elles existent depuis longtemps sous la forme, par exemple, des Bases de Données Orientées Objet, Bases de Données Hiérarchiques (e.g. LDAP) et bien d'autres. Mais durant ces quelques dernières années, un grand nombre de nouveaux projets ont été lancés qui sont rassemblés sous le nom de Bases de Données NOSQL.

Cet article a pour but de donner une vue d'ensemble de comment les bases de données orientées graphes se positionnent dans le mouvement NOSQL. La seconde partie de l'article est une introduction à Neo4j, une base de données graphes en Java.

L'environnement NOSQL

NOSQL (Not Only SQL) est en réalité une catégorie très vaste regroupant des solutions de persistance qui ne suivent pas la modélisation relationnelle, et qui n'utilisent pas SQL comme langage de requêtage.

En bref, les bases de données NOSQL peuvent être catégorisées selon leur modèle de données dans les 4 catégories suivantes:

  1. Dépôts Clés-Valeurs (Key-Value Stores)
  2. clones BigTable
  3. BDD orientées Documents (Document-stores)
  4. BDD Orientées Graphes

Pour les systèmes Clés/Valeurs comme Voldemort ou Tokyo Cabinet, l'unité de modélisation la plus fine est la paire clé-valeur. Avec les clones BigTable, ce sont des tuples avec un nombre variable d'attributs, et avec les BDD orientées Documents comme CouchDB et MongoDB c'est le document. Les BDD orientées Graphes modélisent l'ensemble du dataset comme une grosse structure, un réseau unique et dense.

Nous allons ici examiner plus en profondeur deux aspects intéressants des bases NOSQL - la montée en charge et la complexité.

1. Montée en Charge

CAP: ACID vs. BASE

Afin de garantir l'intégrité des données, la plupart des systèmes de base de données classiques reposent sur les transactions. Cela permet de s'assurer de la cohérence des données dans toutes les situations où on doit en gérer. Ces caractéristiques transactionnelles sont aussi connues sous l'acronyme ACID (Atomicité, Cohérence, Isolation, Durabilité). Néanmoins, la montée en charge horizontale sur des systèmes ACID s'est prouvé être un exercice problématique. Il existe des conflits entre les différents aspects de la haute disponibilité dans les systèmes distribués qui ne sont pas complètement contournables - ceci est connu sous le nom du théorème CAP (cf en anglais ici):

  • Forte Cohérence : tous les clients voient la même version de la donnée, même pendant les mises à jour du jeu de données - p. ex. grâce au protocole de commit en deux phases (two-phase commit, transactions distribuées XA) et à l'ACIDité
  • Haute Disponibilité : tous les clients peuvent toujours trouver au moins une copie de la donnée, même si certaines machines du cluster sont injoignables
  • Résistance au Morcellement (ou Partition Tolerance en anglais) : le système dans sa globalité garde ses caractéristiques même s'il est déployé sur différents serveurs, de manière transparente pour l'utilisateur.

Le théorème CAP postule que seuls deux des trois aspects de la montée en charge peuvent être pleinement accomplis en même temps.

Afin de pouvoir travailler avec de grands systèmes distribués, les différentes contraintes CAP ont été examinées de plus près.

Beaucoup des bases NOSQL ont plus que tout lâché du lest sur les contraintes de Cohérence afin d'obtenir une meilleure Disponibilité et un meilleur Partitionnement. Cela a conduit à des systèmes dits BASE (Basically Available, Soft-state, Eventually consistent, soit essentiellement disponibles, à état 'léger', au final cohérent). Ceux-ci n'ont pas de transactions au sens classique du terme et introduisent des contraintes dans le modèle de données pour permettre de meilleures stratégies de partitionnement (comme le système Dynamo, etc...). Une discussion plus en profondeur de CAP, l'ACID et la BASE est disponible dans cette introduction en anglais.

2. Complexité

Protein Homology Network, par Alex Adai, Institut de Biologie Cellulaire et Moléculaire - Université du Texas

L'inter-connectivité croissante des données comme des systèmes a conduit à des jeux de données beaucoup plus denses qui ne peuvent être répartis automatiquement d'une manière évidente, simple ou indépendante du domaine, comme le note Todd Hoff. On pourra se référer à Visual Complexity pour plus de détails sur la visualisation de jeux de données gros et complexes.

Le modèle relationnel

Avant de déclarer le modèle de données relationnel dépassé, nous ne devrions pas oublier que l'une des raisons du succès des systèmes de base de données relationnelle est la capacité de ce modèle tel qu'imaginé par E.F. Codd à modéliser en principe n'importe quelle structure de données sans redondance ni perte d'information, au travers de la Forme Normale. Après la phase de modélisation, la donnée peut être insérée, modifiée et interrogée de manière complexe et puissante via le SQL. Il y a même des SGBDR qui implémentent des schémas optimisés par exemple pour la rapidité d'insertion ou les requêtes multidimensionnelles (p. ex. schémas en étoile) pour différents cas d'utilisation comme l'OLTP (traitement transactionnel en ligne), l'OLAP (traitement analytique en ligne), les applications web ou le reporting.

Ceci est la théorie. En pratique néanmoins, les SGBDR atteignent les limites du problème CAP mentionné plus haut, et ont des problèmes liés à l'implémentation en ce qui concerne la performance d'exécution de requêtes SQL "profondes" qui s'étendent sur beaucoup de jointures de tables. Parmi d'autres problèmes, on peut citer la montée en charge, l'évolution des schémas au cours du temps, la modélisation de structures arborescentes, de données semi-structurées, de hiérarchies et réseaux, etc.

De plus, le modèle relationnel est mal aligné avec les approches contemporaines du développement logiciel telles que l'orienté objet ou les langages dynamiques, ce qui est connu comme la "difficulté d'inadaptation d'impédance objet-relationnelle" (object-relational impedance mismatch). À ce niveau, des couches ORM comme Hibernate pour Java ont été développées et appliquées, avec des résultats mitigés. Elles permettent sans équivoque de faciliter la tâche de mise en correspondance du modèle objet avec le modèle relationnel de données, mais ne délivrent pas des performances optimales en termes de requêtes. En particulier, les données semi-structurées sont souvent modélisées comme de grosses tables avec beaucoup de colonnes qui sont vides pour la plupart des lignes (sparse tables, que l'on pourrait traduire par "tables clairsemées"), ce qui conduit à des performances pauvres. Même l'alternative de modéliser ces structures en une multitude de tables jointes pose problème, puisque les jointures sont des opérations très coûteuses en performance dans les SGBDR.

Le Graphe comme alternative à la normalisation relationnelle

Quand on s'intéresse à la projection du modèle métier sur une structure de données, il existe deux écoles dominantes - la voie relationnelle telle qu'utilisée par les SGBDR et les graphes - et les structures en réseaux, utilisées par exemple pour le Web Sémantique.

Alors que les structures en graphes sont en théorie normalisables même dans un SGBDR, cela a de sérieuses implications en termes de performance pour des structures récursives comme par exemple des arborescences de fichiers ou encore des graphes sociaux, et ceci à cause des caractéristiques d'implémentation des bases relationnelles. Chaque opération sur une relation dans un réseau résulte en une opération de jointure dans le SGBDR, implémentée comme une opération ensembliste entre l'ensemble des clés primaires de deux tables - une opération lente et sans capacité à monter en charge alors que le nombre de t-uples de ces tables augmente.

Terminologie de base pour les graphes marqués-attribués : Nœud, Relation, Propriété

Il n'existe pas de consensus général sur la terminologie en ce qui concerne le domaine des graphes. Il existe beaucoup de modèles de graphes différents. Cependant, un certain effort est fait pour créer le Modèle de Graphe Attribué (Property Graph Model), unifiant la plupart des différentes implémentations de graphes. Selon celui-ci, l'information dans un graphe attribué est modélisée grâce à trois blocs de base:

  • le nœud ou sommet (node, vertex)
  • la relation ou arête (relationship, edge), avec une orientation et un type (orienté et marqué)
  • la propriété ou attribut (property, attribute), portée par un nœud ou une relation

Plus spécifiquement, le modèle est un multigraphe attribué, marqué et orienté. Un graphe marqué a une étiquette pour chaque arête qui est utilisée comme type pour celle-ci. Un graphe orienté autorise des arêtes avec une direction fixée, depuis le nœud source/queue vers le nœud destination/tête. Un graphe attribué autorise une liste variable d'attributs pour chaque nœud et arête, dans laquelle un attribut est une valeur associée à un nom, simplifiant la structure du graphe. Un multigraphe autorise plusieurs arêtes entre deux nœuds. Cela signifie que deux nœuds peuvent être connectés plusieurs fois par différentes arêtes, même si deux arêtes ont la même queue, tête et étiquette.

Le schéma suivant montre un petit graphe marqué-attribué:

Un petit graphe des personnes autour de TinkerPop

La théorie des graphes a eu une grande utilité et une grande pertinence dans de nombreux problèmes de domaines variés. Les algorithmes de théorie des graphes les plus utilisés incluent différents types de calculs du plus court chemin, les chemins géodésiques, les mesures de centralité telles que PageRank, la centralité des vecteurs propres, la "proximité" (closeness), l'interpositionnement (betweeness), les HITS, et bien d'autres. Cependant l'application de ces algorithmes a été dans bien des cas confinée à la recherche, puisqu'en pratique il n'existait pas d'implémentation haute-performance de base orientée graphes prête pour la production. Heureusement, ces dernières années ça a changé. Il existe un certain nombre de nouveaux projets ayant été développés avec une vision "production 24h/24 7j/7":

Le diagramme suivant montre le positionnement des principales catégories NOSQL dans le contexte des aspects de Complexité et de Montée en Charge.

Pour plus de détails sur le débat "s'adapter à la Taille vs. s'adapter à la Complexité", voir l'article par Emil Eifrem (en anglais).

Neo4j - La Base de Données Orientée Graphes en Java

Neo4j est une base orientée graphes, complètement compatible avec les transactions ACID, écrite en Java. Les données sont stockées sur disque sous la forme d'une structure de données optimisée pour les réseaux de graphes. Le Noyau Neo4j est un moteur de graphes extrêmement performant, avec toutes les caractéristiques attendues d'une base de données de production telles que la récupération, les transactions par commit en 2 phases, la compatibilité XA, etc. Neo4j est utilisé en production 24h/24 7j/7 depuis 2003. Le projet vient tout juste de passer en version 1.0 - une étape majeure en ce qui concerne la stabilité et la mise à l'épreuve par la communauté. La haute disponibilité via la sauvegarde en ligne et la réplication maître-esclave sont en bêta et les prochains sur la roadmap de livraison. Neo4j peut être utilisé à la fois comme base embarquée sans aucun travail supplémentaire d'administration et comme un serveur à part entière, avec une interface REST pour une intégration facilitée dans les environnements basés sur PHP, .NET ou JavaScript. Cet article va cependant se concentrer sur l'utilisation directe de Neo4j.

Le développeur travaille directement sur le modèle de graphe via une API Java qui expose cette structure de donnée flexible. Il existe de bons connecteurs produits par la communauté pour d'autres langages tels que JRuby/Ruby, Scala, Python, Clojure et autres. Les caractéristiques typiques de la donnée pour Neo4j sont:

Même les applications "traditionnelles" SGBDR tendent à contenir un certain nombre de jeux de données plus difficiles qui seraient mieux traités avec des graphes, comme les arborescences de fichiers, les configurations de produits, les catégories de produits, les métadonnées média, le trading sémantique et la détection de fraudes dans le monde financier, etc...

Neo4j a des composants optionnels qui viennent en complément du noyau. On peut ainsi structurer le graphe via un méta-modèle, obtenir une implémentation de RDF TripleStore compatible SAIL et SparQL ou encore des implémentations d'un bon nombre d'algorithmes de graphe communs, entre autres.

Au cas où vous voudriez exécuter Neo4j comme serveur séparé, le wrapper REST est disponible. Cela convient à des architectures ayant été construites avec la "suite" LAMP. REST simplifie même la montée en charge sur des lectures plus importantes via memcached, les etag et les couches web et cache d'Apache.

Haute Performance ?

Il est difficile de donner des nombres définitifs dans les benchmarks de performance, puisqu'ils dépendent beaucoup du matériel sous-jacent, du jeu de données et d'autres facteurs. Côté taille, Neo4j gère tel quel des graphes de plusieurs milliards de nœuds, relations et propriétés. Il est normal d'atteindre des performances en lecture de 2000 parcours de relations par milliseconde (environ 1-2 millions d'étapes de parcours par seconde) de manière complètement transactionnelle, avec des caches "chauds" (c.-à-d. les données utiles ont tendance à bien être en cache), par thread. En ce qui concerne les calculs du plus court chemin, Neo4j est même 1000 fois plus rapide que MySQL sur des petits graphes de quelques milliers de noeuds, la différence se faisant plus significative au fur et à mesure que le graphe augmente en taille.

La raison derrière cela est que dans Neo4j les parcours de graphes sont exécutés en temps constant, indépendamment de la taille du graphe. Il n'y a pas d'opérations ensemblistes qui diminuent la performance comme on le voit avec les opérations de jointure dans les SGBDR. Neo4j traverse le graphe de manière "paresseuse" (lazy) - les noeuds et relations sont visités et retournés que quand l'itérateur résultat les appelle, augmentant la performance des parcours les plus importantes et profondes.

La vitesse d'écriture est très dépendante des performances en recherche du système de fichier et du matériel utilisé. Les disques SSD et le système Ext3 sont une bonne combinaison et donnent lieu à des vitesses d'écriture transactionnelles aux environs des 100 000 opérations par seconde.

Exemple - MATRIX

Le Graphe

Comme mentionné précédemment, les Réseaux Sociaux représentent juste une minuscule fraction du domaine d'application des bases orientées graphes, mais ils sont faciles à comprendre pour l'exemple. Afin de démontrer les fonctionnalités basiques de Neo4j, vous trouverez ci-dessous un petit graphe du film Matrix, visualisé dans l'application Eclipse RCP Neoclipse pour Neo4j :

Le graphe est connecté à un nœud connu de référence (id=0) pour un aspect pratique de manière à trouver son chemin dans le réseau depuis un point d'entrée connu. Cela n'est pas nécessaire, mais s'est révélé très utile en pratique.

L'implémentation Java ressemble à cela :

Créer une nouvelle base graphe dans le répertoire "target/neo"

EmbeddedGraphDatabase graphdb = new EmbeddedGraphDatabase("target/neo");

Les types de relations peuvent être créés à la volée:

RelationshipType KNOWS = DynamicRelationshipType.withName("KNOWS");

ou via un Enum Java fortement typé:

enum Relationships implements RelationshipType { KNOWS, INLOVE, HAS_CODED, MATRIX }

Maintenant, créons deux nœuds et attachons une propriété "name" à chacun d'entre eux. Ensuite, connectons ces nœuds avec une relation "connais" (KNOWS) :

Node neo = graphdb.createNode();
neo.setProperty("name", "Neo");
Node morpheus = graphdb.createNode();
morpheus.setProperty("name", "Morpheus");
neo.createRelationshipTo(morpheus, KNOWS);

Toute opération modifiant le graphe ou nécessitant des degrés d'isolation pour les données est encapsulée dans une transaction, et ainsi la récupération et le rollback sont prêts à l’emploi:

Transaction tx = graphdb.beginTx();
try {
    Node neo = graphdb.createNode();
    ...
    tx.success();
} catch (Exception e) {
    tx.failure();
} finally {
    tx.finish();
}

Le code complet nécessaire pour créer le graphe Matrix ressemble à quelque chose comme çà:

graphdb = new EmbeddedGraphDatabase("target/neo4j");
index = new LuceneIndexService(graphdb);
Transaction tx = graphdb.beginTx();
try {
    Node root = graphdb.getReferenceNode();
    // we connect Neo with the root node, to gain an entry point to the graph
    // not neccessary but practical.
    neo = createAndConnectNode("Neo", root, MATRIX);
    Node morpheus = createAndConnectNode("Morpheus", neo, KNOWS);
    Node cypher = createAndConnectNode("Cypher", morpheus, KNOWS);
    Node trinity = createAndConnectNode("Trinity", morpheus, KNOWS);
    Node agentSmith = createAndConnectNode("Agent Smith", cypher, KNOWS);
    architect = createAndConnectNode("The Architect", agentSmith, HAS_CODED);
    // Trinity loves Neo. But he doesn't know.
    trinity.createRelationshipTo(neo, LOVES);
    tx.success();
} catch (Exception e) {
    tx.failure();
} finally {
    tx.finish();
}

Avec la fonction interne...

private Node createAndConnectNode(String name, Node otherNode,
    RelationshipType relationshipType) {
    Node node = graphdb.createNode();
    node.setProperty("name", name);
    node.createRelationshipTo(otherNode, relationshipType);
    index.index(node, "name", name);
    return node;
}

...pour créer les noeuds et relations.

Qui sont les amis de Néo?

L'API Neo4j a un certain nombre de méthodes orientées Collections Java pour répondre à des requêtes simples. Ici, un regard aux relations du noeud "Néo" est suffisant pour trouver ses amis:

for (Relationship rel : neo.getRelationships(KNOWS)) {
    Node friend = rel.getOtherNode(neo);
    System.out.println(friend.getProperty("name"));
}

retourne "Morpheus" comme seul ami.

Le vrai pouvoir de Neo4j provient cependant de l'utilisation de l'API de Parcours, qui procure des filtres et descriptions de parcours bien plus complexes. Elle consiste en un Traverser, qui évalue un StopEvaluator pour la condition d'arrêt et un ReturnableEvaluator pour l'inclusion d'un nœud au résultat. De plus, les types et directions des relations à parcourir peuvent être spécifiés. Le Traverser implémente l'Iterator Java classique, chargeant les nœuds et se déplaçant dans le graphe de manière paresseuse quand ils sont requis, par exemple dans une boucle for. Quelques Evaluators communs sont fournis:

Traverser friends = neo.traverse(Order.BREADTH_FIRST,
StopEvaluator.DEPTH_ONE,
ReturnableEvaluator.ALL_BUT_START_NODE, KNOWS, Direction.BOTH);
for (Node friend : friends) {
    System.out.println(friend.getProperty("name"));
}

Nous voulons commencer par visiter tous les nœuds du même niveau que le nœud de départ avant de continuer dans les niveaux plus distants (parcours en largeur, Order.BREADTH_FIRST), stopper après une profondeur de parcours (StopEvaluator.DEPTH_ONE), et retourner tous les nœuds excepté le nœud de départ "Néo" (ReturnableEvaluator.ALL_BUT_START_NODE). Nous ne traversons que les relations de type KNOWS, dans les deux sens (Direction.BOTH). Ce Traverser ne retourne lui aussi que Morpheus, le seul ami direct de Néo.

Amis d'un ami?

De manière à trouver qui sont les amis des amis de Néo, la relation KNOWS doit être suivie sur une profondeur de 2 étapes, en partant de Néo, retournant Trinity et Cypher. De manière programmatique, cela peut être réalisé en ajustant le StopEvaluator de notre Traverser afin de limiter la profondeur de parcours à 2:

StopEvaluator twoSteps = new StopEvaluator() {
    @Override
    public boolean isStopNode(TraversalPosition position) {
        return position.depth() == 2;
    }
};

De plus, le ReturnableEvaluator personnalisé ne retourne que les nœuds trouvés à la profondeur 2:

ReturnableEvaluator nodesAtDepthTwo = new ReturnableEvaluator() {
    @Override
    public boolean isReturnableNode(TraversalPosition position) {
        return position.depth() == 2;
    }
};

Le Traverser ami-d'un-ami deviens donc:

Traverser friendsOfFriends = neo.traverse(Order.BREADTH_FIRST,
    twoSteps, nodesAtDepthTwo, KNOWS, Direction.BOTH);
for (Node friend : friendsOfFriends) {
    System.out.println(friend.getProperty("name"));
}

Celui-ci retourne Cypher et Trinity comme résultat.

Qui est amoureux?

Une autre question intéressante pourrait être de savoir s'il y a quelqu'un d'amoureux dans ce graphe, en commençant par exemple par l'Architecte.

Cette fois le graphe entier devrait être examiné le long de toute relation partant de l'Architecte (en supposant que son ID de nœud soit connu, mais gardons cela pour plus tard) et les nœuds retournés devraient avoir une relation LOVE sortante. Un ReturnableEvaluator permettra de faire cela:

ReturnableEvaluator findLove = new ReturnableEvaluator() {
@Override
    public boolean isReturnableNode(TraversalPosition position) {
        return position.currentNode().hasRelationship(LOVES, Direction.OUTGOING);
    }
};

Tous les types de relations dans le graphe entier sont nécessaires afin de pouvoir effectuer son parcours au travers de toutes les relations:

List<Object> types = new ArrayList<Object>();
// we have to consider all relationship types of the whole graph
// (in both directions)
for(RelationshipType type : graphdb.getRelationshipTypes()) {
    types.add(type);
    types.add(Direction.BOTH);
}
//let's go!
Traverser inLove = architect.traverse(Order.BREADTH_FIRST,
StopEvaluator.END_OF_GRAPH, findLove, types.toArray());
for (Node lover : inLove) {
    System.out.println(lover.getProperty("name"));
}

Cela retourne seulement Trinity, puisque nous ne retournons que les nœuds ayant une relation LOVE sortante.

Indexer le Graphe

Bien que les opérations de traversée des relations soient l'un des points forts de Neo4j, on a souvent besoin de fonctionnalités orientées théorie des ensembles sur le graphe entier. La recherche Fulltext des propriétés de tout le graphe est un exemple typique. Ici Neo4j utilise des systèmes d'index externes de manière à ne pas réinventer la roue. Pour les cas communs de recherches textuelles, Neo4j s'intègre facilement avec Lucene et Solr, ajoutant la possibilité d'indexer des propriétés de noeuds arbitraires avec des sémantiques transactionnelles dans Lucene/Solr.

Dans l'exemple Matrix, par exemple la propriété "name" pourrait être indexée avec

GraphDatabaseService graphDb = // a GraphDatabaseService instance

IndexService index = new LuceneIndexService( graphDb );

//create a new node and index the "name" property
Node neo = graphDb.createNode();
neo.setProperty( "name", "Neo" );
index.index( neo, "name", neo.getProperty( "name" ) );

//search for the first node with "name=Neo"
Node node = index.getSingleNode( "name", "Neo" );

Lucene est un exemple d'index externe du graphe. Cependant, avec un moteur de graphe rapide il y a un vaste nombre de stratégies pour construire des structures d'indexation dans le graphe lui-même, réduisant les schémas de parcours pour des jeux de données et domaines spécifiques. Par exemple, il existe les timeline et les B-Arbres pour les données à 1 dimension, les RTrees et QuadTrees pour indexer les données à 2 dimensions (très communes dans les communautés GIS et modélisation Spatiale) et bien d'autres. Souvent un autre schéma utile est de connecter des sous-graphes importants directement au nœud racine de manière à avoir des raccourcis sur les nœuds de départ importants.

Java c'est nul. Rien de plus court svp?

Neo4j possède de bonnes librairies pour différents langages, ce qui simplifie encore plus le travail avec la structure de graphe. Cet exemple utilise l'excellent Neo4j-JRuby, qui diminue considérablement la quantité de code:

Après avoir installé la gem neo4j par un

gem install neo4j

Le code JRuby pour l'ensemble du graphe Matrix et les requêtes précédemment mentionnées ressemble à:

require "rubygems"

require "neo4j"

class Person
  include Neo4j::NodeMixin

  #the properties on the nodes
  property :name

  #the relationship types
  has_n :friends

  # Lucene index for some properties
  index :name
end

#the players

neo   = Person.new :name => 'Neo'
morpheus  = Person.new :name => 'Morpheus'
trinity   = Person.new :name => 'Trinity'
cypher= Person.new :name => 'Cypher'
smith = Person.new :name => 'Agent Smith'
architect = Person.new :name => 'Architect'

#the connections

cypher.friends << morpheus
cypher.friends << smith
neo.friends << morpheus
morpheus.friends << trinity
trinity.rels.outgoing(:loves) << neo

architect.rels.outgoing(:has_coded) << smith

#Neos friends

neo.friends.each { |n| puts n }

#Neos friends-of-friends

neo.friends.depth(2).each { |n| puts n }

#Who is in love?
architect.traverse.both(:friends, :has_coded, :loves).depth(:all).filter do
  outgoing(:loves).to_a.size > 0
end.each do |n|
 puts 'In love: ' + n.name
end

Un langage de programmation graphe - Gremlin

Jusqu'à récemment, il n'existait pas de langage de requêtage qui couvrait le large domaine des graphes et projets associés. Dans le Web Sémantique/RDF, il y a SPARQL, un langage inspiré de SQL qui focus sur la description de graphes exemples utilisés pour identifier des triple sets. Cependant, il y a un grand nombre de graphes qui ne sont pas compatibles RDF et qui ont des approches différentes ou plus pragmatiques de la modélisation de données, comme par exemple l'exemple Matrix de cet article, ou d'autres jeux de données spécifiques à leur domaine. D'autres langages de requêtage sont orientés JSON, comme MQL, le langage de requête de Freebase. Ces langages ne fonctionnent que dans leur modèle de donnée propre et ne fournissent pas ou peu de support des algorithmes de graphes en profondeur ou des méthodes d'analyse heuristiques, ce qui est nécessaire pour les gros graphes d'aujourd'hui.

Pour des requêtes plus complexes et plus intéressantes sur des modèles de graphes variés (incluants RDF), Gremlin - un langage de programmation pour graphes Turing-complet et orienté XPath - est en cours de développement par l'équipe TinkerPop, principalement conduite par Marko A. Rodriguez. Via l'introduction du Modèle de Graphe Attribué, il crée un dénominateur commun pour la plupart des modèles existants. Cependant il autorise aussi la connexion d'autres frameworks de graphes (p. ex. Gremlin avec JUNG) et l'expression de parcours de graphes dans des implémentations différentes. Il existe déjà quelques implémentations de supportées, du simple graphe en mémoire TinkerGraph, en passant par un adaptateur RDF-SAIL pour AllegroGraph, Sesame et le LinkedData SAIL de ThinkerPop (originellement développé par Josh Shinavier pour le langage Ripple), jusqu'à Neo4j.

La syntaxe Gremlin est basée sur XPath de manière à être capable d'exprimer des descriptions de parcours même profonds avec des expressions simples. Beaucoup de cas faciles ressemblent presque à du XPath classique.

Après avoir installé Gremlin ou l'avoir essayé en ligne, une session Gremlin sur le graphe exemple Matrix pourrait ressembler à ceci:

peterneubauer$ ~/code/gremlin/gremlin.sh

         \,,,/
         (o o)
-----oOOo-(_)-oOOo-----
gremlin> #open a new neo4j graph as the default graph ($_g)
gremlin> $_g := neo4j:open('tmp/matrix')
==>neo4jgraph[tmp/matrix]
gremlin> #the vertices
gremlin> $neo := g:add-v(g:map('name','Neo'))
==>v[1]
gremlin> $morpheus := g:add-v(g:map('name','Morpheus'))
==>v[2]
gremlin> $trinity := g:add-v(g:map('name','Trinity'))
==>v[3]
gremlin> $cypher := g:add-v(g:map('name','Cypher'))
==>v[4]
gremlin> $smith := g:add-v(g:map('name','Agent Smith'))
==>v[5]
gremlin> $architect := g:add-v(g:map('name','The Architect'))
==>v[6]
gremlin> #the edges
gremlin> g:list($cypher,$neo,$trinity)[g:add-e($morpheus,'KNOWS',.)]
==>v[4]
==>v[1]
==>v[3]
gremlin> g:add-e($cypher,'KNOWS',$smith)
==>e[3][4-KNOWS->5]
gremlin> g:add-e($trinity,'LOVES',$neo)
==>e[4][3-LOVES->1]
gremlin> g:add-e($architect,'HAS_CODED',$smith)
==>e[5][6-HAS_CODED->5]
gremlin> #go to Neo as the current root ($_) via a full-text index search
gremlin> $_ := g:key('name','Neo')
==>v[1]
gremlin> #is this Neo?
gremlin> ./@name
==>Neo
gremlin> #what links to here and from here?
gremlin> ./bothE
==>e[0][1-KNOWS->2]
==>e[4][3-LOVES->1]
gremlin> #only take the KNOWS-edges
gremlin> ./bothE[@label='KNOWS']
==>e[0][1-KNOWS->2]
gremlin> #Neo's friend's names
gremlin> ./bothE[@label='KNOWS']/inV/@name
==>Morpheus
gremlin>
gremlin> #Neo's Friends of friends, 2 steps
gremlin> repeat 2
             $_ := ./outE[@label='KNOWS']/inV
         end
==>v[4]
==>v[3]
gremlin> #What are their names?
gremlin> ./@name
==>Cypher
==>Trinity
gremlin> #every node in the whole graph with an outgoing LOVES edge
gremlin> $_g/V/outE[@label='LOVES']/../@name
==>Trinity

Les algorithmes de parcours de graphe en profondeur - La Valeur des Relations

L'exemple Matrix est un usage vraiment trivial si on considère la puissance de Gremlin. Ce qui est plus intéressant, c'est de développer et tester des algorithmes sur de gros graphes. Les algorithmes exhaustifs tels que la "centralité de vecteur propre" (Eigenvector Centrality) ou Dijkstra ne montent pas bien en charge sur ces graphes car ils nécessitent de toucher à toutes les arêtes du réseau. Les approches heuristiques sont plus appropriées pour ces problèmes, avec des concepts tels que les Parcours Aléatoires Basés sur une Grammaire ou la Spreading Activation (explication plus détaillée, en anglais, par Marko Rodriguez ici). L'algorithme de Google PageRank est l'une de ces heuristiques, et peut être modélisé en Gremlin par le code suivant (un exemple portant sur le graphe des chansons, concerts et albums de Grateful Dead trouvés ici, 2500 boucles et une perte d'énergie de 15% sur chaque répétition):

$_g := tg:open()

g:load('data/graph-example-2.xml')

$m := g:map()

$_ := g:key('type', 'song')[g:rand-nat()]

repeat 2500

  $_ := ./outE[@label='followed_by'][g:rand-nat()]/inV

  if count($_) > 0

g:op-value('+',$m,$_[1]/@name, 1.0)

  end

  if g:rand-real() > 0.85 or count($_) = 0

$_ := g:key('type', 'song')[g:rand-nat()]

  end

end

g:sort($m,'value',true())

Ce qui retourne la liste pondérée des chansons suivantes:

==>DRUMS=44.0
==>PLAYING IN THE BAND=38.0
==>ME AND MY UNCLE=32.0
==>TRUCKING=31.0
==>CUMBERLAND BLUES=29.0
==>PROMISED LAND=29.0
==>THE MUSIC NEVER STOPPED=29.0
==>CASSIDY=26.0
==>DARK STAR=26.0
==>NOT FADE AWAY=26.0
==>CHINA CAT SUNFLOWER=25.0
==>JACK STRAW=25.0
==>TOUCH OF GREY=24.0
==>BEAT IT ON DOWN THE LINE=23.0
==>BERTHA=23.0

Un autre exemple intéressant, dans lequel le graphe sous-jacent est le graphe de LinkedIn en direct d'Internet, est un algorithme de recommandation de musique basé sur LinkedData et DBPedia.

Conclusion

Les graphes ne sont pas la panacée pour tous les problèmes, pas plus que les SGBDRs et autres solutions de persistance des données. L'aspect le plus important est la donnée, son type et le type de requêtes et d'opérations structurantes que l'on devra gérer, et quelles contraintes existent en termes de montée en charge et du théorème CAP.

Ne considérer que l'aspect "haute capacité à monter en charge" des bases NOSQL comme unique argument pour l'utilisation de solutions non relationnelles n'est souvent ni requis ni désirable. Avec Neo4j et le matériel contemporain, on peut dans la plupart des cas modéliser des modèles métiers entiers, avec des milliards d'objets métiers stockés et interrogeables sur une seule instance.

Si cela ne suffit pas, il y a toujours la possibilité d'introduire un partitionnement optimisé pour le domaine sans pour autant imposer les limitations lourdes en termes de modélisation de données des systèmes orientés documents ou clés/valeurs. Que cela résulte en un modèle document, une "base objet" spécifique au domaine ou quelque chose d'autre dépend du contexte et du scénario d'application.

Le code complet de cet article est disponible ici.

Pour leur excellents retours et avis utiles, l'auteur souhaite remercier Michael Hunger et Marko Rodriguez.

A propos de l'auteur original

Peter Neubauer est CEO de Neo Technology. Peter est co-fondateur d'un certain nombre de projets Open Source Java orientés graphes tels que Neo4j, Gremlin, LinkedProcess, OPS4J, Qi4j. Peter peut être contacté à peter@neotechnology.com.

Bonjour étranger!

Vous devez créer un compte InfoQ ou cliquez sur pour déposer des commentaires. Mais il y a bien d'autres avantages à s'enregistrer.

Tirez le meilleur d'InfoQ

Donnez-nous votre avis

Html autorisé: a,b,br,blockquote,i,li,pre,u,ul,p

M'envoyer un email pour toute réponse à l'un de mes messages dans ce sujet
Commentaires de la Communauté

Html autorisé: a,b,br,blockquote,i,li,pre,u,ul,p

M'envoyer un email pour toute réponse à l'un de mes messages dans ce sujet

Html autorisé: a,b,br,blockquote,i,li,pre,u,ul,p

M'envoyer un email pour toute réponse à l'un de mes messages dans ce sujet

Discuter

Contenu Éducatif

Rien ne serait possible sans le soutien et la confiance de nos Sponsors Fondateurs:

AppDynamics   CloudBees   Microsoft   Zenika
Feedback Général
Bugs
Publicité
Éditorial
InfoQ.com et tous les contenus sont copyright © 2006-2013 C4Media Inc. InfoQ.com est hébergé chez Contegix, le meilleur ISP avec lequel nous ayons travaillé.
Politique de confidentialité
BT