Décomposition d'une relation

Présentation & objectifs

Dans cette activité, vous apprendrez à restructurer une base de données constituée d’une seule table pour la transformer en plusieurs tables normalisées. Cette approche vous permettra de maintenir l’intégrité des données tout en minimisant la redondance. À la fin de cette session, vous serez capable de :

• Comprendre et appliquer les règles d’inférence d’Armstrong
• Identifier une couverture minimale de dépendances fonctionnelles
• Appliquer l’algorithme de décomposition en 3NF
• Évaluer la qualité d’une décomposition de base de données

Contexte

Pourquoi normaliser une base de données ?

Prenons un exemple simple pour comprendre l’utilité de la normalisation. Imaginons une base de données d’une bibliothèque universitaire avec une seule table :

EMPRUNT(numéro_emprunt, titre_livre, isbn_livre, éditeur_livre, nom_étudiant, email_étudiant, formation_étudiant, date_emprunt)

Cette structure pose plusieurs problèmes :

• Les informations sur les livres (titre, éditeur) sont répétées pour chaque emprunt du même livre
• Les informations sur les étudiants sont dupliquées à chaque nouvel emprunt
• Si un étudiant change d’email, il faut mettre à jour plusieurs enregistrements
• Si l’éditeur d’un livre change, il faut modifier tous les emprunts concernant ce livre

Pour résoudre ces problèmes, nous devons :

1. Identifier les dépendances fonctionnelles (DF) qui existent entre les attributs
2. Utiliser ces dépendances fonctionnelles pour décomposer la table en plusieurs tables plus petites et mieux structurées

C’est là qu’interviennent la couverture minimale et les règles d’Armstrong.

La couverture minimale : un outil d’optimisation

Dans notre exemple de bibliothèque, nous pourrions avoir ces dépendances fonctionnelles :

• isbn_livre $\rightarrow$ titre_livre, éditeur_livre
• numéro_étudiant $\rightarrow$ nom_étudiant, email_étudiant, formation_étudiant
• isbn_livre, numéro_étudiant $\rightarrow$ date_emprunt
• isbn_livre, numéro_étudiant $\rightarrow$ numéro_emprunt
• numéro_emprunt $\rightarrow$ isbn_livre, numéro_étudiant, date_emprunt

Certaines de ces dépendances fonctionnelles sont redondantes et peuvent être déduites des autres. La couverture minimale nous aide à identifier l’ensemble minimal nécessaire.

Les règles d’Armstrong : un cadre formel de déduction

Les règles d’Armstrong nous fournissent un cadre mathématique pour déterminer toutes les dépendances fonctionnelles valides à partir d’un ensemble initial de dépendances fonctionnelles. Ces règles sont essentielles pour :

• Valider qu’une décomposition est correcte
• Vérifier qu’aucune dépendance importante n’a été oubliée
• Identifier les dépendances fonctionnelles redondantes

Règles fondamentales

1. Réflexivité : Si $Y \subset X$, alors $X \rightarrow Y$

   • {isbn_livre, date_emprunt} $\rightarrow$ {isbn_livre}

2. Augmentation : Si $X \rightarrow Y$, alors $XZ \rightarrow YZ$ pour tout Z

   • Si isbn_livre $\rightarrow$ titre_livre, alors :
     {isbn_livre, date_emprunt} $\rightarrow$ {titre_livre, date_emprunt}

3. Transitivité : Si $X \rightarrow Y$ et $Y \rightarrow Z$, alors $X \rightarrow Z$

   • Si numéro_emprunt $\rightarrow$ isbn_livre et isbn_livre $\rightarrow$ titre_livre, alors:
     numéro_emprunt $\rightarrow$ titre_livre

Règles dérivées

Ces règles peuvent être déduites des règles fondamentales mais sont utiles en pratique :

1. Union : Si $X \rightarrow Y$ et $X \rightarrow Z$, alors $X \rightarrow YZ$

   • Si isbn_livre $\rightarrow$ titre_livre et isbn_livre $\rightarrow$ éditeur_livre, alors :
     isbn_livre $\rightarrow$ {titre_livre, éditeur_livre}

2. Décomposition : Si $X \rightarrow YZ$, alors $X \rightarrow Y$ et $X \rightarrow Z$

   • Si isbn_livre $\rightarrow$ {titre_livre, éditeur_livre}, alors :
     isbn_livre $\rightarrow$ titre_livre et isbn_livre $\rightarrow$ éditeur_livre

3. Pseudo-transitivité : Si $X \rightarrow Y$ et $WY \rightarrow Z$, alors $WX \rightarrow Z$

   • Plus rarement utilisée mais utile dans certains cas complexes

L’application systématique de ces règles permet de :

1. Dériver toutes les dépendances fonctionnelles valides dans le système
2. Identifier la couverture minimale
3. Guider le processus de décomposition vers une forme normale

Algorithme de décomposition

Pour décomposer une relation $R$ de clé $K$ avec son ensemble de dépendances fonctionnelles $F$ :

1. Trouver une couverture minimale $G$ pour $F$
2. Partitionner $G$ en sous-ensembles $F_1, …, F_n$ où chaque $F_i$ contient les dépendances fonctionnelles avec la même partie gauche
3. Créer une relation $R_i$ pour chaque partition $F_i$
4. Si aucune relation ne contient une clé de $R$, ajouter une nouvelle relation avec les attributs de la clé

Cas d’étude 1 : Gestion des fournisseurs

Considérons la relation :

FOURNISSEUR (n°fournisseur, ville, frais)

Contexte :

• Un fournisseur livre dans une seule ville
• Les frais dépendent uniquement de la ville

Analyse et décomposition :

1. Dépendances fonctionnelles initiales :

   • n°fournisseur $ \rightarrow $ ville
   • ville $ \rightarrow $ frais
   • n°fournisseur $ \rightarrow $ frais (transitive)
   • n°fournisseur, ville $ \rightarrow $ frais (non élémentaire)
   • n°fournisseur, frais $ \rightarrow $ ville (non élémentaire)

2. Couverture minimale :

   • n°fournisseur $ \rightarrow $ ville
   • ville $ \rightarrow $ frais

3. Relations résultantes :

   • R1 (n°fournisseur, ville)
   • R2 (ville, frais)

Cas d’étude 2 : Gestion des véhicules de fonction

Considérons la relation :

VEHICULE_FONCTION (n°agent, n°véhicule, nom, prénom, marque_véhicule, 
puissance_véhicule, couleur_véhicule)

Analyse et décomposition :

1. Couverture minimale :

   • n°agent $ \rightarrow $ nom, prénom
   • n°véhicule $ \rightarrow $ marque_véhicule, puissance_véhicule, couleur_véhicule

2. Relations résultantes :

   • AGENT (n°agent, nom, prénom)
   • VEHICULE (n°véhicule, marque_véhicule, puissance_véhicule, couleur_véhicule)
   • AFFECTATION_VEHICULE (n°agent, n°véhicule)

Exercice d’application

Un centre de réparation aéronautique souhaite restructurer sa base de données actuellement constituée d’une seule table :

OPERATION_MAINTENANCE (n°operation, n°intervention, n°technicien, nom_technicien, specialite_technicien, n°avion, compagnie_avion, date_mise_en_service_avion, code_imputation, cout_intervention, date_operation)

Règles métier :

• Une opération de maintenance concerne un avion à une date donnée
• Plusieurs techniciens peuvent effectuer plusieurs interventions
• Une même intervention peut nécessiter plusieurs techniciens
• Un avion est identifié par son numéro et possède une compagnie et une date de mise en service
• Un technicien a un nom et une spécialité
• Une intervention a un coût et un code d’imputation

Exercice 1 : Identifiez toutes les dépendances fonctionnelles de la relation OPERATION_MAINTENANCE

Exercice 2 : Appliquez l’algorithme de décomposition en détaillant chaque étape

Testez vos connaissances