TD 10: Normalisation

Normalisation, Perte de DF, Perte d’Information, FNBC, FN3

L3 MIASHS/Ingémath

Université Paris Cité

Année 2024

Course Homepage

Moodle

Exercice

Soit \(\mathcal{A}=\left\{A,B,C,D,E\right\}\) un schéma et soit \(\mathcal{A}_1=\left\{A,B,C\right\}\). Pour chaque ensemble \(\Sigma\) de dépendances fonctionnelles ci-dessous, déterminer un ensemble de DF équivalent à \(\pi_{\mathcal{A}_1}(\Sigma)\).

• \(\Sigma=\left\{AB\to DE, C\to E, D\to C, E\to A\right\}\)
• \(\Sigma=\left\{A\to D, BD\to E, AC\to E, DE\to B\right\}\)
• \(\Sigma=\left\{AB\to D, AC\to E, BC\to D, D\to A, E\to B\right\}\)
• \(\Sigma=\left\{A\to B, B\to C, C\to D, D\to E, E\to A\right\}\)

Exercice

Soit \(\mathcal{A}=\left\{A,B,C,D,E\right\}\) un schéma et soit la décomposition \(\left\{\mathcal{A}_1,\mathcal{A}_2,\mathcal{A}_3\right\}\) où \[\mathcal{A}_1=\left\{A,B,C\right\}\quad \mathcal{A}_2=\left\{B,C,D\right\}\quad \mathcal{A}_3=\left\{A,C,E\right\}\] Pour chaque ensemble \(\Sigma\) de dépendances fonctionnelles ci-dessous, déterminer quelles dépendances sont préservées par cette décomposition, c’est-à-dire quelles DF de \(\Sigma\) sont impliquées par \(\bigcup_{i=1}^3 \pi_{\mathcal{A}_i}(\Sigma)\).

• \(\Sigma=\left\{b\rightarrow E, CE\rightarrow A\right\}\)
• \(\Sigma=\left\{aC\rightarrow E, BC\to D\right\}\)
• \(\Sigma=\left\{a\rightarrow D, D\to E, B\to D\right\}\)
• \(\Sigma=\left\{a\rightarrow D, CD\to E, E\to D\right\}\)

Exercice

On considère le schéma de relation suivant concernant la gestion de rendez-vous d’un service d’intervention hospitaliers. \[ \mathcal{A}=\left\{\texttt{IdM,NomM,PrenomM,DateRV,HeureRV,IdP,NomP,PrenomP,IdInterV}\right\} \]

Chaque rendez-vous implique un médecin et un patient. Chaque médecin est identifié par un numéro, IdM, un nom NomM et un prénom PrenomM. Le rendez-vous est à une date, DateRV, et à une heure, HeureRV données. Chaque patient est identifié par un numéro, IdP, un nom NomP et un prénom PrenomP. Chaque rv est programmé pour un type d’intervention médical, IdInterV. On suppose que chaque jour, un médecin ne peut pratiquer qu’un seul type d’intervention médicale (consultation, type de chirurgie donnée).

On a les dépendances fonctionnelles \(\Sigma\) suivantes:

IdM, DateRV,HeureRV, IdInterV → IdP
IdM, DateRV →  IdInterV
IdM → NomM, PrenomM
IdP → NomP, PrenomP
IdP,DateRV,HeureRV → IdInterV
IdP,DateRV,HeureRV →  IdM,NomM

• Quels sont les inconvénients d’une telle modélisation par une seule table en terme d’anomalies d’insertion ou de suppression ?

• Calculer \([\texttt{IdM}]^+_{\Sigma}\)

• Proposez un ensemble d’attributs formant une clé de la relation.

• Donner un ensemble de dépendances fonctionnelles \(\Sigma'\) équivalent à \(\Sigma\) qui soit minimal (i.e. sans règles redondantes, notamment). Justifiez

On se donne la décomposition de \(\mathcal{A}\) suivante~: \[ \begin{array}{l} \mathcal{A}_1=\left\{\texttt{IdM,HeureRV,DateRV,IdP,NomP,PrenomP}\right\},\\ \mathcal{A}_2=\left\{\texttt{IdM,DateRV,IdInterV}\right\},\\ \mathcal{A}_3=\left\{\texttt{IdM,NomM,PrenomM}\right\} \end{array} \]

• Toutes les dépendances fonctionnelles sont-elles préservées par cette décomposition ?

• Est-elle sans perte d’information ?

• Pour \(i=1,2,3\), déterminer si \(\mathcal{A}_i\) est en forme normale de Boyce-Codd.

• Mêmes questions pour la décomposition :

\[ \begin{array}{rl} \mathcal{A}_1 &=\left\{\texttt{IdM,HeureRV,DateRV,IdP}\right\}\\ \mathcal{A}_2 &=\left\{\texttt{IdP,NomP,PrenomP}\right\}, \\ \mathcal{A}_3 &=\left\{\texttt{IdM,DateRV,IdInterV}\right\},\\ \mathcal{A}_4 &=\left\{\texttt{IdM,NomM,PrenomM}\right\} \end{array} \]

Exercice

Soit une relation concernant des personnes résidant en France avec les attributs suivants:

Nom, Numéro de sécurité sociale, Commune, Département, Code postal, Numéro de téléphone

avec l’ensemble \(\Sigma\) de DF suivantes~:

Numéro de sécurité sociale → Nom, Commune, Département, Code postal, Numéro de téléphone 
Commune → Département 
Code postal → Commune, Département

• Ce schéma est-il en forme normale de Boyce-Codd ?

Soit la décomposition \[\mathcal{A}_1=\left\{\texttt{Code postal}, \texttt{Commune}, \texttt{Département}\right\}\] et \[\mathcal{A}_2=\left\{\texttt{Numéro de sécurité sociale}, \texttt{Nom}, \texttt{Code postal},\texttt{Numéro de téléphone}\right\}\]

• Chaque \(\mathcal{A}_i\) est-elle en forme normale de Boyce-Codd ?

• Cette décomposition préserve-t-elle les dépendances fonctionnelles ?

• Cette décomposition est-elle sans perte d’information ?

• Mêmes questions pour la décomposition \[\mathcal{A}_1=\left\{\texttt{Commune}, \texttt{Département}\right\}\]

\[\mathcal{A}_2=\left\{\texttt{Numéro de sécurité sociale}, \texttt{Nom}, \texttt{Commune}, \texttt{Code postal},\texttt{Numéro de téléphone}\right\}\]

Exercice

Soit un schéma d’attributs \(A_1, A_2,\dots A_n\) et un ensemble de dépendances fonctionnelles. Calculer le nombre de super-clefs (en fonction de \(n\)) dans les cas suivants~:

• La seule clef est \(\left\{A_1\right\}\).
• Les seules clefs sont \(\left\{A_1\right\}\) et \(\left\{A_2\right\}\).
• Les seules clefs sont \(\left\{A_1,A_2\right\}\) et \(\left\{A_3,A_4\right\}\).
• Les seules clefs sont \(\left\{A_1,A_2\right\}\) et \(\left\{A_1,A_3\right\}\).

Exercice

Soit le schéma \(\mathcal{A}=\{A,B,C,D\}\) et l’ensemble de dépendances fonctionnelles \[\Sigma = \{ A \to B, B \to C\} \]

• Quelle est la fermeture \(\{A\}^+\) de \(\{A\}\) ?

• Quelles sont les super-clés ? Les clés ?

Exercice

Soit le schéma \(\mathcal{A}=\{A,B,C,D,E,F\}\) et l’ensemble de dépendances fonctionnelles \[\Sigma = \Bigl\{ \left\{A,B\right\}\to C, \left\{B,C\right\}\to \left\{A,D\right\}, D\to E, \left\{C,F\right\}\to B \Bigr\}\]

• Calculer la fermeture \(\left\{A,B\right\}^+\) de \(\left\{A,B\right\}\).
• Est-ce que \(\Sigma\) implique la dépendance fonctionnelle \(\left\{A,B\right\}\to D\)~?
• Est-ce que \(\Sigma\) implique la dépendance fonctionnelle \(D\to A\)~?

Exercice

On considère une schéma \(\mathcal{A}\) avec les attributs

Propriétaire, Occupant, Adresse, Noapt, Nbpièces, Nbpersonnes

Un nuplet/tuple (p, o, a, n, nb1, nb2) ayant la signification suivante : La personne o habite avec nb2 personnes l’appartement de numéro n ayant nb1 pièces dont le propriétaire est p.

Une analyse de cette relation nous fournit un ensemble initial \(\Sigma\) de dépendances fonctionnelles

Occupant → Adresse
Occupant → Noapt
Occupant → Nbpersonnes
Adresse, Noapt → Proprietaire
Adresse, Noapt → Occupant
Adresse, Noapt → Nbpieces

• Déterminer les clés du schémas
• Les schéma est-il en FN3 ?
• Si la réponse est Non, décomposer sans perte d’information et sans perte de dépendances fonctionnelles.

Exercice

Soit le schéma \[\mathcal{A}=\{\texttt{IdLivre, Titre, Langue, Pays, IdTraducteur, Nom, Date}\}\] et l’ensemble de DF

IdLivre → Titre 
Langue → Pays 
IdTraducteur → Nom 
IdLivre, IdTraducteur, Langue → Date
IdLivre, IdTraducteur → Langue

Appliquer l’algorithme de décomposition vu en cours pour obtenir une décomposition de \(\mathcal{A}\) qui respecte la FNBC et est sans perte d’information. Déterminer quelles DF sont préservées.

Exercice

Soit le schéma \[\mathcal{A}=\left\{\texttt{A,B,C,D,E,F,G,H}\right\}\] et l’ensemble de DF

BE → AC  
B → H  
F → CD  
D → G

• Appliquer l’algorithme de décomposition vu en cours pour obtenir une décomposition de \(\mathcal{A}\) qui respecte la FNBC et est sans perte d’information. Déterminer quelles DF sont préservées.
• Peut-on, en ajoutant un sous-schéma à la décomposition, obtenir une décomposition FNBC sans perte d’information et sans perte de DF ?

Exercice

Reprendre les questions de l’exercice précédent pour le schéma \[\mathcal{A}=\left\{\texttt{A,B,C,D,E,F,G,H}\right\}\] et l’ensemble de DF

BE → AC  
B → H
F → CD
D → G
A→ E