Modèle graphes

▪ Principes
▪ Neo4j
▪ OrientDB
▪ Graphes et Bases de Données Relationnelles

©Maude Manouvrier - Univ. Paris-Dauphine 510

 Base de données graphes
▪ Graphe : représentation d’un réseau
▪ Graphe : ensemble de nœuds et d’arêtes
▪ Nœud : représentation d’une entité avec des propriétés
▪ Arête : directionnelle avec des propriétés
▪ Exemples de graphes :
• Réseaux sociaux
• Métro

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de de [Link]/rchiky/nosql/[Link] et de [Link] 511

 Base de données graphes : exemples
▪ Nœud ou sommet (node, vertex)
▪ Arête ou relation (relationship, edge), avec une
orientation et un type (orienté et marqué)
▪ Propriété ou attribut (property, attribute), portée par
un nœud ou une relation

©Maude Manouvrier - Univ. Paris Dauphine – Figures reprises de [Link] 512

 Base de données graphes : cas d’utilisation
▪ Cas d’utilisation : Domaine riche en liens entre des entités (cf.
[Link] )

• Applications avec des données connectées

• Applications de routage ou basées sur la localisation
• Moteurs de recommandation
• Business Intelligence
▪ Non applicable aux:
• Applications avec des forts besoins de mises à jour
• Données non interconnectés

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link]/rchiky/nosql/[Link] et de [Link] 513

 Base de données graphes vs relationnel (1/3)

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 514

 Base de données graphes vs relationnel (2/3)

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 515

 Base de données graphes vs relationnel (3/3)
Bases de données graphes : index-free adjacency

Chaque nœud ~ un micro index des nœuds

voisins

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] et du cours de M. Rukoz à Nanterre 516
 Base de données graphes : index-free adjacency

▪ Maintien pour chaque nœud des références directes vers ses nœuds
adjacents

▪ Temps de requêtes généralement indépendantes de la taille totale du graphe

et proportionnel à la taille du graphe recherché

▪ En relationnel : jointures bidirectionnelles précalculées et stockées dans la

base de données

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] et du cours de M. Rukoz à Nanterre/ 517
 Classement des moteurs orientés graphe

©Maude Manouvrier - Univ. Paris-Dauphine - [Link] 51

 Neo4j
▪ Système de gestion de graphes par Neo Technology, Inc
▪ Interrogation de la base avec un langage à travers HTTP : Cypher
Query Language
▪ Développé en Java et Scala
▪ Existe depuis 2000
▪ Peut fonctionner en stand-alone ou en temps que serveur web

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] et [Link] 519

 Neo4j : liens utiles
▪ Site officiel : [Link]
▪ Pour tester en ligne (mais en s’identifiant) : [Link]
▪ Console en ligne : [Link]
▪ Documentation : : [Link]
▪ Exemples d’application :
• [Link]

• Gestion du tour de France : [Link]

2014-in-a-neo4j-graph-database

▪ Tutoriels :
• [Link]
• [Link]
• [Link]
©Maude Manouvrier - Univ. Paris Dauphine
520
 Neo4j : modèle de données
▪ Nœud : unité fondamentale d’un graphe, pouvant être associé à des
labels (~type) et avoir des propriétés
▪ Relation : connexion entre deux nœuds avec une direction, pouvant
avoir des propriétés
▪ Propriété des nœuds et relations : paires clé-valeur avec des valeurs
de type nombre, chaine de caractères, booléen et listes
▪ Traversée d’un graphe : réponse à une requête (navigation de nœud
en nœud exprimée en Cypher)
▪ Chemin : séquence de nœuds avec des relations (utilisé comme
résultat d’une requête)
©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 521
 Neo4j : exemple de graphe

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 522

 Neo4j : Langage Cypher
▪ Deux clauses principales en Cypher pour construire des requêtes
• CREATE pour créer une nouvelle entité
• MATCH pour chercher/récupérer des entités
▪ Représentation graphique des entités :
• Nœud représenté entre parenthèses et deux-points pour label
• Relation représentée avec flèches/tirets et crochets pour détails
• Propriétés représentées par un dictionnaire à la JSON
▪ Manuel Cypher : [Link]
▪ Exemples de commandes : [Link]
the-first-steps-in-the-graph-world-with-the-regesta-of-emperor-frederick-iii
©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 523
 Neo4j : création d’un nœud
Nom de variable non obligatoire

Les nœuds d’un même label n’ont pas

forcement la même structure :

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 524

 Neo4j : création d’une relation

Inutile de créer un arc dans les 2 sens, lors des requêtes

le sens des arcs peut être omis.

Autre manière d’écrire l’instruction :

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 525

 Neo4j : création d’un graphe

©Maude Manouvrier - Univ. Paris Dauphine Adapté de [Link] 526

 Neo4j : CREATE

Attention : rien n’empêche de créer plusieurs fois le « même » nœud.

©Maude Manouvrier - Univ. Paris Dauphine Adapté de [Link] 527

 Neo4j : Créer des nœuds à partir d’un fichier csv
(1/2)

id label
Extrait du contenu du fichier csv dede Dédé
[Link]
tathan Tathan

joinville Joinville

marcel Marcel

lecteur Le Lecteur
©Maude Manouvrier - Univ. Paris Dauphine Adapté de [Link] 528
 Neo4j : Créer un graphe à partir d’un fichier csv (2/2)
LOAD CSV WITH HEADERS FROM "[Link]
france-2014/master/[Link]" AS csvLine
MERGE (r:Race { id: toInt(csvLine.RACE_ID), name: csvLine.RACE_NAME, from:
csvLine.RACE_FROM, to: csvLine.RACE_TO, edition: csvLine.RACE_EDITION, distance:
csvLine.RACE_DISTANCE, number_of_stages: csvLine.RACE_NUMBER_OF_STAGES, website:
csvLine.RACE_WEBSITE })
MERGE (t:Team { id: toInt(csvLine.TEAM_ID), name: csvLine.TEAM_NAME, country:
csvLine.TEAM_COUNTRY, sportingDirectors: csvLine.TEAM_MANAGERS })
MERGE (p:Rider { name: csvLine.RIDER_NAME, country: csvLine.RIDER_COUNTRY })
CREATE (t)-[:TAKES_PART_IN]->(r)<-[:TAKES_PART_IN { number:
toInt(csvLine.RIDER_NUMBER), info: csvLine.RIDER_INFO }]-(p), (p)-[:RIDES_FOR {
year: toInt(csvLine.RACE_YEAR) }]->(t);

Pour voir le contenu du fichier :

[Link]
-de-france-2014/master/tour-de-france-2014-
[Link]

©Maude Manouvrier - Univ. Paris Dauphine Adapté [Link] 529

 Neo4j : recherche de nœuds

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 530

 Neo4j : CREATE et MATCH (1/2)

Attention si vous avez plusieurs nœuds répondant au MATCH

©Maude Manouvrier - Univ. Paris Dauphine 531

 Neo4j : CREATE et MATCH (2/2)

©Maude Manouvrier - Univ. Paris Dauphine 532

 Neo4j : CREATE et MERGE (1/2)
Si on réitère ces instructions on peut
créer plusieurs nœuds « identiques »

MERGE récupère un nœud s’il

existe déjà et le crée sinon

©Maude Manouvrier - Univ. Paris Dauphine Adapté de [Link] 533

 Neo4j : CREATE et MERGE (2/2)

MERGE récupère un nœud s’il existe ( ~MATCH) ou le

crée s’il n’existe pas (~CREATE)

©Maude Manouvrier - Univ. Paris Dauphine Adapté de [Link] 534

 Neo4j : recherche de nœuds / sous-graphes (1/2)

©Maude Manouvrier - Univ. Paris Dauphine – Adapté de [Link] 535

 Neo4j : mise à jour de nœuds / sous-graphes (2/2)

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 536

 Neo4j : requêtes complexes

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 537

 Neo4j : supprimer un nœud sans relation (1/2)

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 538

 Neo4j : supprimer un nœud sans relation (2/2)
Pour supprimer tous les nœuds d’un même label :

Erreur si les nœuds sont liés à d’autres :

©Maude Manouvrier - Univ. Paris Dauphine 539

 Neo4j : supprimer un nœud avec relation

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 540

 Neo4j : comparaison SQL / Cypher

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 541

 Neo4j : exemple d’union en SQL

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 542

 Neo4j : plan d’exécution de l’union en
SQL

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 543

 Neo4j : la même requête Cypher

▪ Recherche par label

▪ Filtrage de recherche de la personne ayant pour prénom
"jak" appliqué directement (filtrage au plus tôt)
▪ Extension avec les nœuds associés par la relation
FRIENDS

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 544

 Neo4j : architecture Maitre-esclave à 2 composants

▪ HA Database: pour
le stockage et la
recherche des
données
▪ Cluster Manager :
pour la tolérance aux
pannes

©Maude Manouvrier - Univ. Paris Dauphine - Repris de ttps://[Link]/book/big_data_and_business_intelligence/9781783555178/7/ch07lvl1sec44/neo4j-architecture-and-advanced-settings 545

 Neo4j : Composition d’un noeud

read-committed isolation level

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 546

 Neo4j : conclusion
▪ Langage Cypher
▪ Gestion de transactions ACID
▪ Bien adapté aux requêtes de type « parcours de graphe »

▪ Perte en performance en raison de l’implémentation sous-jacente

▪ Modélisation pensée pour les graphes
▪ Non adapté aux requêtes de type « opération sur ensembles »

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link]/rchiky/nosql/[Link] et de [Link] 547

 Exemple
d’applications
polyglottes
utilisant
Redis,
MondoDB et
Neo4j

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link]

548
 OrientDB
▪ Base de données multi-modèles : graphes, documents, clé-valeur et
objets
▪ Créé en 2010 par CallidusCloud
▪ Développé en Java
▪ Association des points forts tirés des bases de données graphes et des
bases de données orientée document
▪ Langage de requête « à la SQL »

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] et [Link] 549

 OrientDB : liens utiles

▪ Site officiel : [Link]

▪ Documentation : : [Link]

▪ Tutoriels :
• [Link]
[Link]

• [Link]

©Maude Manouvrier - Univ. Paris Dauphine 550

 OrientDB : modèle de données
▪ Notion de classes pour représenter des enregistrements
▪ Partition des classes en clusters
▪ Relations entre les classes
• LINK pointe vers un objet
• LINKSET pointe vers plusieurs objets (ensemble)
• LINKLIST pointe vers plusieurs objets (liste)
• LINKMAP pointe vers plusieurs objets (dictionnaire)
▪ Possibilité de stocker des graphes avec des classes particulières

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 551

 OrientDB : classe Document et classe Graphe

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] 552

 OrientDB : classe clé-valeur et classe objet

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] 553

 OrientDB : exemple de graphe

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] 554

 OrientDB : création de classe et d’attribut
▪ Création d’une nouvelle classe : CREATE CLASS
▪ Ajout éventuel de propriété : CREATE PROPERTY

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 555

 OrientDB : insertion
▪ Insertion d’un nouvel enregistrement : INSERT INTO

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 556

 OrientDB : rechercher des informations

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 557

 OrientDB : créer un graphe (1/2)

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 558

 OrientDB : créer un graphe (2/2)

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 559

 OrientDB : interrogation en SQL ou parcours de graphe

©Maude Manouvrier - Univ. Paris Dauphine - Adapté de [Link] 560

 OrientDB : architecture (1/2)
Avant 2012 : architecture Maître-Esclave

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] 561

 OrientDB : architecture (2/2)
Depuis 2012 : architecture Multi-Maîtres ("master-less") avec
partitionnement des données en cluster

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] 562

 OrientDB : réplication
Possibilité de réplication :

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] 563

 OrientDB : exécution d’une requête

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] 564

 OrientDB : WriteQuorum

©Maude Manouvrier - Univ. Paris Dauphine – Repris de [Link] 565

 OrientDB : conclusion
▪ Langage de requête et traversée de graphe
▪ Transactions ACID
▪ Architecture multi-master
▪ Multi-Modèles

▪ Monitoring, gestion des sauvegardes sous licence commerciale

▪ Multi-Modèles

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 566

 Graphes et Base de Données Relationnelles
Possibilité de simuler un graphe via des requêtes récursives :

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 567

 Requête SQL récursive

src dest path src dest path

1 2 [1,2] 2 5 [2,3,5]
2 3 [2,3] 2 1 [2,4,1]
2 4 [2,4] 3 1 [3,4,1]
3 4 [3,4] 3 2 [3,4,1,2]
4 1 [4,1] 4 3 [4,1,2,3]
3 5 [3,5] 1 4 [1,2,3,4]
4 2 [4,1,2] 1 5 [1,2,3,5]
1 3 [1,2,3] 2 1 [2,3,4,1]
1 4 [1,2,4] 4 5 [4,1,2,3,5]
2 4 [2,3,4]

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 568

 Clause SQL WITH RECURSIVE
Pour faire des itérations
La requête faisant
WITH RECURSIVE R AS ( référence à R doit
requeteDeBase ! finir par ne
UNION ALL retourner aucun
requeteFaisantReferenceàR nuplet pour
) arrêter la boucle !
SELECT ... FROM R

Exemple : requête, qui

calcule la somme des
nombres de 1 à 100

©Maude Manouvrier - Univ. Paris Dauphine – cf. [Link] 569

 Fonctionnement de la clause WITH RECURSIVE

©Maude Manouvrier - Univ. Paris Dauphine – Figure reprise de [Link] 570

 Simuler un Graphe dans une Base de Données Relationnelles

Exemples :
▪ [Link]
▪ [Link]
7842b8075ca8
▪ [Link]
and-topological-sort-with-postgres/620/
▪ [Link]
▪ [Link]
scale-graph-with-millisecond-response_595039

©Maude Manouvrier - Univ. Paris Dauphine 571

 Plusieurs implémentation et extensions du langage Cypher (1/2)

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 572

 Plusieurs implémentation et extensions du langage Cypher (2/2)

RPQs (Regular
path queries)

LDBC (Linked Data Benchmark Council)

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link] 573
 Extension du standard SQL pour les graphes

(Graph Query
Language)

(SQL Property Graph Querying)

©Maude Manouvrier - Univ. Paris Dauphine - Repris de [Link]

[Link] , [Link] et
[Link] 574
 Property Graph Queries (SQL/PGQ)
▪ Extension du standard SQL aux graphes – SQL:2023 :
[Link]

©Maude Manouvrier - Univ. Paris Dauphine – Exemple repris de [Link] 575

 Property Graph Query Language (PGQL) d’Oracle
▪ Description : [Link]
▪ Projet Open-source d’Oracle : [Link]
▪ Langage de la base de données Graphe d’Oracle, Oracle’s Graph Database :
[Link]
▪ Dernière spécification en août 2022 : [Link]

©Maude Manouvrier - Univ. Paris Dauphine – Images reprises de [Link]

[Link] 576
 Exemple sous PGQL d’Oracle

©Maude Manouvrier - Univ. Paris Dauphine – Images reprises de [Link] 577

 Graph Query Language (GQL)
▪ Page web officielle : [Link]
▪ Page web avec des liens : [Link]
pgq-pointers

©Maude Manouvrier - Univ. Paris Dauphine – Figure reprise de [Link] 578

 Exemples de requêtes en GQL

©Maude Manouvrier - Univ. Paris Dauphine – Figure reprise de [Link] 579

 Principaux moteurs orientés graphes

©Maude Manouvrier - Univ. Paris Dauphine – Repris [Link] 580