Dépendance Fonctionnelle et Normalisation PDF 2021

Faculté des Sciences Semlalia Dépendance Fonctionnelle et Normalisation Enseigné par: Pr. J. ZAHIR 20 décembre 2021 Objectifs d’apprentissage de la séance Comprendre la redondance des...

Faculté des Sciences Semlalia Dépendance Fonctionnelle et Normalisation Enseigné par: Pr. J. ZAHIR 20 décembre 2021 Objectifs d’apprentissage de la séance Comprendre la redondance des données Comprendre les concepts reliés au principe de la dépendance fonctionnelle Comprendre le principe de la décomposition sans perte Connaitre les 1FN, 2FN, 3FN, BCNF et 4FN Pouvoir e↵ectuer une transformation en 3FN Plan 1 La redondance Anomalie d’insertion Anomalie de suppression Anomalie de modification 2 Dépendances fonctionnelles 3 Clés candidates 4 Normalisation des Relations 5 Fermeture transitive et couverture minimale 6 Dépendances Multivaluées et 4ème forme normale La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Une définition La redondance des données au sein d’une BD désigne le fait qu’une même donnée soit stockée/répétée dans deux ou plusieurs champs di↵érents. Exemple : NUM LIVRE LIVRE TITRE CATEGORIE PRIX 1 Hergé Objectif Lune Enfants 200 2 Gosciny Astérix le Gaulois Enfants 200 3 Gossiny Dalton City Enfants 200 4 Franquin Le Cas la Ga↵e Enfants 200 5 Franquin Idées noires Adultes 300 J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 4 / 53  La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Une définition La redondance des données au sein d’une BD désigne le fait qu’une même donnée soit stockée/répétée dans deux ou plusieurs champs di↵érents. Exemple : NUM LIVRE LIVRE TITRE CATEGORIE PRIX 1 Hergé Objectif Lune Enfants 200 2 Gosciny Astérix le Gaulois Enfants 200 3 Gossiny Dalton City Enfants 200 4 Franquin Le Cas la Ga↵e Enfants 200 5 Franquin Idées noires Adultes 300 ) Redondance des valeurs (catégorie, prix) : (Enfant, 200) apparaı̂t 4 fois. J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 4 / 53 La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Conséquences de la redondance Perte d’espace sur le support physique de stockage (n’est plus vraiment une contrainte de nos jours) Anomalies de stockage Anomalies de stockage 1 Anomalie d’insertion 2 Anomalie de suppression 3 Anomalie de modification J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 5 / 53  La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Anomalie d’insertion Insérer l’information suivante : ” Les livres de la catégorie ”Jeune âge” coûtent 150 euros” NUM LIVRE AUTEUR TITRE CATEGORIE PRIX 1 Hergé Objectif Lune Enfants 200 2 Gosciny Astérix le Gaulois Enfants 200 3 Gossiny Dalton City Enfants 200 4 Franquin Le Cas la Ga↵e Enfants 200 5 Franquin Idées noires Adultes 300 J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 6 / 53 La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Anomalie d’insertion Insérer l’information suivante : ” Les livres de la catégorie ”Jeune âge” coûtent 150 euros” NUM LIVRE AUTEUR TITRE CATEGORIE PRIX 1 Hergé Objectif Lune Enfants 200 2 Gosciny Astérix le Gaulois Enfants 200 3 Gossiny Dalton City Enfants 200 4 Franquin Le Cas la Ga↵e Enfants 200 5 Franquin Idées noires Adultes 300 Pas de livre ) Pas de NUM LIVRE ) Impossible d’insérer En plus de la possibilité d’introduction d’erreurs J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 6 / 53  La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Anomalie de suppression Et si nous supprimions la dernière ligne ? NUM LIVRE AUTEUR TITRE CATEGORIE PRIX 1 Hergé Objectif Lune Enfants 200 2 Gosciny Astérix le Gaulois Enfants 200 3 Gossiny Dalton City Enfants 200 4 Franquin Le Cas la Ga↵e Enfants 200 5 Franquin Idées noires Adultes 300 J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 7 / 53 La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Anomalie de suppression Et si nous supprimions la dernière ligne ? NUM LIVRE AUTEUR TITRE CATEGORIE PRIX 1 Hergé Objectif Lune Enfants 200 2 Gosciny Astérix le Gaulois Enfants 200 3 Gossiny Dalton City Enfants 200 4 Franquin Le Cas la Ga↵e Enfants 200 5 Franquin Idées noires Adultes 300 ) Perte d’information J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 7 / 53  La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Anomalie de modification Et si le prix de la catégorie ”Enfants” changeait ? NUM LIVRE AUTEUR TITRE CATEGORIE PRIX 1 Hergé Objectif Lune Enfants 200 2 Gosciny Astérix le Gaulois Enfants 200 3 Gossiny Dalton City Enfants 200 4 Franquin Le Cas la Ga↵e Enfants 200 5 Franquin Idées noires Adultes 300 J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 8 / 53 La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Anomalie de modification Et si le prix de la catégorie ”Enfants” changeait ? NUM LIVRE AUTEUR TITRE CATEGORIE PRIX 1 Hergé Objectif Lune Enfants 200 2 Gosciny Astérix le Gaulois Enfants 200 3 Gossiny Dalton City Enfants 200 4 Franquin Le Cas la Ga↵e Enfants 200 5 Franquin Idées noires Adultes 300 ) Coût élevé de la mise à jour J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 8 / 53  La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Une solution ? NUM LIVRE AUTEUR TITRE CATEGORIE 1 Hergé Objectif Lune Enfants CATEGORIE PRIX 2 Gosciny Astérix le Gaulois Enfants Enfants 200 3 Gossiny Dalton City Enfants Adultes 300 4 Franquin Le Cas la Ga↵e Enfants 5 Franquin Idées noires Adultes Anomalie d’insertion ) Résolue Anomalie de suppression ) Résolue Anomalie de modification )Résolue J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 9 / 53 La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Une solution ? NUM LIVRE AUTEUR TITRE CATEGORIE 1 Hergé Objectif Lune Enfants CATEGORIE PRIX 2 Gosciny Astérix le Gaulois Enfants Enfants 200 3 Gossiny Dalton City Enfants Adultes 300 4 Franquin Le Cas la Ga↵e Enfants 5 Franquin Idées noires Adultes Anomalie d’insertion ) Résolue Anomalie de suppression ) Résolue Anomalie de modification )Résolue Question : Pourra t-on retrouver la relation initiale ? J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 9 / 53  La redondance Dépendances fonctionnelles Anomalie d’insertion Clés candidates Anomalie de suppression Normalisation des Relations Anomalie de modification Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Une solution ? NUM LIVRE AUTEUR TITRE CATEGORIE 1 Hergé Objectif Lune Enfants CATEGORIE PRIX 2 Gosciny Astérix le Gaulois Enfants Enfants 200 3 Gossiny Dalton City Enfants Adultes 300 4 Franquin Le Cas la Ga↵e Enfants 5 Franquin Idées noires Adultes Anomalie d’insertion ) Résolue Anomalie de suppression ) Résolue Anomalie de modification )Résolue Question : Pourra t-on retrouver la relation initiale ? Réponse : Oui, en e↵ectuant une jointure entre les deux relations sur l’attribut catégorie. ) Nous venons d’e↵ectuer une décomposition réversible, appelée aussi décomposition sans perte J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 9 / 53 Plan 1 La redondance 2 Dépendances fonctionnelles Définition Axiomes d’armstrong Propriétés supplémentaires des DF Types des DF Graphe de Dépendances Fonctionnelles 3 Clés candidates 4 Normalisation des Relations 5 Fermeture transitive et couverture minimale 6 Dépendances Multivaluées et 4ème forme normale  La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale Dépendance fonctionnelle : Introduction Notion introduite par Codd Objectif : ! Caractériser les relations pouvant être décomposées sans perte d’information Définition Soient A et B deux attributs (ou deux groupes d’attributs) et R une relation, on dit que : B est fonctionnellement dépendant de A, ou A détermine B si à toute valeur de A correspond au plus une valeur de B Notation : A ! B J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 11 / 53 La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale Exemple Remarque Une DF est une assertion sur TOUTES les valeurs possibles et non pas uniquement sur les valeurs actuellement présentes J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 12 / 53  La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale Réflexivité, Augmentation et Transitivité Les DF obéissent à des propriétés mathématiques particulières, dites axiomes d’Armstrong. Réflexivité Tout ensemble d’attributs détermine lui-même, ou une partie de lui-même E!E A, B!A Augmentation Si E!F alors 8G E, G!F Transitivité Si E!F et F!G alors E!G J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 13 / 53 La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale Union, Pseudo-Transitivité et Décomposition Union (additivité) Si E!F et E!G alors E!F, G Décomposition Si E!F et G2F alors E!G Pseudo-transitivité Si E!F et F, G!H alors E, G!H J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 14 / 53  La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale DF Canonique E!F est canonique si F ne contient qu’un seul attribut. Exemple NV ! Type NV ! Marque J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 15 / 53 La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale DF Directe E!F est directe s’il n’existe pas G tel que E!G et G!F Exemple NV!Marque n’est pas directe puisque NV! Type et Type ! Marque J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 16 / 53  La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale DF Elémentaire : DFE E!F (avec F 2 / E) est une DFE s’il n’existe aucun sous-ensemble de E qui détermine F (il n’existe pas G 2 E pour lequel G!F) Exemple NV, Type! Coul n’est pas une DFE puisque NV! Coul Remarque La transitivité est le seule axiome applicable sur les DFE J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 17 / 53 La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale ) Moyen de visualiser les Dépendances Fonctionnelles. Les sommets correspondent aux attributs Les arcs correspondent aux DFE entre les attributs J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 18 / 53  La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale GDF : Cas d’un ensemble d’attributs Soit la relation CodePostal (Code, ville, Rue) Code ! ville (Ville, Rue) ! Code Pour pouvoir représenter le GDF, il faut introduire une sorte d’association entre plusieurs sommets vers un autre sommet J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 19 / 53 La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale Graphe de DF : Exercice d’application 2 Dessiner le GDF correspondant à l’exemple suivant : J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 20 / 53  La redondance Définition Dépendances fonctionnelles Axiomes d’armstrong Clés candidates Propriétés supplémentaires des DF Normalisation des Relations Types des DF Fermeture transitive et couverture minimale Graphe de Dépendances Fonctionnelles Dépendances Multivaluées et 4ème forme normale Graphe de DF : Exercice d’application 2 Dessiner le GDF correspondant à l’exemple suivant : J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 20 / 53 Plan 1 La redondance 2 Dépendances fonctionnelles 3 Clés candidates 4 Normalisation des Relations 5 Fermeture transitive et couverture minimale 6 Dépendances Multivaluées et 4ème forme normale  La redondance Dépendances fonctionnelles Clés candidates Normalisation des Relations Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Clé candidate : Définition Soit X ✓ {A1 ,..., An } un ensemble d’attributs d’un schéma R(A1 ,..., An ). X est une cle candidate si : 1 X ! A1 ,..., An et 2 pour chaque Y ✓ X , si Y ! A1 ,...An alors X = Y X est une clé candidate si X est le plus petit ensemble d’attributs qui détermine tous les autres de R. J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 22 / 53 La redondance Dépendances fonctionnelles Clés candidates Normalisation des Relations Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Exemple : Soit R(A,B,C,D) et les DF {AB ! C ; C ! D; D ! A}. Les clés candidates sont : CB et AB J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 23 / 53 Plan 1 La redondance 2 Dépendances fonctionnelles 3 Clés candidates 4 Normalisation des Relations 1FN 2FN 3FN 5 Fermeture transitive et couverture minimale 6 Dépendances Multivaluées et 4ème forme normale La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Normalisation : Le pourquoi Une mauvaise conception des entités et associations représentant le monde réel modélisé conduit à des relations problématiques Une redondance des données conduit à des risques d’incohérences Solution Eliminer toute anomalie afin de faciliter la manipulation des relations ) Normalisation des relations ( Décomposition sans perte ou décomposition réversible) Principe ) décomposer une relation en plusieurs, en fonction des dépendances fonctionnelles, afin d’éliminer les anomalies (redondances). DFs et Normalisation Les DFs guident la normalisation DSPI : Décomposition sans perte d’information DSPDF : Décomposition sans perte de dépendances fonctionnelles. J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 25 / 53  La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Formes Normales Permettent d’éviter les anomalies transactionnelles dues à une mauvaise modélisation des données, Il existe 8 formes normales, Le respect d’une FN de niveau supérieur implique le respect des FN des niveaux inférieurs, Les 3 premières formes normales (1FN, 2FN et 3FN) sont les plus utilisées. J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 26 / 53 La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale 1ère Forme Normale Consiste à éviter les domaines composés de plusieurs valeurs et des attributs multivalués irréguliers. Exemple : CODE COURS TITRE COURS PROF NIVEAU MOTS CLES 001 Bases de données Dupont S5 SGBD, Modèle EA, Relationnel 002 Systèmes d’informations Durand S4 UML,MERISE................ Table – Relation Cours CATEGORIE PRIX enfant 200-250 adulte 300-400 adolescent 200 Table – Relation CategrorieLivre J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 27 / 53  La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale 1ère Forme Normale 1FN : Définition Tout attribut dépend fonctionnellement de la clé, La relation ne contient que des attributs atomiques. Exemple : Relation Cours à la 1FN CODE COURS MOTS CLES CODE COURS TITRE COURS PROF NIVEAU 001 SGBD 001 Bases de données Dupont S5 001 Modèle EA 002 Systèmes d’informations Durand S4 001 Relationnel............ 002 UML 002 MERISE Remarque : La 1FN crée des redondances J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 28 / 53 La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale 1ère Forme Normale Transformer Intuitivement la relation CategrorieLivre en 1FN CATEGORIE PRIX enfant 200-250 adulte 300-400 adolescent 200 J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 29 / 53  La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale 1ère Forme Normale Transformer Intuitivement la relation CategrorieLivre en 1FN CATEGORIE PRIX enfant 200-250 adulte 300-400 adolescent 200 CATEGORIE PRIX MIN PRIX MAX enfant 200 250 adulte 300 400 adolescent 200 200 J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 29 / 53 La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Deuxième forme normale On supposera dans ce qui suit que chaque relation a exactement une clé candidate, c’est-à-dire une clé primaire et aucune clé alternative. La deuxième forme normale élimine les redondances en garantissant qu’aucun attribut n’est déterminé par une partie de la clé. 2FN : Définition Etre en 1FN Tout attribut dépend de toute la clé ) Uniquement des DFEs entre les attributs non-clé et la clé J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 30 / 53  La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Deuxième forme normale : Exemple Soit la relation : FOURNISSEUR (NOM, ADRESSE, ARTICLE, PRIX) Est ce que la relation FOURNISSEUR est en deuxième forme normale ? J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 31 / 53 La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Deuxième forme normale : Exemple Soit la relation : FOURNISSEUR (NOM, ADRESSE, ARTICLE, PRIX) Est ce que la relation FOURNISSEUR est en deuxième forme normale ? Si (NOM, ARTICLE) ! PRIX et NOM ! ADRESSE. ) La réponse est Non. En considérant ces DF, mettre la relation FOURNISSEUR en 2FN. J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 31 / 53  La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Deuxième forme normale : Exemple Soit la relation : FOURNISSEUR (NOM, ADRESSE, ARTICLE, PRIX) Est ce que la relation FOURNISSEUR est en deuxième forme normale ? Si (NOM, ARTICLE) ! PRIX et NOM ! ADRESSE. ) La réponse est Non. En considérant ces DF, mettre la relation FOURNISSEUR en 2FN. FOURNISSEUR (NOM, ADRESSE) PRODUIT (#NOM, ARTICLE, PRIX) J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 31 / 53 La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Troisième forme normale Elimine les redondances dues aux dépendances transitives 3FN : Définition Être en 2FN Il n’existe aucune DF entre les attributs non-clé ) Uniquement des DF élémentaires directes entre les attributs clés et les attributs non-clé J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 32 / 53  La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Troisième forme normale : Exemple (1/2) Est ce que la relation VOITURE(NV, MARQUE, TYPE, PUISSANCE, COULEUR) est en 3FN ? J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 33 / 53 La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Troisième forme normale : Exemple (1/2) Est ce que la relation VOITURE(NV, MARQUE, TYPE, PUISSANCE, COULEUR) est en 3FN ? Si TYPE! PUISSANCE et TYPE ! MARQUE ) La réponse est Non En considérant ces DF, mettre la relation VOITURE en 3FN J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 33 / 53  La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Troisième forme normale : Exemple (1/2) Est ce que la relation VOITURE(NV, MARQUE, TYPE, PUISSANCE, COULEUR) est en 3FN ? Si TYPE! PUISSANCE et TYPE ! MARQUE ) La réponse est Non En considérant ces DF, mettre la relation VOITURE en 3FN VOITURE (NV, #TYPE, COULEUR) MODELE (TYPE, MARQUE, PUISSANCE) J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 33 / 53 La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Troisième forme normale : Propriétés La 3FN est une décomposition sans perte qui preserve les DF Exemple : Soit la relation VOITURE et les DF : TYPE! PUISSANCE, TYPE ! MARQUE, NV ! COULEUR et NV ! TYPE Décomposition 1 : R1(NV, #TYPE, COULEUR) , R2(TYPE, MARQUE, PUISSANCE) Décomposition 2 : V1(NV, #TYPE), V2(TYPE, PUISSANCE, COULEUR) et V3(#TYPE, MARQUE) Laquelle des deux décompositions n’est pas en 3FN ? Pourquoi ? J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 34 / 53  La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Troisième forme normale : Exemple (2/2) J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 35 / 53 La redondance Dépendances fonctionnelles 1FN Clés candidates 2FN Normalisation des Relations 3FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Normalisation 1FN, 2FN et 3FN : Synthèse J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 36 / 53 Plan 1 La redondance 2 Dépendances fonctionnelles 3 Clés candidates 4 Normalisation des Relations 5 Fermeture transitive et couverture minimale Fermeture transitive Couverture minimale Algorithme de décomposition Algorithme de synthèse BCNF 6 Dépendances Multivaluées et 4ème forme normale La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale Fermeture transitive : Définition A partir d’un ensemble de DFE, on peut composer par transitivité d’autres DFE Fermeture Transitive de F notée F + Ensemble des DFE considérées (F) enrichies de toutes les DFE obtenues par transitivité Exemple : Déterminer la fermeture transitive de : F={ NV ! TYPE ; TYPE! MARQUE ; TYPE! PUISSANCE ; NV! COULEUR } F + = F [{NV ! MARQUE ; NV ! PUISSANCE} Notion d’équivalence des ensembles Deux ensembles de DFE sont dits équivalents s’il ont la même fermeture transitive. Le sous ensemble minimal de F permettant de générer tous les autres ensembles équivalents est appelé Couverture minimale de F J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 38 / 53  La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale GDF de F et de F + Figure – GDF de F Figure – GDF de F + J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 39 / 53 La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale Couverture minimale Définition Ensemble F de DFE associé à un ensemble d’attributs vérifiant les propriétés suivantes : 1 Aucune DF dans F n’est redondante ) Pour toute DF f de F, F f 6⌘ F 2 Tout ensemble d’attributs a une couverture minimale qui n’est pas unique J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 40 / 53  La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale 3FN : Algorithme de décomposition Transformation en 3FN, deux façons de faire : 1 Algorithme par décomposition 2 Algorithme par synthèse Algorithme par décomposition En pratique, considérer les relations obtenues après l’étape de la modélisation logique Appliquer les transformations de normalisation pour obtenir des relations en 3FN J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 41 / 53 La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale 3FN : Algorithme de synthèse Entrée : Relation universelle R ( tous les attributs) et un ensemble F de DF Sortie : Schémas R1 , R2 ,... , Rn avec Ri en 3NF pour tout i Etape 1 : Rechercher une couverture minimale G de F ( Eliminer les DF redondantes) Etape 2 : Partitionner G en groupes ayant la même partie gauche Etape 3 : Fusionner les groupes Gi et Gj possédant des parties gauches Xi et Xj équivalentes Etape 4 : Pour chaque groupe, créer un schéma relationnel Ri dont la clé est la partie gauche des DF et les attributs non clés est la partie droite des DF. Etape 5 Si aucune des clés candidates ne figure dans une des relations Ri alors il est nécessaire de rajouter une relation dont les attributs constituent une clé candidate J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 42 / 53  La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale 3FN : Algorithme de synthèse -Exercice d’application- Soit R(A,B,C,D,E) et les dépendances A!B ; A!C ; C,D!E ; B!D ; décomposer R à la 3FN en utilisant l’algorithme de synthèse Étape 1 : Ces DF forment déjà une couverture minimale, il est impossible d’enlever une de ces dépendances. Étape 2 : Il y a trois groupes de dépendances avec la même partie gauche : {A!B ; A!C} {C,D!E} et {B!D} Étape 4 : On obtient une décomposition en trois relations R1(A,#B,C), R2(C,D,E), R3(B,D). J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 43 / 53 La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale La forme normale Boyce et Codd Introduite par Boyce et Codd pour éliminer les redondances crées par des dépendances entre parties de clés et celles déjà éliminées par la 3e FN. Définition Une relation est en BCNF si et seulement si les seules dépendances fonctionnelles élémentaires sont celles dans lesquelles une clé entière détermine un attribut. J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 44 / 53  La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale BCNF : Exemple Soit la relation : UNIVERSITE(étudiant, matière, enseignant, note), avec les DF : étudiant, matière !enseignant étudiant, matière ! note enseignant ! matière Est ce que la relation UNIVERSITE est en BCNF ? La réponse est Non. Mettre la relation UNIVERSITE en BCNF : UNIVERSITE(étudiant, matière, note) REPARTITION(enseignant, matière) J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 45 / 53 La redondance Fermeture transitive Dépendances fonctionnelles Couverture minimale Clés candidates Algorithme de décomposition Normalisation des Relations Algorithme de synthèse Fermeture transitive et couverture minimale BCNF Dépendances Multivaluées et 4ème forme normale BCNF : Propriétés Ressortir les DF de la décomposition obtenue dans l’exemple précédent : UNIVERSITE(étudiant, matière, note) REPARTITION(enseignant, matière) Comparer avec les DF de la relation intiale étudiant, matière !enseignant étudiant, matière ! note enseignant ! matière ) Une décomposition en BCNF ne préserve en général pas les DF. Il a été montré que toute relation a une décomposition en BCNF qui est SPI. J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 46 / 53 Plan 1 La redondance 2 Dépendances fonctionnelles 3 Clés candidates 4 Normalisation des Relations 5 Fermeture transitive et couverture minimale 6 Dépendances Multivaluées et 4ème forme normale Introduction Dépendances Multivaluées 4FN La redondance Dépendances fonctionnelles Introduction Clés candidates Dépendances Multivaluées Normalisation des Relations 4FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Exemple Introductif Soit la relation ETUDIANT(NE, COURS, SPORT) La relation ETUDIANT est elle en 3FN ? BCNF ? J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 48 / 53  La redondance Dépendances fonctionnelles Introduction Clés candidates Dépendances Multivaluées Normalisation des Relations 4FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Exemple Introductif Soit la relation ETUDIANT(NE, COURS, SPORT) La relation ETUDIANT est elle en 3FN ? BCNF ? Mais des redondances existent toujours ) d’où le besoin de la 4FN J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 48 / 53 La redondance Dépendances fonctionnelles Introduction Clés candidates Dépendances Multivaluées Normalisation des Relations 4FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Dépendances Multivaluées : Définition Définition Soient : R (A1, A2... An) un schéma de relation, X et Y deux sous-ensembles de {A1, A2,... An} On dit que X ⇣Y (X multidétermine Y, ou il y a une dépendance multivaluée de Y sur X) si étant données des valeurs de X, il y a un ensemble de valeurs de Y associées et cet ensemble est indépendant des autres attributs Z = R – X – Y de la relation R. Plus formellement (X ⇣ Y ) , {(xyz)et(xy 0 z 0 ) 2 R ) (xy 0 z)et(xyz 0 ) 2 R} J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 49 / 53  La redondance Dépendances fonctionnelles Introduction Clés candidates Dépendances Multivaluées Normalisation des Relations 4FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale Retour à l’exemple introductif A partir de la relation ETUDIANT (exemple introductif) : NE⇣ COURS NE ⇣ SPORT J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 50 / 53 La redondance Dépendances fonctionnelles Introduction Clés candidates Dépendances Multivaluées Normalisation des Relations 4FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale DF vs DM Soient : R (A1, A2... An) un schéma de relation, X et Y deux sous-ensembles de {A1, A2,... An} X ! Y , {(xyz)et(xy 0 z 0 ) 2 R ) y = y 0 } X ! Y , {(xyz)et(xy 0 z 0 ) 2 R ) (xy 0 z)et(xyz 0 ) 2 R} X !Y )X ⇣Y Conclusion Les dépendances fonctionnelles sont un cas particulier des dépendances multivaluées J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 51 / 53  La redondance Dépendances fonctionnelles Introduction Clés candidates Dépendances Multivaluées Normalisation des Relations 4FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale DM élémentaires DM élémentaire : Définition Dépendance multivaluée X ⇣ Y d’une relation R telle que : 1 Y n’est pas vide et est disjoint de X. 2 R ne contient pas une autre DM du type X 0 ⇣ Y 0 telle que X 0 ⇢ X et Y0 ⇢ Y. Exemple de DME : Soit la relation : VOL (NV, AVION, PILOTE), où : NV est un numéro de vol. On suppose disposer d’un ensemble d’avions et d’un ensemble de pilotes. Tout pilote est conduit à piloter tout avion sur n’importe quel vol. Y’a t-il des DM ? Si oui, sont elles élémentaires ? J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 52 / 53 La redondance Dépendances fonctionnelles Introduction Clés candidates Dépendances Multivaluées Normalisation des Relations 4FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale DM élémentaires DM élémentaire : Définition Dépendance multivaluée X ⇣ Y d’une relation R telle que : 1 Y n’est pas vide et est disjoint de X. 2 R ne contient pas une autre DM du type X 0 ⇣ Y 0 telle que X 0 ⇢ X et Y0 ⇢ Y. Exemple de DME : Soit la relation : VOL (NV, AVION, PILOTE), où : NV est un numéro de vol. On suppose disposer d’un ensemble d’avions et d’un ensemble de pilotes. Tout pilote est conduit à piloter tout avion sur n’importe quel vol. Y’a t-il des DM ? Si oui, sont elles élémentaires ? Les avions et les pilotes sont indépendants, donc oui des DM existent et elles sont élémentaires NV ⇣ AVION NV ⇣ PILOTE J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 52 / 53  La redondance Dépendances fonctionnelles Introduction Clés candidates Dépendances Multivaluées Normalisation des Relations 4FN Fermeture transitive et couverture minimale Dépendances Multivaluées et 4ème forme normale 4ème forme normale : Définition Définition Une relation est en 4FN si les seules DME sont celles dans lesquelles une clé multidétermine un attribut. Soit la relation : ETUDIANT(NE, COURS, SPORT) Est ce que ETUDIANT est en 4FN ? La clé est l’ensemble des attributs et il existe des DM élémentaires entre des attributs participants à la clé ) ETUDIANT n’est pas en 4FN. Décomposer ETUDIANT en 4FN R1(NE,COURS) R2(NE,SPORT) J. ZAHIR, FSSM Dépendance Fonctionnelle et Normalisation 20 décembre 2021 53 / 53