Fiche de révision : Modèle relationnel et normalisation

📋 Plan du Cours

1. Fondements mathématiques et relationnels
2. Tables, tuples et schémas
3. Contraintes d’intégrité
4. Dépendances fonctionnelles et clés
5. Couverture minimale des dépendances
6. Décomposition et normalisation
7. Formes normales et BCNF
8. Forme normale de Boyce-Codd
9. Dépendances multivaluées et 4NF
10. Dépendances de jointure et 5NF
11. Dépendances d’inclusion
12. Dépendances généralisées

📖 1. Fondements mathématiques et relationnels

🔑 Notions clés & Définitions

• Modèle relationnel : Un modèle logique associé aux SGBD relationnels, fondé sur la théorie des ensembles et organisé autour de structures de données, de contraintes d’intégrité et d’opérations de manipulation.
• Domaine : Un ensemble de valeurs atomiques, c’est-à-dire non décomposables, comme les chaînes de longueur maximale 20, les entiers positifs, les entiers compris entre 1 et 30 ou l’ensemble des couleurs {Vert, Jaune, Rouge}.
• Relation n-aire : R sur des ensembles A1, A2, ..., An est un sous-ensemble du produit cartésien A1 × A2 × ... × An, et ses éléments sont des n-uplets ou tuples.
• Partition : D’un ensemble non vide S est une famille d’ensembles non vides dont l’union est S et dont les ensembles sont deux à deux disjoints.

💡 Astuce mémo

Ensemble → produit cartésien → relation

📖 2. Tables, tuples et schémas

🔑 Notions clés & Définitions

• Schéma relationnel : R(A1, A2, ..., An) décrit en intention une relation en donnant son nom, ses attributs et son degré ou arité n.
• Tuple : T sur un ensemble d’attributs R associe à chaque attribut Ai une valeur t(Ai) appartenant au domaine Dom(Ai), et une relation sur R est un ensemble de tuples.

📝 Points essentiels

★ À maîtriser

📌 Dans une représentation tabulaire, les lignes correspondent aux tuples, les colonnes correspondent aux attributs et la table représente une relation.

📌 Une relation est un ensemble de tuples : chaque tuple est unique et aucun ordre n’est imposé entre les tuples.

Compléments

🔄 Processus — La construction d’un schéma relationnel peut être réalisée par traduction automatique d’un schéma Entité-Association et par l’utilisation de la théorie des dépendances et de la normalisation.

💡 Astuce mémo

Attributs en colonnes, tuples en lignes

📖 3. Contraintes d’intégrité

🔑 Notions clés & Définitions

• Contrainte d’intégrité : Une contrainte d’intégrité est une propriété logique P qui doit être vraie pour une relation R et rester vraie après toute modification de R.
• Contrainte de domaine : Impose que chaque attribut prenne une valeur appartenant au domaine qui lui est défini, par exemple 0 < PrixUni < 1000.
• Contrainte référentielle : Impose que la valeur d’un groupe d’attributs d’une relation apparaisse comme valeur de clé dans une autre relation, ce qui définit une clé étrangère.

📝 Points essentiels

★ À maîtriser

📌 Une contrainte élémentaire se vérifie tuple par tuple, une contrainte statique se vérifie sur l’état global de la relation et une contrainte dynamique se vérifie sur la transition entre deux états de la relation.

Compléments

📌 Une contrainte d’entité impose que toute relation possède une clé primaire et que tout attribut participant à cette clé primaire soit non nul.

💡 Astuce mémo

Élémentaire, statique, dynamique

📖 4. Dépendances fonctionnelles et clés

🔑 Notions clés & Définitions

• Dépendance fonctionnelle : X → A signifie que, pour tous tuples ti et tj, si ti[X] = tj[X], alors ti[A] = tj[A].
• Axiomes d’Armstrong : La réflexivité, l’augmentation et la transitivité : Y ⊆ X implique X → Y, X → Y implique XZ → YZ, et X → Y avec Y → Z implique X → Z.
• Fermeture d’attributs : La fermeture X+ par rapport à F est l’ensemble des attributs A tels que F implique logiquement X → A.
• Clé candidate : Un ensemble minimal d’attributs X tel que X détermine tous les attributs de la relation, tandis qu’une clé primaire est une clé candidate privilégiée.

📝 Points essentiels

📌 Une dépendance X → A est triviale si A appartient à X, standard si X est non vide, minimale si aucun sous-ensemble propre de X ne détermine A, et partielle si elle n’est pas minimale.

🔄 Processus — Pour calculer X+ par rapport à F, on part de X, on ajoute les attributs déterminés par des dépendances dont la partie gauche est déjà incluse, puis on répète jusqu’à stabilisation.

💡 Astuce mémo

X détermine A : X → A

📖 5. Couverture minimale des dépendances

🔑 Notions clés & Définitions

• Couverture minimale : De F est un ensemble G ayant la même fermeture que F, dont les parties droites contiennent un seul attribut, dont les parties gauches ne contiennent aucun attribut redondant et dont aucune dépendance n’est superflue.
• Implication logique : Une dépendance X → Y est impliquée logiquement par F si toute relation qui satisfait F satisfait aussi X → Y, et la fermeture F+ contient toutes les dépendances ainsi impliquées.

📝 Points essentiels

★ À maîtriser

🔄 Processus — Pour calculer une couverture minimale, on décompose d’abord chaque partie droite en dépendances élémentaires, puis on supprime les dépendances redondantes et les attributs superflus des parties gauches.

Compléments

• Si F = {A → B, B → C}, alors F implique A → C et l’ensemble {A → B, B → C} est équivalent à {A → B, B → C, A → C}.

💡 Astuce mémo

Décomposer, réduire, supprimer

📖 6. Décomposition et normalisation

🔑 Notions clés & Définitions

• Normalisation : Vise à réduire les redondances, éviter les anomalies d’insertion, de suppression et de modification, limiter les valeurs nulles et choisir des décompositions adaptées.
• Décomposition : De R(U) est un ensemble de schémas R1(U1), ..., Rn(Un) tels que U = U1 ∪ ... ∪ Un, chaque relation étant obtenue par projection de R sur son sous-ensemble d’attributs.
• Décomposition sans perte : Une décomposition est sans perte d’informations si toute relation r satisfaisant F peut être reconstruite exactement par jointure de ses projections, soit r = r[U1] ⋈ ... ⋈ r[Un].
• Préservation des dépendances : Une décomposition préserve les dépendances si F+ est égal à la fermeture de l’union des dépendances projetées sur les relations décomposées.

📝 Points essentiels

📌 Pour une décomposition en deux relations R1 et R2, le théorème de Heath garantit l’absence de perte si leur intersection est une superclé d’au moins une des deux relations.

🔄 Processus — L’algorithme CHASE construit un tableau associé aux relations décomposées, applique répétitivement les dépendances fonctionnelles en égalisant les valeurs correspondantes et conclut à une décomposition sans perte si une ligne devient entièrement définie.

💡 Astuce mémo

Sans perte et sans redondance

📖 7. Formes normales et BCNF

🔑 Notions clés & Définitions

• Première forme normale : Une relation est en première forme normale si tous ses attributs sont atomiques et si les attributs non clés dépendent fonctionnellement de la clé.
• Deuxième forme normale : Une relation est en deuxième forme normale si elle est en 1NF et si tout attribut non clé dépend entièrement de la clé primaire, sans dépendance fonctionnelle élémentaire sur une partie de cette clé.
• Troisième forme normale : Une relation est en troisième forme normale si elle est en 2NF et s’il n’existe aucune dépendance entre deux attributs non clés, donc aucune dépendance transitive d’un attribut non clé vers la clé.

📝 Points essentiels

🔄 Processus — L’algorithme de synthèse calcule une couverture minimale, regroupe les dépendances ayant la même partie gauche et construit une relation pour chaque groupe afin d’obtenir une décomposition en 3NF préservant les dépendances.

💡 Astuce mémo

1NF → 2NF → 3NF → BCNF

📖 8. Forme normale de Boyce-Codd

🔑 Notions clés & Définitions

• Forme normale de Boyce-Codd : Un schéma relationnel est en forme normale de Boyce-Codd si, pour toute dépendance fonctionnelle non triviale X → A, X est une super-clé.

📝 Points essentiels

★ À maîtriser

• Toute relation peut être décomposée en relations en troisième forme normale sans perte d’information et sans perte de dépendances fonctionnelles, contrairement aux formes normales supérieures.

• La relation COURS(ETUDIANT, MATIERE, PROF), avec (ETUDIANT, MATIERE) → PROF et PROF → MATIERE, est en 3FN mais pas en BCNF, car PROF n’est pas une super-clé.

📌 Toute relation possède une décomposition en BCNF sans perte, mais cette décomposition ne préserve pas nécessairement les dépendances fonctionnelles, tandis qu’une décomposition en 3FN peut préserver les dépendances et être sans perte.

Compléments

🔄 Processus — L’algorithme de décomposition en BCNF ajoute la relation initiale au schéma, puis décompose toute relation qui n’est pas en BCNF selon une dépendance X → Y violant la condition, en la remplaçant par les relations T1(U−Y) et T2(X,Y), jusqu’à obtenir uniquement des relations en BCNF.

• Pour R(Horaire, Salle, Cours), défini par Horaire, Salle → Cours et Cours → Salle, une décomposition en BCNF peut autoriser dans la relation restante un couple Horaire-Cours qui ne respectait pas la dépendance initiale.

💡 Astuce mémo

BCNF : toute partie gauche est une clé

📖 9. Dépendances multivaluées et 4NF

🔑 Notions clés & Définitions

• Dépendance multivaluée : X ↠ Y signifie que la connaissance d’une valeur de X détermine un ensemble de valeurs de Y indépendant des autres attributs R−X−Y.
• Quatrième forme normale : Une relation est en quatrième forme normale si, pour toute dépendance multivaluée non triviale X ↠ Y, X contient une clé candidate de la relation.

📝 Points essentiels

★ À maîtriser

🔄 Processus — Une relation satisfait X ↠ Y lorsque, pour deux tuples ayant la même valeur de X, elle contient aussi les combinaisons croisées des valeurs de Y et de R−X−Y.

📌 Toute dépendance fonctionnelle X → Y implique la dépendance multivaluée X ↠ Y, mais la réciproque est fausse.

Compléments

• Les dépendances multivaluées satisfont la règle du complément: si X ↠ Y, alors X ↠ R−X−Y, les dépendances multivaluées triviales sont toujours satisfaites

• ETUDES(MATIERE, PROF, LIVRE) n’est pas en 4NF, car MATIERE ↠ PROF et MATIERE ↠ LIVRE représentent deux ensembles indépendants ; sa décomposition sans perte est R1(MATIERE, PROF) et R2(MATIERE, LIVRE).

💡 Astuce mémo

Deux ensembles indépendants, deux relations

📖 10. Dépendances de jointure et 5NF

🔑 Notions clés & Définitions

• Dépendance de jointure : *{X1, X2, …, Xn} est satisfaite lorsque la relation est exactement la jointure de ses projections sur X1, X2, …, Xn.
• Cinquième forme normale : Une relation est en cinquième forme normale si, pour toute dépendance de jointure non triviale, chacune des parties Xi contient une clé candidate de la relation.

📝 Points essentiels

★ À maîtriser

• Dans la relation Fournisseur(NumFournisseur, codeProduit, numUsine), la contrainte de jointure permet une décomposition en FournisseurProduit, FournisseurUsine et ProduitUsine, qui sont trois relations en 5NF.

Compléments

📌 Une dépendance multivaluée est un cas particulier de dépendance de jointure avec n = 2.

• La 5NF est une forme normale finale vis-à-vis de la projection et de la jointure, car elle élimine les anomalies supprimables par décomposition de ce type.

• Les dépendances de jointure sont rares et difficiles à détecter en pratique, si bien que la normalisation est généralement arrêtée à la 4NF lorsque cela est possible.

💡 Astuce mémo

5NF : chaque branche contient une clé

📖 11. Dépendances d’inclusion

🔑 Notions clés & Définitions

• Dépendance d’inclusion : Ri[X] ⊆ Rj[Y] est satisfaite lorsque toute valeur de la projection X dans Ri apparaît dans la projection Y de Rj, avec X et Y de même longueur.

📝 Points essentiels

★ À maîtriser

📌 Les dépendances d’inclusion peuvent relier des attributs de relations différentes et sont définies sur des séquences d’attributs de même taille, dont l’ordre est important.

📌 Une contrainte d’intégrité référentielle est une dépendance d’inclusion dont la partie droite est une clé et dont la partie gauche est une clé étrangère, mais toutes les dépendances d’inclusion ne sont pas des clés étrangères.

Compléments

• La dépendance Seance[codeMatiere] ⊆ Matiere[codeMatiere] impose que tout code matière utilisé dans une séance corresponde à une matière existante.

• La dépendance Reservations[date, codeMatiere] ⊆ Seance[date, codeMatiere] impose que toute réservation corresponde à une séance de cours existante.

📌 Le système d’inférence de Casanova pour les dépendances d’inclusion comprend la réflexivité, la permutation-projection et la transitivité, et il est correct et complet.

💡 Astuce mémo

Les valeurs de gauche doivent exister à droite

📖 12. Dépendances généralisées

🔑 Notions clés & Définitions

• Dépendance généralisée : Affirme que, si un ensemble de patrons de lignes est présent dans une table, alors une condition doit être respectée, par exemple la présence d’un patron de ligne particulier.

📝 Points essentiels

📌 Une dépendance généralisée est plus générale qu’une dépendance de jointure et permet notamment d’exprimer des dépendances emboîtées.

• Dans l’exemple Fournisseur-Produit-Usine, les trois premières lignes forment un patron général et la dernière ligne représente la conclusion imposée par la dépendance généralisée.

💡 Astuce mémo

Des patrons présents imposent une conclusion

📊 Tableaux de synthèse

Propriétés des décompositions

Comparaison des formes normales avancées

⚠️ Pièges & confusions fréquents

1. Le modèle relationnel ne se confond pas avec les modèles conceptuels Entité-Association ou relationnel-objet.
2. Un tuple est une ligne, et non une colonne.
3. Le schéma seul ne restreint pas nécessairement les données sans contraintes explicites.
4. Une dépendance fonctionnelle exprime une contrainte sémantique générale, pas seulement une régularité observée dans une instance.
5. Une couverture minimale peut ne pas être unique.
6. La normalisation n’a pas pour seul objectif de réduire l’espace de stockage.
7. Une valeur composée ou un ensemble de valeurs dans un attribut viole l’atomicité.