Thèse de Doctorat

Gestion scalable des graphes RDF

Un cadre unifié pour l’exécution parallèle de requêtes
et le partitionnement sémantique personnalisable

Présentée par
Boumediene SAIDI
Sous la direction de
Pr. H. MATALLAH – Pr. L. BELLATRECHE
Co-encadrement : Dr. A. MESMOUDI

Université de Tlemcen • ISAE-ENSMA

Soutenance | 1er décembre 2025

Valorisation des Données du Web

Les données du Web : pilier central de l’économie mondiale

Marché mondial
30.9
➤ GAFAM : 1 500 Mds USD/an 30

Milliards USD
1%
Marché européen 20 +
28

8.1
➤ Digital Europe : 8,1 Mds e 10

➤ EOSC, EuroHPC 0
2024 2030

Marché français
➤ 2024 : 8,1 Mds → 2030 : 30,9 Mds
➤ TCAC : +25%/an

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 2 / 51
Valorisation des Données du Web

Les données du Web : pilier central de l’économie mondiale

Marché mondial
30.9
➤ GAFAM : 1 500 Mds USD/an 30

Milliards USD
1%
Marché européen 20 +
28

8.1
➤ Digital Europe : 8,1 Mds e 10

➤ EOSC, EuroHPC 0
2024 2030

Marché français
⇒ Les données du Web
➤ 2024 : 8,1 Mds → 2030 : 30,9 Mds constituent une res-
➤ TCAC : +25%/an source stratégique

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 2 / 51
Les Graphes de Connaissances
Représentation structurée des connaissances sous forme de graphe

Caractéristiques : Exemple : Google Knowledge Graph

➤ Entités : personnes, lieux, concepts
➤ Relations : liens sémantiques
➤ Propriétés : attributs descriptifs
Avantages :
➤ Interconnexion des données
➤ Raisonnement automatique Marie Curie : entités, relations, propriétés

➤ Requêtes complexes

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 3 / 51
Les Graphes de Connaissances
Représentation structurée des connaissances sous forme de graphe

Caractéristiques : Exemple : Google Knowledge Graph

➤ Entités : personnes, lieux, concepts
➤ Relations : liens sémantiques
➤ Propriétés : attributs descriptifs
Avantages :
➤ Interconnexion des données
➤ Raisonnement automatique Marie Curie : entités, relations, propriétés

➤ Requêtes complexes
⇒ Implémentés avec RDF et interrogés via SPARQL
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 3 / 51
RDF : Modèle de Données

Structure fondamentale Représentation textuelle

➤ Standard W3C depuis 1999 < Sujet > < Predicat > < Objet >
-----------------------------------------------
➤ Triplet : (Sujet, Prédicat, ex : Car25
ex : Car25
ex : has_model ex : Camry
ex : ha s_co nst ruc tor ex : Toyota
Objet) ex : Car25 ex : horsePower "301"

➤ Graphe orienté étiqueté

Représentation graphique
Composants d’un triplet has_model
Car25 Camry
➤ Sujet : IRI ou nœud anonyme
➤ Prédicat : IRI (propriété/relation) has_constructor horsePower

➤ Objet : IRI, littéral ou nœud "301"

anonyme Toyota

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 4 / 51
SPARQL : Langage de Requête
Caractéristiques Exemple de requête BGP
➤ Standard W3C depuis 2008 1
2
SELECT ? car ? constructor WHERE {
? car ex : has_model ex : Camry .

➤ Interroge les graphes RDF 3

4 }
? car ex : has _co nst ruct or ? constructor .

➤ Pattern matching sur triplets

Opérations avancées
Basic Graph Pattern (BGP)
➤ FILTER, OPTIONAL
➤ Ensemble de triplets avec variables
➤ Agrégations (COUNT, AVG...)
➤ Motif de base pour l’interrogation
➤ Sous-requêtes
➤ Construction de requêtes complexes
➤ UNION, jointures

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 5 / 51
SPARQL : Langage de Requête
Caractéristiques Exemple de requête BGP
➤ Standard W3C depuis 2008 1
2
SELECT ? car ? constructor WHERE {
? car ex : has_model ex : Camry .

➤ Interroge les graphes RDF 3

4 }
? car ex : has _co nst ruct or ? constructor .

➤ Pattern matching sur triplets

Opérations avancées
Basic Graph Pattern (BGP)
➤ FILTER, OPTIONAL
➤ Ensemble de triplets avec variables
➤ Agrégations (COUNT, AVG...)
➤ Motif de base pour l’interrogation
➤ Sous-requêtes
➤ Construction de requêtes complexes
➤ UNION, jointures

⇒ Périmètre de la thèse : évaluation de requêtes BGP uniquement

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 5 / 51
Croissance du Linked Open Data (LOD)
Principe :
➤ Données ouvertes publiées
➤ Liens entre datasets 2007

Évolution spectaculaire :

1,500 Wikidata 12B DBpedia 1.8B

Nombre de datasets

LOD Cloud
1,000

500 2025

0
2,007 2,014 2,020 2,025
Temps
Année
DBLP 882M Freebase 2B

er
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1 décembre 2025 6 / 51
Croissance du Linked Open Data (LOD)
Principe :
➤ Données ouvertes publiées
➤ Liens entre datasets 2007

Évolution spectaculaire :
Comment gérer et interroger efficace-
1,500 ment ces volumes massifs de données ? Wikidata 12B DBpedia 1.8B
Nombre de datasets

LOD Cloud
1,000

500 2025

0
2,007 2,014 2,020 2,025
Temps
Année
DBLP 882M Freebase 2B

er
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1 décembre 2025 6 / 51
Paysage des Systèmes de Gestion RDF

Il existe de nombreuses solutions pour gérer les données RDF

Systèmes centralisés : Centralisés (67)

Distribués (72)
➤ RDF-3X, Virtuoso, gStore

Nombre cumulatif
100

➤ Limite de passage à l’échelle

Systèmes distribués : 50

➤ Passage à l’échelle horizontale

➤ > 139 systèmes au total 0

4
00

00

01

01

02

02
2,

2,

2,

2,

2,

2,
(2001-2024) Année
➤ Goulot d’étranglement :
communication réseau
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 7 / 51
Paysage des Systèmes de Gestion RDF

Il existe de nombreuses solutions pour gérer les données RDF

Systèmes centralisés : Centralisés (67)

Distribués (72)
➤ RDF-3X, Virtuoso, gStore

Nombre cumulatif
100

➤ Limite de passage à l’échelle

Systèmes distribués : 50

➤ Passage à l’échelle horizontale

➤ > 139 systèmes au total 0

4
00

00

01

01

02

02
2,

2,

2,

2,

2,

2,
(2001-2024) Année
➤ Goulot d’étranglement :
⇒ Une fracture majeure sépare ces systèmes
communication réseau
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 7 / 51
La Grande Fracture : 20% vs 80%
Analyse de 59 systèmes distribués révèle une fracture majeure

80% : Mémoire modérée Comparaison de performances

➤ Disque
1,000,000
100,000

Temps (ms)
AdPart
10,000
➤ Ex : S2RDF, gStoreD 1,000
100
SHAPE
10
➤ Performances limitées
SHARD
1
0.1

20% : Mémoire très élevée L1 L3 L5 L7

100,000
➤ Tout en RAM

Temps (ms)
10,000 Trinity
1,000 RDF-3X
➤ Ex : AdPart (12 × 150 GB), 100
BitMat
[Link] (12 × 100 GB) 10
1

➤ Plusieurs ordres plus rapide L1 L3 L5 L7

AdPart et Trinity : 10× plus rapides
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 8 / 51
La Barrière des Ressources
Infrastructure nécessaire pour les systèmes haute performance

Systèmes haute performance (20%)

GAFAM
Capacité illimitée
AdPart
RAM 12 × 150 GB = 1,8 TB
Coût 150-180 k€ Grandes
entreprises
[Link] Seuil

RAM 12 × 100 GB = 1,2 TB PME

Coût 120-150 k€ Recherche académique
Budgets limités

Barrière financière : ~120-180 k€

EXCLUS
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 9 / 51
La Barrière des Ressources
Infrastructure nécessaire pour les systèmes haute performance

Systèmes haute performance (20%)

GAFAM
Capacité illimitée
AdPart Comment permettre aux 80% exclus
RAM 12 × 150 GB = 1,8 TB
Coût
d’accéder
150-180 k€
à ces performances ?
Grandes
entreprises
[Link] Seuil

RAM 12 × 100 GB = 1,2 TB PME

Coût 120-150 k€ Recherche académique
Budgets limités

Barrière financière : ~120-180 k€

EXCLUS
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 9 / 51
Notre Objectif de Recherche
OBJECTIF DE LA THÈSE
Proposer une solution qui combine :
Performances élevées
S’approcher des 20% Performances Ressources

✓ Temps de réponse rapides

élevées
(20%)
PQDAG modérées
(80%)

Ressources modérées
Supérieur aux 80%
✓ Infrastructures accessibles Notre
solution
✓ Coûts réduits
Le meilleur
des deux mondes !
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 10 / 51
Contributions Principales

PQDAG

SemPart Évaluation Distribuée

Partitionnement Sémantique Guidé Exploration Logique de Graphe avec le
par un DBA modèle BSP
Catégorie : Agnostique • Fragment logique • CM Catégorie : Entre Synchrone et Asynchrone
Piliers : Piliers :
✓ Fragmentation sémantique + Transformations ✓ Synchronisation sélectif
Physiques + Allocation
✓ Production incrémentale des résultats sans
✓ Langage RDPAL via un DBA jointure finale
✓ Partitionnement Initial + Repartitionnement ✓ Nouvels opérateurs de distribution

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 11 / 51
Plan de la Présentation

✔ Problématique et Contexte
➤ SemPart : Partitionnement Sémantique
➤ PQDAG : Évaluation Distribuée
➤ Validation Expérimentale
➤ Conclusion et Perspectives

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 12 / 51
État de l’Art : Partitionnement

Travail d’analyse : Dispersion des 59 systèmes

➤ Étude systématique de 59 systèmes
Mémoire
➤ Identification de 3 dimensions du Guidé

partitionnement CE
2
Charge
Agnost.
10 0
Les 3 dimensions : 60 1
✓ Dépendance à la charge : 27
CM 0
2
Agnostique vs Guidé
Triplet
3 2
✓ Granularité : Triplet, Nœud,
Nœud
6
Fragment
Fragment
✓ Usage mémoire : CM (modérée) vs Granulari
CE (élevée)
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 13 / 51
État de l’Art : Partitionnement

Travail d’analyse : Dispersion des 59 systèmes

➤ Étude systématique de 59 systèmes
Mémoire
2 charges
➤ Identification de 3 dimensions du × 3 granu-
Guidé

partitionnement Charge 2
larités × 2 mémoires
CE
10 0
Agnost.

Les 3 dimensions : 60 1
=
✓ Dépendance à la charge :
12 classes27 0
2 CM

Agnostique vs Guidé
Chaque classe = une approche de conception
Triplet distincte
3 2
✓ Granularité : Triplet, Nœud,
Nœud
6
Fragment
Fragment
✓ Usage mémoire : CM (modérée) vs Granulari
CE (élevée)
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 13 / 51
Dimension 1 : Dépendance à la Charge

Comment le système exploite-t-il la charge des requêtes ?

Agnostique — 78% (46/59) Guidé par Charge — 22% (13/59)

Principe : Principe :
➤ Partitionnement indépendant ➤ Analyse patterns requêtes
➤ Basé sur structure du graphe ➤ Réplication ou redistribution
Techniques : METIS, MPC, Hachage Approches : Statique, Dynamique
Exemples : TriAD, gStoreD, S2RDF Exemples : AdPart, SHAPE, Wukong

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 14 / 51
Dimension 1 : Dépendance à la Charge

Comment le système exploite-t-il la charge des requêtes ?

Agnostique — 78% (46/59) Guidé par Charge — 22% (13/59)

Principe : Principe :
➤ Partitionnement indépendant ➤ Analyse patterns requêtes
➤ Basé sur structure du graphe ➤ Réplication ou redistribution
Techniques : METIS, MPC, Hachage Approches : Statique, Dynamique
Exemples : TriAD, gStoreD, S2RDF Exemples : AdPart, SHAPE, Wukong

☞ Compromis : Agnostique = Simple mais rigide | Guidé = Adaptatif mais coûteux

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 14 / 51
 Dimension 2 : Granularité du Partitionnement

Quelle est l’unité de distribution ?

Triplet — 71% (42/59) Nœud — 12% (7/59) Fragment — 17% (10/59)

Principe : Principe : Principe :

➤ Chaque <s,p,o> distribué ➤ Sujet/Objet + arcs ➤ Sous-graphes logiques ou
individuellement sortants/entrants physiques
Techniques : Hachage, METIS, Structure : SPO, OPS, Réplication Types : CS, mintermes, RSG
Round-robin Avantages : Avantages :
Avantages : ✓ Requêtes étoile locales ✓ Forte localité
✓ Simple
Inconvénients : Inconvénients :
Inconvénients : ✗ Toujours Problème de ✗ Complexité de construction
✗ Nombreuses jointures Jointures
Ex : SemStore, WARP
Ex : [Link], TriAD Ex : SHAPE, StarMR, EAGRE
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 15 / 51
Dimension 3 : Usage des Ressources Mémoire

Quelles sont les exigences matérielles ?

CM - Capacité Modérée — 80% (47/59) CE - Capacité Élevée — 20% (12/59)

Principe : Principe :
➤ Ressources limitées (Disque) ➤ Tout en mémoire
Caractéristiques : Caractéristiques :
➤ Structures compressées ➤ Prétraitement léger
Exemples : Virtuoso, gStoreD, TriAD Exemples : [Link], AdPart, Wukong

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 16 / 51
Dimension 3 : Usage des Ressources Mémoire

Quelles sont les exigences matérielles ?

CM - Capacité Modérée — 80% (47/59) CE - Capacité Élevée — 20% (12/59)

Principe : Principe :
➤ Ressources limitées (Disque) ➤ Tout en mémoire
Caractéristiques : Caractéristiques :
➤ Structures compressées ➤ Prétraitement léger
Exemples : Virtuoso, gStoreD, TriAD Exemples : [Link], AdPart, Wukong
☞ Compromis : CM = Accessible mais limité en scale | CE = Performant mais coûteux
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 16 / 51
Problématiques : Rigidité & Granularité Inadaptée

78% (46/59) ignorent la charge | 71% (42/59) utilisent granularité triplet

Requête Q1 :

1: SELECT ?car ?model ?version Exécution

2: WHERE {
3: ?car has_model ?model .
4: ?model version ?version .
5: }
Système RDF distribué
[Link] Partition 1

hash Car1 has_model Model3

Car1 has_model Model3 Camry version 2022
Model3 version 2023 transfert
Car25 has_model Camry Triplet
Camry version 2022 Partition 2
Car25 has_model Camry
Model3 version 2023

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 17 / 51
Problématique 3 : Coûts en Ressources Prohibitifs

Systèmes Capacité Élevée (CE) : Comparaison CE vs CM

➤ 20% des systèmes (12/59) 6× plus cher
150
➤ Trinity (1.2 TB), AdPart (1.8 TB),

Coût (k€)
100
Leon (1.2 TB)
50
➤ Configuration pour 4 milliards de
triplets 0
CM GStoreD
Trinity CE
➤ ≈ 150 GB de données RDF (1.2 TB) (10×32GB)

Coûts prohibitifs :
✗ Cluster CE : 100 000-200 000 € Ratio : CE est 4x à 8x plus cher que CM
pour la même capacité (4B triplets)
✗ Exclusion PME, laboratoires, secteur
public
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 18 / 51
Problématique 4 : Absence d’Expertise Humaine

Constat frappant : 0% des systèmes offrent une interface

d’expertise métier

Approches Agnostiques (46%) :

L’administrateur possède :
✗ Zéro personnalisation possible

Approches Guidées (13%) : ➤ Connaissance du domaine

✗ Boîte noire : aucun contrôle ➤ Entités critiques identifiées
➤ Requêtes stratégiques connues
Fragments Logiques (10%) :
⇒ Expertise inutilisée !
✗ Transformations rigides prédéfinies
✗ Pas d’ajustement expert
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 19 / 51
SemPart : Positionnement & Architecture
SemPart se positionne : Agnostique + Fragment Logique +
CM + AVEC expertise humaine guidée

Fragmentation Transformation Repartition-

Physique Allocation
Sémantique nement
METIS • MPC • LP
Characteristic Sets split • filter • neighbors Transformations

Langage RDPAL — Couche d’Orchestration

API déclarative contrôlée par le DBA

Objectifs : Performance • Adaptabilité • Passage à l’échelle

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 20 / 51
Fragmentation Sémantique (1/2)
→
−
Définition : Gs = {t ∈ G | sujet(t) = s} — Les triplets partageant s/o

−−→ −−−→
Graphe RDF complet Étoiles de graphe : Car1 et Car25
−−→
"2023"
Car1 : 5 triplets
version_number (Car1, has_type, Car)
has_name (Car1, horse_power, 283)
"4.69" Model3 FremontCA "Fremont"
ha
s_
(Car1, has_length, 4.69)
len
gt
h has_model located_in (Car1, has_model, Model3)
horse_power has_constructor
(Car1, has_constructor, Tesla)
"283" Car1 Tesla "Toyota City" −−−→
Car25 : 5 triplets
has_name
has_type (Car25, has_type, Car)
has_type
ToyotaCityJP
(Car25, horse_power, 301)
"2022" Car er Car25
ve

p ow l ha
(Car25, has_length, 4.7)
rs

s_
se_ ode
io

co
hor has_length
n_

m ns located_in
tru
_ (Car25, has_model, Camry)
nu

s c
ha tor
m
be

(Car25, has_constructor, Toyota)

r

Camry "4.7"
"301" Toyota

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 21 / 51
Fragmentation Sémantique (2/2)
Characteristic Set (CS) : CS(s) := {p | ∃o : (s, p, o) ∈ G }

Graphe RDF avec fragments Fragments par CS (Sortants)

"2023"

version_number
Voitures - CS1 = {has_model, has_length,
horse_power, has_type}
has_name −−→ −−−→
"4.69"
ha
Model3 FremontCA "Fremont" Étoiles : Car1, Car25
s_
len
gt has_model located_in
h

"283"
horse_power
Car1
has_constructor
Tesla
Constructeurs - CS2 = {has_constructor}
"Toyota City"
−−−→ −−−−→
Étoiles : Tesla, Toyota
has_type has_name

has_type
"2022" Car er Car25 ToyotaCityJP
Modèles - CS3 = {version_number}
ve

p ow l ha
rs

s_
se_ ode
io

r co
h o has_length −−−−→ −−−→
n_

m ns located_in
t r
s_ uc
Étoiles : Model3, Camry
nu

ha tor
m
be
r

Camry "4.7"
"301" Toyota

Villes - CS4 = {has_name}

−−−−−−−→ −−−−−−−−−→
Étoiles : FremontCA, ToyotaCityJP
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 22 / 51
Transformations Physiques (1/2)

1. Sélection/Filtrage 3. Opérations Ensemblistes

• select(Γ) : sélectionne fragments par CS, direction • union : fusionne étoiles de graphe
• intersection : conserve étoiles communes
• neighbors(path) : collecte voisins via chemin
• difference : retire étoiles du 2ème fragment
• filter(Γ) : filtre étoiles selon condition
Nécessitent même CS

2. Découpage (Split)
Exemple : groupby
−−→ −−−→
Soit Gfcars = {Car1, Car25}.
• split(N) : divise en sous-fragments de N étoiles
Regroupement selon has_constructor :
• split(Γ) : split conditionnel (true/false)
( −−→
• groupby(p) : regroupe par valeurs d’un prédicat GfTesla = {Car1}
groupbyhas_constructor (Gfcars ) −→ −−−→
• derivedSplit : propage split aux voisins GfToyota = {Car25}

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 23 / 51
Transformations Physiques (2/2)

Structure du DAG Pipeline de Transformation

Fragments Logiques
◦ Nœuds initiaux : fragments logiques (CS) (Conception)
Niveau
Logique

⇝ Nœuds intermédiaires : fragments virtuels

select
→ Arcs : opérateurs de transformation
Fragments Virtuels 1
■ Nœuds matérialisés : fragments physiques (Transformation 1)
Transfo.
Virtuelles

groupby
Opérateurs de Contrôle
Fragments Virtuels 2
(Transformation 2)
M : persiste fragments virtuels
µ : fusionne dans ensemble existant M

R : retire fragments Fragments Physiques Stockage

Physique
(Matérialisés)

Optimisations
✓ Redondances, Réordonnancement.
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 24 / 51
 Integrated Fragments
Initial Fragments

Physical Fragments
Étape 3 : Allocation des Fragments

1. Objectif Principal
Allouer les fragments physiques sur k machines
2. Modélisation
Question : Comment modéliser le problème d’allocation ?
Réponse : Réduction à un problème de partitionnement de graphe

3. Solutions Existantes
Utiliser les solutions déjà disponibles dans la littérature :
✓ LP (Programmation Linéaire) : solution exacte
✓ METIS : heuristique edge-cut
✓ MPC : heuristique property-based

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 26 / 51
Modélisation : Graphe de Fragments

Définition formelle :
Exemple Visuel
Gf = (V , LV , fV , E , LE , fE , WV , WE ) ☞ Ex : 2 voitures
reliées aux modèles
⇒ WE = 2

➤ Nœuds (V) : Fragments physiques

Gfmodels Gfcities
➤ Poids des nœuds (WV ) : WV = 4 WV = 4

WV (Gfi ) = |Gfi | (nb. de triplets) has_model

WE = 2

➤ Arcs (E) : Connexions via prédicats Gfcars

located_in
WE = 2

WV = 10
E = {(Gfi , Gfj , p) | Gfi ∼p Gfj }

➤ Poids des arcs (WE ) : ☞ Ex : 2 étoiles has_constr

WE = 2
avec 5 triplets cha-
Nombre de connexions objet-sujet via p cune
⇒ WV = 10 Gfconstr
WV = 4

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 27 / 51
Fonction Objectif d’Allocation

Formulation Mathématique

k
WV (Ni ) − k1 WV (V ) +
X X
minimize (α + 1) · WE (Gfu , Gfv , p)
Partition
|i=1 {z } (Gfu ,Gfv ,p)∈E
Gfu ∈Ni , Gfv ∈Nj
Déséquilibre de charge i̸=j
| {z }
Coût de communication

P
où WV (Ni ) = Gf ∈Ni WV (Gf ) et α ∈ [0, 1] (déséquilibre toléré)

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 28 / 51
Stratégies et Opérateurs d’Allocation
Comparaison des stratégies d’allocation :

Critère LP METIS MPC

Type Exacte Heuristique Heuristique

Objectif Optimale Edge-cut Property-cut
Scalabilité Petite Grande Grande
Rapidité × Lent ✓ Rapide ✓ Rapide
Adaptation — Générique Sémantique

Opérateurs d’allocation :
allocateStrategy ({Gf1 , . . . , Gfn }) −→ {Gfi → Nj }
redistribute(Gfi , Nj ) −→ {Gfi → Nj }

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 29 / 51
RDPAL : Exemple Complet de Partitionnement

// 0. Chargement dataset // 4. Decoupage derive #2

Graph graph = new Graph("[Link]") // Propage via has_model
// 1. Extraire fragments split2 = new Derived(
fragments = [Link](FORWARD) GroupBy("has_constructor"),
"has_model"
// 2. Selectionner voitures )
cars = [Link]( splitted2 = [Link](split2)
[Link]([
"has_constructor", // 5. Supprimer doublons
"has_model" newSplit1 = [Link](
]) [Link](["has_constructor"])
) )

// 3. Decoupage derive #1 // 6. Integration

// Propage via has_constructor result = fragments
split1 = new Derived( .integrate(newSplit1)
GroupBy("has_constructor"), .integrate(splitted2)
"has_constructor->located_in", .remove(fragments)
[Link] .materialize()
) // 7. Allocation
splitted1 = [Link](split1) allocate(10, result, "METIS")

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 30 / 51
RDPAL : Re-partitionnement
Contexte : Après l’allocation, le système permet le repartitionnement pour s’adapter à
la charge

Scénario : Capacités :
Redistribuer les constructeurs Tesla et Toyota vers des
machines spécifiques
✓ Réappliquer transformations
✓ Nouvelle allocation
// 1. Obtenir fragments ✓ Redistribution ciblée
fragments = [Link](FORWARD)
// 2. Selectionner constructeurs ✓ Eviter un processus de
// Retourne 2 fragments : Tesla et Toyota
constructors = [Link]( monitoring complexe
[Link](["located_in"])
)
// 3. Redistribuer selectivement
redistribute([Link](0), 1)
Adaptation guidée par le DBA
redistribute([Link](1), 2)

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 31 / 51
État de l’Art : 4ème Dimension – Mode d’Exécution

4ème Dimension – Mode d’Exécution

➤ Constat : Les systèmes distribués adoptent deux paradigmes d’exécu-

tion distincts
➤ Synchrone : Coordination globale avec barrières de synchronisation
➤ Asynchrone : Communication par messages sans attente globale

Objectif : Analyser ces deux ap-

proches pour identifier leurs limites

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 32 / 51
Mode d’Exécution Synchrone
Approche Synchrone
Principe : Schéma illustratif :
➤ Exécution en étapes globales
➤ Chaque étape se termine par une barrière de
Sync Sync Sync
synchronisation
➤ Tous les nœuds doivent terminer avant de Join 1 Join 2 Join 3 Rés.
temps
passer à l’étape suivante

Systèmes représentatifs : Calcul parallèle

Barrière (tous attendent)

➤ SHARD : MapReduce-based
➤ S2RDF : Spark-based, SQL rewriting

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 33 / 51
Limites de l’Approche Synchrone

Barrières Résultats Partitionnement

➤ Tous les nœuds attendent ➤ Production finale uniquement ➤ Souvent Rigide : approches basées
sur Spark
➤ Nœud lent bloque tout ➤ Latence élevée
➤ Pas de contrôle

Résultats
Sync Exécution Spark : Hash automatique
Partitionnement imposé

Non modifiable
N1 Attente Pas de résultats
temps ❖
N2
Attente
N3 Conséquence :
Pas d’optimisation
pour requêtes SPARQL

temps ✗
Impact : Latence utilisateur élevée

Impact : Pas de contrôle sur la localité

Impact : Sous-utilisation des ressources

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 34 / 51
Mode d’Exécution Asynchrone & Limites

Approche Asynchrone
Principe : Problème :
➤ Communication par messages ➤ Pas de tolérance aux pannes
➤ Pas d’attente globale ➤ Si un nœud échoue ⇒ tout recom-
➤ Approches basées sur le modèle MPI mencer

Schéma :
Systèmes représentatifs :
➤ TriAD : basé sur MPI, Jointure temps
Évaluation continue
➤ [Link] : MPC, CE, Explora-
tion
Messages asynchrones

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 35 / 51
PQDAG : Un Mode d’Exécution Hybride
Positionnement par rapport à l’État de l’Art

Barrières Pas de
fréquentes pannes
Zone Hybride

Synchrone Asynchrone
S2RDF
(Spark)
[Link] TriAD
(MPI)
Exploration graphe
MPI asynchrone
➤ BSP + Sync Sélective
Modèle de calcul parallèle avec
synchronisation uniquement si nécessaire

PQDAG
BSP + Synchro sélective
➤ RDF_QDAG : Exploration de graphe (Volcano)
➤ + Nouveaux opérateurs distribués
Exploration graphe + RDF_QDAG ➤ SemPart
SemPart Partitionnement sémantique guidé

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 36 / 51
RDF_QDAG : Étoiles de Requête

Définition : Une étoile de requête est un sous-ensemble de motifs de triplets de Q partageant

−→
un même nœud central v (appelé tête). On distingue : étoile sortante Qs (v ) où v est sujet,
←−
et étoile entrante Qs (v ) où v est objet.

Graphe de la Requête SPARQL 3 Étoiles Sortantes

−
→
Qs (?car )
?length h
as
_
le
ng −
→
th ?length h Qs (?constructor )
as −
→
has_constructor located_in _
le Qs (?city )
ng
?car ?constructor ?city h th
a s_
el

has_constructor located_in
od

na ?car ?constructor ?city h

m

m as
s_

el
_

od
ha

na

m
m

s_
Toyota e

ha
Camry City
Toyota
Camry City

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 37 / 51
RDF_QDAG : Évaluation d’une Étoile de Requête
−
→
Définition : L’évaluation d’une étoile de requête Qs (v ) consiste à identifier toutes les étoiles de graphe dans
les fragments qui correspondent aux motifs de triplets de l’étoile de requête.

−
→ −→
Étoile de Requête Qs (?car ) Gf1
?length h
as
(has_constructor, has_length, has_model, horse_power, has_type)
_
le
ng
th
has_constructor
?car ?constructor S P O
el
od
m

Car1 has_type Car

s_
ha

Camry
Car1 has_model Model3
Car1 has_length "4.69"
Car1 horse_power "283"
Évaluation en 2 Étapes :
Car1 has_constructor Tesla
Étape 1 : Identifier le fragment pertinent
−
→ −→ Car25 has_type Car
→ Vérifier : P(Qs ) ⊆ C (Gf1 )
−→ Car25 has_model Camry
→ {has_model, has_length, has_constructor} ⊆ Gf1 ✓
Étape 2 : Extraire l’étoile de graphe et générer les correspon-
Car25 has_length "4.7"
dances Car25 horse_power "301"
→ Étoile compatible trouvée : Car25 Car25 has_constructor Toyota
→ µ = {?car 7→ Car25, ?length 7→ "4.7", ?constructor 7→
Toyota}

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 38 / 51
RDF_QDAG : Évaluation d’une requête
Exploration de graphe : Les correspondances partielles d’une étoile génèrent les candidats pour l’étoile suivante.

−
→
Qs (?car ) – µ1

−
→
?length h Qs (?constructor ) – µ2
as
_
le −
→
ngt Qs (?city )
h
has_constructor located_in
?car ?constructor ?city h
as
el
od _
na
m

m
s_

e
ha

Toyota
Camry City

−→ −→ −→
Gf1 Gf2 Gf3

−−− → Solution Finale :

Étoile : Car25 Candidat : Toyota
µ = {?car 7→ Car25,
µ1 = {?car 7→ Car25, µ2 = {?constructor 7→ Toyota,
?length 7→ ”4.7”,
?length 7→ ”4.7”, ?city 7→ ToyotaCityJP}
?constructor 7→ Toyota,
?constructor 7→ Toyota} ✓ Compatible
?city 7→ ToyotaCityJP}

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 39 / 51
RDF_QDAG : Opérateurs & Modèle Volcano
Opérateur Fonctionnement
EEG Rôle : Extrait les étoiles de graphe pertinentes depuis les fragments
Extracteur d’Étoiles de 1ère étoile : Mode exploration, interroge le fragment et récupère toutes
Graphe les étoiles ayant les prédicats requis par la requête
Étoiles suivantes : Mode par lot, récupère uniquement les étoiles dont
les têtes correspondent aux candidats générés par l’étoile précédente
→ Tampon MTD : Stocke temporairement les étoiles extraites.
EC Rôle : Génère les correspondances partielles (mappings) pour chaque
Extracteur de Corres- étoile de requête
pondances 1ère étoile : Crée les correspondances initiales directement depuis les
étoiles de graphe extraites par EEG
Étoiles suivantes : Extension incrémentale – pour chaque nouvelle étoile,
fusionne les correspondances précédentes avec les nouvelles si elles sont
compatibles (variables communes)
→ Tampon MTC : Stocke les correspondances partielles.
MD Rôle : Interface avec le dictionnaire distribué pour encoder et décoder les
Mappeur de Dic IRIs et littéraux

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 40 / 51
RDF_QDAG : Exemple d’Évaluation

1. Première étoile ( ?car) :

EEG1 extrait les étoiles avec has_model = Camry
−→
depuis Gf1 EC1 EC2 EC3

Résultat : car25
MTC1 : MTD1 MTc1 MTD2 MTc2 MTD3 Resultats
HE1 = {?car 7→ car25 , ?constructor 7→ Toyota}

2. Deuxième étoile ( ?constructor) : ED1 ED2 ED3

−→
EEG2 extrait l’étoile Toyota depuis Gf2
MTC2 : HE2 = {?constructor 7→ Toyota, ?city 7→
ToyotaCityJP}

3. Troisième étoile ( ?city) :

−→
EEG3 extrait l’étoile ToyotaCityJP depuis Gf3 Résultat final : (car25 , Toyota)
MTC3 : HE3 = {?city 7→ ToyotaCityJP, ?name 7→
"Toyota City"}

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 41 / 51
Intégration du modèle BSP dans PQDAG
Le master génère un plan d’exécution : séquence d’étoiles de requête [Qs1 , Qs2 , . . . , Qsn ]
➤ Pire cas : 1 super-étape par étoile (échange après chaque étoile)
➤ Meilleur cas : 1 seule super-étape (données toutes locales)

Déroulement d’une super-étape : Synchronisation Sélective BSP

1. Calcul local
W1 Calcul local continu
➤ Évaluation de l’étoile courante
➤ Progression jusqu’au besoin de données distantes W2 Calcul Attente Reprise

2. Échange de données W3 Calcul local continu

➤ Synchronisation sélective : seules les machines
nécessitant des données externes participent temps
➤ Les autres continuent localement
3. Barrière partielle Avantage : W1 et W3 continuent pendant que W2 attend les données
➤ Reprise après réception des données
➤ Machines autonomes : pas d’attente

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 42 / 51
Intégration du modèle BSP dans PQDAG
Le master génère un plan d’exécution : séquence d’étoiles de requête [Qs1 , Qs2 , . . . , Qsn ]
➤ Pire cas : 1 super-étape par étoile (échange après chaque étoile)
➤ Meilleur cas : 1 seule super-étape (données toutes locales)

Comment implémenter cette

synchronisation sélective ?
Mécanisme permettant aux workers de continuer leur traitement
tant qu’ils disposent de données locales

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 42 / 51
Nouveaux Opérateurs pour l’Évaluation Distribuée

Transition : RDF_QDAG (centralisé) → PQDAG (distribué)

Opérateurs RDF_QDAG (centralisés) : Nouveaux Opérateurs PQDAG (distribués) :

➤ EEG : Extraction d’étoiles de graphe ✓ OR : Opérateur de Routage

➤ EC : Extraction de correspondances ✓ OGE : Opérateur de Gestion d’Échange
➤ MD : Mappeur de dictionnaire ✓ ER : Opérateur d’Écriture Réseau
Suffisants pour l’évaluation locale Nécessaires pour la distribution

EEG EC OR OGE EEG EC ER Client

Local Distribution Local Résultat

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 43 / 51
Opérateur de Routage (OR)

Rôle : Déterminer la localisation des données nécessaires (locale ou distante)

Fonctionnement : Schéma de décision

he de ECi
1. Identification des candidats
➤ Depuis µ de Qis
➤ Identifier têtes pour Qi+1
s
Fragment
local ?

2. Consultation des fragments Oui Non

➤ Exploiter métadonnées GradeasID MTCi TT

➤ Vérifier direction (sortante/entrante)

Évaluation Transfert
locale réseau
3. Décision de routage
✓ Local → MTC
✗ Distant → TT (Tampon de Transfert)
Impact BSP : Réduit hmax (volume comm.)

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 44 / 51
Tampon de Transfert (TT) – Organisation Hiérarchique
Organisation à 3 niveaux : Structure hiérarchique
Niveau 1 : Worker destinataire TT
➤ Grouper par machine cible
➤ Minimiser nombre de messages
Worker 1 Worker 2
Niveau 2 : Étoile de requête
➤ Grouper par Qi+1
s Q2 Q2
s s
➤ Faciliter traitement en bloc

Niveau 3 : Fragment Gf2 Gf2

➤ Grouper par fragment requis
➤ Traitement parallèle côté récepteur Optimisation : Prédécesseurs partagés
he1

Débordement : Sérialisation sur disque en blocs de taille fixe, prêts

au transfert he2 he3 he4

he1 sérialisé 1 fois, références pour he2 , he3 , he4

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 45 / 51
Opérateur de Gestion d’Échange (OGE)
Rôle : Coordinateur des communications et synchronisation BSP

1. Détection du besoin d’échange Arbre de décision

➤ MTCi−1 vide + Qi−1
s non terminée
➤ MTDi vide + fragments restants Worker pro-
gresse ?

➤ TT saturé O N

➤ Progression bloquée globalement Continuer local

MTC/MTD
vide ?
O
N
2. Orchestration de l’envoi
TT saturé Qi−1 finie ?
➤ Fusion tampons associés
s

O N

➤ Organisation flux par worker Échange

Passer à Qi+1
s Échange

➤ Sérialisation + transmission

3. Orchestration de la réception
➤ Files d’attente par émetteur Impact BSP : Synchronisation sélective → Réduit l (latence bar-

➤ Désérialisation parallèle rière)

➤ Injection adaptative dans MTC

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 46 / 51
Opérateur d’Écriture Réseau (ER)

Rôle : Acheminer les résultats finaux vers le client de manière incrémentale

1. Consommation du tampon résultats Pipeline de transformation

➤ Hyper-arêtes complètes de ECn Hyper-arête finale
hefinal
➤ Correspondances finales µfinal

2. Reconstruction de la correspondance Remontée

prédécesseurs
µcomplet

➤ Remonter chaîne des prédécesseurs

➤ Collecter toutes les liaisons variables Traduction
GradeasID → IRI
Format SPARQL

3. Traduction et formatage
Transmission
➤ GradeasID → IRI/Littéral (via MD) Client

➤ Extraire variables SELECT

4. Transmission incrémentale Avantage : Production incrémentale → Latence réduite pour l’uti-

✓ Streaming vers client
lisateur
✓ Sans jointure finale centralisée
Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 47 / 51
Exemple d’Évaluation Distribuée (1/2)

Cluster (2 machines) :

Requete SPARQL Machine 1

−
→ −−→ − −→
Qs (?car ) ➤ Gf11 : Car1
−
→ −−→ − −−→
?length h Qs (?constructor ) ➤ Gf21 : Tesla
as
_
le −
→ −−→ −−−−−−−−→
ng Qs (?city ) ➤ Gf31 : ToyotaCityJP
th
has_constructor located_in
?car ?constructor ?city h
as
el

_
od

na
m

m
s_

e
ha

Toyota
Machine 2
Camry City −−→ − −−→
➤ Gf12 : Car25
−−→ −−−→
➤ Gf22 : Toyota
−−→ − −−−−− →
➤ Gf32 : FremontCA

Plan : 3 super-étapes BSP pour évaluer les 3 étoiles

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 48 / 51
Exemple d’Évaluation Distribuée (2/2)
−
→
Super-étape 1 : Qs (?car )
M1 : EEG extrait Car1 → EC génère he1
OR : Tesla local → MTC1
EC1 EC2 EC3
M2 : EEG extrait Car25 → EC génère he2
OR
OR : Toyota local → MTC2

MTD1 MTc1 MTD2 MTc2 TT2 MTD3 RT

Machine 1
OGE : TT vides ⇒ Pas de synchronisation

−
→
Super-étape 2 : Qs (?constructor )
ED1 ED2 ED3
M1 : EEG reçoit he1 → extrait Tesla
EC génère he3 (FremontCA)
OR : FremontCA ∈ M2 ⇒ TT
M2 : EEG reçoit he2 → extrait Toyota
EC génère he4 (ToyotaCityJP)
OR : ToyotaCityJP ∈ M1 ⇒ TT
EGFDT OGE

OGE : TT non vides ⇒ Échange M1↔M2 + Sync

EC1 EC2 EC3

OR −
→
Super-étape 3 : Qs (?city )
MTD1 MTc1 MTD2
MTc2 TT2
MTD3 RT
M1 : EEG reçoit he4 → EC génère he5
Machine 2 ER : Reconstruit chaîne → (Car 25, Toyota)
M2 : EEG reçoit he3 → EC génère he6
ED1 ED2 ED3 ER : Reconstruit chaîne → (Car 1, Tesla)

Résultat : 3 super-étapes, 1 sync, ER streaming incrémental

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 49 / 51
Synthèse : Contributions de PQDAG

Innovations Architecturales Nouveaux Opérateurs

✓ Production incrémentale distribuée ✓ OR (Opérateur de Routage)
➜ Chaque worker émet des résultats au fil de ➜ Organisation par destination dès production
l’eau ➜ Routage local (MTC) vs distant (TT)
➜ Réduction de la latence perçue ✓ OGE (Orchestration d’Échange)
✓ Synchronisation sélective BSP ➜ Synchronisation sélective dynamique
➜ Asynchronisme local si données locales ➜ Minimise les super-étapes BSP
➜ Sync uniquement si échange nécessaire ✓ ER (Écriture Réseau)
➜ Exploite la localité des données ➜ Streaming décentralisé vers client
✓ Points de reprise cohérents ➜ Élimine goulot d’étranglement central
➜ Super-étapes = frontières cohérentes
➜ Facilite tolérance aux pannes

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 50 / 51
 Merci pour votre attention
Questions ?

Université de Tlemcen - ISAE-ENSMA Gestion scalable des graphes RDF 1er décembre 2025 51 / 51