Fichier de rejeu Close
Indication Close
A propos de... Close
Commentaire Close
Systèmes d'Information
- Notions mathématiques
- Calcul relationnel
- Algèbre relationnelle
- Langage de requêtes
- Arbre de requêtes
- Exercices
- Introduction
- Commandes de bases
- Langage de définition de données (LDD)
- Langage de manipulation de données (LMD)
- Types de données
- Exercice
- Dépendances fonctionnelles
- Décomposition de relations
- Inférence logique
- Normalisation
- Aux pays des bières
- Modélisation
- Exercices
© Your Copyright
Aide
Normalisation
L’intérêt de la normalisation d’un schéma relationnel, où l’on veut représenter :
- un ensemble d’informations (attributs)
- liées entre elles par des dépendances fonctionnelles
est d’aboutir à une structuration (ensembles de relations) qui évitera :
- de manipuler des données redondantes
- difficiles à mettre à jour
- et à rechercher de manière efficace.
Il existe six formales imbriquées (la dernière doit respecter l’avant-dernière qui doit respecter … jusqu’à la première). Un modèle de données en 3NF suffira à éviter les problèmes de redondances et de mises à jours d’informations.
Une structuration en 3NF permettra de décomposer sans perte d’information ni de dépendances fonctionnelles entre les informations un schéma relationnel initialement constitué d’une seule table (ensemble) contenant toutes les informations.
Les principes de normalisation d’une base de données se décompose en trois phases :
- collecter toutes les informations à mémoriser
- déterminer les dépendances fonctionnelles importantes (fermeture,couverture minimale)
- normaliser le schéma relationnel en le décomposant en plusieurs relations sans perte (théorème de décomposition)
Lorsque le schéma relationnel initial \(R\) est correctement décomposé (normalisé), la reconstitution de toutes les informations dans un seul ensemble qui représenterait le schéma relationnel initial doit pouvoir se faire par une simple jointure naturelle entre tous les ensembles (tables) normalisés :
- \(R=(R_1 \Join R_2 ... \Join R_i \Join ...\Join R_{n-1} \Join R_n)\)
Dans cette partie nous allons présenter les principes de normalisation d’une base de données à partir des définitions des trois premières formes normales et de la forme normale BCNF.
Nous illustrerons ce problème de normalisation à travers le modèle de données « Aux pays des bières » en partant d’un schéma relationnel initial
- \(barsdumonde(\underline{id\_bar,id\_biere},bar,pays,continent,biere,couleur,origine,stock)\)
où nous décomposerons la relation non-normalisée pour aboutir à une représentation en 3NF de ce schéma relationnel
Première forme normale
Une relation est en première forme normale si, et seulement si :
- tous ses attributs ont des valeurs simples (contiennent une valeur atomique).
Autrement dit :
- aucun attribut n’est lui-même une relation.
- tous les attributs sont de type élémentaire.
- tout attribut est non-décomposable
la relation :
- \(livres(\underline{code},titre,auteurs)\)
n’est pas en première forme normale.
En effet plusieurs auteurs peuvent correspondre à un même livre.
Une solution consiste à décomposer la relation initiale en deux relations :
- \(livres(\underline{code},titre)\)
- \(auteurs(\underline{code},auteur)\)
Une jointure naturelle entre les deux relations :
- \(\Join_{[livres.code=auteurs.code]}(livres,auteurs)\)
permettra de retrouver les informations présentes dans la table initale.
Remarque :
on aurait pu conserver une seule relation avec des valeurs non-renseignées lorsque l’auteur correspondant n’a pas participé à l’écriture du livre :
- \(livres(\underline{code},titre,auteur 1, auteur 2, ....)\)
cette solution présente l’avantage d’éviter les jointures mais oblige à stocker des valeurs nulles et ne permet pas de rajouter plus d’auteurs que le nombre prévu.
Deuxième forme normale
Une relation est en première forme normale si, et seulement si :
- la relation est en première forme normale (1NF) et tous les attributs non-primitifs sont pleinement dépendant d’une clé
Attribut non-primitif
C’est un attribut qui n’appartient à aucune clé (est toujours cible dans une DF).
Attribut pleinement dépendant d’une clé
Soit \(A\) un attribut non-primitif et \(X\) un groupe d’attributs où \(X \rightarrow A\).
L’attribut \(A\) pleinement dépendant du groupe d’attributs \(X\) si
- \(\nexists X' \subset X, X' \rightarrow A \in F^+\)
Autrement dit :
- il n’existe pas de partie de clé (sous-clé) qui soit une clé pour un attribut non-clé
- tout attribut n’appartenant pas à une clé ne dépend pas d’une partie de cette clé
- Toute la clé est nécessaire
Décomposition de relation non NF2
Si on a le schéma relationnel suivant :
- \(R(\underline{A,B},C,D)\) avec \(B \rightarrow C\)
Alors on utilise le théorème de décomposition sans perte d’information :
- \(R_1(\underline{A,B},D)\)
- \(R_2(\underline{B},C)\)
pour obtenir une schéma relationnel 2NF.
La 2NF ne concerne que les relations à clé primaire composée (clé constitué d’un groupe d’attributs).
la relation :
- \(livres(\underline{code,auteur},titre,nom,nationalite)\)
n’est pas en deuxième forme normale.
En effet la nationalité de l’auteur ne dépend pas du code du livre.
Le code du livre ne sert à rien pour savoir de quel pays l’auteur est originaire.
- \(auteur \rightarrow nom, nationalite\)
Une solution consiste à décomposer la relation initiale en deux relations en appliquant le théorème de Heath
en fonction de la dépendance fonctionnelle \(auteur \rightarrow nom, nationalite\)
- \(livres(\underline{code,auteur},titre)\)
- \(auteurs(\underline{auteur},nom,nationalite)\)
Troisième forme normale
Une relation est en troisième forme normale si, et seulement si:
- la relation est en deuxième forme normale (2NF) et tous les attributs non-primitifs sont directement dépendant d’une clé
Dépendance directe
Soit \(A\) un attribut non-primitif et \(X\) une clé (\(X \rightarrow A\)).
\(A\) est directement dépendant de \(X\) si :
- \(\nexists Y, A \notin Y \land X \rightarrow Y \land Y \rightarrow A\)
où :
- \(Y \nsubseteq X \land Y \nrightarrow X\)
Autrement dit :
- il n’existe pas de dépendances fonctionnelles entre les attributs non-clé.
- tout attribut n’appartenant pas à une clé ne dépend pas d’un attribut non clé.
- toute la clé (2NF) et rien que la clé
Decomposition de relation non NF3
Si on a le schéma relationnel suivant :
- \(R(\underline{A,B},C,D,E)\) avec \(C \rightarrow D\)
Alors on utilise le théorème de décomposition sans perte d’information :
- \(R_1(\underline{A,B},C,E)\)
- \(R_2(\underline{C},D)\)
La 3NF permet d’éliminer les redondances d’informations liés aux dépendances transitives entre attributs non-clés.
la relation :
- \(auteurs(\underline{auteur},nom,nationalite,langue)\)
n’est pas en troisième forme normale.
En effet la langue d’écriture de l’auteur ne dépend pas de la clé mais dépend de sa nationalité.
- \(nationalite \rightarrow langue\)
Une solution consiste à décomposer la relation initiale en deux relations en appliquant le théorème de Heath:
en fonction de la dépendance fonctionnelle \(nationalite \rightarrow langue\)
- \(auteurs(\underline{auteur},nom,nationalite)\)
- \(pays(\underline{nationalite},langue)\)
Forme normale BCNF
Une relation est en BCNF (Boyce-Codd Normal Form) si, et seulement si:
- la relation est en 3NF et les seules dépendances fonctionnelles élémentaires (DFE) sont celles dans lesquelles une clé détermine un attribut.
Autrement dit :
- il ne peut pas avoir d’attributs de clé qui puissent dépendre d’attributs cible d’une DFE.
Decomposition de relation non BCNF
Si on a le schéma relationnel suivant :
- \(R(\underline{A,B},C,D,E)\) et \(C \rightarrow D\)
- avec \(\underline{A,C}\) : clé candidate
Alors on utilise le théorème de décomposition sans perte d’information :
- \(R_1(\underline{A,C},D,E)\)
- \(R_2(\underline{C},B)\)
la relation :
- \(auteurs(\underline{auteur,nationalite},langue,region)\)
n’est pas en BCNF du fait de la DFE :
- \(region \rightarrow nationalite\)
En effet la région d’origine permet de retrouver la nationalité de l’auteur.
Une solution consiste à décomposer la relation initiale en deux relations en appliquant le théorème de Heath:
en fonction de la dépendance fonctionnelle \(region \rightarrow nationalite\)
- \(regions(\underline{region},nationalite)\)
- \(auteurs(\underline{auteur},region,langue)\)