Ecole Nationale Polytechnique de Maroua

UFD Sciences de l’Ingénieur

Master 1 Recherche, Option Informatique
Année Académique : 2021/2022

Bases de Données Avancées

MAI
Dr Guidedi KALADZAVI, PhD
 Présentation de l’enseignant

Guidedi KALADZAVI, PhD

• Chef de Département d‟Informatique et Télécoms, École Nationale Supérieure

Polytechnique de Maroua (ENSPM), Cameroun
• Enseignant-associé à l‟Université Virtuelle du Sénégal
• Membre de l'Équipe WIMMICS, Inria Sophia Antipolis-Méditerranée, Nice, France
• Email : [email protected]
Pré-requis et Objectif général

Pré-requis
• Introduction aux Bases de données
• Introduction à la programmation Orientée Objet
• Introduction à la programmation parallèle

Objectifs généraux
À la fin ce cours, chaque apprenant sera capable
• de concevoir et d‟exploiter des Bases de Données Réparties
• d‟optimiser des requêtes
• de concevoir et d‟exploiter les Entrepôts de Données
• de stocker, traiter analyser des données massives à l‟ère du Big Data
●
Présentation cours
Table des matières
• Séquence 1 : Bases de Données distribuées
• Objectifs spécifiques
1. Identifier des besoins de distribution des données
2. Concevoir une base de données distribuées par la fragmentation ou intégration
• Séquence 2 : Optimisation des requêtes
• Objectifs spécifiques :
1. Analyser et identifier des requêtes optimisables
2. Produire des réécritures algébriques et des plans d‟exécution
• Séquence 3 : Système Décisionnel (business Intelligence) et Entrepôts de Données (Data Warehouse)
• Objectifs spécifiques :
1. Faire une différence entre Systèmes opérationnels et Décisionnels
2. Concevoir et exploiter un Entrepôt de Données
• Séquence 4 : Big data, MapReduce et NoSQL
• Objectifs spécifiques :
1. Identifier les nouveaux enjeux informatiques à l'ère du Big Data
2. Produire des algorithmes du type Mapreduce et prendre en main le framework Hadoop
3. Concevoir et exploiter des bases de données NoSQL
 Consignes de travail

Consignes
• Suivre plusieurs fois les vidéos des séquences, au besoin, réduire la vitesse de lecture
• Faire plusieurs fois des exercices d‟application des séquences
• Faire tous les tests de connaissance à la fin de chaque séquence
• Faire tous les exercices de TD et TP, le travail en groupe est vivement recommandé
• Être actif dans les forums de discussions
• Avoir l‟esprit d‟autonomie
Introduction Générale
Introduction Générale
Rappels

Définition
• Une base de données est un ensemble de données modélisant les objets d‟une partie du
monde réel et servant de support à une application informatique ( G. Gardarin, 2003 ).

Préalables
• Données interrogeables selon n‟importe quel critère.
Exemple : Retrouver tous les produits qui coûtent au moins 100 fcfa

• Retrouver leur structure des données

Exemple : Retrouver un nom, un prix, une quantité d‟un produit dans la Base
Introduction Générale
Rappels
Donnée, Information, connaissance, Valeur, etc.
Introduction Générale

Rappels
Evolution des systèmes de Bases de Données

Répondre mieux aux problématiques se

Stockage,
normalisation,
temps de réponses
…
Introduction Générale

Rappels
Evolution des modèles de données

Mieux représenter les données pour le

Stockage,
normalisation,
temps de réponses
…
Introduction Générale

Rappels
Evolution des architectures

Mieux organiser les systèmes pour le

Stockage,
normalisation,
temps de réponses
…
Introduction Générale
Les séquences de ce cours …

• Bases de Données Distribuées

• Optimisation des Requêtes
• Système Décisionnel et Entrepôt des Données
• Big Data, MapReduce et NoSQL
Séquence 1: Bases de Données Distribuées
Bases de Données Avancées
Guidedi KALADZAVI
Séquence 1 : Bases de Données Distribuées

• Introduction
• Architectures
• Fragmentation
• Réplication
• Conclusion
Introduction
Rappels

Une Base de Données

• Une base de données est un ensemble de données modélisant les objets d‟une partie du
monde réel et servant de support à une application informatique ( G. Gardarin, 2003 ).

Une Base de Données Centralisée

• Problèmes :
● Augmentation du volume de données
● Augmentation du volume de traitements
● Augmentation du volume des transactions
● etc.
 Introduction
Système distribué

Un système distribué est une application qui coordonne les actions de plusieurs ordinateurs pour réaliser une
tâche particulière.

Le calcul distribué a une composante importante de gestion de données :

• Les données de l‟application
• Les échanges des données entre les ordinateurs (communications)
• Les états du système et des sessions des utilisateurs
• Les profils des utilisateurs
• ...
Introduction
Base de Données distribuée

Une base de données distribuées : une grande quantité de données résidant sur plusieurs machines

Un système de gestion de données distribuées : un logiciel qui permet d‟avoir un point d‟entrée unique sur une
base de données distribuées

Contradiction apparente
• Les Calculs de données sont centralisés
• Un point d‟entrée unique pour accéder à toutes les données de manière transparente
• ...
Introduction
Base de Données distribuée

Fragmentation
• On part d‟une grosse Base de Données
• On la distribue en fragments pour améliorer les performances
• On obtient une base de données distribuées
Intégration
• On part de bases de données existantes (autonomes)
• On les intègre pour obtenir un point d‟entrée unique
• On obtient une base de données distribuées
Réplication de données
Introduction
Pourquoi intégrer : conserver l’autonomie

Autonomie des différents systèmes permet

• L‟intégration de données provenant d‟organismes indépendants ( par ex, entreprises
indépendantes)
• L‟intégration de données provenant de différentes branches d‟un même organisme mais en laissant
plus de liberté à chaque branche
BDR
Tendance dans l‟industrie
intégratio
des structures de moins en moins hiérarchiques, de plus en plus d‟autonomes n
B
D
B … B
D D
1 2 n
Introduction
Pourquoi fragmenter : performance

Un ordinateur et un disque
• 1 téraoctet
• Scan séquentiel
• 166 minutes (> 2.5 heures)
100 disques en parallèle
• moins de 2mn
100 ordinateurs distribués
• Chacun son propre CPU
• Chacun son disque
• Ça passe à l‟échelle
Introduction
Pourquoi répliquer : sûreté/disponibilité

Mono-serveur
• Panne du processeur ou du disque
• Arrêt du service
• Perte des données
Multi-serveurs
• Panne d‟un processeur ou d‟un disque
• Le service continue, Grâce à la réplication,
• pas de perte des données
Énormément utilisé
• Réplication par 2 : banque
• Réplication par 3 : airbus
Introduction
Concept essentiel : transparence

de localisation
• l‟utilisateur n‟a pas savoir où sont les données
de réseau/système
• Panne d‟un processeur ou d‟un disque
de fragmentation
• il n‟a pas à connaître comment les données sont fragmentées
de réplication
• il n‟a pas à savoir comment/si elles sont répliquées

Chaque entité a un nom unique

Introduction
Pas seulement des avantages

Complexité
• Rajoute des couches de logiciel Incohérences
• Que fait-on quand deux systèmes donnent des
• Communication
• Distribution du contrôle informations contradictoires
• Exemple : réservation de place, collision
• Conception de la base de données
• Gestion des contraintes d‟intégrité d‟avion

Absence de standards

Moins d‟expérience
Séquence 1 : Bases de Données Distribuées

Architectures
Séquence 1 : Bases de Données Distribuées

• Introduction
• Architectures
• Fragmentation
• Réplication
• Conclusion
Architectures
Rappels
Evolution des architectures

Mieux organiser les systèmes pour le

Stockage,
normalisation,
temps de réponses
…
Architectures
Mono-machine : pas de distribution

Les SGBD des débuts : centralisés

• Pluri-utilisateurs et terminaux
Architectures
Architecture Client-Serveur

Client
• Interface utilisateur
• Application
Serveur
• Gestion des requêtes
• Gestion des transactions
• Gestion des pannes
• Stockage des données
Architectures
Architecture Client-Serveur 3-tiers

Client
• Un navigateur qui présente le contenu, HTML par exemple

Le niveau intermédiaire
• Communication avec le SGBD
• Gère l‟application (Java, C++, etc)
• Génère le contenu au client
Serveur
• Stockage des données
Architectures
Vers la distribution : plusieurs serveurs de données
Architectures
Architecture Cloud, Fog, et Edge
Architectures
Typologie : hétérogénéité des SGBD locaux

• Modèles différents : Relationnel, XML, Objet, JSON

• Langages de requêtes différents ; SQL, Xquery, NoSQL
• Systèmes d‟exploitation différents : Windows, Linux, MacOS
• SGBD différents, Oracle, MySQL, Db2, Sesame, etc.

L’hétérogénéité introduit de la complexité

Architectures
Séquence 2 : Bases de Données Distribuées

Fragmentation
Séquence 2 : Bases de Données Distribuées

• Introduction
• Architectures
• Fragmentation
• Réplication
• Conclusion
Fragmentation
Cas de figure

Base de Données Dakar

• Relation Employé E(enum, nom, site, salaire,…)
• Un employé n‟appartient qu‟à un seul site
• 40 000 employés à Dakar et Thiès, et 20 000 à St-Louis
Charge de travail
• 90 % des requêtes à Dakar/Thiès/St-louis sont sur les employés locaux
Pour illustrer
• Accès disque = 1 unité
• accès réseau =10 unités
Thiès

St-louis
Fragmentation
Fragmentation : performance

Sans fragmentation (SGBD à Dakar) Dakar

Coût
• À Dakar=1 unité
• À Thiès/St-Louis=10 unités
• Moyenne=0.4+0.6*10=6.4 unités

Avec fragmentation (3SGBD : BD-D, BD-T, BD-S )

Coût
• À Dakar/Thiès/St-Louis 0.9+0.1*10=1.9
• Moyenne=1.9 unités
• Éviter
● le risque de saturation de la SGBD de Dakar
● Le temps de réponse. Thiès
St-louis
Fragmentation
Fragmentation horizontale

Fragmentation horizontale : Consiste à faire une

séparation selon les enregistrements. On définit le critère
de sélection suivant les valeurs d'un ou plusieurs champs
et la division est faite.

σ site≠Dakar (E)
=Dakar (E)⋃ σ site≠Dakar (E)
Fragmentation
Fragmentation Verticale :
Fragmentation Verticale :
La division est faite non au niveau des données, mais de
la structure même de la base. Certains champs sont
envoyés dans un fragments et d'autres ailleurs

Π enum,adresse... (E)

Π enum,nom (E) ⨝ Π enum,adresse enum,adresse ...

(E)
Fragmentation
Fragmentation Mixte :

Fragmentation mixte : La division est faite non au niveau des

données, mais de la structure même de la base. Certains champs
sont envoyés dans un fragments et d'autres ailleurs
Fragmentation
Les 3 règles de la fragmentation

• Perte d‟information : Pour toute donnée de la relation R, il doit avoir une sous relation Ri la
contenant
● σ site=Dakar (E) ⋃ σ site≠Dakar (E) = E
● Π enum,nom (E) ⨝ Π enum, adresse...(E) = E
• Pour toute fragmentation de la relation R en plusieurs sous relations Ri, il doit avoir un
procédé inverse de la reconstitution de la relation principale R
• Redondance : Aucune donnée ne doit se trouver dans plus d‟un fragment, sauf dans le cas
d‟une fragmentation verticale ou la clé primaire doit être présente partout
● σ salaire>10K (E) et σ salaire<15K (E)
● Les deux fragments ne sont pas disjoints
●
Fragmentation
Exemple de fragmentation plus complexe

● Schéma

● Employé E(enum, nom, site, salaire, …)

● Projet P(enum, projet)
● enum clé d‟Employé et clé étrangère de projet

Question fréquente : donner toutes les informations de X ainsi que ses projets
Fragmentation
Exemple de fragmentation plus complexe

Employé E(enum, nom, site, salaire, …)

Projet P(enum, nomprojet, budget, ...)

E1@site 1 = σ site=Dakar (E) P1@site 2 = P ⋉ E1

E2@site 3 = σ site≠Dakar (E) P2@site 4 = P ⋉ E2

Le nuplet d‟un projet qui a des employés à Dakar et sur un autre site est répliqué
Fragmentation
Fragmentation & SGBD

● Les deux grandes classes de fragmentation (horizontale et verticale) correspondent à deux grandes classes
de SGBD relationnels

Les SGBD à stockage par ligne

Ex d‟unité de stockage
[nom : Martin, âge : 45, adresse : Thiès]

Les SGBD à stockage par colonne

Ex d‟unité de stockage
{nom : Diallo, nom : Manè, nom : Massata, ... }
Fragmentation
Fragmentation & SGBD
Allocation
Types

● Non-dupliquée
● partitionnée : chaque fragment réside sur un seul site
● Dupliquée
● chaque fragment sur un ou plusieurs sites
● maintien de la cohérence des copies multiples
● Règle intuitive:
● si le ratio est [lectures/màj] > 1, la duplication est avantageuse
Semaine 2 : Bases de Données Distribuées

Réplication
Séquence 2 : Bases de Données Distribuées

• Introduction
• Architectures
• Fragmentation
• Réplication
• Conclusion
Réplication
Raisons de réplication de données

Fiabilité
• Faire qu‟il y ait plusieurs copies de la même donnée
• Si une machine n‟est plus accessible, on peut quand même accéder à la donnée
• Si une machine perd une donnée, la donnée existe encore

Performance
• Rendre des données plus disponibles
• Économiser les communications
Réplication
Réplication de données : trade-off

Trade-off requêtes vs. mises-à-jour

• Classique en BD

Avantage : Requête
• Interroger une des copies
• Interroger une vue

Désavantage : Mise-à-jour
• Mise-à-jour d‟une copie – propager aux autres
• Mise-à-jour d‟une vue – traduire en MàJ des relations de bases – ambiguïté

Les copies peuvent ralentir les requêtes (verrous)

Économiser des communications
Réplication
Performance

Base de Données
• Relation Employé E(enum, nom, site, salaire,…)
• Un employé n‟appartient qu‟à un seul site
• 40 000 employés à Dakar et Thiès, 20 000 à St-Louis
• 90 % des requêtes à Dakar/Thiès/St-louis s ont sur les employés locaux
• Accès disque = 1 unité & Accès réseau = 10 unités
• 3 SGBD avec les employés locaux

Sans fragmentation 6.4 unités

Avec fragmentation 1.9 unités

FRAGMENTATION + REPLICATION D/T/S

1 unité
Réplication
Choisir la réplication

Que doit-on répliquer et où ?

• Problème complexe d‟optimisation : Utilise une approche « gloutonne »

Faire jusqu‟au point fixe, Pour chaque réplication d‟un fragment sur un site
• Quel est le gain
• Quel est le coût

Répliquer le fragment tel que

• (gain > coût) et (gain – coût) maximal
Séquence 2 : Bases de Données Distribuées

• Introduction
• Architectures
• Fragmentation
• Réplication
• Conclusion
Séquence 2 : Bases de Données Distribuées

conclusion
Conclusion
Nouvelle tendance : Architecture Pair à pair

• Chaque machine est à la fois un serveur et un client avec autonomie totale

• Mieux utiliser les ressources disponibles sur le réseau
■ Les CPU inoccupés
■ Les espaces libres sur disques et mémoire
■ Les réseaux de communications disponibles

• Exemple : Serveur de musique ou vidéos

 Conclusion
Nouvelle tendance : Big Data et l’Architecture Cloud, Fog, Edge Computing
● Big Data
■ De plus en plus de données disponibles : Web, réseaux sociaux, Internet des objets,
téléphones intelligents…
■ Analyse de ces données pour en tirer de la valeur : Techniques d‟apprentissage (machine
learning)
■ Calcul massivement parallèle comme Hadoop
■ Systèmes NoSQL
Cloud, Fog, Edge Computing
L‟utilisation de la puissance de calcul ou de stockage de
serveurs informatiques distants par l'intermédiaire
d‟Internet
• L‟application est dans le cloud
• Les données sont dans le cloud
Références

1. Philippe Rigaux, Cours de bases de données, http://www.info.univ-angers.fr/~gh/internet/cbd.pdf

2. Georges gardarin, Bases de données, eyrolles, 2003
3. Serge Abiteboul, bases de données avancées support de cours
4. David TSOTO, SQL SERVER : architectures et Structure d'une Base de données,
https://www.supinfo.com/articles/single/6498-sql-server-architectures-structure-une-base-donnees
5. Gerti Kappel, Birgit Proll, Siegfried Reich, Werner Retschitzegger, Web Engineering : The Discipline of
Systematic Development of Web Applications, 2003,
http://gen.lib.rus.ec/book/index.php?md5=959310F138D0A7338202BCD53B51EEE6
Séquence 2: Évaluation et Optimisation
Bases de Données Avancées
Guidedi KALADZAVI
Séquence 2 : Évaluation et Optimisation

• Introduction
• Réécriture algébrique
• Plans d‟exécution
• Tri et hachage
• Algorithmes de jointure
• Optimisation
• Conclusion
Introduction
Le problème étudié

Une requête SQL est déclarative, ne dit pas comment calculer le résultat

Besoin d‟une forme opératoire : un programme

Introduction
La notion de plan d’exécution

Dans un SGBD le programme qui exécute une requête est appelé plan d‟exécution.

Il a une forme particulière : c‟est un arbre, constitué d‟opérateurs.

Introduction
De la requête SQL au plan d’exécution

Deux étapes :
1. (A) plan d‟exécution logique (l‟algèbre) ;
2. (B) plan d‟exécution physique (opérateurs).

Le SGBD s‟appuie sur un catalogue d‟opérateurs.

Introduction
En quoi consiste l’optimisation ?

À chaque étape, plusieurs choix. Le système les évalue et choisit le « meilleur ».

Séquence 2 : Évaluation et Optimisation

Réécriture algébrique
Séquence : Évaluation et Optimisation

• Introduction
• Réécriture algébrique
• Plans d‟exécution
• Tri et hachage
• Algorithmes de jointure
• Optimisation
• Conclusion
Réécriture algébrique
De SQL vers une forme opératoire : l’algèbre

En SQL :

Select titre
From Film f, Role r
Where nom_role =‟Ferguson‟
and f.id = r.id_ilm
and f.annee = 1958

Deux sélections (l‟année, le rôle), une jointure, une projection.

Réécriture algébrique
Le Plan d’Exécution Logique (PEL)

En algèbre, sous une forme normalisée projection-sélection-jointure :

π titre (σ annee=1958∧nom_role= ′ ferguson ′ (Film ⋊id=id_film Role))

Réécriture algébrique
Le Plan d’Exécution Logique (PEL)

La même expression, sous forme d‟un arbre.

Des réécritures vont nous permettre d’en trouver d’autres

Réécriture algébrique
Il y a plusieurs expressions équivalentes pour une même requête.

On peut explorer ces expressions grâce à des règles de réécriture. Exemple

• Commutativité des jointures : R ⋊S ≡ S ⋉ R

• Regroupement des sélections : σ A= ′ a ′ ∧ B= ′ b ′ (R) ≡ σ A= ′ a ′ (σ B= ′ b ′ (R))
• Commutativité de σ et de π : π A 1 ,A 2 ,...A p (σ A i = ′ a ′ (R)) ≡ σ A i = ′ a ′ (π A 1 ,A 2 ,...A p (R))
• Commutativité de σ et de ⋊ : σ A= ′ a ′ (R[. . . A . . .] ⋉ S) ≡ σ A= ′ a ′ (R) ⋉ S
• …

L‟application dirigée d‟une règle d‟équivalence (réécriture) transforme une expression e en une expression
équivalente e„.
Réécriture algébrique
Ce que fait l’optimiseur

• Trouve les expressions équivalentes, évalue leur coût et choisit la meilleure.

• Important : on ne peut pas énumérer tous les plans possibles (trop long) : on applique des
heuristiques.

Heuristique classique : réduire la taille des données

• en filtrant les nuplets par des sélections
• en les simplifiant par des projections dès que possible.
Réécriture algébrique
Exemple

Reprenons : le film paru en 1958 avec un rôle ‟Ferguson‟.

Réécriture algébrique
Exemple

Reprenons : Première étape : je sépare les sélections.

Réécriture algébrique
Exemple

Puis on pousse chaque sélection vers sa table. les sélections.

À ce stade : reste à choisir les chemins d‟accès et les

algorithmes de jointure.
Réécriture algébrique
Résumé : la réécriture algébrique

Principes essentiels :
1. L‟algèbre permet d‟obtenir une version opératoire de la requête.
2. Les équivalences algébriques permettent d‟explorer un ensemble de plans.
3. L‟optimiseur évalue le coût de chaque plan.

Bien retenir
• Heuristique : on ne peut pas tout explorer
• Nécessaire mais pas suffisant : il reste à choisir le bon algorithme pour chaque opération.
Séquence 2 : Évaluation et Optimisation

Opérateurs et Plans d‟Exécution

Séquence 2 : Évaluation et Optimisation

• Introduction
• Réécriture algébrique
• Plans d’exécution
• Tri et hachage
• Algorithmes de jointure
• Optimisation
• Conclusion
Opérateur
Rappel : un plan d’exécution est un arbre constitué d’opérateurs échangeant des
flux de données.

Caractéristiques des opérateurs

• ont une forme générique (itérateurs) ;

• fournissent une tâche spécialisée (cf. l‟algèbre relationnelle)
• peuvent être ou non bloquants.
• Un petit nombre suffit pour couvrir SQL !
Opérateur
Mode naïf : matérialisation

Dans ce mode, un opérateur calcule son résultat, puis le transmet.

Dex inconvénients :
● Consomme de la mémoire.
● Introduit un temps de latence.
Opérateur
La bonne solution : pipelinage

Le résultat est produit à la demande.

• Plus de stockage intermédiaire.

• Latence minimale
Opérateur
La bonne solution : l’opérateur FullScan

• Le premier next() entraîne l‟accès au premier bloc, placé en mémoire.

• Le curseur se place sur le premier nuplet, qui est retourné comme résultat : Le temps de réponse est
minimal.
Opérateur
La bonne solution : l’opérateur FullScan

Le deuxième next() avance d‟un cran dans le parcours du bloc.

Opérateur
La bonne solution : l’opérateur FullScan

Après plusieurs next(), le curseur est positionné sur le dernier nuplet du bloc..
Opérateur
La bonne solution : l’opérateur FullScan

L‟appel suivant à next() charge le second bloc en mémoire.

Bilan : besoin en mémoire réduit (1 bloc) ; temps de réponse très court

Opérateur = itérateur
Tout opérateur est implanté sous forme d‟un itérateur. Trois fonctions :
•open : initialise les ressources et positionne le curseur ;
•next : ramène l‟enregistrement courant se place sur l‟enregistrement suivant ;
•close : libère les ressources ;

Échanges
•
Un itérateur consomme des nuplets d‟autres itérateurs source.
•
Un itérateur produit des nuplets pour un autre
•
itérateur (ou pour l‟application).
●
Opérateur bloquant
Tous les opérateurs peuvent-ils fonctionner en mode pipelinage ?

Exemple : Select min(date) from T

● On ne peut pas produire un nuplet avant d‟avoir examiné toute la table. Il faut alors
introduire un opérateur bloquant, avec une latence forte.
● Avec un opérateur bloquant, on additionne le temps d‟exécution et le temps de traitement.
Opérateur = itérateur
Tout opérateur est implanté sous forme d’un itérateur. Trois fonctions :

• open : initialise les ressources et positionne le curseur ;

• next : ramène l‟enregistrement courant se place sur l‟enregistrement suivant ;
• close : libère les ressources

Échanges
• Un itérateur consomme des nuplets d‟autres itérateurs source.
• Un itérateur produit des nuplets pour un autre itérateur (ou pour l‟application).
Exemple : parcours d’index (IndexScan)
Opérateur IndexScan

• Rappel : index = arbre B

• Pendant le open() : parcours de la racine vers la feuille.
• À chaque appel à next() : parcours en séquence des feuilles.

Efficacité : très efficace, quelques lectures logiques (index en mémoire)

Accès mémoire
Accès par adresse : DirectAccess

• Pendant le open() : rien à faire.

• À chaque appel à next() : on reçoit une adresse, on produit un nuplet.

Très efficace : un accès bloc, souvent en mémoire.

Plan d’exécution
Plan d’exécution

Un plan d‟exécution connecte les opérateurs. Ici, recherche avec index.

Le pipelinage reste complet.

Séquence 2 : Évaluation et Optimisation

Tri et hachage
Séquence 2 : Évaluation et Optimisation
• Introduction
• Réécriture algébrique
• Plans d‟exécution
• Tri
• Algorithmes de jointure
• Optimisation
• Conclusion
Tri externe
Le tri externe est utilisé

• Pour les algorithmes de jointure (sort/merge)

• l‟élimination des doublons (clause distinct)
• pour les opérations de regroupement (group by)
• ... et bien sûr pour les order by
•

Opération coûteuse sur de grands jeux de données.

Algorithme de tri-fusion (externe).
Tri externe
Première phase : le tri

Il faut une zone de tri, en RAM, allouée par le système.

On veut trier une source de données (ici, un fichier).

Première phase : le tri
Cas favorable : tout le fichier tient en mémoire.

On charge, on trie avec quicksort : prêt pour l‟itération.

Première phase : le tri
Et si le fichier ne tient pas en mémoire ?

On lit le premier fragment, on trie, on stocke.

Première phase : le tri
On lit le fragment suivant, on trie, on stocke.

Chaque fragment est trié.

Fusion de listes triées
À l’issue de la phase de tri : n fragments triés.

Il faut maintenant les fusionner.

Fusion de listes triées
On place un curseur au début de chaque liste.

On compare les valeurs, et on prend la plus petite.

Fusion de listes triées
On a avancé sur le curseur de la valeur extraite.

On applique la même méthode.

Fusion de listes triées
On continue sur le même principe.

On ne revient jamais en arrière.

Fusion de listes triées
On continue sur le même principe.

On ne revient jamais en arrière : Résultat, liste globale triée

 Résumé : tri et opérateurs bloquants
L’opérateur de tri est bloquant

La phase de tri est effectuée pendant le open()

Le next() correspond à la progression de l’étape de fusion.

Conséquence : latence importante des requêtes impliquant un tri.

● Il faut lire au moins une fois toute la table.
● Si mémoire insuffisante, il faut lire deux fois,
● écrire une fois.
● Parfois pire...
Séquence 2 : Évaluation et Optimisation

Algorithmes de jointure
Optimisation des Requêtes

• Introduction
• Réécriture algébrique
• Plans d‟exécution
• Tri et hachage
• Algorithmes de jointure
• Optimisation
• Conclusion
Algorithmes de jointure
L’opérateur qui nous manque

La jointure : opération très courante, potentiellement coûteuse.

L‟opérateur de jointure complète notre petit catalogue pour (presque) toutes les
requêtes SQL.
Exemple :
Select a1, a2, .., an
from T1, T2, ..., Tm
where T1.x = T2.y and ...
order by …

Plusieurs
algorithmes possibles.
Algorithmes de jointure
Principaux algorithmes

Jointure avec index

Algorithme de jointure par boucles imbriquées indexées.

Jointure sans index

Le plus simple : boucles imbriquées (non indexée).
Plus sophistiqué : la jointure par hachage.
Algorithmes de jointure
Exemple de Jointure avec index

Très courant ; on effectue naturellement la jointure sur les clés primaires/étrangères.

Les employés et leur département

select * from emp e, dept d
where e.dnum = d.num

Garantit au moins un index sur la condition de jointure.

Algorithmes de jointure
Jointure avec index : l’algorithme

On parcourt séquentiellement la table contenant la clé étrangère.

On obtient des nuplets employé, avec leur no de département.

Algorithmes de jointure
Jointure avec index : l’algorithme

On utilise le no de département pour un accès à l‟index Dept.

On obtient des paires [employé, adrDept].

Algorithmes de jointure
Jointure avec index : l’algorithme

Il reste à résoudre l‟adresse du département avec un accès direct

On obtient des paires [employé, dept].

Algorithmes de jointure
Jointure avec index : l’algorithme

Avantages :
● Efficace (un parcours, plus des recherches par adresse)
● Favorise le temps de réponse et le temps d‟exécution
Séquence 2 : Évaluation et Optimisation

Optimisation des Requêtes

Séquence 2: Évaluation et Optimisation

• Introduction
• Réécriture algébrique
• Plans d‟exécution
• Tri et hachage
• Algorithmes de jointure
• Optimisation des Requêtes
• Conclusion
Optimisation
En quoi consiste l’optimisation ?

À chaque étape, plusieurs choix. Le système les évalue et choisit le « meilleur ».

Optimisation des Bases de données Distribuées
Que faut-il optimiser ?

Bases de données classiques

• I/O : Accès disque (millisec)
>> Opération du processeur (microsec)
Bases de données distribuées
• Communication (jusqu‟à 1sec sur Internet)
>> Accès disque (millisec)
Attention : basé sur des communications lentes
• par ex, kilo-octets par second
• LAN : bande passante
même ordre de grandeur qu’un disque
Optimisation des Bases de données Distribuées
Quel est le problème ?

E1@site1 = σ site=Dakar (E) P1@site2 = P ⋉ E1

E2@site3 = σ site≠Dakar (E) P2@site4 = P ⋉ E2
• Une requête arrive à site5
Select enom
from E, P
where E.enum =
P.enum
and projet = “info”
Q = Π enom ( σ projet=“info” (E ⨝ P) )
= Π enom ( [σ projet=info (E1⨝ P1) ] ⋃ [σ projet=info (E2 ⨝ P2)] )
Optimisation des Bases de données Distribuées
Plusieurs plans possibles : centralisation brutale

E1@site1 = σ site=Dakar (E) P1@site2 = P ⋉ E1

E2@site3 = σ site≠Dakar (E) P2@site4 = P ⋉ E2

centralisation brutale
Optimisation des Bases de données Distribuées
Plusieurs plans possibles : solution optimisée

E1@site1 = σ site=Dakar (E) P1@site2 = P ⋉ E1

E2@site3 = σ site≠Dakar (E) P2@site4 = P ⋉ E2

Optimisation
Optimisation des Bases de données Distribuées
Architecture logique : intégration de données

BD centralisée – 3 niveaux BD distribuée – 4 niveaux

• •
Optimisation des Bases de données Distribuées
Séparer les problèmes pour simplifier

Analyse syntaxique
• SQL Q sur SCG ⇒ requête algébrique H sur SCG
Localisation
• requête algébrique H sur SCG ⇒ requête algébrique G(H 1 , H 2 ) avec H 1 ,H 2 sur SCL 1 , SCL 2
Optimisation globale
• Minimise globalement les communications
• Obtient G(H 1 , H 2 ) en G‟(H 1 ‟, H 2 ‟) avec H 1 ‟, H 2 ‟ sur SCL 1 , SCL 2
Optimisation locale
• Minimise localement les I/O (et aussi les calculs)
• Localement chaque H i ‟ est optimisé en H i ‟‟
• On évalue
G‟(H 1 ‟‟, H 2 ‟‟) = G‟(H 1 ‟, H 2 ‟) = H = Q
Références

1. Philippe Rigaux, Cours de bases de données, http://www.info.univ-angers.fr/~gh/internet/cbd.pdf

2. georges gardarin, Bases de données, eyrolles, 2003
3. Serge Abiteboul, bases de données relationnelles, support de cours
4. https://www.youtube.com/watch?v=IzjL2QJq2Pc&t=59s
Séquence 3: Système Décisionnel
et Entrepôts de Données
Bases de Données Avancées
Guidedi KALADZAVI
Séquence 3: Système Décisionnel et Entrepôts de Données

• Introduction
• Système Décisionnel- Business Intelligence
• Entrepôt de Données – Data Warehouse
• Conclusion
Introduction
Dirigeants, Entreprise, informatique décisionnelle

Information en Entreprise
● Informations noyées sous de nombreuses données, éparses, déstructurées et hétérogènes
● Ces décideurs ont besoin qu'on leur expose les faits importants, base de leurs décisions.

informatique décisionnelle.
● Elle permet une sélection des informations opérationnelles pertinentes pour l'entreprise
● Elle doit produire des indicateurs et des rapports à l'attention des analystes.
● Elle doit également proposer des outils de navigation, d'interrogation et de visualisation de
l'entrepôt.
Introduction
Entrepôt de données – Data Warehouse

● Entrepôt de données est une collection de données orientées sujet, intégrées, non
volatiles et historisées, organisées pour la prise de décision
❏ orienté sujets
❏ données intégrées
❏ Données non volatiles
❏ Données historisées
Introduction
OLTP vs. OLAP

● OLTP : On Line Transaction Processing

❏ Exemple : Le 15/01/2012 à 13h12, le client X a retiré 500fCFA du compte Y

● OLAP : On Line Analytical Processing

❏ Exemple : Quel est le volume des ventes par produit et par région durant le deuxième
trimestre de 2012?
Introduction
OLAP et Modélisation dimensionnelle

● Les BD relationnelles ne sont pas adaptées à l'OLAP

❏ Pas les mêmes objectifs
❏ Pas les mêmes données:
❏ Pas les mêmes traitements et requêtes:

● Nécessité d'une structure de stockage adaptée à l'OLAP

❏ représenter les données dans plusieurs dimensions,
❏ manipuler les données facilement et efficacement.
Introduction
Représentation multidimensionnelle : ‘Cube’
Séquence 3: Système Décisionnel et Entrepôts de Données

Système Décisionnel
Reporting
Exemple d’un reporting imprécis
Reporting
En fait, l’important est dans la variation
Reporting
Mais une information peut en cacher une autre...
Enjeux du Décisionnel
Le système d'information décisionnel

La prise de décisions stratégiques dans une organisation nécessite le recours et le croisement de

multiples informations qui concernent tous les départements : production, RH, DAF, achats,
ventes,marketing, service après-vente, maintenance, R&D..

Finalité : Transformation des données de production en informations stratégiques

Système Décisionnel
Exploitation des données

Les données agrégées dans un système décisionnel servent à trois grandes catégories d'usage :

• La production de rapport récurrents ( reporting )

• L'exploration manuelle
• L'analyse de données (descriptive ou prédictive)
Système Décisionnel
Reporting

Le principe du reporting est d'agréger et de synthétiser des données nombreuses et complexes sous
forme d'indicateurs, de tableaux, de graphiques permettant d'en avoir une appréhension globale et
simplifiée.

• récurrent
• agrégats (GROUP BY en SQL par exemple)
Système Décisionnel
Reporting

Le principe du reporting est d'agréger et de synthétiser des données nombreuses et complexes sous
forme d'indicateurs, de tableaux, de graphiques permettant d'en avoir une appréhension globale et
simplifiée.

• récurrent
• agrégats (GROUP BY en SQL par exemple)
Système Décisionnel
Exploration manuelle

• L'idée générale est plutôt que les réponses aux premières questions que l'on se posent
conduiront à se poser de nouvelles questions
• Explorer les données de façon peu dirigée (heuristique) afin de trouver des réponses à des
questions que l'on ne s'est pas posées (sérendipité).
• Explorer les données de façon peu dirigée (heuristique) afin de trouver des réponses à des
questions que l'on ne s'est pas posées (sérendipité).
Système Décisionnel
Exploration manuelle

• L'idée générale est plutôt que les réponses aux premières questions que l'on se posent
conduiront à se poser de nouvelles questions
• Explorer les données de façon peu dirigée (heuristique) afin de trouver des réponses à des
questions que l'on ne s'est pas posées (sérendipité).
• Explorer les données de façon peu dirigée (heuristique) afin de trouver des réponses à des
questions que l'on ne s'est pas posées (sérendipité).
●
Système Décisionnel
Analyse de données

• Analyse descriptive
• Analyse prédictive
Système Décisionnel
Systèmes Opérationnels vs Systèmes Décisionnels
Systèmes Opérationnels Systèmes Décisionnels

• Analyse Appelés OLTP (On-Line Transaction • Appelés OLAP (On-Line Analytical Processing)
Processing) ou systèmes de gestion • Dédiés à la gestion de l‟entreprise pour l‟aider au
• Dédiés aux métiers de l‟entreprise pour les assister pilotage de l‟activité pour une vision transversale
dans leurs tâches de gestion Quotidiennes de l‟entreprise
• Utilisation des PGI (ou ERP) pour la gestion des • Utilisation des Entrepôts de donnée
données
Système Décisionnel
Architecture

Tout système décisionnel est architecturé globalement de la même façon :

• En amont un accès au système transactionnel en lecture seule

• Un ETL permettant d'alimenter le DW à partir des données
existantes
• Un DW fusionnant les données requises
• D'éventuels DM , permettant de simplifier le DW en vue de
certaines applications
• Des applications d'exploitation de reporting , exploration et/ou
prédiction
Système Décisionnel
Conception d'un système décisionnel

1- Étude des besoins et de l'existant 3. Implémentation du data warehouse

● Étude des besoins utilisateurs ● Implémentation du DW et des DM
● Étude des données existantes ● Mise en place de l'ETL
4. Implémentation des outils d'exploitation
2. Modélisation et conception ● Implémentation des outils de reporting
● Modélisation dimensionnelle ● Implémentation des outils d'exploration
● Architecture technique ● Implémentation des outils de prédiction
● Spécification des outils d'exploitation
Séquence 3 : Système Décisionnel et Entrepôts de Données

Entrepôt de Données – Data Warehouse

Séquence 3: Système Décisionnel et Entrepôts de Données

• Introduction
• Système Décisionnel- Business Intelligence
• Entrepôt de Données – Data Warehouse
• Conclusion
Entrepôts de Données
Entrepôt de donnée ou concept central du BI

● Quelle structure permet-elle d'avoir les fonctionnalités requises pour un entrepôt de données ?
● Quelles sont les techniques utilisées pour bien concevoir ?
● Quels sont les indicateurs d'une bonne conception ?
Entrepôts de Données
Concepts fondamentaux

Entrepôt de données
● une structure (comme une base de données) qui à pour but, contrairement aux bases de
données, de regrouper les données de l'entreprise pour des fins analytiques et pour aider à la
décision stratégique.
● un gigantesque tas d'informations épurées, organisées, historisées et provenant de plusieurs
sources de données, servant aux analyses et à l'aide à la décision

Entrepôt de données = Système d'information Opérationnel +Temps+données externes

Entrepôts de Données
Concepts fondamentaux

Data Mart, ou magasin de données

● Subdivision d‟un Entrepôt de Données en bouchées plus faciles à créer et entretenir

● Subdivision
❏ fonction (ventes, commandes, Ressources humaines)
❏ sous-ensemble organisationnel (un data mart par succursale).
Entrepôts de Données
Implémentation d'un Data Warehouse
● Relational OLAP (ROLAP)
❏ Données sont stockées dans un SGBD relationnel
❏ Un moteur OLAP permet de simuler le comportement d'un SGBD multidimensionnel

● Multidimensional OLAP (MOLAP)

❏ Structure de stockage en cube
❏ Accès direct aux données dans le cube

● Hybrid OLAP (HOLAP)

❏ Données stockées dans SGBD relationnel (données de base)
❏ + structure de stockage en cube (données agrégées)
Entrepôts de Données
ROLAP Idée:
● Données stockées en relationnel.
● La conception du schéma est particulière: schéma
en étoile,
● schéma en flocon
● Des vues (matérialisées) sont utilisées pour la
représentation multidimensionnelle
● Les requêtes OLAP (slice, rollup...) sont traduites
en SQL.
● Utilisation d'index spéciaux: bitmap
● Administration (tuning) particulier de la base

Avantages/inconvénients
● Souplesse, évolution facile, permet de stocker de
gros volumes.
● Mais peu efficace pour les calculs complexes
Entrepôts de Données
Multi-Dimensional OLAP

Idée
● Modélisation directe du cube
● Ces cubes sont implémentés comme des matrices à plusieurs
dimensions
● CUBE [1:m, 1:n, 1:p...] (mesure)
● Le cube est indexé sur ses dimensions
Avantages/inconvénients:
● rapide
● formats propriétaires
● ne supporte pas de très gros volumes de données
 Entrepôts de Données
HOLAP
.
Idée
● MOLAP + ROLAP
● Données stockées dans des tables relationnelles
● Données agrégées stockées dans des cubes.
● Les requêtes vont chercher les données dans les tables et les
cubes
Entrepôts de Données
Modèles de représentation des données

● Cubes
● Étoile
● flocon
Entrepôts de Données
Hyper Cube

Hypercube : BD multidimensionnelle
● Axes: dimensions (date, type de produits, région),
● Chaque cellule de l'hypercube contient une mesure calculée (vente de produit)
Entrepôts de Données
Hyper Cube

● Principe de base : ce sont les analyses des indicateurs qui intéressent l‟utilisateur
● 2 types d‟attributs : les dimensions et les mesures
❏ Les mesures
❏ Les dimensions
Entrepôts de Données
Opérations sur la structure des cubes
Entrepôts de Données
Opérations sur le contenu des cubes
Entrepôts de Données

Opérations entre cubes

 Entrepôts de Données
Représentation en Étoile

Une étoile est une façon de mettre en relation le dimensions et les faits dans un entrepôt de données
Entrepôts de Données

Représentation en Étoile

Avantages:
● Facilité de navigation
● Nombre de jointures limité

Inconvénients:
● Redondance dans les dimensions
● Toutes les dimensions ne concernent pas les mesures

167
 Entrepôts de Données
Conception d’un modèle en étoile
Etude cas
On vous demande de créer un data Mart (une étoile) pour l'analyse de l'activité des représentants
d'une entreprise de vente d'imprimantes. Le chef d'entreprise veut savoir ce qui se passe pour ses
vendeurs. Les employés font ils leur travail, quelle est la zone de couverture des vendeurs, ou sont
les endroits où les vendeurs sont le moins efficaces, quelle est la moyenne de ventes des
représentants, etc., etc. L'entreprise possède un système de gestion de ressources humaines, un
système de gestion des ventes et des feuilles de routes avec des informations concernant les
vendeurs : kilomètres parcourus, litres d'essence utilisée, frais de voyage, ventes, promesses de
ventes, etc.

168
 Entrepôts de Données

Conception d’un modèle en étoile

● Solution

Ce qu‟il faut savoir :

● D'où provient chaque champ ?
● Comment transite l'information ?
● Où trouver l'information voulue?

171
Entrepôts de Données

Représentation en Flocon

Modéliser existence des hiérarchies de dimensions et qu'elles sont reliées au faits, ça fait comme un flocon
 Entrepôts de Données

Conception d’un modèle en Flocon

Etude cas
On vous demande de créer un data Mart (une étoile) pour l'analyse de l'activité des
représentants d'une entreprise de vente d'imprimantes. Le chef d'entreprise veut savoir ce
qui se passe pour ses vendeurs. Les employés font ils leur travail, quelle est la zone de
couverture des vendeurs, ou sont les endroits où les vendeurs sont le moins efficaces,
quelle est la moyenne de ventes des représentants, etc., etc. L'entreprise possède un
système de gestion de ressources humaines, un système de gestion des ventes et des
feuilles de routes avec des informations concernant les vendeurs : kilomètres parcourus,
litres d'essence utilisée, frais de voyage, ventes, promesses de ventes, etc.

174
 Entrepôts de Données
Représentation en Flocon
Solution

● Le principe de la modélisation en flocon est de créer des hiérarchies de dimensions

● Avoir moins de lignes par dimensions.
● Augmenter la performance

175
Entrepôts de Données
Représentation Constellation

Constellation
Une constellation est une série d'étoiles ou de flocons
reliées entre eux par des dimensions.

Entrepôt de Données = constellation des étoiles ou

des flocons
Entrepôts de Données
Approche de Conception d'entrepôts de données

Top-Down : Elle consiste en la conception de tout l'entrepôt (ie : toutes les étoiles), puis en la réalisation de ce
dernier. Lourde, contraignante et la plus complète .

Bottom-Up : Elle consiste à créer les étoiles/flocons une par une, puis les regrouper par des niveaux
intermédiaires jusqu'à obtention d'un véritable entrepôt pyramidal avec une vision d'entreprise.

Middle-Out : c'est l'approche hybride, . Elle consiste en la conception totale de l'entrepôt de données (ie :
concevoir toutes dimensions, tous les faits, toutes les relations), puis créer des divisions plus petites et plus
gérables et les mettre en œuvre. Conseillée par les professionnels du BI

177
1. Michael Tranchan, Qu'est-ce que l'informatique décisionnelle ? https://business-
intelligence.developpez.com/tutoriels/quest-ce-que-la-bi/
2. Yazid Grim, Conception d'un entrepôt de données (Data Warehouse),
http://grim.developpez.com/cours/businessintelligence/concepts/conception-datawarehouse/
3. Didier Donsez. Janvier 2006. Principes et architectures des entrepôts de données
4. georges gardarin, Bases de données, eyrolles, 2003
5. Yazid Grim, OLAP, les fondamentaux, http://grim.developpez.com/articles/concepts/olap/
6. Silvera David, Utilisation de BIRT, http://dsilvera.developpez.com/tutoriels/Business-
Intelligence/utilisation-birt/
Séquence 4: Big Data, MapReduce et NoSQL
Bases De Données Avancées
Guidedi KALADZAVI
 Séquence 4 : Big Data, MapReduce et NoSQL

Contenu
•Introduction
•Big Data
•MapReduce
•NoSql
•Conclusion
 Introduction
Déluge de données et le Big Data
Le monde des e- notre e-monde
• e-administration
• e-commerce
• E-transport
• Les dossiers et fichiers scolaires, médicaux, sociaux, ou de police sont informatisés.
• Intensification des moyens de payement en ligne
• Essor phénoménal des réseaux sociaux
• Les objets domestiques ou urbains deviennent intelligents et se connectent à l' « Internet des objets ».
• ….
• Vers l‟Internet du tout connecté

Big data
Données telles que les solutions de stockage, gestion et de traitement ne suffissent plus ?
Introduction
Big data et aux nouveaux challenges informatiques

Ces volumes de données soulèvent des interrogations

• Le stockage
• La Gestion
• Le traitement
• L‟analyse
 Introduction
Infrastructures du Big Data / informatique du Big data
Séquence 4: Big Data, MapReduce et NoSQL
 Big Data
Déluge de données et le Big Data

Quelques facteurs de l‟avalanche de données

• Omniprésence du Web et d‟Internet
• Des capteurs connectés
• Des grandes installations scientifiques (CERN)
• Tous les nouveaux usages
• Etc.
• Vers l‟Internet du tout connecté
Big Data
Déluge de données et le Big Data
D’ici 2020
Aujourd‟hui

7 To de données par jours Objets connectés :

● 12 Milliards 2014
10 To de données par jours ● 50 Milliards en 2020
Internautes :
145 milliards d‟emails par jours
2.3 Milliards 2014
● 4 Milliards en 2020
100h de vidéos chaque minute
Data
● 40 ZétaOctets /an
Big Data
Déluge de données et le Big Data

À partir de quel moment peut-on parler de "Big Data" ?

Exemple
• 100 G représentent un faible volume de données pour Facebook
• Or, tout le monde ne possède pas un pétaoctet de données à analyser chaque jour
• Est-ce que cela signifie que seuls les GAFA (Google, Apple, Facebook, Amazon) sont en
mesure de faire réellement du big data ?
Big Data
Déluge de données et le Big Data

À partir de quel moment peut-on parler de "Big Data" ?

● une application web au départ:

❏ Génère 1 Go de logs/jour
❏ Fonction d‟analyse nombre pages/utilisateur: 1h/j pour 1 Go de logs
● l‟application populaire
❏ Génère 1000 Go de logs/jour
❏ Fonction d‟analyse : 1000 h/jour (impossible)
Big Data
Big Data et ses 3V

d‟autres V existent ...

Big Data
Big data et nouveaux besoins

Le déluge des données crée de nouveaux besoins, tant en matière d'infrastructures de stockage que
de calculs
• Quelle stratégie adopter pour distribuer les calculs entre les machines ?
• Comment distribuer les données entre les machines ?
• Comment agréger les résultats des différentes machines ?
• Que faire en cas de panne d'une des machines lors de l'exécution du calcul ?
• Comment faire en sorte que l'architecture déployée ne coûte pas une fortune ?
Séquence 4: Big Data, MapReduce et NoSQL

MapReduce
Big Data, MapReduce et NoSQL

• Introduction
• Big Data
• MapReduce
• NoSQL
• Conclusion
MapReduce
Qu’est ce que MapReduce ?

• Modèle de conception d‟algorithmes

• Cadre générique pour la parallélisation des traitements
MapReduce
Divisez pour mieux Régner

Principe
MapReduce
Un problème de Big Data

Map
• Itérer sur un grand nombre d‟enregistrements
• Extraire une information pertinente de chacun d‟eux
Reduce
• Regrouper et trier les résultats intermédiaires
• Agréger les résultats intermédiaires
• Produire le résultat final

But :Fournir une abstraction fonctionnelle pour les deux opérations

MapReduce
MapReduce et ses Ingrédients

● Structuration des données en pairs clé-valeur : (k,V)

● Deux fonctions

❏ Map :

❏ Reduce:
MapReduce

Plan d’exécution de MapReduce

 MapReduce
Étapes de MapReduce

4 Étapes
● Découper (SPLIT)
● Transformer (MAP)
● Grouper (SHUFFLE)
● Réduire(REDUCE)
 MapReduce
Penser en MapReduce

• Découper les données d‟entrée pour rendre l‟opération MAP parallélisable

• Définir les clés associées à notre problème
• Écrire le programme de l‟opération MAP
• Écrire le programme de l‟opération REDUCE
MapReduce
Exemple de problème MapReduce
 MapReduce
Exemple de problème Word Count

Étape 1 : Découper (SPLIT)

 MapReduce
Exemple de problème Word Count

Étape 2 : MAP, Pour chaque mot, générer la paire (MOT, 1)

 MapReduce
Exemple de problème Word Count

Étape 2 : MAP, Pour chaque mot, générer la paire (MOT, 1)

 MapReduce
Exemple de problème Word Count

Étape 3 : Grouper (SHUFFLE) groupement/tri

des tous les couples par clé commune
MapReduce
Exemple de problème Word Count
Étape 4 : REDUCE additionne toutes les valeurs associées à une clé
MapReduce
Schéma d’exécution de Mapreduce
MapReduce
Mapreduce et Word count !
MapReduce
Word count en MapReduce !
Séquence 4: Big Data, MapReduce et NoSQL

Hadoop
Hadoop: Mapreduce en Pratique
MapReduce en pratique !

Challenges
Hadoop: Mapreduce en Pratique
MapReduce en pratique !

Une infrastructure logicielle dédiée

 Hadoop
Hadoop et ses composants principaux

•
Hadoop: Mapreduce en Pratique

HDFS (Hadoop Distributed File System)

Le système de fichier distribué
Hadoop: Mapreduce en Pratique
Architecture d’un cluster HDFS

Maître/esclave
Hadoop: Mapreduce en Pratique
Architecture d’un cluster HDFS

Tolérance aux pannes

Hadoop: Mapreduce en Pratique
Architecture d’un cluster HDFS

Écriture d‟un fichier

Hadoop: Mapreduce en Pratique
Architecture d’un cluster HDFS

Lecture d’un fichier

 Hadoop: Mapreduce en Pratique

Framework
MapReduce
Hadoop: Mapreduce en Pratique
Framework MapReduce

Maître /esclave
Hadoop: Mapreduce en Pratique
Framework Mapreduce

Soumission et exécution d‟un job Mapreduce

Hadoop: Mapreduce en Pratique

Merci
Séquence 4 : Big Data, MapReduce et NoSQL
Séquence 4: Big data, MapReduce et NoSQL

• Introduction
• Big Data
• MapReduce-Hadoop
• NoSQL
• Conclusion
Qu’est ce NoSQL ?
Présentation
Depuis les années 70, la base de données relationnelle était l'incontournable référence pour gérer les données
d'un système d'information

Les années 2000, le big data et ses 3V (Volume, Velocity, Variety), le relationnel peut difficilement lutter contre
cette vague de données

Alors relâcher certaines contraintes lourdes du relationnel pour favoriser la distribution : d'où le "Not Only SQL".

NoSQL et ses Familles

• Orienté Clés-Valeurs
• Orienté-Colonnes
• Orienté-Documents
• Orienté-Graphes
NoSQL
Bases de données Relationnelles et NOSQL
Illustration

Il manque le lien entre les films et les artistes

NoSQL
Bases de données Relationnelles et NOSQL

Le système de référencement en relationnel

Permet de faire des jointures

NoSQL

Bases de données Relationnelles et NOSQL

Méthode générale : schémas entité/association

Le schéma E/A des films

NoSQL

Bases de données Relationnelles et NOSQL

Schémas relationnels

Exprime des contraintes : clé primaire, unicité (nom, prénom), typage, valeurs obligatoires.
Modélisation de bases NoSQL

Bases de données Relationnelles et NOSQL

Schémas relationnels

La contrainte d‟intégrité référentielle foreign key garantit la cohérence du référencement.

Modélisation de bases NoSQL

Bases de données Relationnelles et NOSQL

La normalisation relationnelle

En relationnel, toutes les données sont "à plat". Cela tend à multiplier le nombre de tables contenant les
informations sur une même entité
Exemple : pour représenter toutes les informations sur un film, il faut
• La table Film (une ligne pour le film)
• La table Artiste (une ligne pour le réalisateur, autant de lignes que d‟acteurs)
• La table Role (autant de lignes que de rôles)
• et la table Pays, et d‟autres encore…
Impact de la NORMALISATION.
• Il faut beaucoup d‟écritures , et autant de lectures pour reconstituer l‟information
Modélisation de bases NoSQL

Bases de données Relationnelles et NOSQL

Puissance du modèle semi-structuré

Les documents structurés ne sont pas soumis aux contraintes de normalisation.

Un attribut peut avoir plusieurs valeurs (en utilisant la structure de tableau)
Exemple
{
"title": "Pulp fiction",
"year": "1994",
"genre": ["Action", "Policier", "Comedie"]
"country": "Dakar"
}
En relationnel, il faudrait ajouter deux tables.
Modélisation de bases NoSQL
Bases de données Relationnelles et NOSQL
Puissance du modèle semi-structuré
Il est également facile de représenter des données régulières.

Table relationnelle = arbre de hauteur constante. Trois niveaux : ligne, attribut, valeur.
Modélisation de bases NoSQL

Bases de données Relationnelles et NOSQL

Plus puissant que la représentation relationnelle ?

Premiers constats
• pas du tout efficace : peut être utile pour échanger des informations ; pas pour les stocker.
• Dans une base relationnelle, les données sont très contraintes /structurées : on peut stocker séparément
la structure (le schéma) et le contenu (la base)
• Une représentation arborescente XML / JSON est plus appropriée pour des données de structure
complexe et / ou flexible
Modélisation de bases NoSQL
Bases de données Relationnelles et NOSQL
Documents structurés = imbrication des structures
Grâce à l‟imbrication des structures , il est possible de représenter dans une même unité un film
ett son metteur en scène.
{
"title": "The Social network",
Dans les bases documentaires : on "summary": "On a fall night in 2003, Harvard undergrad and \n
essaie de créer des unités programming genius Mark Zuckerberg sits down at his \n
d‟information autonomes pour limiter computer and heatedly begins working on a new idea. (...)",
les écritures et éviter d‟avoir à faire "year": 2010,
des jointures. "director": {"last_name": "Sali",
"first_name": "David"},
Les systèmes NoSQL sont conçus "actors": [
pour passer à l‟échelle par {"first_name": "Jesse", "last_name": "Eisenberg"},
distribution. C‟est en partie {"first_name": "Rooney", "last_name": "Mara"}
incompatible avec les jointures et ]
}
les transactions
Modélisation de bases NoSQL
Bases de données Relationnelles et NOSQL

On peut coder toutes

les informations sur un film.
Séquence 4: Big Data, MapReduce et NoSQL

Familles NoSQL
Familles NoSQL

Les Clés-valeurs
Familles NoSQL

Les Clés-valeurs : Requêtes

Familles NoSQL

Les Clés-valeurs

Solutions techniques
Familles NoSQL
Orienté - colonnes

Stockage orienté Colonnes

Familles NoSQL

Orienté - colonnes
Familles NoSQL
Orienté - colonnes

Solutions techniques
Familles NoSQL

Orienté-documents

Stockage orienté document

Familles NoSQL

Orienté-documents

Stockage orienté document

Familles NoSQL
Orienté-documents

Solutions techniques
Familles NoSQL

Orienté-Graphes
Familles NoSQL

Orienté-Graphes
Familles NoSQL
Orienté-documents

Solutions techniques
NoSQL
Modèles NoSQL
● Forces ● Faiblesses
● Plus besoin de jointure ( ?): il est inutile de faire des ● Chemin d‟accès privilégié : les films apparaissent
jointures pour reconstituer l‟information puisqu‟elle près de la racine des documents, les artistes sont
n‟est plus dispersée, comme en relationnel, dans enfouis dans les profondeurs ; L‟accès aux films
plusieurs tables. est donc privilégié
● Plus besoin de transaction ( ?) : une écriture (du ● Les entités ne sont plus autonomes : pas moyen de
document) suffit ; une lecture suffit pour récupérer créer un réalisateur s‟il n‟y a pas au moins un film.
l‟ensemble des informations. ● Redondance : la même information doit être
● Adaptation à la distribution . Si les documents sont représentée plusieurs fois, ce qui est tout à fait
autonomes, il est très facile des les déplacer pour fâcheux (Quentin Tarantino est représenté deux
les répartir au mieux dans un système distribué. fois).
Modélisation de bases NoSQL
Modèles NoSQL
Les autres inconvénients

Pas de langage de requête ?

Il faut faire un programme pour tout, même la moindre mise à jour !

Pas de schéma ?
On peut mettre n‟importe quoi dans la base ; c‟est l‟application qui doit faire les contrôles et les corrections.

Pas de transaction ?
Ne convient pas pour beaucoup d‟applications (commerce électronique).
 Modélisation de bases NoSQL

Bilan, NoSQL ou relationnel ?

Quand utiliser (ou pas) une base documentaire ?

• Des données très spécifiques, peu ou faiblement structurées : texte, données multimédia, graphes)
• Peu de mises à jour, beaucoup de lectures. ; la redondance ne pose pas de problème.
• on veut traiter de très gros volumes de manière “scalable”
• De forts besoins en temps réel
•
NoSQL = Not Only SQL. Personne (de sérieux) ne prétend que ces systèmes vont remplacer les systèmes
relationnels, sauf pour certaines niches (Entrepôts de Données, Big data) pour Buisness Intelligence
 Références
1. Big Data : premiers pas avec MapReduce, brique centrale d'Hadoop ,
https://www.journaldunet.com/developpeur/outils/mapreduce.shtml
2. Mickael BARON, Tutoriel d'introduction à Apache Hadoop ,
http://mbaron.developpez.com/tutoriels/bigdata/hadoop/introduction-hdfs-map-reduce/
3. Gartner et le Big Data: http://www.gartner.com/technology/research/big-data/.
4. https://www.lebigdata.fr/hadoop
5. http://www.opentuto.com/hadoop-pour-les-nuls/
6. Réalisez des calculs distribués sur des données massives, https://openclassrooms.com/courses/realisez-
des-calculs-distribues-sur-des-donnees-massives/familiarisez-vous-avec-hadoop
7. R u d i Br u c h e z, Les bases de données NoSQL et le Big Data : Comprendre et mettre en œuvre,
Eyrolles, 2013, 2015, ISBN : 978-2-212-14155-9