Un support de cours magistraux de Bases de données

Modèle relationnel : formes normales

Pierre Crescenzo

Dépendance fonctionnelle

Définition : Une dépendance fonctionnelle, notée DF, indique que la valeur d'un ou plusieurs attributs est associée à au plus une valeur d'un ou plusieurs autres attributs.

Soit la relation R(X, Y, Z) avec X, Y et Z des ensembles d'attributs, seul Z pouvant être vide. La notation X →^R Y signifie que Y (appelé but de la DF) est fonctionnellement dépendant de X (appelé source de la DF). En d'autres termes, Y dépend de X.

Plus formellement : ∀ x, x′, y, y′, z et z′ tels que ⟨x, y, z⟩ ∈ R et ⟨x′, y′, z′⟩ ∈ R, on a (X →^R Y) ⇔ (x = x′ ⇒ y = y′)

Par exemple, voici une relation Anniversaire(numéro : Entier, amie : Chaîne, ville : Chaîne, cadeau : Chaîne) :

numéro	amie	ville	cadeau
1	Sylvie Dupont	Nice	Fleurs
2	Sylvie Dupont	Nice	Collier
4	Corinne Durand	Menton	Fleurs
12	Juliette Dubois	Nice	Livre
14	Corinne Durand	Menton	Livre

On peut déterminer les DF suivantes pour cette relation :

numéro →^Anniversaire amie, ville, cadeau
amie →^Anniversaire ville

Propriétés de dépendance fonctionnelle

Soient W, X, Y et Z des ensembles d'attributs non vides d'une relation R. Voici quelques propriétés remarquables :

Réflexivité

(X ⊆ W) ⇒ (W →^R X)

Augmentation

(W →^R X) ⇒ (W, Y →^R X, Y)

Transitivité

(W →^R X ∧ X →^R Y) ⇒ (W →^R Y)

Union

(W →^R X ∧ W →^R Y) ⇒ (W →^R X, Y)

Pseudo-transitivité

(W →^R X ∧ X, Y →^R Z) ⇒ (W, Y →^R Z)

Décomposition

(W →^R X ∧ Y ⊆ X) ⇒ (W →^R Y)
Définitions pour les dépendances fonctionnelles

Soient X, Y et Z des ensembles d'attributs non vides d'une relation R avec X →^R Y. Cette DF est alors dite :

triviale

si et seulement si Y ⊆ X

élémentaire

si et seulement si ∀ Z tel que Z ⊂ X on n'a pas Z →^R Y

canonique

si et seulement si Y n'a qu'un seul attribut

directe

si et seulement si X →^R Y est élémentaire et ∀ Z tel que Z ≠ X ∧ Z ≠ Y on n'a pas X →^R Z ∧ Z →^R Y
Clé candidate

Rappel : Toute relation a au moins une clé candidate. (cf. chapitre 3 Modèle relationnel : concepts)

Soit une relation R.

si R ne contient qu'un seul attribut

Cet attribut a une valeur distincte pour chaque occurrence et forme alors l'unique clé candidate de R.

si R contient plusieurs attributs

Soient X et Y deux ensembles non vides disjoints d'attributs de R tels que X ∪ Y = R. Si on a X →^R Y avec X minimal, alors X est une clé candidate de R (il peut y en avoir plusieurs). Si aucun X ne peut être trouvé ainsi, toutes les occurrences de R sont distinctes et l'unique clé candidate de R est formée de tous ses attributs.

Indication : Pour vérifier que X est minimal, il faut contrôler qu'il n'est pas possible de prendre un attribut dans X pour le mettre dans Y tout en maintenant X →^R Y.
Pourquoi normaliser ?

La normalisation est utile :
- pour limiter les redondances de données,
- pour limiter les pertes de données,
- pour limiter les incohérences au sein des données et
- pour améliorer les performances des traitements.
Première forme normale

Définition : Une relation est en première forme normale si et seulement si tous ses attributs ont des valeurs simples (non multiples, non composées).
- La première forme normale est notée 1NF (1FN en français).
- Si besoin est, on décompose les attributs ou la relation pour respecter la 1NF.
Par exemple, Pers1(nom, prénom, rueEtVille, prénomEnfants) n'est pas en 1NF alors que Pers2(nom, prénom, nombreEnfants) est en 1NF.

La 1NF ne résout pas tout car aucune DF n'est prise en compte. Par exemple, Commande(codeClient, codeArticle, client, article) est en 1NF. Il est cependant possible d'y trouver les occurrences ⟨20, 5, Dupont, Table⟩, ⟨21, 5, Dupont, Table⟩ et ⟨22, 5, Durand, Chaise⟩, ce qui est incohérent.

Exercices de passage en 1NF

Passez les relations suivantes en 1NF. Donnez le contenu de la (des) relation(s) déduite(s).

numéro	avion
100	Airbus A320	A1247
110	Boeing 747	B1248
200	Boeing 737	B323
221	Airbus A330	A100
222	Boeing 747	B222

Vol

type	commandants
Airbus A320	Bernard
	Gilbert
	Joséphine
Boeing 747	Gilbert
Boeing 747	Marianne
Boeing 737	Gilbert

Avion

Passez les relations suivantes en 1NF.
1. Personne1(numéroSécu, nom, prénom, adresse, prénomEnfants, âgeEnfants)
2. Personne2(nom, prénom, natureDiplômes, lieuExamenDiplômes, dateExamenDiplômes, prénomEtÂgeEnfants)

Deuxième forme normale

Définition : Soient C une clé candidate de R et A un attribut de R. R est en deuxième forme normale si et seulement si elle est en 1NF et pour tout A tel que A n'appartient pas à C, on a C →^R A élémentaire (cf. définition d'élémentaire ci-dessus).
- La deuxième forme normale est notée 2NF (2FN en français).
- Un relation peut être en 2NF par rapport à une de ses clés candidates et ne pas l'être par rapport à une autre.
- Pour rechercher une 2NF, il est au préalable nécessaire de déterminer toutes les DF et de choisir une clé candidate. Il est recommandé de trouver toutes les clés candidates afin de ne pas en laisser passer une plus intéressante qu'une autre.
- Si besoin est, on décompose les attributs ou la relation pour respecter la 2NF.
- Une relation avec une clé candidate choisie réduite à un seul attribut est, par définition, forcément en 2NF.
Par exemple, Commande(codeClient, codeArticle, client, article) avec les DF
- codeClient →^Commande client et
- codeArticle →^Commande article
n'est pas en 2NF alors que Pers(nom, prénom, âge, nombreEnfants) avec la DF
- nom, prénom →^Pers âge, nombreEnfants
est en 2NF.

La 2NF ne résout pas tout. Des DF sont désormais prises en compte, ce qui est une chose positive. Mais toutes les DF ne le sont pas. Par exemple, Commande(numéroCommande, codeClient, client, article) avec les DF
- numéroCommande →^Commande codeClient, client, article et
- codeClient →^Commande client
est en 2NF. Il est cependant possible d'y trouver les occurrences ⟨20, 5, Dupont, Table⟩ et ⟨21, 5, Durand, Chaise⟩, ce qui est incohérent.
Exercices de passage en 2NF

Déterminez toutes les DF et clés candidates des relations suivantes puis passez les en 2NF. (La détermination des DF dépend notablement du contexte. En l'absence de celui-ci, il convient toujours de faire des hypothèses raisonnables, justifiées explicitement.)
1. Personne1(numéroSécu, nom, prénom, adresse, prénomEnfants, âgeEnfants)
2. Personne2(nom, prénom, natureDiplômes, lieuExamenDiplômes, dateExamenDiplômes, initialeNom, prénomEtÂgeEnfants)
3. Commande1(codeClient, codeArticle, client, article)
4. Commande2(numCommande, numProduit, libelléProduit, quantitéCommandée)
5. Enseignement1(nomÉtudiant, âge, cours, jourCours) Chaque cours n'a lieu qu'une fois par semaine.
6. Enseignement2(cours, joursCours, nomProfesseur, salaireProfesseur) Chaque cours n'a qu'un enseignant et n'a lieu qu'une fois par semaine.
Troisième forme normale

Définition : Soient C une clé candidate de R et A et B deux ensembles non vides disjoints d'attributs de R. R est en troisième forme normale si et seulement si elle est en 2NF et pour tous A et B tels que A et B disjoints de C, on n'a pas A →^R B.
- La troisième forme normale est notée 3NF (3FN en français).
- Un relation peut être en 3NF par rapport à une de ses clés candidates et ne pas l'être par rapport à une autre.
- Si besoin est, on décompose les attributs ou la relation pour respecter la 3NF.
- Une relation en 2NF avec au plus un attribut qui n'appartient pas à la clé candidate choisie est, par définition, forcément en 3NF.
Par exemple, Commande(numéroCommande, codeClient, client, article) avec les DF
- numéroCommande →^Commande codeClient, client, article et
- codeClient →^Commande client
n'est pas en 3NF alors que Pers(nom, prénom, âge, nombreEnfants) avec la DF
- nom, prénom →^Pers âge, nombreEnfants
est en 3NF.

La 3NF ne résout pas tout. Des DF plus nombreuses que dans la 2NF sont désormais prises en compte, ce qui est une chose positive. Mais toutes les DF ne le sont pas. Par exemple, Université(étudiant, matière, enseignant, note) avec les DF
- étudiant, matière →^Université enseignant, note et
- enseignant →^Université matière
est en 3NF. Il est cependant possible d'y trouver les occurrences ⟨Joseph, SGBD, Durand, 5⟩ et ⟨Patricia, IA, Durand, 17⟩, ce qui est incohérent.
Exercices de passage en 3NF

Passez les relations suivantes en 3NF.
1. Université(étudiant, matière, enseignant, note) Admettez
  - étudiant, matière →^Université enseignant, note et
  - enseignant →^Université matière
2. Personne1(numéroSécu, nom, prénom, adresse, prénomEnfants, âgeEnfants)
3. Personne2(nom, prénom, natureDiplômes, lieuExamenDiplômes, dateExamenDiplômes, initialeNom, prénomEtÂgeEnfants)
4. Commande1(codeClient, codeArticle, client, article)
5. Commande2(numCommande, numProduit, libelléProduit, quantitéCommandée)
6. Enseignement1(nomÉtudiant, âge, cours, jourCours) Chaque cours n'a lieu qu'une fois par semaine.
7. Enseignement2(cours, joursCours, nomProfesseur, salaireProfesseur) Chaque cours n'a qu'un enseignant et n'a lieu qu'une fois par semaine.
8. Répertoire(nom, prénom, numéroAdresse, rueAdresse, codePostal, Ville) Admettez
  - codePostal →^Répertoire Ville.
9. Personne(numéroSécu, nom, prénom, initialeNom, prénomEtÂgeEnfants, âge)
Forme normale de Boyce-Codd

Définition : Une relation est en forme normale de Boyce-Codd si et seulement si ses clés candidates sont les uniques sources de DF.
- La forme normale de Boyce-Codd est notée BCNF (FNBC en français).
- Si une relation est en BCNF, elle l'est par définition pour toutes ses clés candidates.
- Si besoin est, on décompose les attributs ou la relation pour respecter la BCNF.
Par exemple, Université(étudiant, matière, enseignant, note) avec les DF
- étudiant, matière →^Université enseignant, note et
- enseignant →^Université matière
n'est pas en BCNF alors que Pers(nom, prénom, âge, nombreEnfants) avec la DF
- nom, prénom →^Pers âge, nombreEnfants
est en BCNF.

Toutes les DF sont prises en compte par la BCNF. On considère généralement qu'une base de données de bonne qualité ne contient que des relations qui respectent la BCNF.

Cependant, la BCNF ne résout pas tout. Il faut savoir qu'il existe d'autres types de dépendance dont la prise en compte peut encore améliorer la qualité des relations. Notamment, les dépendances multivaluées ont permis de définir la 4NF et les dépendances de jointure ont donné naissance à la 5NF. Leur usage reste cependant plus marginal que celui de la BCNF.
Exercices de passage en BCNF

Passez les relations suivantes en BCNF.
1. Université(étudiant, matière, enseignant, note) Admettez
  - étudiant, matière →^Université enseignant, note et
  - enseignant →^Université matière
2. Personne1(numéroSécu, nom, prénom, adresse, prénomEnfants, âgeEnfants)
3. Personne2(nom, prénom, natureDiplômes, lieuExamenDiplômes, dateExamenDiplômes, initialeNom, prénomEtÂgeEnfants)
4. Commande1(codeClient, codeArticle, client, article)
5. Commande2(numCommande, numProduit, libelléProduit, quantitéCommandée)
6. Enseignement1(nomÉtudiant, âge, cours, jourCours) Chaque cours n'a lieu qu'une fois par semaine.
7. Enseignement2(cours, joursCours, nomProfesseur, salaireProfesseur) Chaque cours n'a qu'un enseignant et n'a lieu qu'une fois par semaine.
8. Répertoire(nom, prénom, numéroAdresse, rueAdresse, codePostal, Ville) Admettez
  - codePostal →^Répertoire Ville.
9. Personne(numéroSécu, nom, prénom, initialeNom, prénomEtÂgeEnfants, âge)
Exercices de création de relations en BCNF

Ce type de travail nécessite habituellement une méthode de conception appropriée (telle Merise ou UML). Mais nous sommes ici dans des cas très simples où vos connaissances actuelles devraient suffire pour vous amener à vous poser les questions pertinentes.
1. Vous devez créer une base de données pour une bibliothèque. Le bibliothécaire vous demande de pouvoir gérer les informations suivantes :
  - des livres qui ont chacun un titre, des auteurs (nom et prénom), un éditeur, une date d'édition et des genres (exemples : amour, science-fiction, politique, roman, nouvelles…) et
  - des clients (nom et prénom) avec une adresse (rue, code postal et ville), les livres qu'ils ont empruntés avec la date d'emprunt, la date prévue de retour et la date effective de retour.
  Vous n'en savez pas plus et devez faire des hypothèses et choix raisonnables et explicitement justifiés. Concevez cette base de données qui, naturellement, doit être formée exclusivement de relations en BCNF.
2. Vous devez créer une base de données pour une société de bus. Le responsable vous donne les indications suivantes :
  - Chaque bus, numéroté, réalise des trajets formés d'un départ, de plusieurs arrêts et d'un terminus. Un bus peut chaque jour être affecté à plusieurs trajets et peut faire plusieurs voyages sur chaque trajet, avec éventuellement des chauffeurs différents.
  - Les horaires sont fixes pour chaque jour dans une semaine, mais ils peuvent différer d'un jour à l'autre (exemple : tous les lundis, le bus 24 démarre le trajet 12 à 8 h alors que le mardi c'est à 9 h).
  - La gestion des clients est réalisée séparément (dans une autre base dont « il ne faut pas s'occuper, c'est un autre service ») mais celles des bus (date de prochaine révision, kilométrage, numéro et nom du dépôt,…), des chauffeurs (nom, prénom, grade, ancienneté, salaire, bus conduits, trajets effectués,…) et des horaires doivent l'être dans cette base.
  Vous n'en savez pas plus et devez faire des hypothèses et choix raisonnables et explicitement justifiés. Concevez cette base de données qui, naturellement, doit être formée exclusivement de relations en BCNF.