École Nationale des Sciences Informatiques

Conception de Bases de Données

II1
Cours Intégré de 45H
(15 semaines de 3 heures)
[Link]@[Link]
 Plan du cours

• Introduction aux Bases de données

• Les systèmes de Fichiers et les SGBD
• Les principaux modèles de données
• Conception d’une base de données relationnelle
• Algèbre relationnelle
• Langage de requêtes SQL
• Les Bases de données No SQL
Conception de BD
2
 I. Introduction
• Volume important de données (Banques, bibliothèques, … etc.)
– Problème : comment stocker et manipuler les données?
– Données  Bases de données (BD)
– Logiciel  Système de Gestion de bases de Données (SGBD)
• I.1. Bref Historique des SGBD?
– Années 1960s:
• Organisation classique en fichiers.
• 1ère génération de SGBD (hiérarchiques puis réseaux).
– Années 1970s:
• 2ème génération de SGBD – SGBD relationnels (commercialisés en
1980).
– Années 1980s:
• 3ème génération de SGBD – SGBD orientés objet
– Années 1990s:
• 4ème génération supportant le web et le multimédia

Conception de BD
RK 3
 I. Introduction
• I.2. Pourquoi les BD?
– Pour pallier aux problèmes des systèmes traditionnels (systèmes de
fichiers):
• Redondance des données:
– Particularisation des fichiers en fonction des traitements.
• Insécurité des données:
– Accès non autorisés
– Abandon d’un ensemble d’opérations
• Incohérence des données:
– MAJ d’une partie des données redondantes
– Non respect des contraintes d’intégrités

Conception de BD
RK 4
 Limites des systèmes de fichiers

Fichiers Applications

BP 2536
Facturation

BP 2536 Commercial

BP 2536
Prospects
Délais de mise à jour

Conception de BD
RK 5
 Avec base de données

Base de données Filtre (vues) Applications

BP 2536 Facturation

Commercial

Prospects

Conception de BD
RK 6
 Propriétés d’une BD

– Une BD permet de :
• Combiner toutes les données
• Centraliser les données
• Partager les données entre plusieurs traitements
– Limitation de la redondance des données
• Appliquer les MAJ qu’une seule fois
• Respecter les contraintes d’intégrités (age d’une personne doit être
un nombre positif)
• Sécuriser les accès
• Abandonner facilement les opérations erronées non validées
• Résister aux pannes éventuelles

Conception de BD
RK 7
 I.3. Qu’est ce qu’une BD?

• Une Base de données (BD) est :

– Collection de données structurées, sures, cohérentes, et partageables.
• Correspond à une représentation fidèle des données et de leur structure avec
le minimum de contraintes imposées par le matériel
• Susceptible d’être utilisée par toutes les applications sans duplication

• Un SGBD est un logiciel permettant de:

– Décrire - la confidentialité
– Manipuler en assurant - l’intégrité
– Consulter les données - la sécurité
– Définir des CI - le partage des données

Conception de BD
RK 8
 I.4. Avantages des BDs

• Usage multiple des données.

• Uniformisation de la saisie (et standardisation des traitements).
• Une grande flexibilité des modifications.
• Facilité d’accès aux données: meilleure disponibilité.
• Protection contre les données erronées et les pannes système.
• Réduction du volume des données stockées: une information n’est stockée
qu’une seule fois, pas de redondance.
• Chaque application ne voit que ce qu’elle doit voir

Conception de BD
RK 9
 SGF v.s. SGBD

Figure prise du livre de Rob & Coronel, Database Systems: Design, Implementation,
and Management, Sixth Edition Conception de BD
RK 10
 Vision simplifiée d’un SGBD

SGBD externe
SGBD interne

Terminaux

Programmes Gestionnaire de fichiers

Conception de BD
RK 11
 I.5. Architecture fonctionnelle type d’un SGBD
• Architecture Ansi/Sparc – 3 niveaux:
– Niveau externe: le niveau d’expression des besoins des users. Il formalise la
manière dont les utilisateurs voient les données.
• Environnement de programmation / interfaces graphiques / deboggueurs / …
– Niveau conceptuel: décrit la structure de la base de données globalement à
tous les utilisateurs (limite la redondance) .
• Compilation / optimisation des requêtes / maintien de l’intégrité / gestion de la
confidentialité.
– Niveau interne: relatif à la mémoire physique
• Gestion de la mémoire secondaire (fichiers), schéma, index
• Gestion de la concurrence
• Reprise après panne

Conception de BD
RK 12
 Architecture à niveaux Ansi/Sparc

Niveau Externe Schéma A Schéma B Schéma C

(vue d’un user)

Correspondance
externe/conceptuelle

Description
Niveau Conceptuel
Unique

Correspondance
Conceptuelle/physique

Niveau Interne Schéma interne

(vue physique)

Conception de BD
RK 13
 Avantage de la séparation en 3 niveaux

• Indépendance physique: on peut modifier l’organisation des données sans

toucher les programmes de traitement.
– Limiter les modifications liées aux changements de matériel, de système
d’exploitation ou des logiciels utilisés.

• Indépendance logique: une modification de l’organisation logique des

fichiers (e.g. une nouvelle rubrique) n’entraîne pas de modification dans les
programmes d’application non concernés.
– la vision de chaque utilisateur est indépendante des visions des autres
utilisateurs et n ’est pas modifiée par les modifications du schéma
conceptuel qui ne le concernent pas.
Conception de BD
RK 14
 I.6. Fonctions des SGBD
• Description des données : Langage de définition de données (LDD)
• Recherche des données
Langage de
• Mise à jour des données Manipulation de
• Transformation des données Données (LMD)

• Contrôle de l’intégrité des données – respect des contraintes d’intégrité:

– Schéma = structure + contraintes
– Formule logique (E.g. Nom character 20, non NULL; age integer between 0 and
120; debit <= credit).
– But: protéger les données
• Gestion de transactions (atomicité des transactions) et sécurité (mots de passe,
etc.)

Conception de BD
RK 15
 Architecture Fonctionnelle de Référence
Requête
Analyse syntaxique
ANALYSEUR Analyse sémantique
Gestion des schémas

Modification de requêtes
META-BASE TRADUCTEUR Contrôle d'intégrité
Contrôle d'autorisation

Ordonnancement
OPTIMISEUR Optimisation
Élaboration d'un plan
Exécution du plan
Plan d'Accès EXECUTEUR Méthodes d'accès
Contrôle de concurrence
Atomicité des transactions

BD

Conception de BD
RK 16
 Types de SGBD
• SGBD Hiérarchique:
– Les données sont représentées dans la base sous forme de structure
arborescente.
• Manipulation des données (balayage ascendant/descendant).
– E. g. IMS-IBM
• SGBD réseau:
– Les données sont représentées dans la base sous forme d ’un graphe
quelconque.
– Les programmes:
• ne sont pas indépendants de la structure logique de la base
• doivent indiquer le chemin d’accès aux données
• utilisent un langage complexe pour travailler avec les données.

Conception de BD
RK 17
 Types de SGBD

• SGBD relationnel:
– fondé sur la théorie mathématique des relations;
– représentation très simple des données (tables);
– langage non procédural (déclaratif), puissant et simple d’emploi
– SQL est un standard parmi ces langages
– dominent le marché:
• Exemples : Oracle, DB2, SQLServer, Access, DBase, Paradox, … etc.
• SGBD Objet:
– enregistre les données sous forme d’objets
– E. g. O2
• … les « Data WareHousing »!

Conception de BD
RK 18
II. Les Systèmes de Fichiers et
les SGBDs

Conception de BD
RK 19
II. 1. Introduction aux fichiers (1)

SGBD
Demande Enregistrement
d’enregistrement mémoire
mémoire retourné

Gestionnaire
de Fichiers
Demande Page
de page mémoire
mémoire retournée ?
Gestionnaire
de disque
Opération Données
d’entrée/sortie lues sur
sur disque le disque

BD

Conception de BD
RK 20
 II. 1. Introduction aux fichiers (2)
• Fichier
 Notion introduite dans les années 1950s afin de simplifier
l’utilisation des mémoires secondaires des ordinateurs,
fournir des récipients de données plus manipulables aux
programmes.
• Système d’exploitation : contient un SGF standard.
• SGBD : deux niveaux indépendants (logique et physique)
 Traiter et conserver des quantités importantes de
données, et de partager ces données entre plusieurs
programmes.
 En général, n’utilise pas le système de fichiers standard
pour des raisons de performance;
Basé au niveau interne des SGBD, complété par des
méthodes d’accès spécifiques.
 offre d'autres fonctionnalités :
 concurrence, reprise sur pannes,
Conception de BD confidentialité…
RK 21
II. 1. Introduction aux fichiers (3)

• Système de fichiers propre au SGBD pour quelles

données
 Données

 Informations (afin de gérer les données)

 sur le schéma logique

 structure des données, autorisation,…

Information sur le schéma physique

 Metabase

 statistiques
Conception de BD
RK 22
 Les couches logiciels

Conception de BD
RK 23
 II.3. Notions de base sur les
fichiers et SGF (1)

• Fichier (file) = ensemble d'informations stockées sur une

mémoire secondaire (MS), structurées en enregistrements.
– Pourquoi sur MS? La mémoire centrale (MC) est limitée en
taille, chère, et volatile (à conserver toujours sous tension,
sinon perte des informations).
– Les MS (disques, disquettes, ...) sont peu coûteuses, non
volatiles et de grande capacité. Mais elles ne sont pas
accessibles par le processeur central des ordinateurs. Il faut
transférer l'information de la MS vers la MC pour pouvoir la
traiter
• Problèmes:
– Les transferts entre MC et MS
Conception de BD (appelés entrées-sorties ou
RK 24
E/S) sont lents (millisecondes –10 ).
-3
 II.3. Notions de base sur les fichiers
et SGF (2)
• Enregistrement (article, record) = élément d'un fichier, qui est
l'unité logique de transfert MC-MS, et l'unité de traitement des
programmes exploitant ce fichier.
 Unité de transfert avec la mémoire secondaire : Blocs
(taille fixe)
 Plusieurs blocs forment un segment
• Format des enregistrements du fichier = description de la liste
des données (attributs, champs, data items, attributes, fields)
contenues dans chaque enregistrement.
 Les champs sont de types élémentaires (entier, caractère,
pointeur,…)(nom, âge, adresse)
 Exemple: format pour un fichier d'étudiants:
Conception de BD
RK 25
nom prénom n°carte datenaissance sexe adresse
II.3. Notions de base sur les fichiers
et SGF (3)
• Fonctions d'un système de fichiers (SGF):
– Fonctions élémentaires (enregistrement)
• ajouter/insérer/chercher/mettre à jour/supprimer
– Fonctions globales (fichier):
• créer/détruire/lister/trier/copier/fusionner deux
fichiers,...
– Gestion
• De la protection contre les pannes;
• de la confidentialité des fichiers;
• de la concurrence (partage simultané des fichiers).
• Les appels aux fonctions SGF sont effectués au moyen de
requêtes dans un programme.
– Les requêtes permettent de modifier le contenu des fichiers
• Les SGBD permettent d'effectuer ce qu'offrent les SGF sous
une autre forme, beaucoup plus puissante (traitements plus
globaux), ainsi que d'autres fonctions (gestion des données et
non d'enregistrements, liens entre
Conception de BDfichiers, ...).
RK 26
• Des produits à mi-chemin entre SGF et SGBD existent sur le
 II.5. Organisations et méthodes
d'accès
• Comment sont organisés les enregistrements sur disque --
organisation de fichiers.
 Selon l’allocation de l’espace disque qu’utilise les SGF
 Organisation séquentielle: les enregistrements d’un
même fichier sont contigus.
 Organisation séquentielle chaînée: les enregistrements
d’un même fichier sont chaînés entre eux.
• Une méthode d'accès est une façon d'accéder à un
enregistrement dans un fichier.
 Selon la valeur d'un attribut de l'enregistrement.
 2 méthodes d’accès: l'accès séquentiel et l'accès sélectif
 Choix de la meilleure méthode d’accès
Conception de BD
RK 27
• Les organisations et accès des SGF adaptés.
 II.5.1 Organisation Séquentielle
• Consiste à mettre les enregistrements dans le fichier les uns
après les autres selon leur ordre d'arrivée (de création), sans
mémoriser l'endroit où ils ont été écrits.
– Ne permet que l'accès séquentiel.
– Elle est efficace dans les cas où les traitements nécessitent
de lire ou d'écrire tous les (ou une grande partie des)
enregistrements du fichier.
• Le blocage d’enregistrements:
– 1 bloc = n enregistrements
– Lorsque plusieurs enregistrements sont transférés ensemble
lors d’un échange, on dit qu’ils sont bloqués.
– Le facteur de blocage est le nombre n d’enregistrements par
bloc.
• Calculé de manière à occuper au mieux les blocs
RK
physiques Conception de BD
28
•
 II.5.1 Organisation Séquentielle
(suite)
• Fichier Séquentiel (interface)
– lire premier
– lire suivant
– écrire
– supprimer
• Avantages de l'organisation séquentielle avec
blocage:
– excellente organisation pour l'accès séquentiel :
1/b E/S par instruction en moyenne (on ne peut
pas faire mieux)
– très bonne utilisation des MS
• Inconvénients:
– Impossibilité d'insérer ou de supprimer un article
(sauf recopie de tout le fichier)
– pas d'accès sélectif
Conception de BD
RK 29
 II.5.2. Organisation Aléatoire (1)

• Organisation séquentielle + format fixe des

enregistrements
• Organisation relative:
– Les enregistrements ont des numéros relatifs (1, 2, 3, ...),
appelés clés, qui est leur numéro d'ordre dans le fichier.
• #enregistrement  adresse
• L'adresse relative dans le fichier de l'enregistrement de
numéro i est :

(i-1)*longueur de l'enregistrement.
– Méthodes d'accès: sélective sur le numéro et
Conception de BD
RK 30
éventuellement séquentiellement.
 II.5.2. Organisation aléatoire (2)

• Le fichier est constitué de blocs qui contiennent les

enregistrements.
• Chaque enregistrement possède un attribut (ou liste
d'attributs) qui identifie l'enregistrement, et qui est appelé clé
de l'enregistrement.
• Une fonction est associée au fichier : n°bloc = f(clé).
– Exemple : modulo le nombre total de blocs du fichier
• Avantage: accès direct aux blocs en temps constant
• Inconvénient: Extension d’un fichier
– Nécessité/connaissance de la taille du fichier, ou le

RK déplacement du fichierConception
lors de son extension
de BD
31
 Le Hachage
• Fichier à N enregistrements
• Table T de N pointeurs vers les blocs de données
• Fonction mathématique H
– H : domaine de la clé  [0..N-1]
– Un enregistrement de clé K se trouve dans le bloc pointé par
T[H(K)]
• Accès direct au bloc
• Statique/dynamique (moins utilisé)
– Dynamique: selon le nombre d’enregistrements, la taille de T est
1, 2, 4, 8, …, 2N
• Gain de place
• Collision possible
0
1
Ki H(K i )
2
3
T
Conception de BD
RK 32
 Techniques de débordement de
blocs

• Il y a plusieurs solutions pour le choix d'un nouveau bloc de

débordement à associer à un bloc qui déborde:
– bloc(s) suivant. Il faut alors noter la liste des blocs de
débordement dans l'en-tête du bloc, ou chaîner les
enregistrements ayant débordé;
– blocs de débordement spéciaux. On chaîne les blocs de
débordement au bloc qui déborde;
– seconde fonction pour les débordements. On note si le
bloc a débordé. Cette solution a l'avantage de répartir les
gros débordements, mais elle multiplie les déplacements
Conception de BD
RK des têtes de lecture/écriture. 33
Organisation aléatoire (suite)

• Avantages:

– La clé peut être quelconque.

– S'il n'y a pas de débordement, très bonnes

performances: 1 E/S par lecture.
• Inconvénients:

– S'il y a de nombreux débordements, les performances

se dégradent.
– Le taux de remplissage est faible (environ 75%).

– Taille fixe du fichier (recherches sur le hachage).

Conception de BD
RK – L'accès séquentiel selon l'ordre des clés impossible. 34
 II.5.3. Organisation indexées
(1)
• Supposant qu’on a :
– Le fichier est trié suivant une clé
– Les enregistrements sont chaînés à l’aide de pointeurs
• Insertion
– Il y a de la place dans un même bloc que
l’enregistrement précédent: l’enregistrement à insérer
est dans l'ordre de la clé
– dans un autre bloc en cas d'absence de place
• Suppression
– simple si on ne cherche pas à compacter
• Problèmes
1. Les mises à jour sont rapidement compliquées
2. Ne marche bien que si la taille du fichier est à peu près
connue.
3. ACCES TROP LENTS  INDEX (le plus courant)
RK Fichier de données + table d’index
Conception de BD
35
 Index

• Index : Structure de données permettant d’accélérer

certains accès
– Deux champs: la clé d’index et l’adresse du bloc de
données contenant la clé.
• NB: la clé est la valeur de un ou plusieurs attributs du fichier
• Index dense :
Index dans lequel chaque valeur de la clé est représentée
(nécessaire quand le fichier n’est pas trié)
nombre d'entrées dans l'index = nombre d‘enregistrements
• Index non-dense
– un index non dense impose un fichier trié
DENSITE / EFFICACITE / ESPACE /
• Solution : index non dense avec une entrée par bloc
– Mise à jour de la base
– Mise à jour des index
Conception de BD
RK 36
 Les opérations sur les index

Recherche : parcours de l’index + une lecture

Insertion

• index dense : insérer la clé dans l’index si elle n'y est pas

• index non dense : pas de changement dans l'index si

l'insertion est réalisée dans un bloc existant. Sinon, insérer la

première clé du nouveau bloc dans l’index.

Suppression

• dense : détruire la clé dans l'index

• non dense : la plupart du temps pas de changement

Conception de BD
RK 37
 Index dense --Exemple

ier avec un index trié dense (i.e., toutes les clés existantes y sont répert

Conception de BD
RK 38
 Index hiérarchisé --Exemple

vec un index hiérarchisé à deux niveaux; les blocs d'index contiennent 4

s d'enregistrements 3 enregistrements. La recherche d'une clé coûte 2 E

Index

Niveau des enregistreme

Conception de BD
RK 39
 Coût de recherche dans un index

• Recherche rapide d'une entrée de l'index dont on connaît la

clé.
• Index comprenant n blocs (chaque bloc contenant c clés, c
étant généralement compris entre 10 à 100 selon la longueur
des clés)
• La recherche nécessite :
– si l'index est non trié: n/2 lectures en moyenne
– si l'index est trié et la recherche dichotomique: log2(n)
lectures en moyenne
– si on indexe les blocs d'index (l'index est trié et
hiérarchisé à plusieurs niveaux) une E/S par niveau de
l'index. Conception de BD
RK 40
 Autres Index
 1. Index primaire
Sur un attribut clé : un enregistrement au plus pour chaque
valeur de la clé
• 2. Index secondaire
Sur un attribut non clé (en général dense)
• 3. Index croisé sur un ensemble d’attributs
Fichier inverse indexé sur tous ses attributs
• 4. Quand l’index grossit (e.g. index dense)  stocker
l’index dans un fichier
– On peut le trier et indexer lui-même.
– Dans chaque bloc, on note la clé la plus petite, et on
construit une table.
– Le fichier d’index est stocké, comme les enregistrements,
sur mémoire secondaire, et il est découpé en blocs qui
constituent l'unité de lecture et d'écriture.
Conception de BD
RK  Idée des B-tree 41
 Les index secondaires

• Objectif: permettre l'accès par plusieurs attributs (ou

groupes d'attributs) différents et qui ne sont pas

nécessairement identifiants.

• Par exemple sur un fichier Etudiant, accéder par le numéro

de carte, par le nom (homonymes possibles), par l'année de

naissance, ...

• Le fichier a une organisation quelconque.

• Pour chaque attribut (ou groupe d'attributs), appelé clé

RK secondaire, on crée unConception

[Link] Ces
BD index sont appelés 42
 Index secondaire --Exemple

Conception de BD
RK 43
• Avantage des index secondaires:
– Plusieurs accès sélectifs selon des attributs différentes
possibles, en plus des accès dus à l'organisation de base du
fichier.
• Inconvénients:
– Multiplier les index secondaires multiplie les E/S lors des
mises à jour des fichiers.
• Il n'est intéressant de faire un index sur une clé que si:
– le nombre d'accès en lecture sur cette clé est très supérieur
au nombre de mises à jour (suppressions, insertions,
modifications de l'attribut clé secondaire) d'enregistrements
– la valeur de la clé est stable (rarement modifiée)
– le "pouvoir sélectif", p, de la clé (nombre total de valeurs
prises par la clé dans le fichier) est supérieur au facteur de
blocage des enregistrements. En effet, une recherche
séquentielle des enregistrements répondant au critère:
attribut = valeur, coûte: N/b E/S
• La même recherche via un index secondaire sur cet
Conception de BD
RK attribut coûte en moyenne: v + N/p E/S (v=nombre de 44
Les méthodes d’accès --Résumé

• Comment accéder aux emplacements des

enregistrements?
• Quelques méthodes d’accès:
– Séquentielle si organisation séquentielle
– Séquentielle chaînée si séquentielle indexée
– Calculée si organisation aléatoire
– Relative si organisation relative
– Directe si adresse physique
connue
– Indirecte si 1er accès donne
adresse du second
• Un SGF gère quelques méthodes
• Ces méthodes sont parfois particulières au
RK SGF
Conception de BD
45
 Conclusion
• Contrairement au SGF, avec un SGBD:
– l’organisation interne des données est transparente
– les applications manipulent des structures de données logiques

 indépendance logique/physique
• Chaque SGBD a son propre SGF avec ses caractéristiques:
– Les fichiers sont souvent de taille fixe
– des organisations et des accès appropriés
• méthode indexée (données + index avec clé): la plus
courante
implantations différentes selon le SGBD
– Arbre-B les plus utilisés dans les SGBD
• Hachage statique très utilisé

Conception de BD
RK 46
 III. Les principaux modèles de
données

1. Introduction

2. Le modèle hiérarchique

3. Le modèle réseau

4. Le modèle Entité-

Association

5. Le modèle relationnel
Conception de BD
RK 47
 III.1 Introduction aux modèles de
données
• La vue conceptuelle:
– la représentation de l’ensemble des informations contenues
dans la base de données.
– Vue globale de la BD
– Définie par un schéma conceptuel: (des entités, des
attributs, des relations, des contraintes d'intégrité, …)
• le résultat de la modélisation de l’entreprise.
• écrit au moyen de LDD conceptuel (la modélisation des
données de manière abstraite, indépendamment de la
manière dont elles seront stockées physiquement.)
– Elle se fait indépendamment de toute référence aux
représentations des champs en mémoire, à l’indexage,
aux pointeurs,…bref à l’implémentation en machine.
 Modélisation sémantique au
Conception de BD problème de la
RK 48
conception de la base de données.
 III.2. Modèle Hiérarchique

III.2.1 Principes
• Modèle hiérarchique (1960)
• Schéma de base arborescent dans lequel les relations entre les
éléments d’un niveau à ceux du niveau immédiatement
inférieur sont de type un à « plusieurs ».
• Il permet une représentation approchée du réel au prix d’une
redondance plus ou forte des données.
• Il impose un chemin d’accès unique à chaque élément de
données (depuis la racine).
• Inconvénient majeur: pas de séparation nette entre le niveau
conceptuel (la représentation du monde) et le niveau physique
Conception de BD
(c-à-d
RK l’indépendance entre données et traitements n’est pas
49
 III.2.1 Principes (suite)

• Concepts du modèle hiérarchique

 Champ (field): plus petite unité de données possédant un

nom.
 Segment: collection de champs rangés consécutivement

dans la base, portant un nom.

une occurrence constitue l’unité d’échange entre la BD

et les applications
 Arbre de segments (segment tree): collection de
segments reliés par des associations père-fils sous la

RK
forme d’hiérarchie. Conception de BD
50
 III.2.2 Caractéristiques du modèle
• Permet aux type de segments d’être reliés par
des relations parents-enfants (1:n) Enseignant
1
n

Etudiant

• Les structures qui traduisent ces éléments sont

fonction du type de requêtes à réaliser:

Etudiant Enseignant cours Enseignant Cours

Cours Cours Enseignant

Cours Etudiant Enseignant Etudiant
Enseignant Etudiant Etudiant

Conception de BD
RK 51
 III.2.3 Limitations du modèle

• Difficulté d’exprimer des relations de type n:m

Enseignant Enseignant Etudiant

n
m
Etudiant Etudiant Enseignant

• Une modification de l’utilisation peut entraîner une perte

d’efficience du système.
• Un espace de stockage très important.
• L’impossibilité d’exprimer des parents multiples
• la difficulté d’exprimer des relation cyclique
Conception de BD
RK 52
 III.2.4 Avantages du modèle

• Les BDs modélisent des informations du monde réel

 Souvent au travers des hiérarchies.

 Plusieurs applications nécessitent uniquement des

relations de type 1:n

• le modèle hiérarchique est conceptuellement simple à

comprendre et à utiliser.

• Le premier support d’IBM qui ade BD

Conception introduit le premier système
RK 53
 Exemple

Conception de BD
RK 54
 Exemple

Conception de BD
RK 55
 III. 3. Le Modèle Réseau

III.3.1 Principe
• Le modèle réseau apporte plus de souplesse car il permet de
créer des liens logiques entre des faits ou objets différents.
• L’accès aux données n’est pas limité aux chemins
descendants/ascendants du modèle hiérarchique, peut se faire
de plusieurs façons différentes pour une même donnée.
• Article (Record): collection d’atomes (champs) –type d’articles
• Lien (Set): type d’association orientée entre articles
propriétaires
RK
vers n articles membres.
Conception de BD
56
 III.3.2 Caractéristiques

• Les liens entre les articles sont de type 1:n et représentés par
une flèche portant le nom du lien.
• La différence majeure avec le modèle hiérarchique est la
capacité du modèle réseau à représenter les parents multiples
d’un type d’articles.
• Exemple:
Compagnie Division

Dépôt Fournisseurs service

Pièces détachées
Employés

Conception de BD
RK 57
 III.3.2 Caractéristiques (suite)

• Le modèle réseau de base exclut les liens de

type n:m.
– Seules sont permises les liens de type 1:n avec
des parents multiples provenant de différent types
d’articles.
Fournisseurs Fournisseurs Pièces détachées

Pièces détachées Fournisseurs-Pièces

Conception de BD
RK 58
 En conclusion ….

• Le modèle réseau est une évolution logique du

modèle hiérarchique.
• Il a permis d ’éliminer les redondances de données
et la création de chemin d ’accès multiples à une
même donnée.
• Il est née des recherches du groupe Codasyl
(Conference on Data System Language) entre 64
et 71.
• Ne permet pas la prise en compte réelle des
phénomènes les plus complexes.
Conception de BD
• Ne
RK
permet pas de résoudre le problème
59
 Schéma exemple

Conception de BD
RK 60
 III.4. Modèle Entité / Association
(suite)
• Type d’entité (TE): représentation abstraite d’un ensemble
d’entités perçues comme similaires, ayant les mêmes
caractéristiques et le même comportement.
– Exemple: toutes les personnes (PERSONNE), les véhicules
(VEHICULE), les clients (CLIENTS), …, etc.
– Un attribut associe à chaque entité une valeur
appartenant à un domaine.
• Type d’association (TA): représentation d’un ensemble
d’associations ayant la même sémantique et décrites par les
mêmes caractéristiques.
– Nombre de liens autorisés entre entités
Conception de BD
RK 61
–
 Ali Khaled
Jamel

Salem Kamel

modélisé par

Personne

Personne Achète Maison

Acheté
Acheteur
(Rôles)

Conception de BD
RK 62
 III.4.1 Exemples d’associations

• Unaire: 1 Mari

Personne Marié

1 femme

• Binaire: donne Cours

Enseigna
nt

Conception de BD
RK 63
 III.4.1 Exemples d’associations
(suite)
• Plusieurs associations entre 2 types d’entité.
Personne

possède conduit

• Ternaires
Fournisseur Voiture

Client Achète Produit

Conception de BD
RK 64
 III.4.2. Diagramme
Entité/Association
• Un graphe entité–association constitue une technique pour
représenter la structure logique d’une base de données de
manière graphique:
 Moyen simple et facilement compréhensible pour
communiquer les caractéristiques principales de la
conception d’une BD particulière.
 Chaque entité est représentée par un rectangle contenant
le nom du type de l’entité correspondante.
 Chaque type d’association est représenté par un losange
contenant le nom de l’association considérée.
 Les attributs attachés aux entités sont représentés par des
ellipses (en pointillé).
 Dans le diagramme E/A les
Conception clés sont soulignés
de BD
RK 65
 III.4.3. Types des associations
• Association binaire (A), reliant deux entités (E et F)
– de type 1:1 (un-à-un): si à une entité de E peut
correspondre par l’association A au plus une entité de F, et
réciproquement.
– de type 1:n (un-à-plusieurs): si à une entité de E peut
correspondre par l’association A plusieurs entités de F
mais à une entité de F au plus une entité de E
– de type n:m (plusiuers-à-plusieurs): si à une entité de E
peut correspondre par l’association
N:m A plusieurs entités de F
et réciproquement.
Personne Voiture
Possède

– Une personne peut posséder plusieurs voitures, et

réciproquement une voiture peut être possédée par
plusieurs (bien très peu fréquent!)
Conception de BD
RK 66
 III.4.3. Types des associations --
Cardinalité
N:m
Personne Possède Voiture

• Combien de voitures (minimum) une personne peut avoir?

• Combien de voitures (maximum) une personne peut avoir?
– Cardinalité d’un couple entité-association (E, A) est
(m, M), où
• m (resp. M) est le nombre minimum (maximum)
d’associations pouvant exister pour l’entité E.
Type d’association
Cardinalité
N:m
Personne (0:n) Possède
(1:n)
Voiture

Entité
Entité Association
Conception de BD
RK 67
 III.4.4. Les Attributs

• Décrit l’information (les propriétés) à

conserver sur:
– Une entité
– Une association
– Un attribut.

Salaire Personne Mariée à

NomPrénom
Date mariage

Jour Mois année

Conception de BD
RK 68
 III.4.4. Attributs (suite)
• Simple (atomique) non décomposé de valeur atomique
(jour)
• Composé: décomposé en d’autres attributs (valeurs
composées)
Exemples: date (jour,mois,année), adresse
( rue,ville,codep)
• Mono-valué: une seule valeur par occurrence
Exemples: nom, date de naissance
• Multi-valué: plusieurs valeurs par occurrence
Exemples: prénoms, téléphones
• Obligatoire: une valeur au moins par occurrence
Exemples: noms, prénoms,
Conception de BD
•RK Manquant/optionnel: peut ne pas prendre de valeur 69
 III.4.5. Identifiants des TE et TA
• Identifiant (clé): un attribut ou un ensemble minimum
d’attributs dont les valeurs identifient de manière unique les
instances d’une entité (resp. association)
– Exemple : ETUDIANT( n°E, nom, prénoms, ddn, adresse)
• n°etudiant forme une clé. Par contre nom+prénom ne
forment pas une clé car deux étudiants ne sont pas
époux employé (si
distingués par les instances du TE étudiant
Salaire Person Mariée à
l’un ou l’autre sont toujours uniques). épouse
ne
– Identifiant d’un TA: NomPrénom
Date mariage
é[Link] + é[Link]
Jour Mois année

• NB. Le choix des attributs, des domaines

Conception de BD et des clés constitue
RK 70
une étape essentielle lors de la définition d’un modèle du
 Démarche à suivre pour produire
un diagramme E/A

1. Identifier les entités

2. Identifier les associations entre les entités

3. Identifier les attributs de chaque entité et de chaque

association

• ’’Il est fréquent de représenter initialement certaines

associations par des attributs pendant la conception du

schéma conceptuel et d’ensuite convertir ces attributs

en associations au fur et à mesure que la conception

Conception de BD
RK 71
progresse et est mieux comprise’’
 Les Règles de validation

• Cohérence du modèle E/A:

– Chaque entité possède une clé.
– Chaque attribut d’une occurrence d’entité ne possède,
au plus, qu’une valeur.
– Tous les attributs sont élémentaires (Adresse email, N de
téléphone, etc)
– Tous les attributs autres que la clé doivent dépendre
pleinement et directement de la clé.
– A chaque occurrence d’une association correspond une
et une seule occurrence de chaque entité participant a
l’association.
– Une cardinalité (0, 1) ou (1, 1) indique une contrainte
d’intégrité fonctionnelle et réciproquement:
• Une association particulière n’est en général pas
Conception de BD
RK nommée 72
 Conception de BD
RK 73
 Exemple d’un hypermarché

(0:n)
NumE Employé (0:1) Chef
Fournisseur
(0:1) (0:n)
Salaire
NomF Adresse

emploi Livraison

Quantité
(0:n) (0:n)
(0:n)
(0:n) (0:n)
Rayon Vente Article

NumR Etage Quantité NomA Type

Conception de BD
RK 74
 Exercice: VPC
• Vente par correspondance – spécifications
– Les clients sont caractérisés par un numéro de client, leur
nom, prénom, date de naissance, rue, code postal et ville.
– Ils commandent des produits à une date donnée et dans
une quantité donnée
– Les produits sont caractérisés par un numéro de produit,
leur désignation et leur prix unitaire.
– Chaque produit est fourni par un fournisseur unique (mais
un fournisseur peut fournir plusieurs produits).
– Les fournisseurs sont caractérisés par un numéro de
fournisseur et leur raison sociale.
• Donnez le diagramme E/A correspondant au VPC.
Conception de BD
RK 75
 Représentation multiple

• Un objet peut avoir plusieurs représentations:

Articles
Habillement

HI-FI

Alimentaire
P. Laitiers Plusieurs points de vues
Fruits légumes • un article
viandes • un article alimentaire
• un produit laitier

Conception de BD
RK 76
 Généralisation et Spécialisation

TE générique
Articles

Lien IS-A

Spécialisation Généralisation
Articles Articles Articles
Alimentaires habillement HI-FI

TE spécifique

Produits laitiers Viandes Fruits et légumes

Conception de BD
RK 77
 Entité Faible

Entité faible = entité sans identifiant propre.

• Identification: deux possibilités
1. par le ou les rôles assumés par d’autres entités qui participent à la même
association que l’entité faible à identifier.
2. par une combinaison d’attributs propres de l’entité et du ou des rôles
assumés par d’autres entités qui participent à la même association que
l’entité faible à identifier.
Remarques:
• La cardinalité du rôle de l’entité faible au sein de l’association
identifiante est (1,1)
• Concrètement, dans la base de données, l’identifiant de l’entité faible
sera formé par une combinaison d’attributs propres (s’il y a lieu) et par
un ou des identifiants des autres entités qui participent à la même
association que l’entité faible à identifier.

Conception de BD
RK 78
 Exemple
• Prenons l'exemple d'un cinéma, et de ses salles. On peut considérer chaque
salle comme une entité, dotée d'attributs comme la capacité, l'équipement en
son Dolby, ou autre. Il est difficilement imaginable de représenter une salle
sans qu'elle soit rattachée à son cinéma. C'est en effet au niveau du cinéma que
l'on va trouver quelques informations générales comme l'adresse ou le numéro
de téléphone.
• Il est possible de représenter le lien en un cinéma et ses salles par une
association classique. La cardinalité « 1..1 » force la participation d'une salle à
un lien d'association avec un et un seul cinéma. Cette représentation est
correcte, mais présente un inconvénient : on doit créer un identifiant artificiel
id pour le type d'entité Salle, et numéroter toutes les salles, indépendamment
du cinéma auquel elles sont rattachées.
• On peut considérer qu'il est beaucoup plus naturel de numéroter les salles par
un numéro interne à chaque cinéma. La clé d'identification d'une salle est alors
constituée de deux parties :
1. la clé de Cinéma, qui indique dans quel cinéma se trouve la salle ;
2. le numéro de la salle au sein du cinéma.
• En d'autres termes, l'entité salle ne dispose pas d'une identification absolue,
mais d'une identification relative à une autre entité. Bien entendu cela force la
salle a toujours être associée à un et un seul cinéma.

Conception de BD
RK 79
 Exemple

Cinéma

1:n

1:1

Salle

Conception de BD
RK 80
 III. 5. Le modèle relationnel

III.5.1. INTRODUCTION
• Le modèle relationnel a été proposé par E.F. Codd (
Edgar Frank Codd) en 1970 (IBM SAN-JOSE, Californie).
• Il est souvent considéré comme le plus simple et le plus
élégant des modèles.
 Sa simplicité est due à une vision tabulaire des données

très intuitive.
 Son élégance résulte de bases formelles issues de la

théorie mathématiqueConception
des ensembles.
de BD
• RK
Aujourd'hui utilisé par beaucoup de SGBD relationnels 81
 III. 5. 1. Introduction (suite)
• Les objectifs du modèle relationnel étaient différents de ceux
des modèles réseau et hiérarchique :
– Permettre un haut degré d'indépendance entre les
applications (programmes, interfaces) et la représentation
interne des données (fichiers, chemins d'accès).
– Etablir une base solide pour traiter les problèmes de
cohérence et de redondance des données.
 LMD (ensembliste) déclaratif (non procédural):
 spécifier ce que l'on souhaite obtenir sans dire comment
l'obtenir (le SGBD est responsable de la politique
d'exécution des requêtes).
 LDD intégré au LMD.
Conception de BD
RK 82
 Un Standard
 III.5.2. Les modèles
•
relationnels
Deux modèles relationnels
1. Modèle formel: une représentation mathématique abstraite
des bases de données. Il définit les structures de données, les
opérations possibles sur ces structures et les règles qui
régissent ces opérations de manière formelle.
 relation, attribut, tuple, identifiant…
 normalisation
 algèbre relationnelle
 calculs relationnels
2. Modèle logique, implémenté : SQL: une représentation
conceptuelle des données et de leurs relations dans une base de
données. Il se concentre sur la manière dont les utilisateurs
perçoivent la structure de la base de données et la manière dont
ils interagissent avec elle.
 table, colonne, ligne, clé primaire…
 SQL - définition et modification du schéma
 SQL - entrée et mise à jour des données
 SQL - requêtes
Conception de BD
RK 83
 Le Modèle Relationnel Formel –
Concepts de Base
• Ensemble de concepts pour formaliser la description
des objets du monde réel.
• Monde réel  Relationnel
objet  relation
propriété (simple, monovaluée) 
attribut
lien (binaire, sans attribut) 
identifiant externe
représentation multiple  /

Conception de BD
RK 84
 Concepts de Base (2)
• Etudiant (N°Etud, nom, prénom, ddn)

nom de la relation noms des attributs

Etudiant
Schéma
N°Etud nom prénom ddn

12304 Ali Mohamed

8/11/1984
Tuple/occurrence 23403 Salah Youssef

11/8/1983

34504 Tounsi Khaled

Conception de BD
RK 85
7/7/1984
 Schéma relationnel, Domaine
• Une BD = un ensemble de relations.
• Un schéma d'une BD relationnelle (sert à décrire les
relations):
 un ensemble de schémas de relations : R1, R2, …, Rn
• Un schéma d'une relation = un ensemble d'attributs avec leurs
domaines
 R = (A1:D1, A2:D2, …, Ap:Dp)
ou, plus simplement, R = (A1, A2, …, Ap)
 Attributs simples et monovalués
 Un domaine D est un ensemble de valeurs caractérisé par
un nom – type de données.
 Chaque valeur du domaine est atomique et donc indivisible.
 Cette notion permet de définir les ensembles de départ. Un
domaine peut être défini en extension en donnant la liste
des valeurs composantes ou en compréhension en
définissant une propriété caractéristique du domaine.
 COULEUR = { jaune; vert; rouge; bleu; rose; orange;
pourpre} Conception de BD
RK 86
 ABONNE = {Personne possédant une carte d'abonné valide
 Relation
• Autre définition :
– Une relation R correspond au sous ensemble du produit
cartésien de n domaines : R  D1 x D2 x D3 x … x Dn
– n : degré de la relation (nombre d’attributs)
– attribut : rôle joué par un domaine dans une relation.
• Exemple:
– Pilote (NumPil, NomPil, adr, sal)
– Avion (NumAv, AvNom, loc, cap)
– Vol (NumVol, NumPil, NumAv, Ville_dep, Ville_arr, Heure_dep,
Heure_arr)

Conception de BD
RK 87
 Exemple de relations
Etudiant N°Etud Nom Prénom Age
136 Tounsi Med
20
253 Ben Foulen Ali
19
101
<253, Ben Foulen, Ali, 19> constitue un tuple
Cherif
Cherif
Cardinalité de Etudiant = Nombre de tuples
20
Cours NomC Horaire Prof
Algorithmique Lundi 10:30-12 Mr X
Système
Lundi 14-15:30
Suit N°Etud NomC Melle Y
136 Algorithmique

253 Système
101 Conception de BD
RK 88
 Exercice
Etudiant N°Etud Nom Prénom Age
136 Tounsi Med
20
253 Ben Foulen Ali
19
Cours 101NomC Horaire Prof
Cherif
Algorithmique
Cherif Lundi 10:30-12 Mr X
Système 20
Lundi 14-15:30
Suit N°Etud NomC Melle Y
136 Algorithmique

253 Système
101
Déterminer le degré et la cardinalité de chaque relation.
Système

Conception de BD
RK 89
 Clé d’une relation – Clé
•
primaire
Une clé de relation est un sous-ensemble (minimal) d'attributs
qui permet d’identifier de manière unique chaque tuple de la
relation.
– Il n'existe jamais 2 tuples ayant mêmes valeurs pour tous
ces attributs
– Une clé n'admet jamais de valeurs nulles.
• Toute relation doit posséder au moins une clé (identifiant).
– La clé choisie est appelée clé primaire
– Par convention, lors de la définition d'un schéma cette clé
est mise en évidence (soulignement ou gras).
• Exemple
– Etudiant ( N°Etud , nom , prénom , age)
– Cours ( NomC , horaire, prof )
– Suit ( N°Etud , NomC )
• N°Etud référence un Etudiant
• NomC référence un Cours
Conception de BD
RK 90
 Clé Etrangère
• Groupe d’attributs devant apparaître comme clé primaire dans
une autre relation
– Décrit les liens binaires entre les relations (TA)
• Les clés étrangères définissent les contraintes d’intégrité
référentielles.
– Lors d'une insertion, la valeur des attributs doit exister dans
la relation référencée
– Lors d'une suppression dans la relation référencée les
tuples référençant doivent disparaître.
• Exemple: la relation Suit contient les clés de Etudiant et Cours
– Suit traduit un TA entre Etudiant et Cours
– La valeur de N°Etud dans Suit est :
• celle de l'identifiant d'un tuple existant de Etudiant
RK (intégrité référentielle)
Conception de BD
91
 Exemple de Schéma

• Etudiant (N°Etud, Nom, Prénom, Age)

• Cours (NomC,Horaire,Prof)

• Suit (#N°Etud,#NomC)

• Clés etrangères

– N°Etud Référence un Etudiant

– NomC Référence un Cours

Conception de BD
RK 92
 Diagramme des Liens

EtudiantN°EtudNomPrénomAge Cour NomC Horaire. Prof

s

Suit N°Etud NomC

Conception de BD
RK 93
 Exercice

Conception de BD
RK 94
 Exercice

Conception de BD
RK 95
 Solution

Conception de BD
RK 96
 Contraintes d’intégrité (CI)
• Une contrainte d’intégrité est une propriété du schéma,
invariante dans le temps.
– Chaque relation doit respecter les contraintes d’intégrité
• Il existe différents types de contraintes d'intégrité:
– Structurelles ou statiques (liées au modèle)
– Applicatives ou dynamiques (contraintes de cohérences
liées à l’application)
• CI de domaine
– «toute valeur d’un attribut doit appartenir à son domaine
de définition»
• CI de relation
– «toute valeur de clé primaire existe et est unique»
• CI de référence
– «Toute valeur de clé étrangère (CE) existe dans la clé
primaire CP associée»
Conception de BD
– la valeur d'attribut de la relation R doit apparaître comme 97
RK
 Vérification de l'intégrité
• Automatiquement, parréférentielle
le SGBD
• Si un utilisateur veut entrer (INSERT) un tuple dans Suit avec un NomC
qui n'existe pas dans Cours
 refus
• Si un utilisateur veut modifier (UPDATE) le nom du cours d'un tuple dans
Suit avec un NomC qui n'existe pas dans Cours
 refus
• Si un utilisateur veut supprimer (DELETE) un tuple de Cours pour lequel il
existe des tuples dans Suit
• refus? L'utilisateur peut choisir de refuser la suppression du tuple dans
la table "Cours" tant qu'il existe des références à ce tuple dans la table
"Suit".
• Détruire les tuples de Suit correspondants? L'utilisateur peut choisir de
supprimer automatiquement les tuples correspondants dans la table
"Suit" lorsque le tuple parent dans la table "Cours" est supprimé. Cela
s'appelle une suppression en cascade, et cela permet de maintenir
l'intégrité des données en supprimant automatiquement les données
associées.
1. Mettre à NULL la valeur de NomC dans Suit? L'utilisateur peut choisir de
mettre à NULL la valeur de l'attribut "NomC" dans les tuples de la table "Suit" qui
font référence au tuple de la table "Cours" à supprimer. Cela signifie que les
Conception de BD
références
RK existent toujours, mais l'information qu'elles contiennent 98 est
maintenant nulle.
Contraintes de Modélisation (1)
• Les notions d'attribut multivalué ou complexe n'existent pas
dans le modèle relationnel. Il faut donc les modéliser
autrement.
• Pour un attribut monovalué complexe, il faut choisir entre le
composé ou les composants.
• Pour un attribut multivalué, il faut créer une autre relation
(ceci pour chaque attribut multivalué).
• Représentation d'attribut monovalué complexe
– Soit pour Personne adresse : nom-rue , n° , ville , CP
– Solution 1: un attribut par composant :
• Personne (AVS, nom,…, nom-rue , n° , ville, CP)
• "Rue AbdelAziz Elaroui", "21", "Tunis", "1002"
• il est éventuellement possible de définir par ailleurs
une vue restituant la notion globale d'adresse (par
exemple 1002 Tunis)
– Solution 2: un attribut adresse, de domaine : chaîne de
caractères
• Personne (AVS, nom,…, adresse)
• "Rue AbdelAziz Elaroui, 21 Tunis 1002"
RK • le système ignore Conception
nom-rue, de BD
n°, ville et CP 99
 Contraintes de Modélisation (2)
• Représentation d'attribut multivalué
• Exemple: mémoriser les différents prénoms des étudiants
• Mauvaise modélisation: plusieurs attributs
– Etudiant (N°Etud, nom, prénom1, prénom2,… )
– 136 BenFoulen Mohamed Slim
– 101 Ali Mohamed Salah
– 253 Tounsi Fatma Null
• Bonne modélisation : créer une relation
supplémentaire
– Etudiant (N°Etud, nom)
– EtudPrénoms ( N°Etud, prénom )
• 136 Mohamed
• 136 Slim
• 101 Mohamed
• 101 Salah
• 253 Fatma
• Clé étrangère: N°Etud référence Etudiant

Conception de BD
RK 100
 Récapitulatif
• Un schéma relationnel se compose :
 pour chaque relation de :
 nom de la relation
 définition
 attributs + domaines
 clé(s)
 éventuellement clé(s) étrangère(s)
 contraintes d'intégrité associées
 et des autres contraintes d'intégrité qui portent
sur plusieurs relations.

Conception de BD
RK 101
 III.5.3. Problème de la
redondance
• [En dehors des clés étrangères]
• ex. Soit la relation COMMANDE_PRODUIT.

NumProd Quantité NumFour Adresse

101 300 901 Tunis
104 1000 902
Mannouba
112 78 904
Mannouba
103 250 901 Tunis
• Cette relation présente différentes
anomalies. (toutes les donnes sont stockes
dans
RK
le même emplacements)
Conception de BD
102
 III.5.3. Problème de la
redondance (suite)

• Anomalies de modification : Si l’on souhaite

mettre à jour l’adresse d’un fournisseur, il faut le

faire pour tous les tuples concernés.

• Anomalies d’insertion : Pour ajouter un

fournisseur nouveau, il faut obligatoirement fournir

des valeurs pour NumProd et Quantité.

• Anomalies de suppression : ex. La suppression

Conception de BD
du produit 104 fait perdre toutes les informations
RK 103
 Normalisation (1)
• Objectifs de la normalisation :
 Suppression des problèmes de mise à jour (c.a.d.
modification, suppression, insertion)
 Minimisation de l’espace de stockage (élimination des
redondances)
 La taille des fichiers normalisés croît de façon
arithmétique alors que la taille des fichiers non
normalisés croît de façon géométrique.
• Les dépendances Fonctionnelles
 Soient R(A1, A2 … An) un schéma de relation, X et Y des
sous-ensembles de A1, A2 …An
 On dit que X détermine Y ou Y dépend
fonctionnellement de X (X  Y) ssi il existe une fonction
qui à partir de toute valeur de X détermine une valeur
unique de Y
• Exemple
Conception de BD
RK
– PRODUIT (NumProd, Dési, PrixUni) 104
 Définitions
• Une dépendance fonctionnelle X→A, est dite élémentaire si
– A n’est pas inclus dans X
– il n’existe pas X’ inclus dans X tel que X’ → A
• Couverture minimale est un
– sous ensemble minimum de DF élémentaires permettant de
générer toutes les autres
Supposons que nous ayons une table "Employés" avec les attributs
suivants : EmployeeID, Nom de EmployeeName, Address), et Numéro de
sécurité sociale (SSN). Si nous constatons que le numéro de sécurité
sociale (SSN) est unique pour chaque employé, alors nous pouvons établir
la dépendance fonctionnelle : SSN -> {EmployeeID, EmployeeName,
Address}. Cela signifie que le numéro de sécurité sociale détermine de
manière unique les autres attributs de l'employé.
Dans ce cas, la couverture minimale signifierait que seul l'attribut SSN est
nécessaire pour identifier de manière unique chaque employé, et les
autres attributs
RK ne sont pas nécessaires
Conception de BD pour cet objectif. Par
105
conséquent, la structure minimale de la table serait : "Employés
 Définition

• On appelle fermeture transitive F+ d'un ensemble F

de DFE, l'ensemble de toutes les DFE qui peuvent être
composées par transitivité à partir des DFE de F.
• Soit l'ensemble F = {A→B, B→C, B→D, A→E}.

• exemple
• La fermeture transitive de F est F+ = { A→B, B→C,
B→D, A→E, A→C, A→D }

Conception de BD
RK 106
 Définition

• La couverture minimale d’un ensemble de

DFE est un sous-ensemble minimum des DFE
permettant de générer toutes les autres DFE.
• Synonymes : Famille génératrice
• Exemple
• L'ensemble F = {A→B, A→C, B→C, C→B}
admet les deux couvertures minimales :
• CM1 = {A→C, B→C, C→B} et CM2 = {A→B,
B→C, C→B}
Conception de BD
RK 107
 Normalisation (2)

Propriétés des dépendances fonctionnelles

• Réflexivité: Si Y  X alors X Y
• Augmentation: Si W  Z et X  Y alors X, Z  Y,
W
• Transitivité: Si X  Y et Y  Z alors X 
Z
• Pseudo-transitivité: Si X  Y et Y, Z  T
alors X, Z  T
• Union: Si X  Y et X  Z alors X  Y, Z
Conception de BD
RK 108
• Décomposition: Si Z  Y et X  Y alors X  Z
 Normalisation (3)

Les formes normales

• Objectifs
– Définir des règles pour décomposer les relations
tout en préservant les DF et sans perdre
d'informations, afin de représenter des objets et
associations canoniques (standard) du monde
réel (les molécules d'informations, c.a.d. unités
fondamentales d'informations)
– Éviter les anomalies
RK de demises
Conception BD a jour 109
 Première Forme Normale

• Définition
– Une relation est en 1ère forme normale si tout
attribut contient une valeur atomique
(unique)
• Exemple
PERSONNE NOM PROFESSION

DUPONT
Ingénieur, Professeur

MARTIN Géomètre

• La relation PERSONNE n’est pas en 1FN!

• Elle doit être décomposée en répétant les noms pour chaque profession

Conception de BD
RK 110
 Première Forme Normale --
Exemple
 Soit une relation en 1FN:
 Fournisseur(NF,NomProduit,Adr,Tel,Prix)
 Problèmes
 Redondances
 Mises à jour pour les insertions
 Suppressions
 Mises à jours des tuples
 Décomposition
 Fournisseur1(NF,Adr,Tel)
 Catalogue(NF,NomProduit,Prix)
 Sans perte d’information, sans perte de
DF
Conception de BD
RK 111
 Deuxième Forme Normale

• Définition
– une relation est en 2ème forme normale ssi :
• elle est en 1ère forme
• tout attribut non clé ne dépend pas d'une
partie de clé
• Schéma
R K1 K2 X Y

Une telle relation doit être décomposée en

R1(K1, K2, X) et R2(K2, Y)
Conception de BD
RK 112
 Deuxième Forme Normale --
Exemples
• Exemple 1 :
– Fournisseur (nom, adresse, article, prix)
– La clé est (nom, article)
– Mais nom  adresse : pas en 2e forme
• Exemple 2 :
– Fournisseur2(NF, Pays,Ville)
• Redondance NF Ville Pays

• Décomposition
– Fourn(NF, Ville)
– Géo(Ville, Pays)
– Sans perte d’information, sans
perte de DF.
Conception de BD
RK 113
 Troisième Forme Normale
• Définition
– une relation est en 3ème forme normale ssi :
• elle est en 2ème forme
• tout attribut n'appartenant pas a une clé ne
dépend pas d'un autre attribut non clé
• Schéma

R K X Y Z

Une telle relation doit être décomposée en

R1(K, X, Y) et R2(X,Z)
Conception de BD
RK 114
 Troisième Forme Normale --
Exemple
• Exemple:
– Voiture (n° veh, marque, type, puissance,
couleur)
 Type  marque
 Type  puissance
• Pas en 3ème forme !
• Il est bon que les relations logiques soient en 3ème
forme :
– Pas de redondance
– Pas de perte d ’information
– Pas de perte de dépendance
Conception de BD
• Représentation canonique du monde réel !
RK 115
 Exemples de Décomposition
• Voiture (n° veh, marque, type, puissance, couleur)
– Se décompose en :
• Véhicule (n° veh, type, couleur)
• Modèle (type, marque, puissance)
• Réduction (cru, type, client, remise)
– Se décompose en :
• Remise (cru,client,remise)
• Type (cru,type)
1. ("Chardonnay", "Vin", "ClientA", 0.1)
2. ("Merlot", "Vin", "ClientB", 0.15)
3. ("Chardonnay", "Vin", "ClientC", 0.08)
4. ("Cabernet Sauvignon", "Vin", "ClientD", 0.2)
5. ("Thé vert cru", "Thé", "ClientA", 0.12)
6. ("Thé noir cru", "Thé", "ClientB", 0.1)
7. ("Huile d'olive extra vierge", "Épicerie", "ClientC", 0.05)
8. ("Chocolat noir cru", "Chocolat", "ClientD", 0.18)
9. ("Café colombien", "Café", "ClientA", 0.15)

Conception de BD
RK 116
Plus loin que la troisième forme
normale :
Pourquoi et comment ?
 Rappels

• Une relation est en 3FN si :

– pas de DF d'une partie d'une clé vers un
attribut non clé (2FN)
– pas de DF entre attributs non clés.
• Toute relation a au moins une
décomposition en 3FN qui :
– préserve les dépendances fonctionnelles (DF)
– et est sans perte

Conception de BD
RK 118
 Une relation en 3FN peut comporter des
redondances

• Exemple : R(region, gouvern, CODE_ POSTAL)

• avec les DF : region,gouvern -> CODE_POSTAL

CODE_POSTAL -> gouver

• et la clé : region gouver

• les redondances : pour toutes les region ayant le même code

postal, on répète le gouvern.

• Problème : une DF d'un attribut non clé vers une partie de la clé.
Conception de BD
RK 119
• Forme normale de BOYCE-CODD :
– Les seules DF autorisées sont celles dans lesquelles une clé détermine un
attribut.

• Exemple :
R (region, gouvern, CODE POSTAL)
n'est pas en BCNF

• R peut être décomposée en :

R1 (region, CODE POSTAL)
R2 (CODE POSTAL,gouvern)
= Décomposition sans perte d’information

• Mais qui ne préserve pas la DF :

region,gouver -> CODE.
• R1 et R2 sont en BCNF.

Conception de BD
RK 120
• Une relation en BCNF peut comporter des redondances
• "L'étudiant de numéro NUMETUD pratique le sport
SPORT et suit le COURS."
– Pas de DF
– CLE = {NUMETUD, SPORT, COURS}
– R est en 3FN et en BCNF
– Cependant R contient des redondances :

R NUMETUD SPORT COURS

100 Foot Math
100 Foot Anglais
200 Foot Math
200 Tennis Anglais
200 Foot Anglais

Conception de BD
RK 121
• La notion de dépendance fonctionnelle ne suffit à définir toutes
les dépendances entre les données.

• Dépendance multivaluée (DM) :

– R (A1, A2, …, An)
– X sous-ensemble de {A1, A2, …, An}
– Y sous-ensemble de {A1, A2, …, An}
– X ->> Y : "X multidétermine Y"si, soit Z = R - X - Y,

• {(xyz) et (xy'z') ∈ R => (xy'z) et (xyz') ∈ R }

• "A chaque valeur de X, il y a un ensemble de valeurs de Y

associées et cet ensemble est indépendant des autres attributs."

Conception de BD
RK 122
• Exemple : R (NUMETUD, SPORT, COURS)
– NUMETUD->>SPORT
– NUMETUD->>COURS

<=> Pas de lien entre les cours suivis et les sports pratiqués.

• Contre-exemple : R (NUMEMP, LANGUE, PRODUIT)

"L'employé NUMEMP parle LANGUE et vend PRODUIT".

• Si pour vendre un produit, il faut parler la langue du pays où il

est distribué, il n'y a pas de dm (dépend. multiv.).

Conception de BD
RK 123
 4ème Forme Normale

• Une relation est en 4FN si les seules DM sont

celles dans lesquelles une clé multidétermine un
attribut.
• Remarques :
– une dépendance fonctionnelle est un cas particulier de
dépendance multivaluée
– 4FN => 3FN et BCNF
• en fait, on ne considère que les DM élémentaires
(parties gauche et droite minimale).
Conception de BD
RK 124
 Dépendance de jointure :

Soit R (A1, A2, …An)

X1, X2, …, Xm sous-ensembles de {A1, A2, …, An}

• Il existe une dépendance de jointure *{X1, X2, …, Xm}

si R = ΠX1 (R)∞ ΠX2 (R) ∞…∞ ΠXm (R)

• S'il existe une telle dépendance de jointure, alors R est

décomposable en m relations X1, X2, …, Xm.

Conception de BD
RK 125
Remarques :
• une DM est un cas particulier de DJ (dépend. de jointure) :

(X ->> Y => X ->> Z) => *{XY, XZ}

• si R (A1, A2, A3, A4) a 2 clés A1 et A2, on a les DJ

*{A1A2, A1A3, A1A4} et *{A1A2, A2A3, A2A4}

Conception de BD
RK 126
 Cinquième Forme Normale :

• Une relation est en 5FN si toutes les DJ sont impliquées

par les clés.

• Autre définition de la 5FN (équivalente) : Une relation est

en 5FN s'il n'est pas possible de créer la relation par
jointure de relations plus simples avec des clés différentes.

• Problème : trouver les DJ (elles n'ont pas d'interprétation

sémantique simple)

• Certaines tables n’ont pas de décomposition en 5FN.

Conception de BD
RK 127
 Méthode de décomposition en 3ème
forme
• Sans perte d ’information
• Sans perte de DF.
• Créer pour chaque source de DF une relation
comprenant comme attributs la source et toutes
les cibles de cette source.
• Si aucun des identifiants de R n’est présent dans
au moins une des relations créées ajouter une
relation supplémentaire, constituées des attributs
composant un des identifiants de R.
• Génère
RK parfois des décompositions
Conception de BD redondantes. 128
 Comment concevoir un schéma
relationnel normalisé
• Concevoir un schéma entité/association puis le traduire en
relationnel.
• Créer une relation regroupant tous les attributs ( la relation
universelle) établir un graphe minimum des dépendances;
puis décomposer jusqu’en 3eme.
• Faire un graphe minimum; en extraire directement les
relations en 3eme forme normale:
– Créer pour chaque source de DF une relation
comprenant comme attributs la source et toutes les
cibles de cette source.
– La source est la clé de la relation établi.
Conception de BD
RK 129
 III.5.4. Passage E/A  relationnel

schéma de relation avec tous les attributs

Entité (TE)  de l’entité schéma de relation avec tous les
attributs de l’entité.
on ajoute dans le schéma correspondant à
Association
(TA) l’entité de cardinalité 1, un identifiant des

1-1, 1-N autres entités participantes à l’association
et les attributs de l’association

nouveau schéma contenant un identifiant

TA N-M  de chacune des entités participantes et les
attributs de l’association

Conception de BD
RK 130
 Passage E/A en relationnel --
Exemple
• TE est représenté par une relation dans laquelle les
attributs de l’entité deviennent ceux de la relation

N°E
Etudiant NomE

Sexe Adresse

Etudiant(N°E, NomE, Adresse, Sexe)

Conception de BD
RK 131
Passage E/A en relationnel --
Exemple (suite)

• Chaque TA est représenté par une relation dans laquelle les

clés des TE participants et les attributs de l’association
deviennent ceux de la relation. Titre
Cours Ncours
0:n

Note obtenir Année

0:n
Prénom NEtud
Etudiants
Nom

• Obtenir(#Ncours,#Netud,Note,Année)
Modèle E/A Modèle Relationnel

Association Nom Relation

Attributs & clés Attributs

Conception de BD
RK 132
Passage E/A en relationnel --
Exemple (suite)
• Pour les TE pour cardinalité max =1, on ne crée pas
de relation mais ce sont les clés des types entités
qui interviennent qui seront ajoutés au TE dont la
cardinalité max=1.
Faculté
Département NDépart
0:n

appart

1:1
Prénom NEtud
Etudiants
Nom

Etudiants(NEtud,Nom,Prénom,
#NDépart,)

Conception de BD
RK 133