TD 10: Normalisation

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

Avec solutions

L3 MIASHS/Ingémath

Université Paris Cité

Année 2024

Course Homepage

Moodle

Exercice

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

• $\mathrm{\Sigma }=\{AB\to DE,C\to E,D\to C,E\to A\}$
• $\mathrm{\Sigma }=\{A\to D,BD\to E,AC\to E,DE\to B\}$
• $\mathrm{\Sigma }=\{AB\to D,AC\to E,BC\to D,D\to A,E\to B\}$
• $\mathrm{\Sigma }=\{A\to B,B\to C,C\to D,D\to E,E\to A\}$

Solution

Rappelons que ${\pi }_{{\mathcal{A}}_1}(\mathrm{\Sigma })$ est l’ensemble des DF de la forme $X\to Y$, avec $X\subset {\mathcal{A}}_1$ et $Y\subset {\mathcal{A}}_1$, qui sont impliquées par $\mathrm{\Sigma }$. Un ensemble de DF équivalent à ${\pi }_{{\mathcal{A}}_1}(\mathrm{\Sigma })$ est l’ensemble des DF $X\to (X^{+}\cap {\mathcal{A}}_1)\setminus X$ où $X\subset {\mathcal{A}}_1$, $X\ne \mathrm{\varnothing }$ et $X\ne {\mathcal{A}}_1$.

• $A^{+}=A$, $B^{+}=B$, $C^{+}=CEA$ donc on ajoute $\boxed{{\displaystyle C\to A}}$\ $A{B}^{+}=ABDEC$ donc on ajoute $\boxed{{\displaystyle AB\to C}}$\ $A{C}^{+}=ACE$, $B{C}^{+}=BCEAD$ donc on ajoute $\boxed{{\displaystyle BC\to A}}$\ Donc ${\pi }_{{\mathcal{A}}_1}(\mathrm{\Sigma })$ est équivalent à $\{C\to A,AB\to C,BC\to A\}$ lui-même équivalent à $\{AB\to C,C\to A\}$.

• $A^{+}=AD$, $B^{+}=B$, $C^{+}=C$ rien à ajouter\ $A{B}^{+}=ABDE$, $A{C}^{+}=ACDEB$ donc on ajoute $\boxed{{\displaystyle AC\to B}}$\ $B{C}^{+}=BC$\ Donc ${\pi }_{{\mathcal{A}}_1}(\mathrm{\Sigma })$ est équivalent à $\{aC\to B\}$.

• $A^{+}=A$, $B^{+}=B$, $C^{+}=C$ rien à ajouter\ $A{B}^{+}=ABD$, $A{C}^{+}=ACEBD$ donc on ajoute $\boxed{{\displaystyle AC\to B}}$\ $B{C}^{+}=BCDAE$ donc on ajoute $\boxed{{\displaystyle BC\to A}}$ \ Donc ${\pi }_{{\mathcal{A}}_1}(\mathrm{\Sigma })$ est équivalent à $\{aC\to B,BC\to A\}$.

• Tout attribut est une clef, donc c’est aussi le cas pour ${\mathcal{A}}_1$. ${\pi }_{{\mathcal{A}}_1}(\mathrm{\Sigma })$ est donc équivalent à $\{a\to B,B\to C,C\to A\}$.

Exercice

Soit $\mathcal{A}=\{A,B,C,D,E\}$ un schéma et soit la décomposition $\{{\mathcal{A}}_1,{\mathcal{A}}_2,{\mathcal{A}}_3\}$ où $${\mathcal{A}}_1=\{A,B,C\}{\mathcal{A}}_2=\{B,C,D\}{\mathcal{A}}_3=\{A,C,E\}$$ Pour chaque ensemble $\mathrm{\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 $\mathrm{\Sigma }$ sont impliquées par $\bigcup _{i=1}^3{\pi }_{{\mathcal{A}}_i}(\mathrm{\Sigma })$.

• $\mathrm{\Sigma }=\{b\to E,CE\to A\}$
• $\mathrm{\Sigma }=\{aC\to E,BC\to D\}$
• $\mathrm{\Sigma }=\{a\to D,D\to E,B\to D\}$
• $\mathrm{\Sigma }=\{a\to D,CD\to E,E\to D\}$

Solution

La DF $X\to Y$ est préservée si et seulement la fermeture de $X$ par rapport aux DF locales $\bigcup _{i=1}^3{\pi }_{{\mathcal{A}}_i}(\mathrm{\Sigma })$ contient $Y$. Pour calculer la fermeture de $X$ par rapport aux DF locales $\bigcup _{i=1}^3{\pi }_{{\mathcal{A}}_i}(\mathrm{\Sigma })$ on peut utiliser l’algorithme suivant~:

• Initialisation $Z\leftarrow X$
• Tant que $Z$ grandit : pour $i=1,2,3$, $Z\leftarrow Z\cup ((Z\cap {\mathcal{A}}_i{)}_{\mathrm{\Sigma }}^{+}\cap {\mathcal{A}}_i)$

L’ensemble $Z$ obtenu est la fermeture recherchée

L’intérêt de cet algorithme est qu’on ne calcule pas toutes les DF locales. Si au cours du calcul on obtient que $Y\subset Z$, on peut conclure immédiatement que $X\to Y$ est préservée.

• $\mathrm{\Sigma }=\{B\to E,CE\to A\}$
  • $CE\to A$ est préservée puisqu’elle est locale à ${\mathcal{A}}_3$.
  • $B\to E$ n’est pas préservée puisque
    $(B\cap {\mathcal{A}}_1{)}^{+}\cap {\mathcal{A}}_1=B^{+}\cap {\mathcal{A}}_1=BE\cap {\mathcal{A}}_1=B$
    $(B\cap {\mathcal{A}}_2{)}^{+}\cap {\mathcal{A}}_2=B^{+}\cap {\mathcal{A}}_2=BE\cap {\mathcal{A}}_2=B$
    $(B\cap {\mathcal{A}}_3{)}^{+}\cap {\mathcal{A}}_3=\mathrm{\varnothing }$
• $\mathrm{\Sigma }=\{AC\to E,BC\to D\}$ est préservé puisqu’il ne contient que des DF locales.
• $\mathrm{\Sigma }=\{A\to D,D\to E,B\to D\}$
  $B\to D$ est préservée
• $\mathrm{\Sigma }=\{A\to D,CD\to E,E\to D\}$
  Aucune DF n’est préservée

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\{\mathtt{\text{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 $\mathrm{\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 ?

Solution

A chaque nouveau rv inséré dans $R$, il faut rappeler les noms, prénoms des médecins et patients. Ce qui peut se traduire par des incohérences si cela n’est pas respecté. En cas de suppression d’un groupe de rv, on peut faire disparaitre l’ensemble des informations concernant un patient ou un médecin.

• Calculer $[\mathtt{\text{IdM}}{]}_{\mathrm{\Sigma }}^{+}$

Solution

$[IdM{]}_{\mathrm{\Sigma }}^{+}=\{\mathtt{\text{IdM, NomM, PrenomM}}\}$

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

Solution

Il y a plusieurs clés possibles. Par exemple, {IdM, DateRV, HeureRV} mais aussi {IdP, DateRV, HeureRV}.

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

Solution

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

On se donne la décomposition de $\mathcal{A}$ suivante~: $$\begin{array}{l}{\mathcal{A}}_1=\left\{\mathtt{\text{IdM,HeureRV,DateRV,IdP,NomP,PrenomP}}\right\},\\ {\mathcal{A}}_2=\left\{\mathtt{\text{IdM,DateRV,IdInterV}}\right\},\\ {\mathcal{A}}_3=\left\{\mathtt{\text{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.

Solution

Préservation des DF

Les dépendances de Σ’ sont locales aux ${\mathcal{A}}_i$, elles sont donc préservées.

Décomposition SPI ?

Oui, en utilisant seulement (b) et (c) dans l’algorithme de poursuite\

${\mathcal{A}}_i$ est en FNBC~?\

Rappelons que, par définition, ${\mathcal{A}}_i$ est en FNBC si et seulement pour toute DF $X\to Y$ dans un ensemble équivalent à ${\pi }_{{\mathcal{A}}_i}(\mathrm{\Sigma })$, soit $Y\subset X$ (DF triviale) soit $Y$ est une super-clef pour ${\mathcal{A}}_i$ relativement à ${\pi }_{{\mathcal{A}}_i}(\mathrm{\Sigma })$.

Donc ${\mathcal{A}}_i$ est en FNBC si et seulement si pour tout $X\subset {\mathcal{A}}_i$, pour la DF locale $X\to (X\cap {\mathcal{A}}_i{)}^{+}\cap {\mathcal{A}}_i$ on a $(X\cap {\mathcal{A}}_i{)}^{+}\cap {\mathcal{A}}_i=X$ (DF triviale) ou $(X\cap {\mathcal{A}}_i{)}^{+}\cap {\mathcal{A}}_i={\mathcal{A}}_i$ (càd $X$ est une super-clef pour ${\mathcal{A}}_i$).

De plus, on n’a pas besoin d’examiner les cas $X=\mathrm{\varnothing }$ ou $X={\mathcal{A}}_i$ ou $cardinal(X)=cardinal({\mathcal{A}}_i)-1$ (dans le dernier cas $(X\cap {\mathcal{A}}_i{)}^{+}\cap {\mathcal{A}}_i=X$ ou $(X\cap {\mathcal{A}}_i{)}^{+}\cap {\mathcal{A}}_i={\mathcal{A}}_i$)

${\mathcal{A}}_1$ n’est pas en FNBC car IdP → NomP, PrenomP est locale à ${\mathcal{A}}_1$ et IdP n’est pas une super-clef de ${\mathcal{A}}_1$.

${\mathcal{A}}_2$ est en FNBC car:

• IdM^+ ∩ \mathcal{A}_2 = {idM, NomM, PrenomM} ∩ \mathcal{A}_2 =IdM
• $DateR{V}^{+}\cap {\mathcal{A}}_2=\left\{dateRV\right\}\cap {\mathcal{A}}_2=DateRV$
• $IdInter{V}^{+}\cap {\mathcal{A}}_2=\left\{idInterV\right\}\cap {\mathcal{A}}_2=IdInterV$\

${\mathcal{A}}_3$ est en FNBC car :

• $Id{M}^{+}\cap {\mathcal{A}}_3=\{idM,NomM,PrenomM\}\cap {\mathcal{A}}_3={\mathcal{A}}_3$\
• $Nom{M}^{+}\cap {\mathcal{A}}_3=\left\{nomM\right\}\cap {\mathcal{A}}_3=NomM$\
• $Prenom{M}^{+}\cap {\mathcal{A}}_3=\left\{prenomM\right\}\cap {\mathcal{A}}_3=PrenomM$

• Mêmes questions pour la décomposition :

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

Solution

La décomposition est SPI. $$\begin{array}{|cccccccccc|}\hline & IdM& NomM& PrenomM& DateRV& HeureRV& IdP& NomP& PrenomP& IdInterV\\ {\mathcal{A}}_1& a& b_1& c_1& d& e& f& g_1& h_1& i_1\\ {\mathcal{A}}_2& a_2& b_2& c_2& d_2& e_2& f& g& h& i_2\\ {\mathcal{A}}_3& a& b_3& c_3& d& e_3& f_3& g_3& h_3& i\\ {\mathcal{A}}_4& a& b& c& d_4& e_4& f_4& g_4& h_4& i_4\\ \hline\end{array}$$ (c) donne $b_1=b$ et $c_1=c$. (d) donne $g_1=g$ et $h_1=h$. (b) donne $i_1=i$. La première ligne est $(a,b,\dots ,i)$.\ \ (b), (c), (d) sont préservées puisque locales.\ Est-ce que (e) est préservée~? Initialisation $Z:=\{idP,DateRV,HeureRV\}$\ $(Z\cap {\mathcal{A}}_1{)}^{+}\cap {\mathcal{A}}_1={\{idP,DateRV,HeureRV\}}^{+}\cap {\mathcal{A}}_1=\mathcal{A}\cap {\mathcal{A}}_1={\mathcal{A}}_1$, donc $Z:={\mathcal{A}}_1$.\ $(Z\cap {\mathcal{A}}_3{)}^{+}\cap {\mathcal{A}}_3={\{idM,DateRV\}}^{+}\cap {\mathcal{A}}_3={\mathcal{A}}_3$ qui contient $IdInterV$. On conclut que (e) est préservée.\ (f) est préservée car (f) est impliquée par $IdP,DateRV,HeureRV\to IdM$ (locale à ${\mathcal{A}}_1$) et (c). Est-ce que (a) est préservée~? Initialisation $Z:=\{idM,DateRV,HeureRV,IdInterV\}$\ $(Z\cap {\mathcal{A}}_1{)}^{+}\cap {\mathcal{A}}_1={\{idM,DateRV,HeureRV\}}^{+}\cap {\mathcal{A}}_1=ALL\cap {\mathcal{A}}_1={\mathcal{A}}_1$ qui contient $IdP$. Donc (a) est préservée.\ \ car\ $Id{M}^{+}\cap {\mathcal{A}}_1=IdM$, $HeureR{V}^{+}\cap {\mathcal{A}}_1=HeureRV$, $DateR{V}^{+}\cap {\mathcal{A}}_1=DateRV$, $Id{P}^{+}\cap {\mathcal{A}}_1=IdP$\ ${\{idM,HeureRV\}}^{+}\cap {\mathcal{A}}_1=\{idM,HeureRV\}$, ${\{idM,DateRV\}}^{+}\cap {\mathcal{A}}_1=\{idM,DateRV\}$, ${\{idM,IdP\}}^{+}\cap {\mathcal{A}}_1=\{idM,IdP\}$, ${\{heureRV,DateRV\}}^{+}\cap {\mathcal{A}}_1=\{heureRV,DateRV\}$, ${\{heureRV,IdP\}}^{+}\cap {\mathcal{A}}_1=\{heureRV,IdP\}$, ${\{dateRV,IdP\}}^{+}\cap {\mathcal{A}}_1=\{dateRV,IdP\}$\ car\ $Id{P}^{+}\cap {\mathcal{A}}_2={\mathcal{A}}_2$, $Nom{P}^{+}\cap {\mathcal{A}}_2=NomP$, $Prenom{P}^{+}\cap {\mathcal{A}}_2=PrenomP$\ car\ $Id{M}^{+}\cap {\mathcal{A}}_3=IdM$, $DateR{V}^{+}\cap {\mathcal{A}}_3=DateRV$, $IdInter{V}^{+}\cap {\mathcal{A}}_3=IdInterV$\ car\ $Id{M}^{+}\cap {\mathcal{A}}_4={\mathcal{A}}_4$, $Nom{M}^{+}\cap {\mathcal{A}}_4=NomM$, $Prenom{M}^{+}\cap {\mathcal{A}}_4=PrenomM$

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 $\mathrm{\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=\{\mathtt{\text{Code postal}},\mathtt{\text{Commune}},\mathtt{\text{Département}}\}$$ et $${\mathcal{A}}_2=\{\mathtt{\text{Numéro de sécurité sociale}},\mathtt{\text{Nom}},\mathtt{\text{Code postal}},\mathtt{\text{Numéro de téléphone}}\}$$

• 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=\{\mathtt{\text{Commune}},\mathtt{\text{Département}}\}$$

$${\mathcal{A}}_2=\{\mathtt{\text{Numéro de sécurité sociale}},\mathtt{\text{Nom}},\mathtt{\text{Commune}},\mathtt{\text{Code postal}},\mathtt{\text{Numéro de téléphone}}\}$$

Solution

• Non, car on a $\mathtt{\text{Commune}}\to \mathtt{\text{Département}}$ et $\mathtt{\text{Commune}}$ n’est pas une clef.
• ${\mathcal{A}}_1$ n’est pas en FNBC car $\mathtt{\text{Commune}}\to \mathtt{\text{Département}}$ est locale à ${\mathcal{A}}_1$ et $\mathtt{\text{Commune}}$ n’est pas une clef de ${\mathcal{A}}_1$.\ ${\mathcal{A}}_2$ est en FNBC puisque ${\pi }_{{\mathcal{A}}_2}(\mathrm{\Sigma })$ est équivalent à\ $\{\mathtt{\text{Numéro de sécurité sociale}}\to \mathtt{\text{Nom, Code postal, Numéro de téléphone }}\}$\ Les DF sont préservées car $\mathrm{\Sigma }$ est équivalent à\ $$\{\mathtt{\text{Numéro de sécurité sociale}}\to \mathtt{\text{Nom, Code postal, Numéro de téléphone }}\};$$ $$\mathtt{\text{Commune}}\to \mathtt{\text{Département}};\mathtt{\text{Code postal}}\to \{\mathtt{\text{Commune, Département}}\}$$ qui ne contient que des DF locales.\ La décomposition est SPI.
• ${\mathcal{A}}_1$ est en FNBC car ${\mathcal{A}}_2$ est de cardinal 2.\ ${\mathcal{A}}_2$ n’est pas en FNBC car $\mathtt{\text{CodePostal}}\to \mathtt{\text{Département}},\mathtt{\text{Commune}}$ est locale et $\mathtt{\text{CodePostal}}$ n’est pas une clé de ${\mathcal{A}}_2$\ La décomposition est SPI et préserve les DF.

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 $\{A_1,A_2\}$ et $\{A_3,A_4\}$.
• Les seules clefs sont $\{A_1,A_2\}$ et $\{A_1,A_3\}$.

Solution

• $2^{n-1}$
• $2^{n-2}+2^{n-2}+2^{n-2}$
• $2^{n-4}Titremes3Titremes2+2^{n-4}$
• $3Titremes{2}^{n-3}$

Exercice

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

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

Solution

Initialisation : $X=\{A\}$

Etape 1 : Il existe une DF dont la partie gauche est incluse dans $ X$ : $A\to B$. On rajoute les attributs en partie droite.

D’où $X=\{A,B\}$

Etape 2: Il existe une DF dont la partie gauche est incluse dans $ X$ : $B\to C$. On rajoute les attributs en partie droite.

D’où $X=\{A,B,C\}$.

C’est fini, plus de DF à utiliser. Conclusion ${\left\{A\right\}}^{+}=\{A,B,C\}$

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

Solution

Une clef doit contenir $\{A,D\}$ puis ces deux attributs ne sont à droite d’aucune DF de $\mathrm{\Sigma }$. De plus ${\{A,D\}}^{+}=\{A,B,C,D\}$. La seule clef est donc $\{A,D\}$.

Exercice

Soit le schéma $\mathcal{A}=\{A,B,C,D,E,F\}$ et l’ensemble de dépendances fonctionnelles $$\mathrm{\Sigma }=\{\{A,B\}\to C,\{B,C\}\to \{A,D\},D\to E,\{C,F\}\to B\}$$

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

Solution

• On obtient ${\{A,B\}}^{+}=\{A,B,C,D,E\}$.
• Oui car $D\in {\{A,B\}}^{+}$
• Non car ${\left\{D\right\}}^{+}=\{D,E\}$ ne contient pas $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 $\mathrm{\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}=\{\mathtt{\text{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.

Solution

${\mathtt{\text{IdLivre}}}^{+}=\mathtt{\text{IdLivre, Titre}}$ $${\mathcal{A}}_1=\mathtt{\text{IdLivre,Titre}}{\mathcal{A}}_2=\mathtt{\text{IdLivre, Langue, Pays, IdTraducteur, Nom, Date}}$$ ${\mathtt{\text{Langue}}}^{+}=\mathtt{\text{Langue, Pays}}$ $${\mathcal{A}}_{2,1}=\mathtt{\text{Langue, Pays}}{\mathcal{A}}_{2,2}=\mathtt{\text{IdLivre, Langue, IdTraducteur, Nom, Date}}$$ ${\mathtt{\text{IdTraducteur}}}^{+}=\mathtt{\text{IdTraducteur, Nom}}$ $${\mathcal{A}}_{221}=\mathtt{\text{IdTraducteur, Nom}}{\mathcal{A}}_{222}=\mathtt{\text{IdLivre,Langue, IdTraducteur, Date}}$$ La décomposition FNBC obtenue est $$\{\mathtt{\text{IdLivre,Titre}}\}\{\mathtt{\text{Langue, Pays}}\}\{\mathtt{\text{IdTraducteur, Nom}}\}\{\mathtt{\text{IdLivre,Langue, IdTraducteur, Date}}\}$$ qui préserve toutes les DF.

Exercice

Soit le schéma $$\mathcal{A}=\left\{\mathtt{\text{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 ?

Solution

Rappelons l’algorithme pour décomposer un schéma $\mathcal{A}$~:

• On considère la décomposition initiale $\rho =\{\mathcal{A}\}$.
• Tant qu’il existe un sous-schéma $\mathcal{B}\in \rho$ et $X\subset \mathcal{B}$ tels que $X^{+}\cap \mathcal{B}\ne X$ et $X^{+}\cap \mathcal{B}\ne \mathcal{B}$ (ce qui signifie que la DF locale $X\to X^{+}\cap \mathcal{B}$ est une violation de FNBC pour $\mathcal{B}$), on remplace $\mathcal{B}$ par les deux sous-schémas $${\mathcal{B}}_1=X^{+}\cap \mathcal{B}\text{ et }{\mathcal{B}}_2=(\mathcal{B}\setminus X^{+})\cup X$$ De plus il n’y a pas besoin de considérer les parties $X\subset \mathcal{B}$ telles que $card(X)=card(\mathcal{B})-1$ puisque dans ce cas on $X^{+}\cap \mathcal{B}=X$ ou $X^{+}\cap \mathcal{B}=\mathcal{B}$.

Il est garanti que la décomposition finale est en FNBC et SPI. Par contre toutes les DF ne sont pas préservées en général. De plus on obtient, en général, des décompositions différentes si on change les DF (violant FNBC) utilisées. } - $B{E}^{+}=BEACH$ donc on remplace $\mathcal{A}$ par $${\mathcal{A}}_1=BEACH{\mathcal{A}}_2=BDEFG$$ $B^{+}=BH$ donc on remplace ${\mathcal{A}}_1$ par $${\mathcal{A}}_{11}=BH{\mathcal{A}}_{12}=BEAC$$ ${\mathcal{A}}_{11}$ est en FNBC car de cardinal 2. ${\mathcal{A}}_{12}$ est en FNBC car $$B^{+}\cap {\mathcal{A}}_{12}=B,E^{+}\cap {\mathcal{A}}_{12}=E,A^{+}\cap {\mathcal{A}}_{12}=A,C^{+}\cap {\mathcal{A}}_{12}=C$$ $$B{E}^{+}\cap {\mathcal{A}}_{12}=BEAC,B{A}^{+}\cap {\mathcal{A}}_{12}=BA,B{C}^{+}\cap {\mathcal{A}}_{12}=BC,E{A}^{+}\cap {\mathcal{A}}_{12}=EA,E{C}^{+}\cap {\mathcal{A}}_{12}=EC$$ $$A{C}^{+}\cap {\mathcal{A}}_{12}=AC$$ $D^{+}=DG$ donc on remplace ${\mathcal{A}}_2$ par $${\mathcal{A}}_{21}=DG{\mathcal{A}}_{22}=BDEF$$ ${\mathcal{A}}_{21}$ est en FNBC car de cardinal 2. $F^{+}=CD$ donc on remplace ${\mathcal{A}}_{22}$ par $${\mathcal{A}}_{221}=FD{\mathcal{A}}_{222}=BEF$$ qui sont tous deux en FNBC

Décomposition obtenue~:

BH  BEAC  DG  FD  BEF

La seule DF qui n’est pas préservée est $F\to C$. Toutes les variantes (en changeant les DF utilisées) que j’ai testées, donne une décomposition qui ne préserve pas toutes les DF. Bien sûr ce n’est pas une preuve que l’algorithme ne peut pas donner une décomposition sans perte de DF. - En ajoutant $FC$ à la décomposition précédente, on obtient

BH   BEAC   DG   FD   BEF   FC

qui est en FNBC et préserve les DF. De plus elle est SPI puisque la décomposition initiale est SPI. ($R\bowtie {\pi }_{FC}(R)=R$ pour toute relation $R$)

Exercice

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

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

Solution

• De manière similaire à l’exercice précédent on arrive à

BH   BEAC   DG   FD   BEF

mais, ici, BEAC n’est pas en FNBC (les autres le sont). A^+=AE donc on remplace BEAC par AE et ABC. Une décomposition FNBC est donc BH   AE   ABC   DG   FD   BEF Les DF BE → AC et F → C ne sont pas préservées. Les autres sont préservées.

• Il n’existe de décomposition FNBC qui préserve BE → A. En effet, si BE → A est préservée, il existe une DF locale à un sous-schéma $\mathcal{B}$ de la forme X → A. Cela implique que BE ⊂ X et donc BEA ⊂ B. Par suite $\mathcal{B}$ n’est pas en FNBC à cause de $A^{+}=AE$.