0% ont trouvé ce document utile (0 vote)

18 vues89 pages

Chap 10

BD 9

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

18 vues89 pages

Chap 10

BD 9

Transféré par

Daouda Gueye

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

16/04/2004

Chapitre 10
Théorie de la normalisation d’une base de données

Nous avons abordé la normalisation du schéma relationnel lors de l’étude du modèle relationnel.
Dans cette section, nous ferons un rappel des définitions de base en les formalisant davantage et nous
étudierons avec plus de détails les fondements théoriques de la normalisation. Les formes normales
supérieures, la FN4 et FN5 sont introduites et illustrées par des exemples complets. Les notions
présentées dans ce chapitre constituent les principaux éléments du corpus théorique sur le processus
de normalisation des bases de données et sur la validation des formes normales 4 et 5.

Schéma canonique d’une table

Dans la conception d’une base de données (BD), les schémas de relation obtenus et constitués par les
attributs ne sont pas uniques. Certains schémas qui regroupent les attributs sont préférables à
1
d’autres! Ils doivent être recherchés pour avoir une base de données relationnelle dite canonique . La
normalisation fondée sur les dépendances a comme objectif d’identifier ces schémas canoniques.

10.1 Dépendance fonctionnelle dans une relation R

Soit une relation R(X, Y, Z) dans laquelle X, Y, Z sont des ensembles d’attributs avec X ∪ Y ∪ Ζ = R.
L’extension de la relation de schéma R est notée r (minuscule r). Les variables de tuple t1 et t2 servant
à définir une dépendance fonctionnelle (DF) dans R entre X et Y. Cette dépendance est notée DF : X --
2
> Y ce qui signifie que Y est en dépendance fonctionnelle avec X ou, en d’autres mots, X détermine Y
avec X⊆ R et Y ⊆ R, ∀t1, t2 de l’extension r :
si t1[X] = t2[X] ⇒ t1[Y] = t2[Y] (cette définition est une implication logique)

NB : si X --> Y dans R, cela nʹimplique pas que Y -/-> X, car la définition de la dépendance
fonctionnelle nʹest pas une équivalence logique. Le X est appelé le déterminant (antécédent) et Y le
déterminé (conséquent). Il faut noter que si l’antécédent est faux quel que soit la paire de tuples, alors
l’implication est vraie et donc la DF est validée. Pour infirmer une dépendance, il suffit d’un seul
contre exemple formé avec une paire de tuples trouvés dans une extension valide. En revanche,
lʹexistence d’une DF dans une relation relève de la sémantique. Il est rare voire impossible dans la
réalité, d’examiner une extension volumineuse de tuples dans laquelle on retrouverait toutes les
dépendances possibles de la relation. Par contre, l’analyse informatique fournit l’information
nécessaire pour spécifier certaines contraintes et de ce fait, valider ou pas certaines dépendances
fonctionnelles ou les autres que nous étudierons plus loin dans ce chapitre.
Projet : noProjet budget site
P2 4,0M$ Québec
P3 2,7M$ Montréal
P4 2,7M$ Québec
P1 3,2M$ Lévis
ajout refusé --->P2 4,0M$ Gaspé
Figure 10.1

Source : [Link]
 André Gamache
Chapitre 10 Théorie de la normalisation du schéma

Si cette extension est représentative de tous les états possibles pour cette relation fort simple, il est
possible après examen d’énoncer les deux DF suivantes :
F = { noProjet --> budget; noProjet --> site }

Le même ensemble de DF peut être aussi formulé autrement en fusionnant les deux dépendances qui
partagent le même antécédent pour obtenir la seule DF suivante :
F = { noProjet --> budget, site }
Cette dernière dépendance fonctionnelle est équivalente aux deux premières.

Lʹensemble des DF dans une BD est représenté par le symbole F qui regroupe que les énoncés de
dépendance valides. Par exemple, lʹajout dʹun tuple (P2, 4,0M$, Gaspé) ne pourra se faire, puisque
lʹétat résultant contredirait une DF de F : le projet P2 correspondrait à deux sites.

Importance des DF dans une base de données

Les dépendances fonctionnelles imposent des contraintes aux extensions de relation ; elles seront
mises à contribution pour qualifier les schémas qui évitent les anomalies potentielles dans
lʹexploitation de la BD. Ces anomalies sont des états possibles qui découlent de la mise à jour, de la
suppression et de l’ajout de tuples. Certaines contraintes peuvent âtre intégrées dans le dictionnaire
de données et utilisées par le noyau du SGBD pour valider l’ajout ou la modification d’un tuple. Par
exemple, cela peut être une contrainte d’intégrité de type clé primaire ou clé candidate. Certaines
autres contraintes ne peuvent être implémentées aussi facilement.
Contrainte d’intégrité de type dépendance fonctionnelle. Une contrainte dʹintégrité est donc une
assertion logique exprimée par une formule sans variable libre et dont l’interprétation est toujours
vraie. Elle est aussi une formule logique fermée qui doit être satisfaite pour toutes les interprétations
ou état de la relation.
La dépendance fonctionnelle (DF) est une contrainte dʹintégrité exprimée par la formule logique
fermée suivante :
∀ti, ∀tj (ti[X] = tj[X] ⇒ ti[Y] = tj[Y])

Et cela pour ∀r (c’est-à-dire pour toutes les interprétations de R). Un tuple est acceptable par rapport à
l’extension r de R s’il vérifie toutes les formules fermées qui expriment les dépendances fonctionnelles
définies dans F dont le déterminant ∪ déterminé ⊆ R.
Dépendance fonctionnelle totale (DFT)
Si X--> Y et si ¬∃ X’ tel que X’ --> Y et que X’ ⊆ X, alors X--> Y est une dépendance totale (DFT) qui est
notée X -t-> Y ou X==> Y.
Une DFT est aussi une dépendance fonctionnelle dont le déterminant est minimal. Au contraire, s’il
existe X’⊆ X, alors Y est en dépendance fonctionnelle partielle sur X, car Y dépend dʹune partie de X.
Voici quelques exemples sur les DFT :
a) R (A, B, C) avec F = {A--> B; A--> C; A, B --> C}

Quelles sont les DFT dans R ?

Réponse :
Les DFT sont {A==> B et A ==> C}, car le déterminant est transitivité. Cependant, A, B =/=> C, n’est pas
une DFT car A --> B dans F.
b) R(A, D, E) avec F = {A--> D; A --> E; D --> E}
Quelles sont les DFT parmi les DF suivantes : D, A --> E; A, E --> D; A --> E ? Il nʹy a que A-t-> E
comme dépendance fonctionnelle totale, car les autres ont un sous-ensemble qui détermine le
déterminé.

Normalisation du modèle relationnel

Considérons le modèle E/R simple ci-dessous qui est transformé en modèle tabulaire comprenant trois
tables avec leurs extensions respectives. La troisième table, Machine est nécessaire en raison du lien
d’association n-m entre les deux classe du MCD E/A.

Operateur 1,n 1,m Machine

EstAutorise
nas* noMachine*
dateValidation
nom marque
debit
totServ
categorie

Operateur (nas*, nom)

Machine (noMachine*, marque, debit, totServ, categorie)
EstAutorise (nas*, noMachine, dateValidation)
Figure 10.2 : Modèle E/A simple et le MRD correspondant

La relation Machine a une extension ci-dessous que nous supposerons représentative de tous les états
possibles de R. i.e. dans laquelle toutes les dépendances sont vérifiées.

machine : noMachine marque debit totServ categorie

M812 Husky 60 25 tour
M975 Husky 60 34 tour
M756 Cincinnati 75 50 perceuse
Figure 10.3
Les DF de F sont alors les suivantes :
F = {noMachine --> marque, debit, totServ, categorie; marque, categorie --> debit}

La clé de cette relation est formée avec l’attribut noMachine parce que tous les attributs de la relation
sont en dépendance fonctionnelle avec celui-ci. Est-ce le meilleur schéma de table pour représenter

l’Entité Machine ? Par exemple, si la machine M756 est mise à la ferraille, le tuple correspondant doit
être supprimé de l’extension de la relation; il y a perte d’information, à savoir que cette machine
identifiée dans cette usine par M756, de marque Cincinnati est une perceuse dont le débit de
production est de 75 unités à l’heure. Si cette information a une importance pour l’organisation, la
suppression constitue une perte de la donnée rattachée à une faiblesse de ce schéma. Ce dernier peut-
il être remplacé par un autre, plus efficace dans la représentation des faits de la base, i.e. en évitant
cette perte d’information ? La réponse sera apportée par la normalisation qui séparera les données
factuelles sur l’équipement de celles spécifiques aux activités de l’usine.
Voici deux nouveaux schémas construits avec les mêmes attributs :
R1 (noMachine, marque, categorie, totServ)
avec la DF : noMachine --> marque, categorie, totServ
R2 (marque, categorie, debit)
avec la DF : marque, categorie --> debit

Chaque schéma de relation est formé avec les DF de F qui partagent le même déterminant.
L’extension de chaque relation est alors obtenue par la projection de la relation initiale Machine sur les
attributs des deux nouvelles relations.

r1 : noMachine* marque categorie totServ

M812 Husky tour 25h
M975 Husky tour 34h
M756 Cincinnati perceuse 50h

r2 : marque* categorie* debit

Husky tour 60
Cincinnati perceuse 75
Husky perceuse 60
Figure 10.4
Les deux relations obtenues rendent le schéma de la BD redondant, mais diminue la redondance des
données. La redondance du schéma n’est pas en soi un défaut puisqu’elle est due quʹà l’apparition
d’une clé étrangère composée, {marque, categorie}. Cette clé étrangère peut être l’objet d’un contrôle
automatique par le SGBD lors de la vérification par des procédures internes du SGBD de la contrainte
dʹintégrité référentielle.

Équivalence des relations

Est-ce que les deux relations R1 et R2 de la figure 10.4 sont équivalentes à la relation initiale Machine,
et cela tant du point de vue du schéma que de celui des données? Du côté du schéma, l’union des
attributs de R1 et R2 fournit le schéma d’origine pour la table Machine. Donc le schéma est
équivalent. Examinons maintenant l’équivalence au plan des données.

Soit R1, R2 et R3, il y a équivalence entre R3 et les deux autres relations, R1 et R2, si et seulement si la
condition suivante est vérifiée : R3 = R1 |x| R2 où |x| est l’opérateur de jointure naturelle. Le résultat
de la jointure doit inclure toutes les données de R3 sans ajouter d’autres données. Donc, dans
l’exemple ci-dessus, le calcul de la jointure reconstruit la table Machine. Il existe cependant d’autres
relations définies avec les mêmes attributs qui ne sont pas équivalentes à Machine, car leur jointure ne
reconstitue pas l’extension d’origine.

Décomposition dʹune relation

Soit une relation R(Α, Β, C), où le schéma de la relation est A ∪ B ∪ C avec A ∩ B ∩ C = vide et F = {A-
>B ; A->C}. En dʹautres mots, les ensembles d’attributs A, B et C sont des partitions dʹattributs. S’il
existe une DF dans F, telle que A --> B, alors le schéma de la relation R peut être décomposé en deux
relations et cela sans perte de données :
R1(A, B) et R2 (A, C)

Le schéma de la deuxième relation est obtenu en supprimant les attributs du déterminant de la DF,
soit {A, B, C} – {déterminant dans A->B}. Cette décomposition est valide, seulement si la jointure des
relations obtenues donne la relation initiale comme résultat de leur jointure :
R(A, B, C) = R1(A, B) |x| R2(A, C)

Or la jointure est sans perte si et seulement si l’attribut commun des deux relations obtenues
détermine tous les autres attributs dans au moins une relation. Dans l’exemple précédent l’attribut
commun dans R1 et R2 est A et dans F, A --> B.

Dans lʹexemple qui suit, la relation Gestion possède deux dépendances fonctionnelles :
Gestion (noProjet, budget, site) avec F= {noProjet --> budget; noProjet --> site}
La clé est définie par les DF de F, soit noProjet puisque cet attribut détermine tous les attributs.
La relation Gestion pourrait cependant être décomposée sans perte en deux relations :
R1 (noProjet, budget) R2 (noProjet, site)

Cette division de la relation Gestion nʹest pas souhaitable dans ce cas-ci, puisque toutes les DF de F
ont le même déterminant. En théorie, toute l’information qu’il était possible de représenter dans la
relation initiale Gestion peut aussi l’être avec les nouvelles relations R1 et R2. S’il est utile pour des
fins de performances ou de confidentialité de représenter les budgets de projets séparément de leurs
sites alors ces dernières peuvent être renommées pour être plus significatives: BudgetProjet et
SiteProjet. Une jointure sera cependant nécessaire pour obtenir le budget et le site d’un projet
particulier.

Voici une décomposition invalide d’une relation au plan des données :

R(A, B, C,) avec F = {A-->B; A -->C}

La décomposition de R en deux relations : R1(A, B) et R2(B, C) est invalide, car l’attribut commun B ne
détermine pas A ou C dans lʹune ou lʹautre des deux relations obtenues par décomposition : B -/-> A et
B -/-> C. Bien que la décomposition préserve l’équivalence du schéma, elle ne garde pas
l’équivalence des données.

Théorème de Heath
Si lʹon a une relation R (A, B, C) avec A, B, et C les ensembles d’attributs du schéma. Si R vérifie la
dépendance fonctionnelle A -> B, alors R est aussi égale à la jointure des projections de R soit R1[A, B]
et R2[A, C]. En d’autres mots, l’attribut commun au deux nouveaux schémas détermine tous les
3
attributs dans une des relations . Notons aussi que la décomposition peut se faire avec une DF
obtenue par fusion de toutes les DF de F qui partagent le même déterminant.

Démonstration : Il faut démontrer que les deux projections R1 et R2 obtenues de R(A, B, C) peuvent
faire l’objet d’une jointure sans perte et cela pour obtenir l’extension initiale. En premier, nous
démontrons que chaque projection d’un tuple de R donne un fragment de tuple qui appartient à R1 ou
à R2. Ainsi aucun tuple de R nʹest perdu par la décomposition. Soit un tuple quelconque (a, b, c) ∈ r,
alors un tuple quelconque de la projection de R sur (A, B), c’est-à-dire (a, b) ∈ R1 et la projection de R
sur (A, C ) donne aussi un tuple (a, c) ∈ R2. Donc le tuple (a, b, c) appartient à la jointure R1 |x| R2.
Donc pour tout tuple de l’extension initiale r, il existe deux projections qui se recomposent pour
donner un tuple de la jointure.

Il faut maintenant démontrer que chaque tuple de la jointure calculée est obligatoirement un tuple de
r et qu’aucun tuple étranger n’est créé par cette jointure. Soit (a, b, c) un tuple du calcul de R1 |x| R2.
La formation d’un tel tuple suppose que les tuples (a, b) ∈ R1 et (a, c) ∈ R2. Supposons maintenant
quʹil existe un tuple quelconque s de R, soit (a, b’, c), avec une valeur quelconque pour b’, la projection
de s sur (A, C) donne un tuple (a,c) ∈ R2. Par conséquent, la projection (a, b’ )∈ R1 devrait être aussi
dans l’extension de R1. Alors, (a, b) ∈ R1 et (a, b’) ∈ R1. Si tel est le cas, il y a infirmation de la DF
donnée en hypothèse qui stipule que A--> B. Par conséquent, il faut que b = b’ pour que seul le tuple
(a, b, c) ∈ R. Le théorème inverse est faux. Lorsqu’une relation R(A, B, C) est obtenue par la jointure de
deux relations R1(A, B) et R2(A, C), il ne s’en suit pas que la dépendance fonctionnelle A --> B soit
valide dans R.

Propriétés des dépendances fonctionnelles

Soit une relation R(X, Y, Z); cette dernière est formée de trois ensembles d’attributs mutuellement
exclusifs. Cette relation possède certaines propriétés qui seront mise en œuvre dans la normalisation
et/ou le design d’une base de données.

1- Réflexivité et dépendances fonctionnelles triviales

Si Y ⊆ X ==> X-->Y. Les éléments d’un ensemble déterminent ceux du sous-ensemble quelle que soit
la relation hôte, pour autant que le déterminé et le déterminant soient dans la même relation. On dit
que la DF est indépendante du contexte, c’est-à-dire qu’il suffit que les attributs qui composent le
déterminant et le déterminé soient présents dans un même schéma de relation, pour que la
dépendance existe entre ces attributs.
Exemple :
R: A B C
a1 b1 c1
a2 b2 c2
a3 b3 c3
a1 b2 c1
a1 b1 c4
Figure 10.5

Un attribut A, du schéma de R est un sous-ensemble de {A, B} et ce dernier détermine chacun des ses
éléments.
Puisque A ⊆ {Α, Β} on a que Α, Β --> A et A, B --> B
Démonstration : Notons que si t1[A, B] = t2[A, B] cela implique que t1[A] = t2[A] et t1[B] = t2[B] pour
toute paire t1 et t2 d’une extension quelconque r de R.
Si t1[A, B] = t2[A, B], alors t1[A] = t2[A] et, selon la définition de la DF, A, B --> A .
Cas particulier : DF triviale
Si A ⊆ A alors A --> A. Les DF dérivées par réflexivité sont dites triviales.

2- Augmentation du déterminant dʹune DF

Il est toujours possible dʹaugmenter un déterminant d’une DF avec un attribut quelconque de R sans
invalider la dépendance fonctionnelle initiale.
Supposons le schéma R composé des attributs X, Y, Z.
Avec Z ⊆ R, si X --> Y est valide dans R, alors X, Z --> Y.
Démonstration
Avec la prémisse X --> Y, alors pour toute paire de tuples t1 et t2 ∈ r, nous avons que
t1[X] = t2[X] ⇒ t1[Y] = t2[Y]. Si la valeur t1[Z] est ajoutée au tuple t1[X], alors (t1[X], t1[Z]) =
t1[X, Z]. Il en est de même pour t2[X, Z]. Cet ajout ne change pas la valeur de vérité de
lʹimplication initiale qui peut être reformulée ainsi :
t1[X, Z] = t2[X, Z] ⇒ t1[Y] = t2[Y]
Par conséquent, en référence à la définition de la DF, on a alors que X, Z ⇒ Y. Avec une DF
valide, on peut toujours ajouter un attribut quelconque au déterminant pour obtenir une
nouvelle DF toujours valide.

Cas particulier : addition de la dépendance triviale Z --> Z

Lʹaugmentation du déterminant et du déterminé avec une DF triviale symétrique est possible et
fournit une DF valide. Supposons la DF triviale Z--> Z avec la DF X --> Y, alors X, Z --> Y, Z.
Démonstration
De l’augmentation avec Z, on a que X, Z --> Y, ce qui est équivalent à l’assertion de la DF : si t1[X, Z] =
t2[X, Z], alors t1[Y] = t2[Y]. Si le deuxième membre est augmenté de la même valeur de Z, cette égalité
demeure : t1[Y, Z] = t2[Y, Z] En se reportant à la définition de la DF, il faut conclure que X, Z --> Y, Z.

3- Transitivité
Si les dépendances X --> Y et Y --> Z sont valides dans une même relation R, alors X --> Z lʹest aussi
dans R.
Démonstration
Supposons une extension r qui vérifie les DF de l’hypothèse et deux tuples quelconques t1 et t2 ∈ r .
La projection d’un tuple sur un attribut donne une valeur. Donc les propositions suivantes sont
vraies :
t1[X] = t2[X] ⇒ t1[Y] = t2[Y] et
t1[Y] = t2[Y] ⇒ t1[Z] = t2[Z] sont vraies par définition.
Donc t1[X] = t2[X] ⇒ t1[Z] = t2[Z] est une formule logique vraie. Par définition cette
implication représente la DF X --> Z, qui est donc valide dans l’extension r de R.

4- Pseudo transitivité
Si X --> Y et Y, W --> Z dans R, alors X, W --> Z est aussi valide dans R.
Démonstration
(1) X --> Y par hypothèse
(2) W --> W une triviale
(3) X, W --> Y, W par augmentation de (1)
X, W --> Z par transitivité avec une DF de F.

5- Union des déterminés (ayant le même déterminant) de F

Si X --> Y et X --> Z sont valides dans le schéma R, alors X --> Y, Z.
Démonstration
(1) X --> Y une DF de F
(2) Z --> Z par réflexivité
(3) X, Z --> Y, Z par augmentation de (1) avec (2)
(4) X --> Z une DF de F
(5) X --> X une réflexive
(6) X --> X, Z par augmentation de (4) avec (5)
(7) X --> Y, Z par transitivité de (6) et (3).
Exemple :

MachineOutil (noMachine, marque, debit)

avec les dépendances fonctionnelles suivantes:
F = {noMachine --> marque; noMachine --> debit}

machineOutil: noMachine * marque debit

M812 Husky 60
M975 Husky 60
M756 Cincinnati 75
Figure 10.6
Par la propriété de l’union des déterminés, on peut énoncer à partir de F que :
noMachine --> marque, debit
L’examen de l’extension de la table MachineOutil ne contredit pas cette nouvelle DF dérivée.

6- Décomposition dʹune DF
Si X --> Y, Z est valide dans l’extension r du schéma R, alors X --> Y et X --> Z le sont aussi dans le
même schéma R. On a alors {X --> Y, Z} ≡ {X --> Y et X --> Z}. On peut aussi écrire cette décomposition
sous la forme d’une conséquence logique :
X --> Y, Z |= X --> Y
X --> Y, Z |= X --> Z
Démonstration
(1) X --> Y, Z par hypothèse : une DF de F
(2) Y, Z --> Y (car Y ⊆ Y, Z) par réflexivité : DF triviale
(3) X --> Y par transitivité avec (1) et (2).

(1) X --> Y, Z par hypothèse : une DF de F

(2) Y, Z --> Z par réflexivité : DF triviale
(3) X --> Z. par transitivité avec (1) et (2).

Le déterminé complexe (ou multiattribut) peut être transformé pour obtenir un déterminé simple,
transitivité, au prix d’une augmentation du nombre de DF dans F. Certains auteurs utilisent
lʹexpression de dépendance élémentaire lorsque le déterminé est formé dʹun seul attribut.

7- Projectabilité dʹune dépendance fonctionnelle

Si X --> Y est valide dans R(W), où W est l’ensemble des attributs du schéma alors X --> Y’ dans R’(Ω’)
lorsque les conditions suivantes sont vérifiées :
W’ ⊆ W et Y’ ⊆ W
X ⊆ W’ et Y’ ⊆ W’∩ Y ) <--
En d’autres mots, une projection de r sur les attributs de W’ notée rʹ comporte une DF valide pour X
sur les attributs communs entre Y et les attributs de rʹ.

Exemple : Soit la relation r (A, B, C, D, E) avec A --> B, C donnée comme une DF valide.
La projection r’(A, B, D) obtenue par la projection de r sur le ou les attributs communs entre le
déterminé de la DF de r et le nouveau schéma de rʹ. Les attributs communs entre les projections {B, C}
et {A, B, D} sont {B}. Donc, la DF A --> B est aussi valide dans le schéma de la nouvelle relation, R’.
Autre exemple :
Soit R(A, B, C, D) avec A --> C, D. La projection r’ (A, B, C) de r vérifie la DF : A --> C.
L’intersection entre (C, D) et (A, B, C) est C et donc A--> C est donc valide.

8- Addition de deux dépendances

Si X --> Y et W --> Z sont deux DF valides dans R, alors X, W --> Y, Z est aussi valide dans R.
Démonstration
(1) X, W -> W une triviale
(2) W --> Z une hypothèse
(3) X, W -> Z ** par transitivité
(4) X, W -> X une triviale
(5) X --> Y une hypothèse
(6) X, W --> Y ** par transitivité
(7) X, W --> Y, Z par addition
CQFD

Sommaire des propriétés des DF

Les propriétés les plus importantes des dépendances fonctionnelles sont les suivantes:
a) Tout déterminant d’une DF peut être augmenté avec n’importe quel attribut;
b) Tout déterminé peut être augmenté avec les attributs du déterminant;
c) Un ensemble quelconque d’attributs détermine chacun de ses sous-ensembles;
d) Un déterminé composé de plusieurs attributs peut toujours être réduit en un déterminé
monoattribut. Il en résulte une augmentation du nombre de DF dans F.

Exemples : Soit R(A, B, C, D), une relation avec des DF valides:

a) Si A --> B est valide dans R, par augmentation avec une triviale, C --> C,
on obtient : A, C --> B, C qui est aussi valide pour R. De même par décomposition pour obtenir les
df équivalentes : A, C --> B et A, C --> C .

b) Si A, C --> D est valide dans R, alors A, C --> A, D est aussi valide dans R par augmentation du
déterminé :
A, C --> D, C ajout de C --> C
A, C --> A, D par ajout de A--> A
A, C --> A et A, C --> D sont les dépendances équivalentes.

On peut donc conclure que tout attribut du déterminant peut être ajouté au déterminé.

c) Les triviales suivantes sont aussi valides dans R :

A, B, C --> A; A, B, C --> B; A, B, C --> C (réflexivité)

Les propriétés étudiées précédemment ne sont pas toutes essentielles, ni minimales. Certaines
4
peuvent être déduites à partir de trois propriétés essentielles que William Armstrong (1974) a
présentées comme étant en quelque sorte les axiomes d’une théorie du premier ordre.

Axiomes dʹArmstrong
Les axiomes dʹArmstrong sont les propriétés des DF à partir desquelles toutes les autres peuvent être
dérivées :
a) la réflexivité : Y ⊆ X ⇒ X --> Y (cas particulier : X --> X);
b) lʹaugmentation : X --> Y et que Z ⊆ W ⇒ X, W --> Y, Ζ;
c) la transitivité : X --> Y et Y --> Z dans R, alors X --> Z;

Dérivabilité d’une dépendance fonctionnelle : F |- f

Une dépendance fonctionnelle (DF) particulière notée f est dérivable de l’ensemble F par les
propriétés des dépendances fonctionnelles (notée F|- f) si et seulement s’il existe une suite (f1, f2, f3, ...
fn) de dépendances fonctionnelles, chacune vérifiant l’une ou l’autre des propriétés suivantes :
a) fn est la dépendance recherchée, soit le résultat;
b) pour ∀i où 1<=i<=n, fi ∈ F où fi peut être obtenue à partir de F en utilisant les trois axiomes comme
seules règles d’inférence.

Exemples d’une suite de d’inférences :

Dériver la DF suivante : I, C, D --> Z de F = {A, B, C-->Z; D, B --> A; I, C --> B}.
Il faut démontrer que F |- I, C, D --> Z.
(1) I, C --> B par hypothèse
(2) D --> D triviale
(3) I, C, D --> D, B par augmentation de (1) par (2)
(4) D, B --> A par hypothèse
(5) I, C, D --> A par transitivité
(6) C --> C
(7) I, C, D --> A, C par augmentation
(8) I, C --> B par hypothèse
(9) I, C, D --> A, C, B par addition de deux DF : 7 et 8
(10) A, B, C --> Z par hypothèse
(11) I, C, D, --> Z de 9

CQFD

En supposant que F = {A --> B; B, C --> D; B, D, E --> J}, dérivez la DF suivante A, C, E --> J

(1) A --> B par hypothèse
(2) C, E --> C, E triviale
(3) A, C, E -->B, C, E par addition de deux DF
(4) B, C --> D par hypothèse
(5) B, E --> B, E augmentation avec la triviale E--> E
(6) B, C, E --> B, E, D par addition de deux DF
(7) A,C,E --> B,E,D transitivité (3) et (6)
(8) B, D, E --> J par hypothèse
(9) A, C, E --> J par transitivité avec (7) et (8);
CQFD

Conséquence logique F |= f
Soit une relation R(W), où W est l’ensemble des attributs du schéma de R et F un ensemble de DF
définies dans W. Une dépendance fonctionnelle f appelée aussi DF est une conséquence logique de F
(notée F |= f) si toute extension (analogue à l’interprétation ) qui vérifie F vérifie aussi f.

Validité
Si F |- f, alors F |= f dans R. Si lʹon peut formellement dériver la dépendance fonctionnelle f de F,
alors toute extension de la relation vérifie f. Une dérivation formelle d’une DF correspond à
une contrainte sémantique dans les données de R.

Complétude sémantique
Si F |= f, alors F |- f. Si la dépendance fonctionnelle f est vérifiée par toute extension de R, alors f est
une formule qui peut être formellement dérivée par les règles dʹinférence dʹArmstrong.
Exemple
Soit la relation R(A, B, C, D) avec F= {A--> B; A-->C; B, C --> D}, démontrez que la DF A, C -->D peut
être dérivée de F.
(1) A --> B hypothèse
(2) A, C --> B, C par augmentation avec C --> C
(3) B, C --> D hypothèse
(4) A, C --> D par transitivité
(5) F |= A, C -->D
CQFD

Les axiomes de Armstrong sont valides et complets par rapport à F. Valides parce que toute DF qui
peut être dérivée de F est aussi vérifiée dans toute extension de R qui vérifie F. Ils sont complets parce

que toute dépendance vérifiée ou découvertes dans toutes les extensions de R peuvent être dérivées
à partir de F.

10.2 Fermeture F+ dʹun ensemble de dépendance fonctionnelles

La fermeture est définie comme étant l’ensemble de toutes les dépendances fonctionnelles f dérivables
de F à partir des axiomes de Armstrong. Elle est notée F+ .
F+ = {f | F |- f}
Sur le plan sémantique, la fermeture peut être considérée comme l’ensemble des DF, qui sont des
conséquences logiques de F : F+ = {f | F |= f}
Cas particulier
Si F+ = F, alors F est une famille complète de DF.
Le schéma relationnel d’une base de données doit vérifier toutes les DF de la fermeture. Plus
particulièrement, toute relation R doit vérifier toute DF de F+ dont les attributs, déterminés et
déterminants, sont dans son schéma.

Calcul détaillé de la fermeture F+

Le calcul de la fermeture de F est fini, mais peut devenir rapidement un calcul long avec plusieurs
dépendances fonctionnelles. La procédure détaillée est la suivante :

Procédure FERMETURE
1- Dérivation de toutes les triviales à partir de F après sa transformation
en dépendances élémentaires;
2- F1 = F ∪ triviales;
3- Dérivation de toutes les DF par augmentation des déterminants de F1 avec
les attributs de F. On obtient F2 = F1 ∪ augmentées;
4- Dérivation de toutes les DF par transitivité
F3 = F2 ∪ transitives.
Lʹensemble résultant de lʹunion des DF dérivées par les axiomes donne la fermeture de F.

Exemple : R(A, B, C) avec F ={A -->B; A --> C}

a) les DF réflexives fournissent les DF triviales :
A --> A; A, B --> A, B; A, B, C --> A, B, C;
B --> B; A, C --> A, C; A, B, C --> A, B;
C --> C; B, C --> B, C; A, B, C --> A, C;
A, B -->A; A, B, C --> B, C;
A, B -->B; A, B, C --> A;
A, C -->A; A, B, C --> B;
A, C -->C; A, B, C --> C;
B, C --> B;

B, C --> C;

Il faut remarquer la redondance introduite par les DF triviales qui ne sont pas élémentaires (italique
gras). Les premières n’ont plus à être produites; seules les df élémentaires obtenues par augmentation
du déterminant suffisent au calcul de la fermeture.

b) les DF augmentées :
A, B--> A; A, B,C -->A ;
A, C --> A; A, B, C -->B
B, A --> B; etc
B, C --> B;

Les dépendances augmentées avec les triviales ne produisent pas de nouvelles DF ; elles sont aussi
redondantes. Seules les augmentées obtenue avec les DF de F sont à conserver.
c) Les DF transitives : {Toutes les DF dérivées par implication logique à partir des dépendances de F }
ne sont dans cet exemple que des triviales. Dans certains cas de F, la transitivité peut générer de
nouvelles DF qui sont à conserver dans la fermeture.

Le calcul de la fermeture peut devenir laborieux avec cette approche naïve fondée sur l’énumération
exhaustive. Une méthode plus rapide, de préférence linéaire, est souhaitable pour que la fermeture
soit pratique! Pour y arriver, il faut utiliser la notion de fermeture d’attribut, notamment d’un attribut
ou ensemble d’attributs déterminant.

10.2.1 Fermeture dʹun ensemble dʹattributs A+

La fermeture d’un ensemble d’attributs A est notée A+ et est définie comme l’union de tous les
5
déterminés par A dans F. Une telle procédure proposée par Ullman permet dʹéviter le calcul détaillé
de F+. Le calcul de la fermeture des attributs de l’ensemble A est plus rapide puisqu’il est linéaire en
fonction de la cardinalité de A.

Calcul de la fermeture dʹun ensemble dʹattributs A+

Il s’agit de former graduellement une suite S par la construction de suites intermédiaires composées,
au départ de la DF réflexive dont le déterminant est l’attribut dont on recherche la fermeture, et d’y
ajouter ses déterminés dans F.
Faire i = 0
Si = A !Initialisation de la suite initiale avec A
Si+1 = Si ∪ d -- où d est l’union des déterminés dans F,
-- dont le déterminant est inclus dans Si .
Faire tant que Si+1 != Si
i = i + 1
Si+1 = Si ∪ d

Afficher A+ = Si
Fin.

Exemple : Soit une relation R(A, B, C, D) avec F = {A, B --> C; D --> B; A, B --> D}.
Calculez AD+: S0 = A, D
S1 = {A, D} ∪ Β = {Α, D, Β} pour i=0
S2 = {Α, D, Β} ∪ {C, B, D} = {A, B, C, D} pour i = 1
S2 = {A, B, C, D} ∪ {C, B, D} = {A, B, C, D} pour i = 2
La procédure se termine car la dernière suite est identique à la précédente soit {A, B, C, D} et donc A,
D --> B ∈ F+. Ainsi, puisque B est contenu dans AD+, il faut en conclure que A, D --> B ∈ F+.

Couverture de F
Une couverture C de F pour laquelle C ⊆ F est un ensemble de DF tel que la fermeture de F est
identique à celle de C : C+ = F+ . La couverture C de F est un sous-ensemble de F qui a une cardinalité
moindre ou égale à F et qui fournit la même fermeture. Lʹensemble F qui résulte de lʹanalyse doit
avoir des déterminés parmi lesquels tous les attributs identifiés sont représentés.

F+
F(1)
F(2)
CC analyse 1 analyse 2

Figure 10.7
La couverture C de F n’est pas unique et appartient à une famille de couvertures. De plus, elle n’est
pas nécessairement minimale par rapport à F. La notion de couverture ne sous-tend pas que celle-ci ait
le plus petit nombre de dépendances.

10.2.2 Couverture non redondante C*

Cette couverture non redondante de F est notée C* et est définie comme l’ensemble des DF strictement
nécessaires pour avoir la même fermeture de F :
C* = C si et seulement si ¬∃ C’⊆ C tel que (C’)+ = F+

Exemple : Soit R(X, Y, Z) avec F = {X --> Y; Y --> Z; X --> Y, Z}.

Calcul de F+ :
F+ = {X --> Y; Y -->Z; X --> Y, Z + les réflexives + les augmentées}
C = {X --> Y; Y --> Z; X --> Z } -- les réflexives et les augmentées sont dérivables
C* = {X --> Y; Y --> Z}

La couverture non redondante ne fournit que les DF strictement nécessaires pour assurer la dérivation
de la fermeture de F.

Quelques propriétés de la fermeture

On note quelques propriétés de la fermeture : La première (a) énonce que chaque dépendance de F est
comprise dans la fermeture et dans la couverture et à la limite, celle-ci se confond avec l’ensemble F.
a) F ⊆ F+ ⊆ C+
La deuxième (b) stipule que la fermeture de la fermeture de F donne F.
b) (F+)+ = F+

c) Une autre propriété a trait à la fermeture d’un attribut W de R. En effet, si celle-ci est égale au
schéma de la relation, alors W est une superclé.
W+= R alors W est une superclé qui contient une clé primaire de R.
Exemple : si R(W, Z, U) est une relation dans laquelle W+ = {W, Z, U} alors W est une superclé à partir
de laquelle, il est donc possible de trouver la clé par des suppressions successives des attributs de W.

Algorithme pour le calcul de C*

On peut calculer C* par lʹalgorithme suivant :
Faire C = F; /*hypothèse que C est identique à F dont les déterminés
sont monoattribut */
Faire tant que F != vide; /*F vide lorsque chaque DF sera testée*/
Choisir une f (i.e. X--> A) dans F (f est une DF de F)
Faire F = F - f; -- enlèvement de f de F
Si f ∈ (C - f)+ alors C = C - f
/*f appartient à la fermeture de C-f ? */
Afficher C;
Fin.
Le test f ∈ (C - f)+ est connu comme le problème de l’appartenance à la fermeture et qui peut être
résolu par un autre algorithme linéaire, c’est-à-dire dont le temps dʹexécution est proportionnel à la
cardinalité de F.

10.2.3 Problème de lʹappartenance à une fermeture

Soit F un ensemble de DF spécifiées au terme d’une analyse et f∈ F. La question est de savoir
rapidement si f ∈ (F - f)+. Pour y répondre, il faut calculer la fermeture de (F-f) et de vérifier si f y est
incluse. Le calcul est de complexité O|F|2. Il est possible d’utiliser un algorithme linéaire proposé et
6
amélioré par Beeri et Bernstein .

Théorème de la fermeture dʹun ensemble dʹattributs

Soit F un ensemble de DF parmi lesquelles une DF est choisie. Supposons que la DF soit du type A-->
B. Si B ⊆ A+ (définie par rapport à F) alors A--> B ∈ F+, sinon A--> B ∉ F+. Le symbole A+ est la
fermeture de A définie comme étant l’union de tous les déterminés de A dans la fermeture de F par les

axiomes. Donc, on peut calculer l’appartenance d’une DF à une fermeture sans la calculer
explicitement grâce à la notion de fermeture d’attributs.

Calcul de la couverture minimale de F

Une manière naïve d’obtenir la couverture minimale de F est de calculer toutes les couvertures non
redondantes et de choisir celles de cardinalité minimale. Il existe toutefois d’autres algorithmes plus
7
rapide pour le calcul de la couverture minimale, dont celui de Mummenmaa et Tanisch qui reprend
8
celui de Maier .
Exemple
Transformer chaque DF de F en une dépendance élémentaire ayant un déterminé monoattribut et
ensuite exécuter lʹalgorithme suivant :
Tant qu’il y a une DF de F qui est non testée :
a)Choisir une DF de F du type X-->A en parcourant les DF dans un ordre
fixe;
b)Si Z⊆X tel que F ⊆((F - {X-->A})⊆{Z--> A})+ alors remplacer
immédiatement X--> A par Z-->A dans F;
c) Tant qu’il y une DF dans le F initial qui n’a pas été testée :
- Choisir une DF de F soit X--> A;
- Si X--> A∈F et X --> A∈(F -{X-->A})+,alors enlever X--> A de F.
L’ensemble résiduel de DF est la couverture minimale de l’ensemble F initial.

Voici un exemple de l’application de cet algorithme pour trouver la couverture minimale :

S = {R1(A, B, C)} et F = {A, B --> C}
La DF est remplacée par A --> C, car A --> C |- A, B --> C par augmentation.
L’ensemble résiduel n’est composé que de A --> C soit la couverture minimale. Il est facile de s’en
convaincre, puisque la DF initiale peut être obtenue par augmentation dans la fermeture de Cmin. Un
9
algorithme encore plus performant a été proposé par Diederich en utilisant le concept de la fermeture
gauche et de la fermeture droite.

Recherche des clés : primaire, candidate et étrangère dans une relation

Soit une relation R (A1, A2, A3, ... An). La spécification d’une clé quelconque X de R définit
automatiquement un ensemble de DF et en exclut d’autres :
a) X --> Ai pour i = 1 à n
b) ¬∃ X’ tel que X’ --> Ai pour i = 1 à n.

Soit la relation R(A, B, C, D, E) avec le F suivant :

F = {A --> B, C; C, D --> E; B --> D; E --> A}
Le problème de trouver les clés candidates pour cette relation est de complexité NP, i.e. que le temps
dʹexécution de lʹalgorithme de recherche de la clé augmente exponentiellement avec lʹaugmentation
du nombre dʹattributs dans le schéma. Avec un petit nombre dʹattributs et en précisant les clés simples

ou monoattribut, le nombre de tests demeure raisonnable. Pour un F de petite cardinalité, il est alors
possible de faire les tests via la fermeture des attributs. Voici quelques exemples :
a) Test de A comme clé : Si A --> B, C, D,E alors B, C, D,E ⊆ A+.
Or A+ = A, B, C, D, E. Donc, A est une clé candidate de R;

b) Est-ce que E une clé ? Si E --> A, B, C, D; alors A, B, C, D ⊆ E+.

Or E+ = A, B, C, D. Donc, E est une clé de R;

c) Test avec C, D : C, D --> A, B, E;

(CD)+ = C, D, E, A, B
Donc C, D est une clé;

d) Test avec B : B --> A, C, D, E?

B+ = B, D
Donc, B n’est pas une clé de R;

e) Test avec B, C : B, C --> A, D, E ?

(B, C)+ = B, C, D, E, A
Donc, B, C est une clé de R.

La recherche exhaustive des clés sous-tend une série exhaustive de tests avec toutes les
combinaisons possibles d’attributs. Il devient évident alors que le processus peut être très
long dès lors que le nombre d’attributs est grand.

10.2.4 Attribut redondant dans une DF

Un attribut A est redondant dans la DF X --> Y de F s’il peut être enlevé du déterminant ou du
déterminé de la DF, sans modifier la fermeture de F. Soit F un ensemble de DF et F’ = F - {X --> Y} ∪ X’
--> Y} où X’ est le déterminant obtenu en enlevant un attribut A à X. La recherche d’attributs
redondants permet de simplifier les déterminants et les déterminés des DF pour alléger le calcul
détaillé de la fermeture d’un ensemble de DF ou d’attributs :
Si (F)+ = (F’ )+ alors X - X’ est redondant dans X --> Y.
Soit une relation R(A, B, C, D) avec F = {A --> B, C; B --> C; A, B --> D}. Il faut trouver lʹattribut ou les
attributs redondants dans les DF de F.
Y a-t-il redondance dʹun attribut dans A, B --> D de F ?
Cas 1 Si l’attribut B est redondant alors F’ = {{A --> B, C; B --> C; A --> D} donne la même fermeture
que F+. Il faut donc démontrer que (F’)+ = (F)+. Pour éviter de calculer explicitement les fermetures, il
suffit de démontrer que : F |- A --> D et F’ |- A, B --> D.

F |- A --> D i.e. que de F, il est possible de dériver la DF A --> D

D ⊆ (Α)+
Or A+ = {A, B, C, D}.
et
F’ |- A, B --> D
D ⊆ (Α, Β) + dans F’
{A, B}+ = {A, B, C, D}

La première dérivation souligne que B est redondant puisque A--> D est dérivable. La deuxième est
facile à démontrer puisquʹelle découle directement dʹune propriété de la DF.
Donc, l’attribut B est redondant dans la DF A, B --> D.

Cas 2 Vérifions maintenant si l’attribut A est étranger dans A, B --> D.

Si tel est le cas, alors les deux ensembles F’ = {A --> B, C; B --> C; B --> D} et
F = {A --> B, C; B --> C; A, B --> D} donneront la même fermeture : (F’)+ = F+

Il suffit donc de démontrer les dérivations suivantes :

F’ |- A, B --> D F |- B --> D
D ⊆ (A, B)+ D⊆B)+
(A, B)+ = A, B, C, D (B)+ = {B, C }
donc F’ |- A, B --> D F |- (B --> D) n’est pas vérifiée.

Donc, A n’est pas étranger dans la DF A, B --> D. On peut faire la même vérification avec les autres
cas pour s’assurer de la nécessité de la présence de B dans la DF A --> B, C et de C dans la
dépendance A --> B, C.

10.3 Conception dʹun schéma de BD

La conception d’une base de données doit aboutir à la formulation dʹun ensemble de schémas
relationnels qui a plusieurs propriétés, à savoir la conservation des données et la conservation des
dépendances. Ces deux qualités de la base de données sont parfois difficiles à faire cohabiter! Au
besoin, il faudra choisir et opter pour la conservation des données.
La conservation des données (CD) privilégie l’invariance de l’information de la BD : quel que soit le
schéma, l’information représentée restera la même. Il ne peut y avoir ni création ni perte
d’information en passant d’un schéma à un autre et cela, avec les mêmes données.

La conservation des dépendances fonctionnelles (CDF) privilégie le respect des contraintes d’intégrité
avec le minimum de calcul de la part du SGBD, c’est-à-dire sans que celui-ci ait à faire des jointures ou
dʹautres calculs à chaque mise à jour ou à chaque suppression de données dans la BD.

Une conception inappropriée d’une base de données se traduit par les phénomènes suivants :
a) Redondance non justifiée par la recherche d’un niveau élevé de performance;
b) Présence des anomalies d’ajout, de suppression et de mise à jour qui mettent en péril l’intégrité de
la BD.

Il faut très souvent faire un compromis entre la conservation des données et celle des dépendances.
Dans plusieurs cas, il faudra choisir la première, quitte à confier au SGBD la mission de vérifier le
respect des dépendances au moyen de déclencheurs (triggers) de la base. C’est une pratique courante
observée dans le domaine des SGBD. En revanche, il n’est pas souhaitable de privilégier la
conservation des DF et de laisser au SGBD seul la vérification de la conservation des données. Il faut
rappeler qu’une bonne conception qui favorise ces propriétés, simplifie la tâche de tout logiciel SGBD
et que certaines faiblesses dans la conception du schéma du schéma de la base peuvent être
compensées en cours dʹexploitation, par le traitement du SGBD. La conservation des données est
considérée comme capitale pour assurer la cohérence et sera prise en considération en cours de la
normalisation des relations de la base de données.

Algorithme simplifié de synthèse du schéma de BD avec CDF

Calculer une couverture minimale Cmin de F :

- Pour chaque déterminant X partagé par toute DF de F :

Créer une relation Ri avec comme schéma; {X ∪ A1 ∪ A2 ∪...} qui est ajoutée au schéma S de la
BD avec pour Ri, F = X-->A1,
X->A2,... comme les seules DF dans la couverture C ayant comme déterminant X;
-Regrouper les autres attributs du schéma S non incorporés dans une Ri dans une relation Rj;
Fin.

Cet algorithme ne fournit pas toujours un schéma acceptable et/ou optimal parce qu’il ne tient pas
compte de la redondance des dépendances fonctionnelles (couverture minimale ignorée), la présence
des attributs étrangers et les clés équivalentes.

10.4 Hypothèse de la relation universelle

La conception d’un schéma de base de données ne débute pas toujours avec le traitement des
dépendances fonctionnelles. Il y a souvent un existant constitué de relations. C’est à partir de ces
dernières qu’il faudra vérifier le degré de normalisation de chacun et au besoin, le transformer pour
le normaliser davantage. La décomposition d’une relation est faite en présumant que chaque attribut a
une sémantique propre qui demeure la même quelle que soit la relation hôte (invariance sémantique
au regard du contexte). C’est l’hypothèse de la relation universelle (U) qui énonce que dans un
schéma tout identificateur de chaque attribut est global et doté d’une sémantique unique. Dans le cas
contraire, certaines ambiguïtés peuvent fausser l’interprétation des relations voire des dépendances
fonctionnelles.
Exemple :

Soit les relations Client (nas*, nom, date) avec F1 = {nas --> date ; nas --> nom} pour R1 et Livraison
(article*, qte, date*, nas) avec F2 = {article, date --> qte ; article, date --> nas }.

client : nas* nom date

n12 Cyr 12-2-85
n9 Vonet 3-7-90
n34 Xircon 7-1-95

livraison : article* qte date* nas

a2 4 4-8-91 n9
a2 2 8-1-95 n12 *
a2 3 22-7-95 n12 *

La DF de F2 signifie que pour un type d’article et pour une date donnée, il a été livré qu’une seule
quantité. Cette dernière pourrait être par exemple la production du jour, et la livraison faite à une
seule personne! Si lʹon considère les dépendances de F1 et de F2 et la pseudo transitivité, on a alors :

nas --> date (de F1)

article, date --> qte (de F2)
{nas, article} --> qte (par pseudo transitivité)

Cette DF n’est pas validée dans l’extension de la relation Livraison (voir les tuples 2 et 3). La raison
tient à la double sémantique de l’attribut date. Dans la relation Client, il s’agit de la date d’inscription
du client, tandis que dans la relation Livraison la date est celle de la livraison de l’article. Pour éviter
de faire une fausse inférence, il faut que les deux attributs soient distincts par leur libellé puisque
qu’ils ont une sémantique différente. Par exemple, dateClient et dateLivraison sont des libellés
différents et les dépendances fonctionnelles deviennent alors les suivantes :

F1 = {nas --> dateClient ; nas --> nom

F2 = {article, dateLivraison --> qte ; article, dateLivraison --> nas }.

Il devient impossible de faire la dérivation impliquant la l’attribut qte.

La relation universelle U est celle formée avec tous les attributs identifiés et dont l’extension est
composée avec les données de ceux-ci. Ainsi, les attributs de l’exemple Client donne la relation
universelle suivante à partir de laquelle il doit être possible d’obtenir par simple projection les
extensions de la base :

U: nas * nom date* article* qte

n12 Cyr 12-2-85 a7 2

n9 Vonet 3-7-90 a2 4
n12 Cyr 12-2-85 a2 3
n9 -- 4-8-91 a2 4
n12 -- 8-1-95 a7 2
n12 -- 22-7-95 a2 3

On constate que les projections ne fournissent pas les extensions recherchées et ce parce que l’attribut
date est présumé avoir une seule sémantique. Ainsi, les dates dateLivraison et dateClient sont
confondues.
Voici un autre exemple dans lequel la même difficulté découle de lʹambiguïté des libellés.
Empl (nas*, telephone) et Gerant (nas*, telephone).

Empl : nas* telephone Gerant : nas* telephone

n2 566-3425 n45 656-2398
n4 645-8954 n22 656-2678
n6 756-0986
n8 549-5648

La relation universelle U de cette base a le schéma (nas, telephone) et son extension est la suivante,
résultat de la jointure :
U: nas telephone
n2 566-3425
n4 645-8954
n6 756-0986
n8 549-5648
n45 656-2398
n22 656-2678

Il nʹest plus possible de recalculer par projection les extensions initiales respectives des tables Empl et
de Gerant parce que l’attribut telephone de la relation universelle U confond celui de l’employé et
celui de son gérant.

Base de dépendances dʹune relation : G(Ri) ou Gi

La base de dépendances de la relation Ri est notée Gi et elle est formée des dépendances de F+ dont le
déterminé et le déterminant sont composés seulement avec des attributs appartenant à Ri. Pour
chaque Ri d’une base, il y aura un Gi. Si F = ∪Gi, alors il y a conservation des DF dans cette base de
données.

Gi = { df ∈ F+ | df = X --> Y et X ∪ Y ⊆ Ri}
La Gi de Ri ne prend en compte que les DF intra relationnelles.

Définition formelle de la conservation des dépendances (CDF)

Lorsqu’il y a conservation des dépendances, le schéma de la base S = {R1, R2, ... Rn} obtenu est tel que
toutes les dépendances de F (donc de F+) peuvent être vérifiées sans calcul de jointure. Dans ce
cas, F = ∪ Gi.

Algorithme de vérification de la conservation des dépendances dans S

Lʹalgorithme fait appel au calcul graduel de la base de dépendances de S :
Gtotal = vide
Calcul de F+
Pour chaque Ri ∈ S
Calculer Gi
Gtotal = Gtotal ∪ Gi
Calcul de (Gtotal)+
Si (Gtotal)+ = F+ alors return(True) else return (False);
Fin.

Lorsque l’algorithme renvoie True, il y a conservation des dépendances dans le schéma de la BD.

Algorithme de décomposition du schéma avec CDF

Soit une relation R avec ses DF regroupées dans l’ensemble F. La relation R est k-décomposée avec
conservation des dépendances fonctionnelles (CDF) en R1, R2, R3, ... Rk avec les bases de
dépendances G1, G2, G3 ... Gk si et seulement si {G1 ∪G2 ∪ G3∪ ... Gk}+ = F+ et avec {G1∪ G2∪ G3∪
... Gk} ⊆ F.
Exemple
R(A, B, C, D) avec F ={A--> B; A --> C; C--> D}.
Décomposition de R avec CDF :
R1(A, B, C) avec G1= {A -->B; A --> C}
R2 (C, D) avec G2 = {C --> D}.
Toutes les dépendances de F sont à nouveau vérifiées dans les deux relations obtenues et partant,
toute DF de la fermeture le sera aussi. Il nʹy a pas de DF inter-relation.

Décomposition sans CDF d’une relation

Soit une 2-décomposition de R(A, B, C) avec F = {A --> B; A --> C; B --> C}. Elle comprend les relations :
R1(A*, B) avec A --> B et R2(A*, C) avec A --> C.
Les deux extensions correspondantes sont obtenues par projections de R sur R1 et ensuite sur R2. La
2-décomposition n’est pas acceptable au regard de la conservation des DF, car pour effectuer la
vérification de B --> C il faut faire un calcul de jointure. La conservation des données est cependant

assurée. En effet, la dépendance B--> C n’est pas dérivable à partir des deux dépendances présentes
dans le nouveau schéma. Cette dernière DF n’appartient donc pas à la fermeture des DF de la
nouvelle BD.
Autre exemple :
R(A*, B*, C*, D) avec F = {A, B, C --> D; D --> A}
Cette relation n’est pas en FNBC, car un attribut primaire A dépend dʹun attribut qui nʹest pas une clé.
La 2-décomposition suivante est effectuée : R1(D*, A) et R2(B*, C*, D*). Ces deux relations sont
maintenant en FNBC. De plus, la 2-décomposition conserve les données, mais pas les dépendances.
En effet, A, B, C --> D ∈F ne peut pas être vérifiée directement sans calculer la jointure (R1 |x| R2). Au
contraire, la conservation des données est assurée, car R1 ∩ R2 --> R1 - R2, i.e. que D --> A.
Remarque
Une relation R peut toujours être k-décomposée en FN3 avec conservation des données et des
dépendances. Toutefois, il n’existe pas toujours une décomposition en FNBC avec CDF et CDD.

Conservation des données (CD)

Un schéma R = {R1 ∪ R2 ∪ ... Rn} où Ri est une relation est n-décomposée avec conservation des
données (CDD) si et seulement si :

R = R1 |x| R2 |x| R3 |x| ... |x| Rn

Les conditions nécessaires pour que R = (R1 |x| R2 ...) sont les suivantes :
R1 ∩ R2 ≠ vide ; -- absence d’attribut commun
et (R1 ∩ R2) --> (R1 – (R1 ∩ R2)) ou (R1 ∩ R2) --> (R2 – (R1 ∩ R2))

Exemple R = r1 |x| r2 avec F = {B --> C, D + les DF de la clé A, B}

r: A* B* C D r1: A* B* r2: B* D
1 5 8 9 1 5 5 9
6 5 8 9 6 5 3 7
2 3 4 7 2 3

Dans cet exemple, r = r1 |x| r2, car R1 ∩ R2 = B et B --> D dans dans la relation r2.

Jointure sans conservation des données

Soit la relation R(A, B, C, D, E, H, G} et F = {A, B --> C; A, B --> D; B, E --> H; A, E --> G}. La clé
composée de R est A,B,E, car la fermeture de ABE donne le schéma de R. Supposons que cette relation
soit décomposée pour obtenir les relations ci-dessous par projection :
R1 (A, B, C, D) R3 (A, E, G)
R2 (B, E, H) R4 (A, B, E)

Quelles sont les clés des relations suivants ? R1(A*, B*, C, D) ; R2(B*, E*, H) ; R3(A*, E*, G) et
finalement R4(A*, B*,E*).
Il faut en outre démontrer que le résultat R1 |x| R2 |x| R3 |x| R4 = R le schéma de la base. Pour cela,
il faut trouver une jointure naturelle intermédiaire de deux relations valide qui conserve les données.
Prenons les relations R1 et R2 : le calcul de la jointure R1 |x| R2 conserve les données si et seulement
si R1∩R2 = B et que B --> R1 − (R1 ∩ R2) ou que B --> R2 - (R1 ∩ R2). Or, est-ce que B --> A, C, D ou
encore B --> E, H ? Sinon, R1 |x| R2 génère des incohérences transitoires. On peut démontrer que ces
deux DF n’appartiennent pas à F+ et que la jointure ne conserve pas les données. Le problème avec le
résultat de cette décomposition repose sur le fait qu’avec la première décomposition, la condition de la
conservation des données n’était pas vérifiée. Certaines formes de relation peuvent être construites
pour conserver les données et les DF, tandis que d’autres relations ne conservent que les unes ou les
autres. Un choix s’impose donc en fonction du contexte de l’analyse et de la qualité de la
représentation attendue. Le plus souvent, il sera choisi de conserver les données.

10.5 Contraintes dʹinclusion (DIN)

Une dépendance d’inclusion (DIN) implique deux relations de la même base de données. Une telle
contrainte énonce des conditions concernant l’occurrence de valeurs dans une relation au regard des
valeurs dans une autre. C’est une contrainte entre relations dont un cas particulier est concrétisé par la
contrainte référentielle.

Définition de la dépendance dʹinclusion (DIN)

Soit une base comprenant les relations P et W. Une dépendance d’inclusion (DIN) dans P est une
expression P[X] ⊆W [Y], où X et Y sont respectivement des ensembles d’attributs de même cardinalité.
Soit les ensembles d’attributs X = {A1, A2, ... An} et Y = {B1, B2, ... Bn} et p et w, deux extensions du
schéma qui satisfont la dépendance d’inclusion P [X] ⊆ S [Y]. Pour chaque tuple ti ∈ p, il y a un tuple
tj ∈w tel que ti [X] = tj [Y] et cela pour tout 1<= i <= n.

Exemple : Supposons une BD pour modéliser un concours artistique :

Spectacle (date*, titre)Artiste (nom*, adresse*)
Score (datEval*, critique*, cote, commentaires}
L’attribut critique représente un artiste qui agit comme critique artistique et il est exigé qu’il soit aussi
un artiste et la date de la critique corresponde bien à un spectacle. Les DF définies par les clés du
schéma et les DIN sont les suivantes :
Score[dateEval] ⊆ Spectacle[date] Score[critique] ⊆ Artiste[nom]

Cette DIN est une assertion qui stipule que, chaque fois qu’une combinaison de valeurs apparaît dans
une ou plusieurs relations du schéma, elle doit obligatoirement apparaître aussi dans une autre
relation du schéma. Cette condition est courante dans un schéma parce que les entités d’un modèle
logique sont associées les unes aux autres par une association. La DIN établit aussi une précédence
dans la mise à jour : la date de l’évaluation artistique doit être postérieure à celle du spectacle.

Contrainte dʹintégrité référentielle

Une contrainte dʹintégrité référentielle est une contrainte DIN particulière dans laquelle lʹinclusion
R1[A] ⊆ R2[A] est vérifiée dans le schéma R et où A est une clé dans R2 et A est aussi une clé
étrangère dans R1.

Cas particulier: contrainte DIN incluant une clé

La dépendance DIN, R1[W] ⊆ R2[V] est du type clé si V est une clé de R2 et W un attribut quelconque
de R2 ayant le même type que celui de V. Toutes les valeurs de V ne sont pas présentes dans la
projection W, mais les valeurs de W ne sont que des valeurs de V.

Propriétés des dépendances dʹinclusion (DIN)

Les dépendances dʹinclusion suivantes sont valides dans R1[A1, A2, ..., An] et R2[B1, B2, ..., Bn]:
a) R [A1, A2, ..., An] ⊆ R [A1, A2, ..., An] est une DIN réflexive valide quel que soit R.

b) Si R1[A1, A2, ..., An] ⊆ R2[B1, B2, ..., Bn] alors R1[Ai, Ai +1 ..., Aj] ⊆ R2[Bi, Bi+1 ..., Bj]
où i et j ∈ [1,n]; la DIN est toujours vérifiée avec un sous-ensemble ordonné des attributs pour autant
quʹil soit aussi défini dans la partie gauche et dans la partie droite de la même dépendance
d’inclusion;

c) Transitivité de la DIN
Si R1[A1, A2, ..., An] ⊆ R2[B1, B2, ..., Bn] et R2[B1, B2, ..., Bn] ⊆ R3[C1, C2, ..., Cn], alors
R1[A1, A2, ..., An] ⊆ R3[C1, C2, ..., Cn].

d) Le graphe des DIN est acyclique

La présence dʹun cycle dans le graphe semble causer des problèmes lors de la mise à jour des
relations. Le graphe est construit en plaçant un arc orienté de R vers W lorsque R[X] ⊆ W [Y].
Exemple dʹune contrainte DIN
Soit les relations suivantes :
Employe (nasEmpl*, nomDep) Gestion (nomDep*, nasGerant)

La DIN suivante est définie dans cette base :

Gestion[nasGerant, nomDep] ⊆ Employe[nasEmpl, nomDep]

Cette DIN contraint chaque gérant dʹun département à être un employé de ce département et
constitue une contrainte dʹinclusion plus stricte que la contrainte de clé étrangère formulée avec
seulement l’attribut nasEmpl.

10.6 Formes normales des relations (Cette partie est un rappel des notions déjà vues)
Le schéma d’une base de données relationnelle S est formé des relations suivantes : {R1, R2, R3, ... Rn}
où chaque Ri ∈ S est normalisée afin d’éviter des anomalies d’ajout, de mise à jour et de suppression
dans l’exploitation de la BD. Ainsi, la cohérence de la BD est conservée de par la structure même du

schéma sans que le noyau du SGBD ait à déployer des efforts de calcul de jointure parfois importants
10
pour garantir l’intégrité de la base . Règle générale, plus la normalité de la relation est grande, plus
les risques d’anomalies sont faibles. La normalité d’une relation est définie essentiellement au regard
11
de certaines dépendances dont les fonctionnelle, la multivaleur et celle de jointure .

Il existe d’autres dépendances qui n’interviennent pas dans la définition des formes normales (voir la
dépendance d’inclusion), mais qui ont leur importance dans la cohérence des données. A partir de
maintenant, nous reviendrons sur les notions vues antérieurement pour les préciser davantage au
regard de la théorie.

Première forme normale (FN1)

La première forme normale (FN1) est caractérisée comme une relation dans laquelle tous les domaines
des attributs sont du type atomique. Cette forme normale interdit les attributs composés ou complexes
dans la même relation. Avec certains nouveaux SGBD, les relations non normalisées se révèlent
parfois intéressantes pour des raisons de performance et parce qu’elles se rapprochent de la réalité
dans certains domaines d’application comme le domaine du multimédia et de la CAO.
Une relation est en FN1 si chaque ses attribut a un domaine atomique.

Ceci se manifeste à l’intersection de chaque colonne et de chaque ligne par une seule valeur et
dʹun même type atomique.
Exemple :Voici une table ou relation de données avec des valeurs atomiques pour chaque attribut.

carnet: noClient* noPiece* norme credit

Aubert p500 n10 A
Dumas p502 n20 B
Dussault p500 n10 A
Pageau p640 n30 C
Aubert p502 n40 A
Figure 10.8
Les domaines correspondants aux attributs sont les suivants :
dom (client) = {‘Aubert’, ‘Dumas’, ‘Dussault’, ‘Pageau’, ...}
dom (noPiece) = {‘p500’, ‘p502’, ‘p504’, ‘p506’, ‘p600’, ‘p610’, ‘p620’, ‘p640’, ...}
dom (norme) = {‘n10’, ‘n20’, ‘n30’, ‘n40’, ‘n50’}
dom (credit) = {‘A’, ‘B’, ‘C’, ‘X’}

Le type des attributs est défini comme une structure de données primitive dont la valeur est comprise
dans l’ensemble énuméré ou défini. Ce type est aussi connu comme un domaine, car les opérations
sur le type ne sont pas spécifiées dans le modèle relationnel.
Dans cet exemple, la relation Carnet est FN1 et les DF sont :

F = {noClient, noPiece --> norme, credit; noClient --> credit}

Anomalies possibles
Il est évident que des anomalies persistent en FN1 :
a) Anomalie de suppression : si la commande du client Pageau est annulée, il y a perte de la cote de
crédit de ce client. Lorsque cette personne redevient alors client il faudra rechercher sa cote en dehors
du système.
b) Anomalie de mise à jour : La cote de crédit du client Aubert qui a commandé la pièce p500 est
lʹobjet dʹune décote de A à B. La mise à jour du premier tuple avec la nouvelle cote engendre une
incohérence, car le crédit de Aubert apparaît comme ayant la cote B dans le premier B et A dans le
dernier tuple. Il y a donc violation de la dépendance fonctionnelle : noClient --> credit.
c) Anomalie dʹajout : Il est impossible dʹajouter une cote de crédit pour le client Gagnon, si ce dernier
ne passe pas en même temps une commande. Ces anomalies seront absentes lorsque les relations
passeront à une autre forme normale dite FN2.

Deuxième forme normale (FN2)

Une relation Ri du schéma S est en FN2 si et seulement si les conditions suivantes sont vérifiées pour
toute extension de Ri :
a) si son extension est en FN1
b) et si chaque attribut non primaire est en dépendance fonctionnelle totale
par rapport à chaque clé (primaire et candidate) de Ri.

En d’autres mots : ri est FN1 et pour ∀j si Aj est non primaire, alors ∀k tel que clék est une clé et que
clék ⇒ Aj dans ri. En d’autres mots, une extension est en FN2 si chaque attribut non primaire de ri est
en dépendance fonctionnelle totale par rapport à chaque clé (primaire et candidate) de la relation.
Dans la relation Carnet (client, noPiece, norme, credit), il y a quʹune clé candidate et les DF de F sont
les suivantes :
F = {noClient, noPiece --> norme, credit; noClient --> credit}

La seule clé est primaire et elle est composée de deux attributs primaires : {noClient*, noPiece*}. Les
attributs non primaires sont norme et credit. Cette relation est-elle en FN2 ? Elle ne l’est pas, car il
existe une DF, soit noClient --> credit, dont lʹattribut non primaire (credit) n’est pas en dépendance
totale sur la clé primaire. Par conséquent, noClient, noPiece =/=> norme, credit.

Transformation de la relation en FN2

Pour faire une transformation afin dʹavoir une FN2, il faut choisir une première DF qui contredit la
forme FN2 et l’isoler dans une nouvelle relation R1. Ensuite, enlever le déterminé de la DF en question
de la relation initiale et vérifier si le schéma résiduel est en FN2. Un libellé plus significatif peut être
donné à la nouvelle relation après examen de ses attributs. Il faut appliquer cette procédure de façon
récursive. Le passage à la forme FN2 sous-tend donc une division de la relation et la multiplication de
celles-ci dans la base. Dans l’exemple ci-dessus, il faut enlever la DF {noClient --> credit} de F pour

obtenir une relation résiduelle : R2 (noClient*, noPiece, norme). Les DF de R1 et R2 sont

respectivement :
noClient --> credit dans R1
noClient, noPiece --> norme dans R2
La décomposition ou la division du schéma correspond à un éclatement correct de l’extension (sans
perte de données), car R1 ∪ R2 --> Aj dans au moins une Ri. Les extensions sont obtenues par
projection de l’extension d’origine sur les attributs recherchés.

r1 : noClient credit
Aubert A
Dumas B
Dussault A
Pageau C

r2 : noClient* noPiece* norme

Aubert p500 n10
Dumas p502 n20
Dussault p500 n10
Pageau p640 n30
Aubert p502 n40
Figure 10.11

Ce nouveau schéma permet maintenant d’inscrire une commande de pièce par un client, même si ce
dernier nʹa pas encore de cote de crédit. En revanche, il est toujours impossible d’inscrire une pièce
produite selon une norme donnée, si cette pièce nʹest pas commandée par un client. La relation en
FN2 a apporté une certaine correction, mais certaines anomalies persistent dans les relations.

Exemple : R (fournisseur, article, ville, qte)

avec F = {fournisseur --> ville; + les DF de la clé} i.e. (fournisseur, article --> ville, qte)
La relation R n’est pas en FN2 en raison de la présence de la 1ère DF. Il suffit donc de transformer R
en deux relations par décomposition ou division de la relation d’origine :
R1 (fournisseur*, article*, qte) R2 (fournisseur*, ville)
F1 = {fournisseur, article --> qte} F2 = {fournisseur --> ville}.

Troisième forme normale (FN3)

Certaines anomalies persistent dans une relation même si cette dernière est en FN2. Ces anomalies
résiduelles sont illustrées dans l’exemple suivant concernant les constructeurs spécialisés assujettis à
la convention des salaires des métiers de la construction.

Lorsqu’un constructeur spécialisé embauche un ouvrier, son salaire est déterminé par la convention.
Les anomalies présentes sont associées à la présence de DF transitives dans la relation Constructeur.
La BD est constituée d’une seule relation :
Constructeur (societe*, metier, salaire)
F = {societe --> metier, salaire; metier --> salaire}

L’extension de la relation en FN2 est la suivante :

constructeur : societe* metier salaire
PEG Inc. menuisier 35 K$
Delna Ltée menuisier 35 K$
Les murs Inc plâtrier 45 K$
Eclair enr électricien 40 K$
WC inc plombier 35 K$
Beaux bois menuisier 35 K$
CGE Inc. électricien 40 K$
Lux inc. électricien 40 K$
Figure 10.12

Anomalies de lʹextension en FN2

Les anomalies présentes en FN2 sont les suivantes :
a) Dans un ajout : impossible d’enregistrer le salaire dʹun électricien, si ce dernier nʹest pas à lʹemploi
dʹun constructeur agréé. En effet, il y aurait violation de la contrainte de validité de la clé qui interdit
les tuples avec une clé nulle.

b) Dans une suppression : si la société Les Murs Inc dépose son bilan, la suppression du tuple la
décrivant fait perdre une information qui ne dépend pas de cette société, à savoir le salaire du plâtrier
qui est prévu par la convention des métiers.

c) Dans une modification : si la société CGE inc embauche dorénavant des menuisiers (en
remplacement des électriciens) au nouveau salaire de 43K$ conventionné par le nouveau décret
gouvernemental, ce changement entraînera une mise à jour du tuple concernant CGE inc. En
modifiant le salaire de 40K$ à 43K$ pour cette seule société, il y a apparition dʹune anomalie. Elle
invalide la DF qui sous-tend un seul salaire pour le métier dʹélectricien. L’anomalie s’explique par la
présence d’une DF transitive dans le schéma de la relation. Il suffira d’isoler une des deux DF
impliquées dans la transitivité pour corriger l’anomalie observée. En isolant la DF : metier --> salaire
dans une nouvelle relation, deux relations sont alors créées, et cela, sans perte d’information par
rapport à l’extension initiale de la relation Constructeur (théorème de Heath) :

R1 (societe, metier) R2 (metier, salaire)

r2 : metier* salaire
plâtrier 45 K$
plombier 35K$
électricien 40 K$
menuisier 35 K$

r1 : societe* metier
PEG Inc. menuisier
Delna Ltée menuisier
Les murs XIC plâtrier
Eclair enr électricien
WC inc plombier
Beaux bois menuisier
CGE Inc. électricien
Lux inc. électricien
Figure 10.13

Les extensions des nouvelles relations sont obtenues par projection de la relation initiale sur
les nouveaux schémas. La transformation qui élimine la transitivité des DF est sans perte
d’information, car R1 ∩ R2 = metier et metier --> salaire dans R2. La condition étant
respectée, la décomposition est valide et aucune perte de données n’est possible.

Définition de la FN3
Une relation Rj est en FN3 si et seulement si les conditions suivantes sont vérifiées :

a) l’extension rj ou le schéma Rj est en FN2;

b) et tout attribut non primaire du schéma ne dépend dans F+ que d’une
clé (primaire ou candidate) de Rj .

Il apparaît donc que le premier schéma Constructeur n’était pas en FN3, mais qu’après la
décomposition, les relations résultantes de la décomposition sont en FN3.

Forme FNBC (Forme normale de Boyce Codd)

Certaines anomalies persistent même si la relation est en FN3. Ces anomalies tiennent au fait que la
transitivité impliquait seulement des attributs non primaires. Or, il arrive que les attributs primaires
12
interviennent dans la transitivité, comme cela est illustré par lʹexemple type proposé par Gardarin .
Exemple :
Vin(vignoble*, pays*, region)
avec F ={vignoble, pays --> region; region --> pays}

Le schéma de la relation Vin a une extension en FN3, mais affiche encore des anomalies. Elle est en
FN3, car tous ses attributs non primaires (soit dans cet exemple region) sont en dépendance
fonctionnelle que sur une clé. Toutefois, il y a une DF entre un attribut primaire (soit pays) et un
attribut non clé (soit region) qui est à la source de quelques anomalies résiduelles.

vin : vignoble* pays* region

Chenas Chili Santiago
Chenas France Beaujolais
Juliénas France Beaujolais
Morgan France Bordelais
Brouilly France Beaujolais
Chablis USA Californie-Est
Figure 10.14

Dans cet exemple, si le vignoble Chablis se retire des affaires, le tuple correspondant est supprimé et
comme il est le dernier de cette extension, il y a perte d’information, à savoir que l’est de la Californie
est une région productrice de vin. Cette anomalie est corrigée si la DF impliquant un attribut primaire
est isolée dans une nouvelle relation.
R1(region*, pays) R2(vignoble*, region)
avec F1= {region --> pays} avec F2 = {vignoble --> region }

La transformation est sans perte, puisque R1 ∩ R2 = region et que region --> pays est une DF
de R1.

Conservation des DF dans un schéma

Dans le nouveau schéma de lʹexemple ci-dessus, F1 ∪ F2 = F’ ⊆ F. Il y a donc perte d’une DF par la
transformation, sauf s’il est possible de démontrer que la DF absente {vignoble, pays --> region}
appartient à la fermeture de F’, soit (F’)+, ou que région ⊆ {vignoble, pays}+ dans F’. Si cette dérivation
dans F’ est impossible, alors la transformation ne conserve pas les DF, mais elle est sans perte de
données. Toutefois, il serait possible de renforcer la DF perdue par une procédure de contrainte (par
un déclencheur) qui calculerait la jointure R1 |x| R2 à chaque mise à jour de l’une ou l’autre des deux
relations et cela, afin de vérifier si la DF {vignoble, pays --> région} est satisfaite par l’extension. Dans
le cas contraire, la mise à jour est refusée par le déclencheur de BD (trigger). C’est un processus qui
peut cependant devenir lourd pour le SGBD et pénaliser la performance du système.
Une relation R est en FNBC si :
a) elle est en FN1;
b) et si chaque déterminant de toutes les DF de F pour la relation R est une clé (primaire
ou candidate).

Il sʹagit dʹavoir les attributs primaires et non primaires qui dépendent que dʹune clé dans F. S’il existe
une transformation (CDF) en FN3 qui permet de conserver les DF et les données, il peut ne pas y avoir
de transformations d’une relation qui conduisent à la forme FNBC qui fournit un schéma qui soit à
la fois CDD et CDF.

Algorithme de transformation dʹune relation R en FNBC

Lʹalgorithme de passage est le suivant :
Résultat = R ! le schéma initial contient que celui de R;
Calcul de F+; -- non nécessaire si l'appartenance est testée
Tant que la relation Résultat n’est pas en FNBC
choisir une DF, X --> Y dans F de R tel que X n’est pas une clé et donc que
X --> R ∉F+
Resultat = {(Resultat - R), (R - Y), (X, Y)}
-- le résultat contient plusieurs schémas de relation
Fin.

Lʹalgorithme est aussi valable lorsque lʹon traite un ensemble de schémas S de la BD. La première
affectation est alors Résultat = S.
Schéma FNBC de la BD
Le cas d’un schéma de BD en FNBC correspond à celui d’une BD composée de schémas relationnels
en FNBC non redondants, c’est-à-dire qu’aucun schéma de relation ne correspond à une projection
d’un autre schéma de la BD. Si un schéma contient entièrement un autre schéma, ce dernier peut être
supprimé.

Test de FNBC (Problème de complexité P)

Pour tester si un schéma relationnel R est en FNBC, il suffit de vérifier que le déterminant de
chaque dépendance dans F est une superclé de R, et cela, en calculant la fermeture de chaque
déterminant par rapport à F. Lʹalgorithme est une fonction polynomiale par rapport au
nombre dʹattributs dans R.

Dépendance entre les formes de normalité des relations

Si R est une relation, alors
a) si elle est en FN2 ⇒ FN1 b) si elle est en FN3 ⇒ FN2
c) si elle est en BCFN ⇒ FN3

Une relation FNBC est en FN4 (cette 4e forme normale sera étudiée plus loin dans ce chapitre) si son
schéma relationnel a au moins une clé (primaire ou candidate) constituée d’un seul attribut. De même,
il a été démontré quʹune relation en FN3 est aussi en forme normale de jointure si cette première nʹa
que des clés formées avec un seul attribut.

Autre exemple : Soit la relation Code(ville, adresse, codePostal)

avec F = {ville, adresse −−> codePostal; codePostal −−> ville}

Quelle est la clé de cette relation ?

Est-ce que cette relation est en FN3 ? Oui, car les attributs non primaires dépendent que de la clé. Est-
elle en FNBC ? Non, car il y a un attribut primaire qui dépend dʹun attribut (codePostal) qui nʹest pas
une clé de la relation.
Voici une extension possible de cette relation :

Code : ville* adresse* codePostal

Québec 2 des Pins F2P
Valcartier 8 des Cèdres S4T
Québec 5 des Roses F2W
Ste-Foy 8 des Mélèzes U5E

Anomalies observées
Les anomalies classiques sont encore présentes dans la relation Code :
a) la suppression du tuple <Ste-Foy, 8 des Mélèzes, U5E> fait perdre une information à savoir que le
code codePostel de Ste-Foy est le U5E;

b) l’ajout d’un code postal pour une nouvelle ville n’est pas possible sans qu’il y ait au moins une
adresse de définie avec ce nouveau code.
En transformant cette relation pour obtenir la forme FNBC, on a :

r1 : ville * codePostal*
Québec F2P
Valcartier S4T
Québec F2W
Ste-Foy U5E

r2 : adresse* codePostal
2 des Pins F2P
8 des Cèdres S4T
5 des Roses F2W
8 des Mélèzes U5E

Exemple : Transformez la relation R (A, B, C, D, E) avec F = {A −> B, C; C, D −> Ε; B −> D; E −> A}.
Quelles sont les clés de R ?
La clé est A, car la fermeture de A, soit A+ est A,B,C,D,E. La relation R est en FN2, mais pas en FN3 en

raison des DF transitives. Il faut donc la décomposer. Avec la DF, B −> D création de R1 (B*, D), une
relation en FNBC et réduire la relation initiale du schéma à R2(A, B, C, E). Cette relation R2 a les DF
suivantes : {A −> B, C; E −−> A}.

Cette relation R2 n’est pas en FN3, car la clé de R2 est E, A −−> B, C et E −>A, c’est-à-dire que ce sont
des attributs non primaires qui dépendent de A qui n’est pas une clé. Il faut donc effectuer une
nouvelle transformation pour obtenir les relations :
R21 (E*, A) avec F21 = {E −> A}
R22 (A*, B, C) avec F22 = {A −> B, C}

Ces deux dernières relations sont alors en FNBC et les clés sont respectivement A et E. La recherche
des clés est un processus complexe, allégé par la sémantique qui vient suggérer des clés possibles.

Algorithme de synthèse de Bernstein 13•

On a proposé un algorithme de synthèse du schéma relationnel fondé essentiellement sur la
connaissance des dépendances fonctionnelles. La base de lʹalgorithme est simple: partitionner les DF
pour les attributs identifiés et ce, sur la base du même déterminant. Créer ensuite une relation pour
chaque partition obtenue dans lʹopération précédente.

Cette version minimale de lʹalgorithme ne résout pas tous les problèmes qui découlent de la présence
dʹattributs redondants, de DF redondantes et de clés équivalentes dans F et F+.

Considérons les exemples ci-dessous qui illustrent bien les cas particuliers qui faut traiter pour
préciser l’algorithme général de synthèse de Bernstein :
a) Présence d’un attribut étranger dans une DF
Soit R(A, B, C, G) si F = { A, B, C --> G ; A --> C}, alors on aurait par l’algorithme de synthèse deux
relations : R1 (A*, B*, C, G) et R2(A*, C). Avec R1 qui n’est pas en FN2.

La clé de R1 est (A, B) et non (A, B, C, G) puisque A, B --> C, G ∈ F+. La décomposition de R1 fournit
alors les relations FN2 : R11(A*, B*, G) et R12(A*, C). Lʹenlèvement de lʹattribut étranger (C) dans le
dépendance A, B, C --> G conduit directement par la synthèse à R(A*, B*, G).

b) Présence dʹune DF redondante cause aussi des problèmes lors de la synthèse.

Si F = {W --> P; W --> Z; P --> Z} génère le schéma: R1(W*, P, Z) et R2(P, Z). Toutefois, R1 nʹest pas en
FN3, car P --> Z.

c) Présence de clés équivalentes

Soit F = { Y --> M; W --> G; W --> Y; Y --> W}. La synthèse qui en découle fournit le schéma R1(W, G, Y)
et R2(Y, M, W). Or ce schéma peut être combiné en un seul R(W*, G, Y, M) qui est en FN3. La fusion

est effectuée sur la base des clés équivalentes.

Soit F ={X --> B; B --> Z; Z --> X} alors la synthèse fournit le schéma suivant qui inclut trop de relations
: R1(X*, B), R2(B*, Z), R3(Z*, X). En ne tenant pas compte des clés équivalentes présentes dans la
fermeture de F, la synthèse fournit trop de relations. La relation R(X*, B, Z) est en FN3.

d) Soit F = { A, B --> D, P; C, D --> A, B; P, B --> I; I, A --> C; C --> P}, alors le schéma généré est le
suivant:
R1 (A, B, C*, D*, P) qui nʹest pas en FN2 puisque C --> P
R2(P*, B*, I)
R3( I*, A*, C)
R4(C*, P)

La présence dʹun attribut étranger dans un déterminé invalide la condition de la FN2 pour R1.
Ces problèmes sont gérés en tenant compte de la couverture minimale, de la suppression des DF et
des attributs redondants.

Version 2 de lʹalgorithme de synthèse de Bernstein

Input : un ensemble de DF :
F = {X->A; X->B; A->Y;Y->B; Y->X; Y->C; C->B}
Output : un ensemble de relations normalisées;

a) Enlevez les attributs redondants ou étrangers dans chaque DF de F :

F1 = F-{attributs étrangers)
Alors, il y a diminution du nombre d’attributs dans les dépendances ce qui les simplifie et
facilite le calcul de la couverture. ans cet exemple, il y aucun attribut étranger, donc F1 = F; Le
graphe des dépendances de F1 est le suivant :
F = {X->A; X->B; A->Y;Y->B; Y->X; Y->C; C->B}

X A B

Y C

b) Calculez la couverture minimale de F1 : (F1)* = F2

Cela permet de diminuer le nombre de dépendances fonctionnelles du schéma.
F2 = {X->A; Y->C; A->Y; C->B; Y->X} (flèches en gras)

Le graphe des dépendances de F est donné ci-dessous :

X A B

Y C

Le graphe de la couverture est celui obtenu en enlevant les arcs qui peuvent être dérivés des autres.

X A B

Y C

c) Regroupez les dépendances restantes en partitions de même déterminant. Cette opération identifie
la base des relations en FN3;
p1 p2 p3 p4
X −> A Y −> C A −> Y C>B
Y −> X
d) Trouvez les clés équivalentes dans la fermeture de la couverture minimale (F2)+. Une clé
équivalente est définie entre deux ensembles dʹattributs X et Y dont les DF X −> Y et Y −> X sont dans
F. Elles correspondent aux arcs doublés dans le sens inverse. Les trois clés équivalentes dans F sont les
suivantes :
{ (X −> A et A −>X); (A −> Y et Y −> A); (X −> Y et Y −> X)}

e) Enlevez les dépendances fonctionnelles qui correspondent aux clés équivalentes explicitement
formulées dans F pour obtenir ainsi F3 représenté par le graphe suivant :

X A B

Y C

-Formez l’ensemble H avec les dépendances des clés équivalentes;

H = {X −> A; A −>X; A −> Y; Y −> A; X −> Y ; Y −> X}
ou H = {X <−> A, Y <−> A, X <−> Y},

-Calculez la couverture minimale de F3 afin de conserver le minimum de DF dans F3, soit(F3)* .

Formez ensuite le nouvel ensemble de dépendances F4 = (F3)* ∪ H pour avoir obligatoirement les clés
équivalentes dans l’ensemble des dépendances de départ. Le graphe de F4 est alors le suivant :

X A B

Y C

f) Regroupez les DF de F4 en partitions de même déterminant. Les partitions sont :

p1 p2 p3 p4
X −> A Y −> A A −> X C −> B
X −> Y Y −> C A −> Y
Y −> X
- Fusionnez les partitions dont le déterminant est une clé équivalente :
X −> A C −> B
X −> Y
Y −> A
Y −> C
Y −> X
A −> X
A −> Y

- Construisez une relation avec chaque partition des DF.

R1 (X, Y, A*, C) R2 (C*, B)

Les relations obtenues sont en FNBC, car les attributs non primaires ne sont en dépendance
fonctionnelle que sur des clés. Mais comme X, Y et A sont des clés équivalentes, il est possible de
choisir qu’une seule clé parmi les trois disponibles et ainsi simplifier le schéma :
R1 (A*, C) R2 (C*, B)

Ces deux relations en FN3 sont aussi, comme nous le verrons plus loin, en forme FN4. L’algorithme
proposé par Bernstein ne fournit pas à chaque fois un schéma de relations sans perte d’informations. Il
faut donc toujours tester les relations obtenues par synthèse, pour vérifier s’il y a conservation des
données (CDD).

Optimisation du schéma
La normalisation minimise la redondance et limite celle-ci aux seules clés (primaires et étrangères) qui
sont alors contrôlées par le SGBD. Dans certains cas, pour obtenir une performance élevée, il faudra
faire le processus inverse et créer volontairement la redondance pour éviter le calcul toujours lourd de
certaines jointures. Il peut en être même pour les contraintes d’intégrité qui peuvent être renforcées ou
désactivées, voire abandonnées pour des fins de performance. Cette dénormalisation ou insertion
volontaire de la duplication des attributs entraîne un travail supplémentaire lors des modifications et
des ajouts, car il faudra propager ces changements dans les relations où il y a les attributs redondants
touchés par la mise à jour ou l’ajout.

10.7 Dénormalisation et performance dans le calcul des requêtes

14
Chaque étape dans la mise en oeuvre d’une base est concernée par l’optimisation . C’est donc une
préoccupation aussi bien du concepteur de la BD lors de la normalisation que du DBA qui en gère, par
la suite, l’exploitation.

Atelier
noAt* 1,n
nomAt 1,1 FicheApprov
site
noFicheApprov*
dateFiche 1,n
LigneFiche
1,1
noLigne*
qte
1,1
1,n Piece
Stock noPi*
1,1
noStock* categorie
qteStock 1,n cout

Figure 10.16

Bien que l’optimiseur du SGBD soit de plus en plus intelligent, il ne peut pas remplacer le concepteur
de la BD qui est en mesure de mieux estimer les caractéristiques de l’exploitation des données par les
applications. Ces considérations influenceront les étapes de design et, par la suite façonneront les
réorganisations éventuelles du schéma. La dénormalisation est l’opération qui consiste à insérer dans
diverses relations certains attributs présents dans d’autres relations pour éviter le calcul de quelques
jointures. Cette opération sous-tend un contrôle supplémentaire par déclencheur afin que toute mise à
jour d’un tel attribut soit propagée aux autres relations ayant le même attribut. Elle dénormalise aussi

le schéma relationnel.

Le schéma relationnel de ce modèle réseau est le suivant :

Atelier (noAt*, nomAt, site)
FicheApprov (noFicheApprov*, dateFiche, noAt)
LigneFiche (noLigne*, noPi*, noFicheApprov*, qte)
Piece (noPi*, categorie, cout, noStock)
Stock (noStock*, qteStock)

Ce schéma est normalisé en FN3. Sa structure n’est cependant pas adaptée au calcul de toute requête.
Par exemple la requête simple ci-dessous exige un calcul lourd au regard du schéma nomalisé :
Quel est le nom des ateliers qui ont demandé un approvisionnement en pièces de la catégorie ʹfreinʹ ?
Pour calculer la réponse, il faut consulter quatre relations et faire trois jointures :
SELECT nomAt /*nom atelier */
FROM Atelier A, FicheApprov F, LigneFiche L, Piece P
WHERE [Link] = [Link] AND
[Link] = [Link] AND
[Link] = [Link] AND [Link] = 'frein';

Il faudra faire trois jointures parce que la réponse nécessite d’accéder à un attribut de la relation
Atelier et un autre de la relation Piece.
Projection sur nomAt

Jointure 3

Atelier Jointure 2

FicheApprov Jointure 1

LigneFiche Piece

Figure 10.18
Plan général dʹexécution
Le plan est établi par l’optimiseur, selon les règles suivantes :
a) Consultation des index dans un ordre donné;
b) Exploitation des cardinalités d’extension des tables visées (approche coût);
c) Exécution des jointures et des autres opérateurs selon des règles syntaxiques de l’optimiseur.
La présence de trois jointures ralentit sensiblement le calcul de la réponse à cette requête. La première
opération consiste à consulter la table Pièce pour trouver le numéro de la pièce libellée frein. Ensuite,

ce numéro permet de faire une première jointure avec la table LigneFiche dont le résultat fournira le
numéro de fiche nécessaire pour la deuxième jointure. Ensuite, le résultat donnera le numéro d’atelier
pour faire la dernière jointure qui fournira le nom de l’atelier.
Plan détaillé du traitement de la requête
Tous les attributs qui font lʹobjet dʹune référence dans les conditions de jointure sont présumés
indexés. Le plan détaillé est le suivant :
a) Sélection de la relation Pièce pour y trouver le numéro (noPi) de la catégorie des freins.
b) Avec ce noPi, accès à l’index sur LigneFiche pour obtenir les numéros de fiche
d’approvisionnement concernant cette pièce (1ère jointure).
c) Avec les numéros de LigneFicheApprov, accès à l’index de FicheApprov pour en obtenir les
numéros des fiches qui ont demandé des freins;
d) Avec les tuples associés à chaque noFicheApprov, accès à l’index de Atelier en vue dʹobtenir le
numéro des ateliers (noAt) visés, pour accéder ensuite à la relation Atelier afin dʹavoir, par un des
accès avec le ROWID, le nom des ateliers demandés.

Dénormalisation pour accélérer le calcul

La dénormalisation évite de faire les jointures coûteuses prévues ci-dessus dans le plan d’exécution.
Cette opération est l’inverse de la normalisation et ne doit être faite qu’à partir dʹune BD normalisée.
La dénormalisation est d’autant plus intéressante que le nombre de requêtes de ce type augmentait
avec le temps. Cʹest donc une opération à faire lorsque les accès aux données par les applications sont
bien connus et relativement stables :
La jointure 1 peut être supprimée en dupliquant l’attribut categorie dans la relation LigneFiche dont le
schéma devient alors le suivant :
LigneFiche1(noLigne, noPi, noFicheApprov, qte, categorie)

Cette nouvelle relation comporte une redondance pour l’attribut categorie, qui permet cependant une
simplification du plan d’exécution en supprimant la première jointure.

Projection sur nomAt

nomAt
Jointure 3

Jointure 2
noAt
Atelier

FicheApprov LigneFiche1

Figure 10.18

Requête modifiée :
SELECT nomAt

FROM Atelier, FicheApprov, LigneFiche1 LF1

WHERE [Link] = [Link] AND
[Link] = [Link]
AND [Link] = 'frein';

b) La jointure 2 peut aussi être supprimée en dupliquant l’attribut noAt dans la relation LigneFiche1
pour obtenir une nouvelle relation :
LigneFiche2 (noLigne*, noPi*, noFicheApprov*, qte, categorie, noAt)

La requête ne comprend alors qu’une seule jointure, soit la 3. Deux attributs redondants sont
maintenant à contrôler par des déclencheurs appropriés (non désactivables) du type préinsertion :
SELECT nomAt
FROM Atelier, LigneFiche2 LF2
WHERE [Link] = [Link]
AND [Link] = 'frein';

c) La jointure 3 de la requête pourrait être également supprimée en dupliquant l’attribut nomAt dans
LigneFiche2 pour ainsi obtenir une nouvelle relation LigneFiche3.
LigneFiche3
(noLigne*,noPi*,noFicheApprov*,qte,categorie,noAt,nomAt)

Le nouveau schéma dénormalisé devient donc le suivant :

Atelier (noAt*, nomAt, site)
FicheApprov (noFicheApprov*, dateFiche, noAt )
LigneFiche3(noLigne*,noPi*,noFicheApprov,qte,categorie,noAt,nomAt)
Piece (noPi*, design, cout, nomStock)

La requête se réduit alors à une seule sélection sur la nouvelle relation :

SELECT nomAt
FROM LigneFiche3 as LF3
WHERE [Link] = 'frein';

En résumé, le processus de dénormalisation consiste à enrichir, dans une même cascade de jointures la
relation de base de la jointure la plus profonde, et cela avec les attributs de jointure utilisés pour
passer d’une relation à l’autre.

Inconvénients de la dénormalisation des relations

La dénormalisation introduit une redondance qui sous-tend son lot d’inconvénients :
a) les actions d’ajout et de mise à jour sont ralenties par les déclencheurs (triggers) qui doivent
propager les mises à jour et vérifier les contraintes. Ainsi, pour ajouter un nouveau tuple dans
LigneFiche3 avec une valeur pour les attributs noLigne, noFicheApprov, noPi et qte, il faudra trouver

la valeur correspondante à design, noAt et nomAt en effectuant les sélections ou les jointures
appropriées. Sans une indexation adéquate des relations, il est possible que les gains obtenus par la
dénormalisation soient éclipsés par ces opérations inhérentes à la mise à jour;
b) un espace disque supplémentaire est utilisé pour les données redondantes;
c) augmentation des risques d’incohérence si les déclencheurs ne sont pas utilisés correctement (effet
de cascade) pour assurer la propagation des ajouts et des mises à jour;
d) contrairement à la création des index, la dénormalisation d’une base de données n’est pas neutre
pour les applications qui exploitent les données de la base. Il faudra les modifier pour tenir compte
des nouveaux schémas et cela, afin qu’elles demeurent opérationnelles.

10.8 Dépendances multivaleurs (DMV)

La présence d’une DMV permet de détecter que deux ensembles d’attributs sont indépendants dans
une même relation, i.e. non contraints l’un par l’autre. Ils peuvent, dans certains cas, être séparés par
une opération de projection pour diminuer la redondance et les anomalies qui en découlent. La DMV
permet de diviser une relation, même lorsqu’il y a absence de toute DF.
Exemple : R(employe*, diplome*, enfant*) avec l’ensemble F vide
Cette relation R est en forme FNBC puisque tous les attributs sont primaires et qu’il n’y a pas d’autres
DF que celles qui découlent de la clé. Certaines anomalies sont encore bien présentes dans cette
relation en FNBC. Par exemple, un employé sans enfant ne peut pas être représenté dans cette BD.
Une dépendance multivaleur triviale (appelée aussi multivaluée) existe entre deux attributs pris hors
contexte (sans le contexte des autres attributs de la relation) si à une valeur du déterminant (partie
gauche), correspond plusieurs valeurs du déterminé (partie droite). Par exemple, si un employé peut
avoir plusieurs enfants sans considérer ses diplômes, cette dépendance est appelée une DMV triviale
lorsquʹelle est formulée sans le contexte des autres attributs dʹune relation. En dʹautres mots, une
DMV triviale dans une relation sous-tend la notion de 1 à plusieurs (1:n) entre les deux attributs. Elle
est notée par le formalisme : employe ->> enfant. Lorsqu’une DMV est sans contexte, elle est aussi
appelée une dépendance multiple.
Si la conception aboutit à une relation avec plusieurs DMV dans la même relation, il peut y avoir un
problème d’anomalies et de redondance si les déterminés des DMV sont indépendants. La DMV revêt
aussi une certaine importance dans la conception puisqu’elle permet de pousser un peu plus loin le
processus de normalisation des tables. Considérons l’exemple précédent, un employé a plusieurs
enfants et aussi plusieurs diplômes. Les enfants dont il est le parent sont indépendants des diplômes
quʹil a obtenus. (indépendance entre les attributs enfant et diplôme).Cette indépendance se traduit par
la présence de DMV dans la relation R(employe*, enfant*, diplome*) :
employe -->> enfant employe -->> diplome

Si un employé e1 a deux enfants {f1 et f2} et un premier diplôme d1, alors l’employé e1 a
nécessairement ce même diplôme pour chaque enfant dont il est le parent. Cette information est
représentée par deux tuples :
r: Employe* Diplome* Enfant*
e1 d1 f2

e1 d1 f1

Si l’employé e1 a un deuxième diplôme d2, alors il faut ajouter non pas un, mais deux nouveaux
tuples dans lʹextension de la relation. Avec ce nouveau diplôme d2, lʹemployé e1 demeure toujours
parent de f1 et f2 !
r: Employe* Diplome* Enfant*
e1 d1 f2
e1 d2 f1
e1 d2 f2
e1 d1 f1

Cette multiplication est une conséquence des DMV présentes dans la relation et dont les déterminés
sont indépendants. En effet, il n’y a pas de lien ou de dépendance entre les diplômes et les enfants.
Cette indépendance se traduit par la présence obligatoire de toutes les combinaisons diplome-enfant
dans lʹextension pour chaque employé concerné. Sʹil y avait une combinaison absente, alors les deux
attributs seraient dépendants, puisque quʹun diplôme serait inscrit, par exemple que pour un enfant.
Cette même relation peut être aussi formulée comme une relation NF2 (Non First Normal Form) dont
l’extension peut être représentée par les ensembles suivants :

1er tuple : {e1,{d1, d2}, {f1, f2}}

2e tuple : {e2,{d2}, {f3}}

Dans un modèle normalisé, l’extension est composée de valeurs atomiques et pour s’y conformer, il
doit y avoir multiplication des tuples dans la table. Le schéma R ci-dessous est en forme FNBC.
R : (employe*, diplome*, enfant*)

r: e1 d1 f1
e1 d1 f2
e1 d2 f1
e1 d2 f2
* e2 d2 f3

La clé est composée de trois attributs : employe*, diplome*, enfant*. Malgré sa forme FNBC, cette
relation contient encore des anomalies. Comment peut-elle être décomposée? Quels sont les critères
pour sa décomposition ?

Anomalies résiduelles dans R

a) Il est impossible d’ajouter dans r un nouvel employé sans enfant :

< e4, d2, null > car il y a violation de la contrainte de clé.

b) Si l’enfant unique de e2 décède (*), son tuple doit être supprimé. Est-il possible de conserver une
trace du diplôme d2 de e2 ? Autrement dit, est-il impossible de garder le tuple <e2, d2, null> dans r ?
c) L’employé e1 parent de f1 et titulaire du diplôme d1 doit être mis à jour pour que son diplôme
porte dorénavant le nom de f5. Une mise à jour limitée au premier tuple laisse la base dans un état
incohérent. En effet, e2 possède toujours le diplôme d1 pour le 3e tuple !

Ces anomalies découlent de la présence de la DMV dans R, soit employe ->> diplome | enfant, c’est-à-
dire du fait que les attributs diplome et enfant sont indépendants et se retrouvent dans la même
relation. Une DMV est une contrainte multiplicatrice de tuples : si un tuple doit être présent dans
l’extension r, d’autres doivent aussi obligatoirement l’être dans la même relation. Sur le plan
sémantique, ceci traduit la réalité suivante : un employé a les mêmes diplômes pour tous ses enfants !
Voici un autre exemple représentant lʹallocation des avions sur différents vols. La relation Service
(vol*, jour*, avion*) n’a pas de DF et présente une redondance qui est une source d’anomalies. Les
DMV non triviales sont les suivantes :
vol ->> jour et vol −>> avion et
Avec F qui est vide, il n’y a donc pas de DF dans la table Service.

Est-ce que ces DMV sont validées ou présentes dans la relation Service ? Si oui, il y a indépendance
entre les attributs jour et avion qui reflète la sémantique sous-jacente à savoir que le type d’avion
B747 dessert le vol 871 (Paris-Montréal), le lundi et le mardi. Forcément, puisque la DMV non triviale
est donnée valide, l’ajout d’un autre avion pour le vol 871 doit faire aussi le service les lundi et mardi.

service(1) : vol* jour* avion*

871 lundi B747
871 mardi B747
871 lundi DC10
871 mardi DC10
870 jeudi A330
870 jeudi B747

Cette relation Service peut être divisée en deux autres relations pour diminuer la redondance. Par
contre, si les attributs jour et avion sont dépendants, la DMV ne serait pas alors validée, la division de
la relation ne pourrait pas se faire sans perdre de lʹinformation. Par exemple, lʹextension service(2) ci-
dessous a des dépendances multiples ou DMV triviales qui ne créent pas de problème à faire
cohabiter certains tuples dans la même relation.
service(2) : vol* jour* avion*
871 lundi B747

871 mardi B747

871 lundi DC10
870 jeudi A330
870 jeudi B747
Le vol 871 du mardi assuré par le DC10 n’a pas l’obligation de l’être aussi le lundi !
Cette dernière extension correspond à une relation qui ne peut pas être décomposée sans perte de
données.

Par contre, la première extension correspond à une relation service(1) qui peut être décomposée sur la
base d’une DMV valide et cela, pour aboutir à deux nouveaux fragments de table qui ne présentent
plus les anomalies observées dans la relation dʹorigine.

volJour : vol jour volAvion : vol avion

871 lundi 871 B747
871 mardi 870 DC10
870 jeudi 870 A330
870 B747

La relation Service(1) peut donc être divisée sans perte d’information (CDD) et cela, grâce à la DMV
présente.
Dépendance entre les attributs
Lorsque deux attributs sont dépendants, la DMV n’existe pas dans la relation ou en d’autres mots, elle
existe avec un contexte vide, i.e. sans aucun autre attribut dans la relation que les deux attributs
dépendants.
Exemple :
R1 : employe* diplôme* pgmEtudes*
jean DEC arts
jean DEC sciences po
jean bacc sciences po
louise DEC humanités
sylvie DEC sciences
pierre DEC santé
claire Bac santé
jean PhD droit <--

Est-ce que la DMV employe -->>diplome est vérifiée ou valide dans cette relation R1 ? En d’autres
mots, est-ce que les attributs diplome et pgmEtudes sont indépendants ? Si la DMV était confirmée,
alors l’indépendance des deux déterminés le serait aussi.

Si Jean obtenait un PhD en droit, il n’aurait pas automatiquement aussi le DEC et le Bac en droit; un
seul tuple serait ajouté dans l’extension dans le cas où le diplôme est dépendant de pgmEtudes. Si tel
est le cas, la DMV employe -/->> diplome n’est pas validée dans R1 et cela, même s’il existe une
association (1-n) entre les attributs employe et diplome.

Notez cependant, qu’une DMV qui n’est pas validée dans R1, pourrait cependant apparaître dans une
autre relation (ou projection) et être vérifiée. Dans un tel cas, la DMV est dite imbriquée (latente) dans
la première, R1. Dans l’exemple R1 ci-dessus, la DMV n’est pas validée et par conséquent les attributs
diplome et pgmEtudes sont considérés dépendants.

Définition formelle de la DMV dans le contexte dʹune relation

Comment détecter qu’une DMV formulée hors contexte est validée dans une relation ? Soit R(A, B, C)
et α(R) = 3 avec a, b, c comme valeurs quelconques (constantes) de A, B et C.

Définition de l’opérateur : Ba,c = {b | (a, b, c) ∈ r} pour une paire donnée (a, c)

Soit la DMV hors contexte : A->> B, elle est validée dans la relation R(A, B, C) (et donc A ->> C),
si B(a, c) = B(a, c’) pour chaque (a, c) et (a,c’), pour (a, c) ∈ R[A, C] et (a, c’) ∈ R[A, C].

Si l’ensemble des éléments de B ne varie pas quelle que soit la valeur de C (c ou c’), alors l’attribut B
est indépendant de C dans la relation R et la DMV est validée ou existe dans le contexte de cette
relation. On peut aussi de démontrer que la DMV A-->> B est validée dans R(A, B, C) si pour toute
paire de tuples dans r ayant la même valeur de A : (a, b, c) et (a, b’, c’), on a aussi (a, b’, c) et (a, b, c’) ∈
r.

A B C A B C
a b c a b’ c

a b’ c’ a b c’

Autre définition de la DMV

Dans R(X, Y, Z), la DMV X -->> Y est validée si, pour toute extension de R, pour chaque paire de tuples
avec le même X, alors deux autres tuples de r obtenus en intervertissant les valeurs de Y de la paire de
départ sont obligatoirement dans l’extension.

Exemple : R: X Y Z

1 1 1
1 2 2
1 2 1
1 1 2
2 2 2

Cette extension est présumée représenter tous les cas de figure admis pour cette relation, c’est-à-dire
que toutes les dépendances de cette relation sont vérifiées.
Test de validité dʹune DMV dans une relation
Pour toute paire de tuples de R partageant la même valeur d’attribut X, d’autres tuples sont
obligatoirement présents dans l’extension de R (X,Y, Z).

X, Y, Z
X -->> Y ? 1, 1, 1 ⇒ 1, 2, 1
1, 2, 2 1, 1, 2
1, 1, 1 ⇒ 1, 2, 1
1, 2, 1 1, 1, 1

X -->> Z ? 1, 1, 1 ⇒ 1, 1, 2
1, 2, 2 1, 2, 1
...

Cas particulier
Si dans R(A, B, C), A −> B et si pour toute paire (a,c) et (a, c’), on a
Ba,c = {b |(a, b, c) ∈r} = {b1} et si Ba, c’ = {b | (a, b, c’) ∈ r} = {b1} (avec un seul élément), alors A->> B
Donc si A -> B, alors A->> B et mais l’inverse nʹest pas vrai. De façon similaire avec A --> B, si pour
toute paire de tuples partageant la même valeur pour A, la relation suivante est vérifiée :

(a, b, c ) ( a, b, c)
si ∈r alors ∈r
(a, b, c’ ) (a, b, c’ )

La condition est toujours vérifiée avec une DF. Toute DF est donc une DMV.

Décomposition dʹun schéma de BD

Cas 1 : décomposition avec DF, mais sans DMV
Soit le schéma de la relation universelle et lʹensemble F des DF : (U, F) :
U = {titre, realisateur, heure, prix, cinema, adresse, tel} et

F = {DF1 : cinema −> adresse, tel;

DF2 : cinema, titre, heure −> prix;
DF3 : titre −> realisateur }

L’algorithme de décomposition en FNBC est utilisé :

a) ( {cinema, adresse, tel}, {DF1}), ({titre, realisateur, heure, prix, cinema}, {DF2, DF3});
b) la deuxième relation obtenue est à nouveau décomposée :
({cinema, titre, heure, prix}, {DF2}), ({titre, realisateur, heure, cinema}, DF3);
c) la décomposition est poursuivie avec DF3
({titre, realisateur}, {DF3}), ({titre, heure, cinema }, {Ø});
d) la relation {titre, heure, cinema } est supprimée parce qu’elle est une projection de la relation déjà
obtenue à l’étape b;
e) Schéma de la base est alors le suivant :
({cinema, adresse, tel}, {DF1}),
({cinema, titre, heure, prix}, {DF2}),
({titre, realisateur}, {DF3}).
Le schéma final est donc CDF et CDD et est composé que de relations FNBC.

Cas 2 : décomposition avec une DMV

Supposons qu’un nouvel attribut, acteur, soit ajouté au schéma initial ci-dessus. De plus, la DMV
suivante: titre -->> acteur est présumée présente dans le schéma (comme hypothèse qui restera
cependant à vérifier).

La décomposition par l’algorithme précédent fournira un schéma en FNBC, mais qui regroupe aussi
des attributs qui ne vont pas ensemble sur le plan de la sémantique (soit l’attribut acteur).
({cinema, adresse, tel}, {DF1}), ({cinema, titre, heure, prix}, {DF2}),
({titre, realisateur}, {DF3}), ({cinema, titre, heure, acteur}, {DMV})

La dernière relation ne peut pas être supprimée en raison de l’attribut acteur. Cette dernière relation
n’est pas naturelle parce que l’heure du cinéma serait associée (dépendant des) aux acteurs ! Or, la
décomposition peut être poursuivie en prenant en compte la DMV. Le schéma obtenu est CDD. La
forme normale FN4 a été formulée pour traiter ce type de problème.
({cinema, adresse, tel}, {DF1}),
({cinema, titre, heure, prix}, {DF2}),
({titre, realisateur}, {DF3}),
(titre, acteur}. {DMV}}, <----
({cinema, titre, heure}, {DF2}) --> relation redondante

La dernière relation est supprimée parce qu’elle est une projection d’une autre relation du schéma
(voir l’algorithme de transformation en FNBC d’un schéma de BD) Le schéma final est donc :
({cinema, adresse, tel}, {DF1}), ({titre, realisateur}, {DF3}),
({cinema, titre, heure, prix}, {DF2}), (titre, acteur}. {DMV sans contexte}}

Le schéma obtenu est de type CDD et CDF. La DMV a donc permis de décomposer un schéma de BD
pour obtenir des relations qui regroupent correctement les attributs en accord avec la sémantique des
DF et les DMV. Doit-on conclure que la présence d’un attribut associé à plusieurs valeurs et que ce
dernier doit être isolé dans une relation ? Non, car il y a multiplication inutile des relations,
notamment lorsque la DMV hors contexte n’en est plus une lorsqu’elle est intégrée avec d’autres
attributs d’une même relation.

Décomposition de Fagin
La présence d’une DMV vérifiée dans une relation R sous-tend des anomalies. La relation R(A, B, C)
est donc décomposée dans le but de corriger certains de ces problèmes : si A->> B est validée dans R,
elle doit induire A->> C dans la même relation. La relation peut être alors divisée en deux nouvelles
relations dont la jointure est équivalente à la relation de départ.
R(A, B, C) = R1(A, B) |x| R2(A, C) et DMV : A->>C

Si R1 ∩R2 -->> R1 ou R1 ∩ R2 -->> R2, alors la décomposition est sans perte d’information (CDD) et la
jointure des deux nouveaux fragments de relation donne la même extension initiale, sans générer de
fausses informations (théorème de Fagin).
Exemple 1 :
employe : nom* diplome* enfant*
dion dec jean
blais dec lise
blais bac lise
dion bac jean
blais dec pierre
blais bac pierre

nom->> enfant ? nom ->> diplome ?

enfant blais, dec = {lise, pierre}

Pour toute paire de tuples partageant la même valeur de nom, l’ensemble des enfants est le même
quel que soit le contexte.
Enfant blais, bac = {lise, pierre} Enfant blais, dec = {lise, pierre}
Enfant dion, bac = {jean} Enfant dion, dec = {jean}

L’ensemble de Enfant ne varie pas lorsque le diplôme (contexte) varie pour un même nom dʹemployé.
Cette propriété est vérifiée pour tous les employés. Il y a donc indépendance des attributs diplôme et
enfant traduisant lʹabsence de lien sémantique entre le diplôme et l’enfant. Le schéma peut donc est
divisé.

DMV triviale
Dans R(X, Y, Z) si X->> Y est une DMV validée, elle est dite triviale si et seulement si Y⊆ X ou
X ∪ Y = R ou si Z = ø, c’est-à-dire lorsqu’il n’y a pas de contexte à la DMV, X ->> Y. En
d’autres mots, puisque Y⊆ X, c’est-à-dire X −>Y, toute DMV qui découle de l’existence d’une
DF équivalente est triviale.

r: A B C
1 1 1
1 2 2
1 2 1
2 2 1
1 1 2
2 1 2

Est-ce que A->> B est validée dans R(A, B, C) ?

Ba, c donne les valeurs de b dans R:
Ba, c = B1, 1 = {1, 2} B1, 2 = {2, 1}
B2, 2 = {2} B2, 1 = { 2}
La DMV, A->> B est validée dans la relation R et elle nʹest pas triviale.
Exemple : R : (A, B), est-ce que A -->> B est validée dans l’extension R ci-dessus?

1 1 (1, 2) ∈ r
1 2 (1, 1) ∈ r
2 2 (2, 1) ∈ r
2 1 (2,2) ∈ r

La DMV est validée, mais triviale, car A∪B = R, le schéma de la relation. Une DMV sans contexte est
dite triviale et a aussi été appelée une dépendance multiple dans certaines méthodologies (voir
15
méthodologie EPAS ). Ces dépendances multiples ne génèrent pas de problèmes et sont les seules
dépendances multivaluées tolérables dans une relation dont le contexte se limite aux attributs de la
DMV triviale. Pour éviter les anomalies qui découlent de la présence de DMV non triviales, il suffit
donc d’isoler chaque DMV non triviale validée qui implique des attributs indépendants dans une
nouvelle relation (sans contexte). Ainsi la DMV est transformée en une dépendance multiple (ou
DMV triviale).

Propriétés des DMV

Soit R(X, Y, Z), une relation dont le schéma est partitionné de sorte que X∪Y∪Ζ = R avec ((X ∩ Y)
∩Ζ) = ø. Les propriétés des DMV sont utiles pour déduire d’autres DMV et ainsi poursuivre la
normalisation du schéma relationnel. Cela permet la transformation des relations autrement
impossible sur la seule base des DF.
Réplication ( ou généralisation de la DF)
La DF est un cas particulier de la DMV. Si X−> Y est validée dans R, alors X->> Y l’est aussi, mais non
l’inverse. Donc, X−>Y |= X ->> Y dans R. La démonstration de cette propriété découle de la définition
même de la DMV.
Réflexivité
Si Y⊆ X alors X->> Y validée dans R et elle est dite triviale parce que Y ∪ X = R.
Démonstration Si Y ⊆ X alors la DF X −−> Y est valide par réflexivité. Par généralisation de la DF, on
obtient la DMV X ->> Y dans R.
Complémentarité
Soit X ∪ Y ∪ Z = R est une partition du schéma de R avec Y∩Z = ø. Si X ->> Y est validée dans R, alors
X ->> R - X - Y, c’est-à-dire X ->> Z dans R est aussi validée.
Transitivité
Si X ->> Y et Y ->> Z sont validées dans R, alors X ->> Z - Y est aussi validée dans R. Si Y∩Z = ø alors X
->> Z.
Augmentation
Soit R(X, Y, W, V), si X ->> Y est valide dans R et W⊆ V (donc V->> W), alors X, V ->> Y, W est aussi
valide dans R.
Cas particulier : augmentation du déterminant
Si X->> Y et Y⊆Y (donc Y->> Y), alors X, Y->> Y
Union (augmentation du déterminé)
Si X->> Y et X->> Z alors X->> Y-Z est valide aussi dans R.
Cas particulier : si W−> W et X −> Y, alors X, W -->> Y, W
Pseudo transitivité
Si X->> Y et W, Y->> Z sont valides dans R, alors X, W ->> Z - Y.
Décomposition ou projectabilité: intersection, différence et union
Si X ->> Y et X ->> Z alors X ->> Y∩Z et X ->> Z – Y et X ->> Y – Z et X ->> Y∪Z
Coalescence : générateur dʹune DF à partir dʹune DMV
Si X ->> Y est valide dans R, alors X−> Y’ est aussi valide dans R si et seulement si ∃ Z⊆ R tel
que Z−> Y’ et que Z∩Y = ø.
Exemple :
Dans R(A, B, C, D) avec A->> B, C et que D -> B, alors A -> B par coalescence.

Fermeture par les DMV (D+)

Si D est l’ensemble des DMV pour la relation R, la fermeture D+ est l’ensemble des DMV obtenues par
l’application récursive des propriétés ci-dessus. Les règles d’inférence essentielles et suffisantes sont la
complémentarité, la transitivité, l’augmentation et la coalescence. Ces règles sont complètes et valides,
c’est-à-dire que leur application récursive génère toutes les dépendances possibles de D+.
Exemple : R(A, B, C, G, H, I) D = {A ->> B; B ->> H, I; C, G ->> H}
Quelques DMV de D+
a) D |– A->> C, G, H, I;
A ->> B par hypothèse, A->> C, G, H, I par complémentarité;

b) D |– A->> H, I; A -->> B par hypothèse, B ->> H, I par hypothèse,

A-->> {H, I - B} = H, I par transitivité;

c) D |– A->> C, G; A-->> C, G, H, I par hypothèse,

A ->> H, I du résultat antérieur, A ->> {C, G, H, I} - {H, I} = C, G par différence.
Exemple : R (employe, profession, langueP)

r: employe* profession langueParlee

Tremblay traducteur français
Tremblay traducteur allemand
Tremblay traducteur grec

Est-ce que la DMV employe ->> profession est valide dans R ?

Si Tremblay devient éditeur, faut-il ajouter un ou trois tuples dans la relation R ?

Tremblay éditeur français

ou
Tremblay editeur français
Tremblay editeur allemand
Tremblay editeur grec

S’il faut en ajouter 3 tuples dans la table, une DMV est présente dans la relation et il y a indépendance
entre les attributs profession et langue-p. La relation peut alors être décomposée ainsi :
R (employe, profession) et R1 (employe, langueParlee)

Dans le cas contraire, la DMV n’est pas valide dans R, alors les attributs sont dépendants ce qui
nécessite l’ajout d’un seul tuple sans la nécessité de diviser la relation.

Forme normale FN4

Une relation R (A1, A2, ... Ai) est en FN4 par rapport à un ensemble D formé avec les DF et les DMV,
si pour chaque DMV ∈ D+ valide dans une relation R telle que X->> Y avec X ⊆ R et Y ⊆ R, au moins
une des conditions suivantes est vérifiée :

a) X->> Y est une DMV triviale dans R

ou
b) X est une superclé dans R, c’est-à-dire que X −> A1, A2, ... Ai (DF)

Donc si chaque déterminant des dépendances de D est une superclé, la relation R est en FN4, car les
DF implicites à la clé correspondent aussi à une DMV. La fermeture de D est alors obtenue par les
propriétés des DMV.

Exemple :
Est-ce que la relation R (A, B, C, D, E) avec l’ensemble D ci-dessous est en FN4 ?
D = {A−>B, C; C ->> D, E} et la clé est {A, D, E}
Puisque C->>D, E alors C->>A, B. En outre, puisque A->B alors A->>B.
Elle n’est pas en FN4, car la DMV C->>D, E n’est pas triviale dans R et C n’est pas une superclé. Après
décomposition de R sur la base du théorème de Fagin, les fragments suivants sont obtenus :
R1(C*, D*, E*) et R2 (A*, B, C) qui sont en FN4.
La décomposition est CDD et CDMV (conservation des dépendances multivaluées)

Algorithme de décomposition de R pour avoir la forme FN4

Soit R = {R1, R2...} et D l’ensemble des DF et DMV de R et F l’ensemble des DF seulement;
RESULTAT := R;
FAIT := FAUX;
tel que (¬FAIT) faire
Si (∃Ri dans RESULTAT, la relation n’est pas FN4)
alors choisissez X ->> Y (non triviale) dans Ri tel que X-> Y ∉ F+ et
X∩Y = ø
RESULTAT :=(RESULTAT - Ri)∪(Ri - Y)∪ (X,Y);
sinon FAIT :=VRAI

Importance du contexte avec les dépendances du DMV

Exemple :
ResHum (employe, enfant, salaire, annee)
F=ø

D = {employe ->>enfant; employe ->> salaire, annee}

D regroupe les DMV valides de la relation Res-Hum.

Est-ce que la relation Res-Hum est en FN4 ? Quelles sont les DF de cette relation ?
employe -> enfant ? employe −> salaire ? employe −> annee ?

Est-ce que par coalescence certaines nouvelles DMV peuvent être dérivées ?
Puisque les DF n’existent pas dans le schéma de la relation Res-Hum (F est vide) alors celle-ci n’est
pas en FN4, car les DMV valides de D présentes dans le schéma ne sont pas triviales.

Décomposition de la relation Res-Hum :

Fam (employe, enfant) HistSal (employe, salaire, annee)
et dans ces deux nouvelles relations, les DMV sont triviales et donc en FN4.

Autre exemple
InscEtud (matric*, cours*, sports*)

Les DMV sont les suivantes : D = {matric -->> cours ; matric -->> sports}. Les DMV valides sont non-
triviales.
Alors pour être en FN4, il faudrait que :
matric -->matric; matric --> cours; et que matric --> sports

Or, comme cela n’est pas le cas, la décomposition s’impose :

ChoixCours (matric*, cours*)
ChoixSports (matric*, sports*)
Fermeture dʹun ensemble dʹattributs avec les DMV (D+)
Pour effectuer la fermeture d’un ensemble ou d’un seul attribut X, il suffit de réunir les ensembles
d’attributs déterminés X dans toutes les DMV dérivables par les règles d’inférence. Ces ensembles
sont appelés une base de dépendances de X laquelle est notée G(X) et correspondent à la fermeture de
l’attribut X par rapport à D.
Base de dépendance de X par rapport à D
Soit D un ensemble de DF et de DMV et U l’ensemble des attributs qui apparaissent parmi les
déterminés ou les déterminants de ces dépendances. La base de dépendance de X, G(X) est constituée
des sous-ensembles d’attributs de {U - X } tel que chacun soit déterminé par le déterminant X dʹune
DMV de D+.

En d’autres mots, la base de dépendances de X est la partition la plus fine des attributs de U : G(X) =
{P1, P2, P3, ... Pk | 1 <= k <= n}. Donc, X -->> Pj ∈ D+ ou X-->> Y ∈ D+ où Y est obtenu par la réunion
de quelques partitions Pj ∈ G(X).

Dépendance DMV élémentaire

Une DMV X ->>Y est dite élémentaire si Y est un élément de la partition de la base de dépendances.
Dans les autres cas, elle est dite DMV.

Calcul de G(X)
Le calcul de la base de dépendances de X n’est pas linéaire, mais plutôt polynomial et proportionnel à
(n3 x m) où n est le nombre d’attributs dans U et m le nombre de dépendances dans D.
Algorithme :
a) À partir de l’ensemble des FD et DMV, convertissez les DF explicites en DMV par la propriété de
généralisation. Soit FD : X ->Y, la DF est alors convertie en X->>Y. L’ensemble D contient alors que
des DMV explicites;
b) Initialisez au départ l’ensemble S comme nul. S = φ;
c) Pour chaque DMV, Y ->> Z dans D si Y ⊆ X, ajoutez {Z-X} et {U-Z-X} dans l’ensemble S, car
1. Y ->> Z et X ->> Y (de Y ⊆ X) et par transitivité, on a que X ->> Z-X;
2. par complémentation, X ->> U - Z - X;
3. S = {(Z - X), (U - Z - X)};
d) Appliquez les règles de projectabilité (addition), tant que cela est possible, à toute paire de
partitions de S non disjointes .
Si Y et Z sont des déterminés de A dans S (i.e. X->>Y et X->> Z ) et X ∩ Ζ ≠ φ, alors (Y ∩ Z), (Y - Z)
et (Z- Y) dont les déterminés de X s’ajoutent à S et remplacent Y et Z, initialement dans S;
e) Pour chaque DMV, W -->> Z de D, recherchez Y dans l’ensemble S tel que W ∩ Y = φ, mais avec
Z ∩ Y ≠ φ et Y - Z ≠ φ. Pour cette DMV remplacez Y par Y - Z et par Y ∩ Z;
f) À la fin de l’algorithme, S∪X contient la base de dépendances pour X, soit G(X).

Exemple :
R (A, B, C, D, E) avec D = {A −> B, C et D, E ->>C}
Calculez la G(A), c’est-à-dire les DMV de D+ ayant A dans la partie gauche (fermeture de A par
rapport à D).
1. Conversion en DMV pour obtenir D = {A ->> B, C; D, E ->>C};
2. Au début, S = φ;
3. De A ->>B, C alors ajout de D, E dans S et B et C pour avoir S = {B, C; D, E};
4. ne s’applique pas;
5. Avec A ->> B, C pas de modification à S avec D, E ->>C de D, le {B, C} de S est remplacé par {C} et
{D, E} pour avoir alors S ={B; C; D, E};

6. Finalement, S ∪ A = {A; B; C; D, E}, c’est-à-dire que la fermeture de A: A->>A; A->> B; A-> C; A-

>> D, E;
Théorème dʹappartenance dʹune DMV à D+
Une DMV, X ->>Z est dans la fermeture D+ si et seulement si le déterminé Z peut être formé par
l’union de quelques éléments de la base de dépendances G(X) .
16

Exemple : A ->> A, D, E est valide si A -> {A} ∪ {D, E} ∈ G(A).

10.8.1 Cohérence dʹune base de données

Avant d’étudier une autre dépendance plus spécialisée, soulignons que les dépendances de type FD et
DMV sont utiles pour la conception du schéma d’une BD parce qu’elles diminuent la redondance et
les anomalies tout en assurant une cohérence de la BD. Lorsque le schéma est déjà connu, la question
est de savoir s’il est cohérent.
Exemple :
Soit la BD formée des relations suivantes : R1(B, E), R2(E, CL), R3 (CL, C) et R4 (C, B)
où R1 (banque, emprunt) R3 (client, compte)
R2 (emprunt, client) R4 (compte, banque)

R1 : B E R2 : E: CL R3 : CL C R4 : C B
b0 e0 e0 cl0 cl0 c0 c0 b0
b1 e1 e0 cl1 cl1 c0 c0 b1
e1 cl0

Pour répondre à la question, quels sont les clients de chaque banque (CL, B), un utilisateur peut
formuler son traitement de différentes façons. Est-ce que ces requêtes sont équivalentes et correctes ?
Par exemple, voici trois requêtes possibles dont le schéma résultant contient les attributs de la
réponse. Ces trois requêtes prétendent donc répondre à la question (Rep) :
R1 |X| R2 = Rep(B, CL) ; b) R3 |X| R4 = Rep(B, CL); c) R2 |X| R3 |X| R4 = Rep(B, CL)

par a) : R1 |X| R2 B E CL
b0 e0 cl0
b0 e0 cl1
b1 e1 cl0

par b) : R3 |X| R4 CL C B
cl0 c0 b0
cl0 c0 b1
cl1 c0 b0
cl1 c0 b1

par c) : R2 |X| R3 |X| R4 E CL C B

e0 cl0 c0 b0
e0 cl1 c0 b0
e1 cl0 c0 b0
e0 cl0 c0 b1
e0 cl1 c0 b1
e1 cl0 c0 b1

Pour calculer la réponse, il faut faire la projection sur B et CL.

de a) B CL de b) CL B
b0 cl0 cl0 b0
b0 cl1 cl0 b1
b1 cl0 cl1 b0
cl1 b1

de c) CL B
cl0 b0
cl1 b0
cl0 b1
cl1 b1

Il y a donc une différence entre ces résultats qui ont pourtant le même schéma de réponse. La réponse
est incohérente en raison d’une déficience du schéma initial de la BD. Sous certaines conditions, le
schéma d’une BD ne fournira que des résultats corrects et cohérents.

Jointure complète dʹordre n

Une jointure (R1 |X| R2 |X|... Rn) est dite complète si les n Ri se retrouvent dans la projection du
résultat de la jointure de toutes ces relations.

Cohérence dʹune base de données

Une basee de données est cohérente si la jointure de toutes les relations de son schéma de BD est
complète et si le schéma de BD est acyclique.

Cohérence par 2
Une basse de données est cohérente par 2 si pour toute paire de relations du schéma de la BD, Ri et Rj,
leur projection respective sur leurs attributs communs est égale. En d’autres mots, la jointure de ces
paires quelconques de relations doit être complète : Π Ri ∩ Rj (Ri) = ΠRi ∩ Rj (Rj) .

Si toutes les jointures sont complètes par 2, il y a aussi une jointure complète dʹordre n.
Exemple : Est-ce que le schéma R1(A, B, C), R2 (B, C, D) et R3 (A, D) de la base de données ci-dessous
est cohérente par 2 ?

R1: A B C R2: B C D R3: A D

0 0 1 0 1 1 0 1
1 0 1 3 4 5 1 1
2 3 4 2 5

ΠC (R1) = ΠC (R2) (R2) = ΠD (R3)

ΠA (R1) = ΠA (R3)
Donc, la jointure est complète et que la base de données est cohérente par 2.

Schéma cyclique
La présence d’un cycle dans certains schémas empêche la cohérence par 2 et n’implique pas la
cohérence de la BD.
Exemple :
R1(A, B, C) R2(B, C, D) R3(A, D) avec F = { B-> C; A -> B; B, C -> D; A -> D} les DF établies
entre les relations forment un cycle qui introduit une incohérence dans la base.

A, B, C
D, B, C

A, D
Le schéma peut être transformé et rendu acyclique par divers moyens :
a) Fusion de schémas relationnels;
b) Ajout de nouveaux attributs aux relations;
c) Supprimer certains attributs;
d) Ajouter de nouveaux schémas de relation.

Test de la présence dʹun cycle dans le schéma dʹune base de données

Algorithme :
a) Création d’un tableau avec les schémas de la BD :
1- chaque ligne représente un schéma de relation;
2- chaque colonne représente un attribut;
b) Appliquez de façon récursive les opérations ci-dessous tant que cela modifie le tableau :
1. opération colonne : toute colonne avec un seul attribut est effacée,
2. opération ligne : effacement de toute ligne qui est un sous-ensemble d’une autre ligne
présente dans le tableau;

c) S’il ne reste plus aucune entrée, le schéma de base, excluant les sous-schémas, est dit acyclique,
sinon il y a un cycle lorsquʹil reste des entrées. Pour être complet, il faut aussi tester tous les sous-
schémas de la BD en les incluant dans le tableau.
Exemple :
Le schéma d’une base est le suivant : R1(A, B, C) R2(B, C, D) et R3(C, D, E).
Le tableau initial est donné ci-dessous.

A B C
B C D
C D E

Effacement des colonnes seules :

B C
B C D
C D

Effacement des lignes qui ont un sur-ensemble :

B C D

Effacement des attributs seuls dans une colonne :

(vide)

Le tableau est vide, le schéma est acyclique et si la cohérence par 2 est démontrée, alors il existe un
schéma de base de données correspondant qui est cohérent.
Exemple :
Est-ce que le schéma suivant est acyclique ? R1(A, B, C) R2(B, C, D) R3(A, D)

10.9 Dépendance complexe dans une relation : introduction à la dépendance mutuelle

Certaines relations ont des contraintes particulières qui ne sont pas formalisables par les DF et les
DMV. Ces contraintes le seraient cependant par une formulation logique plus ou moins complexe
lesquelles pourraient être implantées notamment par des déclencheurs. Certaines de ces contraintes
sur les données revêtent une importance particulière puisqu’elles permettent de décomposer
davantage une relation qui ne peut l’être sur la base des dépendances fonctionnelles ou multivaluées.
En poussant plus loin la décomposition, cela permet de corriger certaines anomalies plutôt rares, mais
bien réelles dans une telle relation. Ces contraintes spéciales sont souvent difficiles à découvrir dans

une base de données. La dépendance mutuelle (DMUT) est une de ces dépendances qui traduit une
contrainte complexe permettant la décomposition dʹune relation. La dépendance mutuelle permet de
décomposer une relation autrement indécomposable sur la base des DF et des DMV.

Voici un exemple proposé par Nicolas18 :

Represente (rep*, prod*, soc)

rep* pro* soc

r1 p1 s1 s1= { p1, p2 }
r1 p2 s1
r2 p4 s3 s3 = {p4}
suppression ! r1 p3 s2 " s2 = {p3 }
r2 p1 s1
r1 p4 s5 s5 = { p4}

Indécomposabilité et anomalies de la table Représente

Dans cette relation, il y a qu’une seule dépendance fonctionnelle, soit DF : rep, pro −> soc qui est celle
sous-jacente à la clé primaire. La relation est donc en FN4, puisque la DMV dérivée est triviale
découlant de la dépendance fonctionnelle. En supprimant le tuple (r1, p3, s2), r1 vend p3 de la société
s2, alors on perd lʹinformation que s2 fabrique le produit p3. Un produit p5 fabriqué par la société s5
ne peut pas être inscrit dans la base sans avoir un représentant. La relation en FN4 a encore une
anomalie de suppression qui persiste en dépit de la normalisation de son schéma. Comment
supprimer ces anomalies résiduelles ? Il faut certes la décomposer, mais comment faut-il le faire ?

Sémantique du tuple dans Represente

Le tuple t = (r, p, s) s’interprète comme un représentant r qui vend le produit p fabriqué par la société
s. Il y a dans cette relation une seule DF qui justifie la clé primaire :
rep, prod --> soc

Cette dépendance fonctionnelle s’interprète ainsi :

Un représentant qui vend un produit ne le fait que pour une société même s’il vend d’autres produits
fabriqués par dʹautres sociétés. Il ne se permet aucune concurrence inter-société pour les produits qu’il
vend.

Ainsi : si les tuples (r1, p1, s1) et (r1, p2, s2) sont valides et présents dans l’extension de Represente,
alors les tuples (r1, p1, s2) et (r1, p2, s3) ne le sont pas en présence des deux premiers. En effet, ils
violeraient la DF définie par la clé primaire. Donc le représentant r1 vend le produit p1 fabriqué par
une seule société, ne pouvant vendre p1 qui est aussi fabriqué par s2. Il doit choisir un fabriquant pour
le produit p1. Remarquez que la nature de l’exclusion dépend du temps puisque si le tuple (r1, p2, s2)
est inscrit en premier dans la base, il sera accepté, mais le tuple (r1, p1, s1) ne le sera pas. Cette table

pourra être de nouveau décomposée en faisant intervenir une nouvelle dépendance dite mutuelle et
notée DMUT.

Définition de la dépendance mutuelle (DMUT <~>)

Considérons l’exemple du fournisseur de matériaux à des chantiers. Cet approvisionnement
est représenté par la relation FMC :

FMC : fournisseur materiau chantier

(1) BDS tige Square-Les-Arts 1

BDS poutre Centre-de-Congrès 2

CPR tige Centre-de-Congrès 3

BDS tige Centre-de-Congrès 4

Si BDS fournit des tiges, (voir tuple 1)

et des tiges sont utilisées par le Centre-de-Congrès (voir tuple 3)

et le Centre-de-Congrès est approvionné par BDS (voir tuple 2)

alors BDS doit fournir des tiges au Centre-de-Congrès (voir tuple no 4)

Cela se traduit par la présence obligatoire de ce tuple no4 dès l’instant que les tuples 1, 2 et 3 sont
ajoutés dans la table. Le lien fonctionnel fait entre le fournisseur, le matériau et le chantier ne tient pas
à l’implication logique, mais est imposé par une contrainte inhérente à la réalité modélisée par la table
FMC. On dit alors qu’il y a une dépendance mutuelle (DMUT) entre les attributs fournisseur et les
attributs matériau et chantier. Cette dépendance mutuelle est notée fournisseur <~>
materiau|chantier. Elle doit être vérifiée pour chaque tuple de l’extension de FMC.
Est-ce que la table FMC contenant un seul tuple valide la DMUT fournisseur <~> materiau, chantier ?

FMC : fournisseur materiau chantier

BDS tige Square-Les-Arts 1

Vérifions la DMUT dans la table FMC contenant un seul tuple :

Si BDS fournit des tiges
et des tiges sont utilisées par le chantier Square-Les-Arts
et le Square-Les-Arts est approvisionné par BDS,
alors BDS fournit des tiges au chantier Square-Les-Arts.

Cette conclusion est surprenante, car BDS pourrait fournir le chantier Square-Les-Arts avec autres
choses que des tiges. Or, la conclusion de l’implication correspond au tuple présent dans la table et la
dépendance mutuelle (DMUT ) fournisseur <~> materiau | chantier est valide.

Voici une deuxième extension, obtenue après l’ajout d’un tuple :

FMC : fournisseur materiau chantier
BDS tige Square-Les-Arts 1

BDS poutre Centre-de-Congrès 2

Pour les mêmes raisons que précédemment, la DMUT fournisseur <~> materiau | chantier est toujours
valide. Si dans cette table avec la DMUT il y a ajout du tuple (CPR, tige, Centre-de-Congrès), la DMUT
impose aussi l’ajout d’un autre tuple : (BDS, tige, Centre-de-Congrès). Examinons cet ajout obligatoire
de 2 tuples dans la tabale FMC. Supposons que dans FMC il y a ajout seulement du tuple (CPR, tige,
Centre-Les-Arts).

FMC : fournisseur materiau chantier

BDS tige Square-Les-Arts 1

BDS poutre Centre-de-Congrès 2

+ CPR tige Centre-de-Congrès 3

Est-ce que cette table valide la DMUT fournisseur <~> materiau | chantier?
Si CPR fournit des tiges
et des tiges sont utilisées par le Square-Les-Arts
et le Square-Les-Arts est approvisionné par BDS,
alors CPR fournit des tiges au chantier Square-Les-Arts.

Donc l’extension ci-dessus ne valide pas la DMUT car ce tuple est absent de l’extension. Pour ce faire,
il faudrait ajouter deux tuples.
Ajout du tuple no 4 :
FMC : fournisseur materiau chantier
BDS tige Square-Les-Arts 1

BDS poutre Centre-de-Congrès 2

+ CPR tige Centre-de-Congrès 3

! CPR tige Square-des-Arts 4 "-

Par contre, après l’ajout du tuples no3, s’il y a aussi l’ajout obligatoire du tuple no 4, la DMUT est
respectée. La DMUT est donc valide dans l’extension ci-dessus.

Définition formelle de la DMUT

Soit une relation R(X, Y, Z) avec X ∩ Y = X ∩ Z = Y ∩ Z = ø. Il existe une DMUT dans R si l’implication
logique suivante vérifiée quel que soit le tuple dans R :
Si (x, y, z )∈ r et (x, y’, z’) ∈ r alors
si (y, z’)∈ R[Y, Z] alors <x, y, z’> ∈ r
et si (y’, z) ∈ R[Y, Z] alors (x, y’, z) ∈ r
Si cette ce prédicat est valide, alors il y a une dépendance mutuelle (DMUT) dans R.
Revenons à la table Represente pour illustrer la DMUT.

Represente : rep* pro* soc

r1 p1 s1 1

r1 p2 s1 2

r2 p4 s5 3

r1 p4 s3 4

r2 p4 s3 5

r2 p2 s1 6

Est-ce que la DMUT rep <~> pro|soc est présente dans cette table ?

no1 : r1, p1 (du tuple no 1)

p1, s1 (du tuple no 1
s1, r1 (du tuple no 2)
donc (r1, p1, s1 ) doit être dans la table (voir tuple no 1).

no 2 : (r1, p2) (du tuple no 2)

(p2, s1) (du tuple no 6)
(s1, r1) (du tuple no 2)
donc (r1, p2, s1) doit être dans la table (voir tuple 2).
no 3 : (r2, p4) (du tuple no 3)
(p4, s5) (du tuple no 3)
(s5, r2) (du tuple no 3)
donc (r2, p4, s5) doit être dans la table (voir tuple no 3).
En vérifiant chaque tuple, on conclura que l’extension Represente vérifie la DMUT
rep <~> pro | soc .
La présence de la DMUT rep<~>prod, soc va permettre une 3-décomposition de la relation Represente
(rep, prod, soc) pour donner trois fragments R1, R2 et R3.
R1(rep, prod ) |x| R2(rep, soc) |x| R3(prod, soc)

R: r1, p1, s1 R1 : r1, p1 R2: r1, s1 R3 : p1, s1

r1, p2 s1 r1, p2 r2, s1 p2, s1
r2, p4, s3 = r2, p4 r2, s3 p4, s5
r1, p4, s3 r1, p4 r2, s5 p4, s3
r2, p2, s1 r2, p2 r1, s3
r2, p4, s5

Ainsi, R1 |x| R2 donne une table dont le schéma est (rep, prod, soc) et dont les tuples sont
filtrés par la 3e jointure.
Théorème de décomposition de Nicolas
S’il y a une DMUT X<~> YΖ dans R(X, Y, Z) alors
R(X, Y, Z) = R1(X,Y) |x| R1(X,Z) |x|RF(Y, Z).

En d’autres mots, la relation R peut être décomposée en 3 fragments. Une telle décomposition est sans
perte d’information (CDD) et donne des fragments de relation présentant un minimum de
redondance des données. L’ordre de calcul des jointures est transparent et ne donne pas de perte
d’information dans le résultat final, pour autant que les trois jointures soient toujours effectuées en
série.

Propriétés de la DMUT
Voici quelques propriétés de la dépendance mutuelle :
a) Si X <~> Y alors Y <~>X (symétrie de l’opérateur).
b) X <~> Y|Ζ est triviale dans R(X, Y) lorsque Z = ø, c’est-à-dire sans contexte.
c) Si X ->> Y|Ζ alors X <~> Y|Ζ, mais pas l’inverse, car s’il y a aucune DMV, il peut y avoir une
DMUT.

La DMUT sous-tend, par généralisation, la décomposition de R en k-relations; la dépendance de

jointure *(R1, R2, RF) dont elle est un cas particulier, permet de restreindre à une 3-décomposition :
R = R1 |x| R2 |x| R3.
La DMV génère une 2-décomposition formée avec les déterminés des dépendances multivaluées.

Décomposition sans perte de données

Une DMUT A <~> B|C existe dans une relation R(A, B, C) si R = R1(A, B) |x| R2(A,C) |x| R3(B,C). Les
projections de R sur les attributs des nouvelles relations sont sans perte de données.
Exemple :
La DMUT A <~> B |C est valide dans r.
r: A B C

1 4 2
1 4 8
1 5 8
2 5 8
2 4 8

Les trois projections obtenues à partir de lʹextension r donnent par jointure la relation initiale :

r1 : A B r2 : A C r3 : B C
1 4 1 2 4 2
1 5 1 8 5 8
2 5 2 8 4 8
2 4

La 3e relation est une sorte de filtre pour supprimer les tuples de la jointure ( r1 |x| r2) dont la valeur
de B et C ne sont pas dans l’extension de r3. Si l’attribut est connu comme un déterminant d’une
DMUT, alors le nombre et la nature des jointures de la suite sans perte d’information ne sont pas
quelconque mais prédéterminés :
R1 |x| R2 |x| R3 ou R3 |x| R1 |x| R2

Toute jointure avec une suite partielle de ces fragments de relation génère des informations fausses.
L’intérêt premier de la DMUT consiste à démontrer la possibilité de raffiner encore la décomposition
et a pavé la voie à sa généralisation soit la dépendance de jointure (DJ).

10.10 Dépendance de jointure (DJ)

La DJ est une autre façon de spécifier le fait qu’une relation qui ne peut pas être décomposée en deux
relations sans perte d’information, pourrait cependant l’être en trois ou en k relations de degré
moindre et cela sans aucune perte (CDD). Cette décomposition est possible au moyen dʹune contrainte
symétrique du genre de la DMUT.

Soit R(A1, A2 ... An) et {R1, R2, ... Rk}, une k-décomposition de R, telle que R = (R1 |x| R2 |x| ... Rk).
Une DJ notée *(R1, R2 ... Rk) est donc une façon de définir parmi toutes les relations possibles
(obtenues par des projections) l’ensemble des relations « légales » ou valides obtenues sans perte
d’information par rapport à R. La DJ définit donc une jointure complète.

Si R = ∪i Ri pour i = 1, k alors l’extension r(R) vérifie *(R1, R2, ... Rk) ssi R = R1 |x| R2 |x| ... Rk
Par exemple, pour i = 2 alors *(R1, R2) est une DJ si R1 ∩ R2 ->> R1 ou R1 ∩ R2 -->> R2 . Cette DJ est
en fait un cas particulier de DMV.
Exemple : R(X, Y, Z) = R1(X, Y) |x| R2 (X, Z), une 2-décomposition de R. La DJ *(R1, R2) est valide si

et seulement si X -->> Y|Ζ est dans R.

DJ sans DMV dans une relation

Voici un exemple qui illustre ce cas où une DJ ne sous-tend pas une DMV : R(A, B, C) sans DF et DMV
non triviales. Est-ce qu’une DJ est présente dans R ? Par exemple, est-ce que la DJ *{(A, B), (A, C), (B,
C)} est validée ?

La décomposition est possible et cela sans perte d’information, en raison de la présence d’une
dépendance de jointure (DJ).
(relation initiale)

R (A,B, C) R1 (A, B) R2 (A, C) R3 (B, C*)

a1 b1 c2 a1 b1 a1 c2 b1 c2
a2 b1 c1 a2 b1 a2 c1 b1 c1
a1 b2 c2 a1 b2 a1 c1 b2 c2
a1 b1 c1

Cette 3-décomposition diminue la redondance dans l’extension initiale r. Toutefois, la jointure de R1

et R2 ne donne pas lʹextension initiale, même si le schéma est (A, B, C). Des tuples faux apparaissent et
qui devront être filtrés par une jointure avec R3.
R1 |x| R2 |x| R3
a1 b1 c2 a1 b1 c2
a1 b1 c1 a1 b1 c1
a2 b1 c1 a2 b1 c1
a1 b2 c2 a1 b2 c2
a1 b2 c1

Dans ce cas, k = 3, il y a une DJ qui justifie la 3-décomposition. Donc R(A, B, C) = R1(A, B) |x| R2(A,C)
|x| R3(B,C).

Dépendance de clé
Cette dépendance de clé existe lorsque R(A, B, C, D) avec A − > B, C, D et B −> A, C, D (clés), i.e. ∀ les
dépendances ont une clé comme déterminant: DF et DMUT avec A <~> D | C et DJ avec *{AB, AD,
BC}. Cette décomposition donne des relations normales non décomposables. C’est en quelque sorte la
forme canonique de la BD.
Ordre de jointure des relations dʹune DJ
Dans une DJ, lʹordre de jointure des fragments nʹa pas dʹimportance, dans la mesure où ils
interviennent tous dans le calcul.
Suite de jointures no 1 :
R[A, B] |x| R[A, D] |x| R[B, C] = R(A, B, C, D)

R1(A, B, D) |x|... avec A -> B

R2(A, B, C, D) et F = {A −> D; A-> B; A −>D; A −> C
Suite de jointures no 2 :
R[AB] |x| R[BC] |x| R[AD] = R(A, B, C, D)

Généralisation de DMUT
La DJ est une généralisation des diverses dépendances DMV, DMUT et des autres dépendances
supérieures. Or, une k-décomposition est différente selon la valeur de k.
k = 2 alors dépendance de jointure ==> présence de DMV
k = 3 alors dépendance de jointure ==> présence de DMUT
...
k= k dépendance de jointure ==> présence d’une dépendance d’ordre supérieur.

Forme normale FN5

Une relation R est en FN5 ou en FNPJ en regard de D, c’est-à-dire de l’ensemble des DF, DMV et DJ, si
elle n’a pas de DJ ou si, pour toutes les dépendances ∈ D+ de R de la forme *(R1, ... Rk) avec R = ∪i Ri
avec (i =1, k), une des conditions suivantes est vérifiée :

a) *(R1, ...Rk) est une DJ triviale, c’est-à-dire quʹil y a un Ri égale à R ou

b) chaque Ri de la DJ est une superclé de R ou
c) la relation R est en FN4 et sʹil n’y a pas de DJ.

Dans le cas affirmatif, la relation initiale R demeure inchangée et elle est en FN5.

Dépendance de jointure triviale dans R(A1 ... An)

Une Dj *(R1, ...Rm) est dite triviale si elle est toujours valide, c’est-à-dire quʹau moins un Ri correspond
au schéma de la relation R.
Exemple :
R(A, B, C, D) et *(ABCD, AB, AD, CD) est triviale, car un des composants de la DJ est elle-même la
relation R.

Test de DJ dans R (A1, A2, ... An) par les tableaux

La recherche des DJ est difficile et longue; celle-ci permet de faire éclater une relation en fragments
sans perte d’information. Par contre, si un éclatement est énoncé, il est plus facile de vérifier si ce
dernier est légal, c’est-à-dire de savoir s’il correspond à ceux dʹune dépendance de jointure. Pour ce
faire, il existe un algorithme qui applique une technique fondée sur les tableaux pour confirmer ou
infirmer une DJ présumée.
Algorithme
1) Construction d’un tableau TDJ avec n colonnes, k lignes de bij pour R(A1, ... An). La DJ étant
*(R1, .., Rk) où chaque Ri correspond à un sous-ensemble du schéma de R, Ri ⊆ R et ∪i Ri = R .

TDJ : A1 A2 A3 ... An
R1 b11 b12 b13 ... b1n
R2 b21 b22 b23 ... b2n

Rk bk1 bk2 bk3 ... bkn

2) Les variables marquées sont par bi,j qui identifient initialement les cellules. Elles sont modifiées par
la suite de la façon suivante :

a- Pour chaque ligne Ri, chaque bij est remplacé par un marqueur aj (colonne) si Aj ∈ Ri pour chaque j
de 1 à n, sinon bij demeure inchangé ;

b- Pour chaque dépendance de F associée à R, Y −> A où Y ⊆ {A1, ..., An} et A∈{A1, ..., An}, si Ri[Y] =
Rj[Y] alors les symboles de Ri[A] = v1 et de Rj[A] = v2. Ces symboles sont par la suite traités de la
façon suivante :

• si l’un des deux symboles v1 ou v2 est une variable marquée alors le symbole est remplacé
par l’autre qui est un marqueur ;
ou
• Si v1 et v2 sont deux variables marquées, alors elles sont remplacées par la variable marquée
ayant l’indice de ligne le plus petit.

3) dès qu’une ligne est formée seulement avec des marqueurs, alors la dépendance de jointure DJ est
vérifiée.
La décomposition de R devient donc possible sans perte d’information.
Exemple :
R(A, B, C, D, E, F) et F= {A-> B; F-> E} et la DJ suivante à vérifier :
D : *((A, B, D, E), (A, C, D, F)), (B, C, E, F))
T
DJ : A1 A2 A3 A4 A5 A6
A B C D E F
R1 : ABDE a1 a2 b13 a4 a5 b16
R2 : ACDF a1 b22 a3 a4 b25 a6
R3 : BCEF b31 a2 a3 b34 a5 a6

Avec A-> B
A B C D E F
R1 a1 a2 b13 a4 a5 b16
R2 a1 a2 a3 a4 b25 a6
R3 b31 a2 a3 b34 a5 a6
Avec F−> E
A B C D E F
R1 a1 a2 b13 a4 a5 b16
R2 a1 a2 a3 a4 a5 a6
R3** b31 a2 a3 b4 a5 a6

Lʹavant-dernière ligne est composée que de marqueurs. Cela indique que la DJ (hypothèse) est
vérifiée. De plus, comme aucun fragment Ri correspond à une superclé de R (la clé étant composée de
tous les attributs), cette relation R nʹest pas en FN5 et devra être décomposée conformément à la DJ
testée et vérifiée.

Exemple :
R(A, B, C, D) avec F= {A −> B, C, D; B −>A, C, D}. Est-ce que la DJ *((A, B), (A, D), (B, C)) est vérifiée
dans R ?
A B C D
R1(A, B) a1 a2 b13 b14
R2(A, D) a1 b22 a23 a4
R3(B, C) b11 a2 a3 b34

A -> B, C, D
(A, B) a1 a2 b13 a4
(A, D) a1 a2 b13 a4
(B, C) b11 a2 a3 b34

B -> A, C, D
A, B a1 a2 a3 a4 <---
A, D a1 a2 a3 a4
B, C a1 a2 a3 a4

Après le traitement de toutes les dépendances, la 1re ligne satisfait le test et donc la DJ en hypothèse
est vérifiée et la décomposition validée. La DJ affirme que lors de manipulations avec les relations, par

exemple par des projections, toute relation intermédiaire n’est pas valide sans risquer d’engendrer
une incohérence sémantique lors de jointures impliquant les projections.

En identifiant une DJ dans R, cela permet de morceler la relation R immédiatement en fragments et

d’autoriser la jointure de certaines projections, malgré le fait que la condition de Delobel et Casey
(Heath) ne soit pas vérifiée. On peut donc obtenir seulement par certaines jointures, l’extension initiale
sans perte d’information. Bien entendu, toute jointure impliquant un fragment devra être poursuivie
pour y inclure tous les fragments identifiés dans la DJ. En d’autres mots, une DJ dans une relation
indique que ce schéma de relation ne peut pas être fragmenté de n’importe quelle façon sans risquer
de perdre des informations.

Voici un exemple d’incohérence dans une relation. Soit la relation R(A*, B*, C, D) avec la clé {A, B} de
ce schéma.
A* B* C D
1 1 1 1
2 1 2 2
2 2 3 3
3 2 3 4
4 3 4 4

Cette relation est en FNBC, mais elle a des anomalies résiduelles associées à la redondance. Supposons
qu’au cours de manipulations sur la BD il y ait projection de R en trois relations intermédiaires
(éventuellement des vues) : R1(A, B, C), R2(B, D) et R3 (A, D).

R1 A* B* C R2 B* D* R3 A* D*
1 1 1 1 1 1 1
2 1 2 1 2 2 2
2 2 3 2 3 2 3
3 2 3 2 4 3 4
4 3 4 3 4 4 4

Qu’arrive-t-il avec une jointure de R1 avec R2 faite à travers deux vues relationnelles ? Est-ce que le
résultat dont le schéma est identique à celui de la relation originale est correct ? Est-ce que l’extension
initiale est retrouvée ? Est-ce que la jointure est complète ?

R12: A B C D
1 1 1 1
2 1 2 1 *
1 1 1 2 *
2 1 2 2
2 2 3 3

3 2 3 3 *
4 3 4 4
2 2 3 4 *
3 2 3 4

Il y a effectivement cohérence par 2 et la jointure est complète par 3. Toutefois, le schéma est cyclique
et, donc la base serait incohérente en lʹabsence dʹune dépendance de jointure (DJ). Le résultat de R12 a
le schéma de la relation initiale et pourrait laisser croire à un utilisateur que son extension représente
toute l’information correspondante dans la BD. Or, la jointure R12 donne une extension incluant de
mauvais tuples (*) et cette fausse information sera produite si une troisième jointure n’est pas
effectuée afin d’agir comme un filtre. Les tuples marqués par * ne sont pas valides dans l’extension
initiale et tout affichage de ce résultat pourrait fournir une information fausse aux utilisateurs. La
raison de cette incohérence repose sur la dépendance de jointure (DJ) présente dans R et, qui permet la
division de la relation en trois fragments et cela, sans perte d’information (CDD). Ces trois relations
sont alors essentielles dans la jointure complète afin de retrouver l’extension initiale.

Toute jointure partielle fournit un bon schéma mais avec une extension erronée. Toutefois, la même
relation peut être décomposée, au regard de la clé, de la façon suivante : *(ABC, ABD), car les DF: A, B
--> C; et A, B --> D sont vérifiées dans R. Dans ce cas particulier, la DJ correspond à une
décomposition en deux relations sans perte d’informations, puisque la condition de décomposition
sans perte dʹinformation est vérifiée.

Anomalie résultant de jointures interdites

Voici une relation Consultation représentant les informations concernant les consultations médicales.
La base de données comprend trois vues définies et autorisées par le DBA: VR1, VR2 et VR3. Les
applications utilisent les vues sans restriction. Une de ces vues est une projection de Consultation
nʹinclut pas une clé candidate. Le système ne peut pas contrôler l’usage des vues autrement que d’en
permettre ou en interdire l’usage par les concepteurs. Une fois que les vues sont autorisées, le
concepteur peut les exploiter à sa guise pour répondre aux besoins de son application et le contrôle du
DBA est inefficace à ce stade.

Consultation noCons* pathologie* traitementPrimaire resultat

C P T O
100 bronchite pénicilline ++
200 bronchite antibiotique --
200 ACV héparine -
300 ACV héparine +
400 infarctus héparine +

Les seules DF sont celles sous-tendues par la clé {noCons, pathologie}. Pour répondre à des besoins
particuliers, les trois vues sont créées par des projections et cela seulement pour des fins
d’affichage.

VR1 : noCons* pathologie* traitementPrimaire

C P T
100 bronchite pénicilline
200 bronchite antibiotique
200 ACV héparine
300 ACV héparine
400 infarctus héparine

Cette division de la relation initiale Consultation se fait sans perte d’information et elle correspond
dans ce cas-ci, aux fragments obtenus suite à la division de la relation et cela grâce à la dépendance de
jointure. La cohérence par 2 est vérifiée pour cette base de données.
VR2 : pathologie* resultat*
P O
bronchite ++
bronchite --
ACV -
infarctus +
ACV +

VR3 : noCons* resultat*

C O
100 ++
200 --
300 +
400 +
200 -

Supposons que les jointures ci-dessous soient effectuées en cours d’exploitation afin de répondre à des
questions précises. Pour ce faire une application peut exploiter des vues existantes ou en définir. Par
exemple, la première jointure ne vérifie pas la condition nécessaire pour avoir une opération sans
perte d’information.
VR1 |x| VR2 noCons* pathologie* traitementPrimaire* resultat*
C P T O
100 bronchite pénicilline ++
200 bronchite antibiotique ++
100 bronchite pénicilline --
200 bronchite antibiotique --
200 ACV héparine -
300 ACV héparine -
400 infarctus héparine +
200 ACV héparine +
300 ACV héparine +
En dépit de la cohérence par 2, cette jointure (VR1 |x| VR2) est trompeuse même si le schéma
correspond à celui de la jointure complète; elle donne une extension avec quelques résultats faux.

Toutefois, comme ces deux relations sont parmi celles incluses dans une dépendance de jointure, il
suffira de faire une 3e jointure avec VR3 pour retrouver l’extension intégrale. Ainsi, avec une sélection
des pathologies d’origine bronchique traitée à la pénicilline, le résultat affiché apparaît contradictoire,
tandis que la réalité représentées par les données ne reflète pas cette situation.

SELECT P, O FROM VR1, VR2

WHERE VR1.P= VR2.P and
P =‘bronchite’ and T = 'pénicilline'

Résultat de la requête :

pathologie* résultat*
P O
bronchite ++ ** contradiction
bronchite -- **

Résultat surprenant qui est la manifestation dʹun cas anormal dans le design dʹun schéma. Que peut-
on conclure d’une telle réponse ?

Imaginez l’impact d’un tel résultat dans un autre contexte, soit celui du contrôle aérien. Une telle
réponse à la requête pour connaître la position de l’un des avions sous son contrôle qui est dans sa
phase finale d’atterrissage ! Le système pourrait lui signaler que l’avion est en descente finale, mais
tout en étant absent de lʹécran radar! La contradiction pourrait être lourde de conséquence.

Explication de lʹanomalie
Ce résultat surprenant découle du fait que la relation Consultation nʹa pas une dépendance de jointure
non triviale du type *((C, P, T); (P, O); (C, O)) et que, dans pareil cas, toute jointure de ces projections
ne fournit pas lʹextension de la relation dʹorigine, Consultation. Ainsi, toute exploitation des jointures
intermédiaires en mode recherche peut fournir des faussetés! En effet, ces faits faux résultent de
lʹabsence de la clé dans le schéma de chaque fragment. Or, ces fragments peuvent correspondre à des
vues autorisées à des moments différents par le DBA. En joignant seulement deux schémas, il est
possible dʹobtenir celui de la réponse recherchée mais son extension est fausse.

Une solution théorique à cette anomalie consiste donc à vérifier si les fragments qui résultent des
projections sont admissibles en vérifiant la présence d’une dépendance de jointure. Ainsi, si cette
dépendance de jointure est vérifiée, alors les vues relationnelles obtenues par décomposition pourront
être utilisées dans un calcul que si tous les fragments de la DJ interviennent dans celui-là. Une autre
solution consiste à interdire la création des vues et à autoriser (pour un SELECT avec jointure) que
celles préalablement définies dans le dictionnaire du système. Cʹest une solution contraignante, car le
DBA peut interdire aux utilisateurs la création ou lʹutilisation des vues, mais ne peut pas contrôler la
dépendance entre les vues autorisées. Dans une telle situation, le DBA verra à ce que la relation

Consultation ne soit décomposée et à ne pas autoriser les vues formées par ces fragments de la DJ. Le
DBA pourrait autoriser que les vues dans lesquelles une superclé de la relation R se retrouve dans la
définition de la vue. Il faut aussi remarquer que le schéma d’origine comporte une clé complexe qui
est la source des anomalies observées.

Test de la DJ *(C,P,T; P,O; C,O) avec des tableaux

Le tableau ne présentant pas deux lignes identiques, la DJ présumée n’existe pas et la décomposition
testée n’est pas valide (donc les vues correspondantes ne devraient pas être autorisées par le DBA).
Comment interdire à un utilisateur de faire ces vues ou le forcer à utiliser un filtre chaque fois qu’il
exploite une combinaison des vues ? Pour le moment il n’y a pas de solution facile à ce problème,
sinon celle de bien contrôler la validation des vues et d’informer les concepteurs.

Dépendance de clé dans une DJ

Lorsque dans une dépendance de jointure, tous les attributs de jointure sont des superclés, on a une
DJ de clé. Cette décomposition fournit donc des relations dont la jointure correspond à la relation
initiale que si les trois fragments sont impliqués dans lʹopération. Le problème observé précédemment
est alors évité.
Exemple :
Soit DF, A--> B, C, D et B-->A, C, D dans R(A, B, C, D) DJ : ((A, B), (A*, D), (B*, C)).
Pour obtenir le schéma initial, il faut forcément faire la jointure des trois projections de la DJ. Donc
R(A, B, C, D) = R1(A, B) |x| R2(A, D) |x| R3(B, C)

Dans cette relation, A et B sont deux clés de R. La relation R(A, B, C, D) est donc en FN5, car elle
satisfait lʹune des conditions de cette forme normale.

10.11 Condition suffisante pour avoir une relation en FN5

17
Il a été démontré en 1992 par Date et Fagin que tout schéma de relation en FN3 dont toutes les clés
sont de type atomiques est un schéma en FN5. En formulant ainsi la FN5, tout concepteur peut obtenir
facilement un schéma normalisé dans cette forme en imposant, au besoin, un identifiant ou en
vérifiant que toutes les clés du schéma de la BD sont simples. Cette condition est suffisante mais pas
nécessaire, car il y a des relations avec une clé composée qui sont aussi en FN5. Toutefois, cette
condition ne peut être vérifiée que pour les relations de base, mais ne règle pas le cas des relations
temporaires formées en cours de calcul ou pour une vue concrète ou dite matérialisée.

Sommaire
La théorie de la normalisation souligne l’importance du processus de validation des schémas pour
appuyer la cohérence et la justesse du contenu de la base de données. Ce travail de validation permet
d’éviter les anomalies bien connues et de réduire la redondance aux seules clés primaires et
étrangères. La formulation des schémas en FN3 est la forme minimale recommandée pour
l’implantation d’une base de données. Tout concepteur doit être en mesure de vérifier la normalité des
tables exploitées par les applications.
Les travaux sur cette question de normalisation sont très nombreux et ont permis de décrire les
problématiques soulevées par les dépendances fonctionnelles, multivaluées, de jointure et d’inclusion.
Bien que la question de la normalisation ne soit plus nouvelle, le DBA doit en connaître les bases et les

résultats pratiques notamment pour les trois premières formes normales. Au besoin, les algorithmes
de transformation des relations doivent être appliqués pour normaliser les schémas.
La recherche des formes FN4 et FN5 est un peu plus complexe, car les dépendances sous-jacentes sont
moins évidentes. Pour certaines BD spéciales dont les clés sont composées, les formes supérieures
s’imposent pour éviter des anomalies rares, mais bien réelles. Les algorithmes de recherche des DJ et
DMV facilitent la tâche à l’administrateur de la BD qui doit voir à la cohérence des schémas, mais
aussi à celle des données. En imposant des identifiants aux relations, il devient possible dʹavoir
facilement un schéma en FN5.

Exercices

Série A (Certaines questions sont reprises du chapitre 4)

1- Démontrez que {B, C--> D, E; A --> B; A, E, G --> H} |- A, C --> D, E. En d’autres mots, il faut dériver
la DF A,C-->D des trois dépendances qui composent F.

2- Démontrez que {B, C --> D, E; A --> B; A, E, G --> H}|- A, C --> A, B, C, D, E.

3- Est-ce que F= {A, B --> C; C --> A; C --> B; A, B, D --> E} est un ensemble redondant ? Il faut trouver
une DF qui enlevée de F ne change pas sa fermeture.

4- Trouvez toutes les clés de R(A, B, C, D) dont le F = {A, B -->C; D -->A; C -> D}. Il faut donc trouver
un ensemble d’attributs dont la fermeture donne le schéma de R.

5- Soit F = {E --> G; B, G, E-->D, H; A, B --> B; G --> D, E}. Vérifiez si les DF ci-dessous sont une
conséquence logique de F :
a) A, B, G --> E b) B, G --> D, B, E c) E --> D.

6- Trouvez une clé pour la relation R (A, B, C, D, E, G, H, I) avec lʹensemble F suivant : {E --> G, I; B, G,
E -->D, H; A, B --> B; G --> D, E}. A noter que le processus de recherche est plus long si la question est
de trouver toutes les clés de R. Il faut trouver un ensemble d’attributs X --> A, B, C, D, E, G, H, I . Pour
ce faire vous pouvez partir avec une DF et tenter d’enrichir le déterminant en utilisant les propriétés
des DF.

7- Trouver les superclés de V(G, H, J, K) dont le F ={G, H --> J; H, J --> K; J, K-->G; G, K --> H}
8- Démontrez par un exemple de relation concrète que les propositions suivantes sont fausses:
a) Si A --> B alors B --> A; b) Si A, B --> C et A --> C alors B --> C;

9- En supposant que le schéma de R soit variable: R (A1, A2, A3, A4, ...An), trouvez en fonction de n,
le nombre de superclés possibles pour R dans les conditions suivantes :
a) La seule clé de R est A1
b) Les seules clés de R sont A1 et A2.
10- Un ensemble dʹattributs X est dit fermé par rapport à F si X+ = X. Avec la relation R(A, B, C) et un
ensemble F indéterminé de DF. Quelles sont les DF de F non triviales si tous les ensembles possibles
avec les quatre attributs de R sont fermés.

Exercices sur les formes normales et les dépendances

Série B (Certaines questions sont reprises du chapitre 4)

Dans les exercices ci-dessous, le contexte et la sémantique sont sous-entendus par les dépendances
fonctionnelles explicites (celles regroupées dans F) et implicites lorsque la clé de la relation est
identifiée. Les autres dépendances, non explicitement énoncées sont réputées absentes, sauf indication
contraire.

Rappel: Une clé de relation est un ensemble minimal dʹattributs qui détermine tous les attributs de la
relation dans laquelle cet ensemble agit comme une clé. Cʹest une autre façon dʹénoncer implicitement
certaines dépendances relatives à une clé.

1- Soit R (A, B, C, D) avec F = {A --> B; A --> C; A --> D}. Démontrez que lʹattribut A est une clé
candidate ?
Réponse : À partir des DF connues et par la propriété de réflexivité : A -> B; A -> D; A -> C, et A ->A
donc A est une clé. Une autre façon est de calculer la fermeture de l’attribut A. A+ = (A, B, C, D), soit
le schéma de la relation. A est donc une clé.
2- Soit R (A, B, C, D) F: {A --> B, A --> C, A --> D} Est-ce que R est en F N 3 ?
Réponse : Oui, car la clé A est transitivité et R est en FN2 et en FN3 puisque tous les attributs non
primaires dépendent que de la clé.

3- Soit la relation Production (noProd*, nomClient, dateLivraison, prix) avec F = {noProd -->
nomClient, noProd --> dateLivraison, prix}. Trouvez une clé et une superclé pour la relation
Production.
Réponse : La clé est noProd, car selon le F, il détermine tous les attributs.
La superclé: est (noProd, date) et dʹautres superclés obtenues par lʹajout dʹun attribut quelconque à la
clé.

4- Soit R (A, B) avec F = { A --> B; B --> A}. Est-ce que A et B sont des clés ?

Réponse : A --> B et A --> A (réflexivité), donc A est une clé, car il détermine tous les attributs de R. De
plus, B --> A et B -->B donc B est aussi une clé. Il y a donc deux clés candidates qui sont équivalentes
parce que ce sont les mêmes attributs qui sont en cause.

5- Est-ce que R (A, B) avec F = { A --> B; B --> A} en FNBC?

Réponse : Si A --> B et B --> A sont les clés, donc B et A sont primaires et équivalentes; tous les
attributs ne dépendent alors que de clés (primaire ou candidate). Elle est donc en FNBC.

6- Soit R (A, B, C) avec F = { A --> B; B --> C; C --> A}. Est-ce que R est en FN2 ?
Réponse :
Les clés candidates sont A, B et C. Donc aucun attribut non primaire. Donc la relation est en FN2.

7- Soit la relation Elections pour représenter les résultats des élections de la dernière décennie:
Elections (date*, region*, depute, premierMin) avec F= { date --> premierMin + les DF de la clé} et
region -/-> depute; depute -/-> premierMin; region -/-> premierMin; premierMin -/-> depute. N.B.
le -/-> est la négation de la dépendance fonctionnelle. Est-ce que cette relation est en FNBC? Justifiez
votre réponse.
Réponse : Comme la clé est composée, les attributs non primaires sont depute et premierMin. Avec la
DF date --> premierMin, la relation nʹest pas en FN3 et donc pas en FNBC.

8- Soit R (A, B, C) avec F= { A, B --> C; C --> A}. Est-ce que (A, B) est une clé ?
Réponse : De F, on a que A, B --> C et par réflexivité , A, B --> A et A, B --> B donc (A, B) est une clé.

9- Est-ce que R (A, B, C) avec F = {A, B --> C; C --> A} est en FN3 ?

Réponse : Pour être en FN3, il faut que le seul attribut non primaire C dépende que de la clé. Cʹest le
cas selon le F donné.

10- Est-ce que la relation R (A, B, C) avec F = { AB --> C; C --> A} est en FNBC?
11- R (A, B, C) avec F = { C --> A}. Est-ce que R est en FN3 ?
Réponse : La clé est {A, B, C} en raison des DF réflexives suivantes: A, B, C -> A; A, B , C -> B; A, B, C
-> C. Comme il nʹy a aucun attribut non primaire, R est en FN3.

12- Est-ce que R (A, B, C) avec F = { C -> A} est en FNBC ? La clé est (A, B, C).
Réponse : Non, car la DF C -> A avec l’attribut A qui est primaire dépend de C lequel nʹest pas une
clé.

13- Soit une relation J pour représenter la naissance des jumeaux : J (nas1, nas2, date) avec F = { nas1 ->

nas2; nas2-> nas1; nas1 ->date}. Est-ce que la relation J est en FNBC ?
Réponse : Les clés candidates sont nas1 et nas2. La clé de choisie sera nas1. Les attributs
primaires,nas1 et nas2 et l’attribut non primaire date sont en dépendance fonctionnelle que sur des
clés. La relation J est donc en NBC.

14- Soit R (A, B, C, D) avec F = { A --> B; C --> D}. Si R est en FN3, la clé est-elle {A, B, C} ?
Réponse : Si la clé est {A, B, C}, alors le seul attribut non primaire est D qui doit dépendre que de la
clé. Or, C --> D, est une DF qui contredit lʹhypothèse. Donc, la clé nʹest pas {A, B, C}.

15- Soit R (A, B, C ) avec F = { A, B --> C; A, C --> B; B, C --> A}. Est-ce que A est une clé candidate ?
Quelle est la plus grande forme normale de R ?
Réponse : L’attribut A ne peut être une clé candidate, car la DF A->B,C n’est pas dans la fermeture de
F. Les clés candidates sont celles données dans F. Donc la relation R est en FNBC.

16- Soit R (A, B , C ) avec F = { A, B --> C; B--> C}. Est-ce que R est en FN3 ?
Réponse : La clé de R est A,B et le seul attribut non primaire est C. Puisque B -> C, il faut en conclure
que R n’est pas en FN2, et donc pas en FN3.

17- Soit R (A, B, C ) avec F ={ A, B --> C; A, C --> B}. Est-ce que A, B, C est une superclé ?
Réponse : De F, on a que (A, B) est une clé et donc que (A, B, C) est une superclé puisque cet
ensemble contient une clé.

18- Un jeu du type cognitif pour les enfants consiste à insérer dans les trous dʹune plaquette, des
pièces en forme de cercle et dont les surfaces et les textures sont celles illustrées ci-dessous. Il y a donc
autant de trous que de pièces.

2
3

5
1
6
4
Les pièces
La plaquette

Afin de représenter les placements possibles pour chaque pièce, on utilise la relation
PlacementPiece(rayon, texture, position) avec F = { position -> rayon; les DF de la clé}.
Servez-vous des informations obtenues en observant la plaquette du jeu qui donnent indirectement les
placements possibles au regard du rayon des trous et des pièces. Est-ce que cette relation
PlacementPiece est en FN3 ?

Réponse : La clé de cette relation est composée des attributs {texture, position}. En effet, en observant
bien les contraintes physiques imposées par la plaquette et les caractéristiques des pièces, un
placement pour une pièce est complètement déterminé par sa position et sa texture. La clé est donc
{texture, position}. L’attribut texture est nécessaire dans la composition de la clé, puisquʹil y a deux
pièces de même surface qui peuvent être placées dans deux positions différentes. Le seul attribut non
primaire est le rayon. La dépendance {texture, position} --> rayon définit la clé et texture -/-> rayon ;
position --> rayon. La relation Placement n’est pas en FN3, car l’attribut non primaire rayon dépend
de l’attribut position qui n’est pas une clé.. Est-elle en FNBC ? Non, car elle n’est pas en FN3.

19- Soit R (A, B, C ) avec F = {A, B --> C; A, C --> B}. Est-ce que A, C est une clé candidate ?
Réponse : De F, on a A, C --> B. Par réflexivité, on a que les DF A, C -> A et A, C -> C. Donc la paire
{A, C} est une clé candidate.

20- Si R(A*, B*, C) en FN3, est-ce que B dépend que dʹune clé ?
Réponse : Par définition de la FN3, R ne contient aucun attribut non primaire en dépendance sur
autre chose qu’une clé. Par conséquent, A, B -> B et aucune autre DF avec B, car R ne serait pas en
FN3.

21- Est-ce que la relation R(A*, B, C) est en FNBC si F = {A, B -> C; A,C -> B ; A-> B, C}.
Réponse : Non, car A, B -> C où C est non primaire et dépend de (A, C) qui n’est pas clé.

22- Soit R (A, B, C, D) avec F = { A, B, C -> A; A, C -> B; B, C -> D ; B->C}. Est-ce que (A, B, C) est une
superclé ? Quelle est la plus grande forme normale de R?
Réponse : Selon F, (A, C) est une clé. En effet, A, C -> B et A, C-> D obtenue pseudo-transitivité et A,C
-> A et A,C -> C par réflexivité. Donc (A, B, C) contient la clé et de ce fait est une superclé. La relation
R n’est pas en FNBC, car l’attribut primaire C est déterminé par B qui n’est pas une clé.

23- Soit R (A) avec F = {A->A }. Est-ce que cette relation est en FNBC ?
Réponse : Oui, car le seul attribut primaire dépend que de la clé A. Elle est en FN3, puisqu’il n’y a pas
d’attributs non primaires.

24- R (A, B, C, D) avec F = { A --> B}. Est-ce que A est une clé?
Réponse : Non, car si A --> B, on a que A-> C et que la DF A -> D n’appartiennent pas à la fermeture
F+.

25- Soit R (A, B, C, D) avec F = { A --> B}. Est-ce que {A, C, D} est une superclé ?
Réponse : Si {A, C, D} est une clé, toutes les DF suivantes doivent exister dans F ou être dérivables :
C, D ->B; A, C, D-> C; A, C, D--> A; A, C, D-> D. Comme ce nʹest pas le cas pour le F donné, il faut en
conclure que A, C, D nʹest pas une superclé.

26- Soit R (A, B, C, D*), est-elle en FN3 ?

Réponse : Le seul attribut non primaire est B et de la clé on a que A, C, D --> [Link] est donc en FN3
puisque le seul attribut non primaire ne dépend que de la clé.
27- R (A, B, C, D) avec F = { (A -> B, C ; C -> D) }. Quelles sont les clés parmi les ensembles d’attributs
suivants :
-Est-ce que A est une clé ?
Réponse : De F on a : A -> B; A -> C; par réflexivité : A --> A et par transitivité, on a que A --> D. Donc,
A détermine tous les attributs de R, il est donc une clé.

27.1 Est-ce que {B, C} est une clé ?

Réponse : Si oui, les DF suivantes doivent être présentes dans F+.
B, C -->B, réflexive ; B, C --> C, réflexive (2)
B, C --> D ? de F, on a que C --> D dans F, donc B, C --> D par transitivité avec (2);
B, C --> A ? Non, car elle ne peut pas être dérivée et donc n’est pas dans F+.
En effet, BC+ = {B,C, D}. Par conséquent, B, C -/-> A.

27.2 Est-ce que C est une clé de R ? Si oui, alors C-> C->A ; C-> B ∈ F+
Réponse : C --> C réflexive;
C --> A est impossible à dériver;
C --> B
C --> D dans F
Donc C ne peut pas être une clé de R.

27.3 Est-ce que {A, B, C} est une clé ?

Réponse : Si oui, les DF suivantes sont dérivables :
A, B, C --> A, réflexive;
A, B, C --> B. réflexive;
A, B, C --> C, réflexive;
A, B, C --> D, par augmentation de C --> D;

27.4 Est-ce que {A, B, C} est minimal ?

Réponse : Non, car A --> A, B, C, D. Donc {A, B, C} est une superclé, mais pas une clé.

28- Soit R (A, B, C) avec F = { A --> B; B --> C; C --> A}. Est-ce que R est en FN3 ?
Réponse : Tous les attributs sont primaires par F ou par dérivation. Donc aucun attribut non primaire
n’est en dépendance fonctionnelle sur une clé R est en FN3.

29- Soit la relation Usine (nom, region, equipement) avec F = {nom , region --> equipement;
equipement --> nom}. Est-ce que la relation Usine est en FN3 ?
Réponse : De F, on peut conclure que la clé est {nom, region}. Le seul attribut primaire ne dépend que
de la clé. Donc, elle est en FN3.

30- Soit la relation Usine (nomUs, regionUs, equipement, capital) avec les dépendances F = {nomUs ,
regionUs --> equipement, capital; equipement --> nomUs} . Est-ce que la relation Usine est en FNBC ?
Réponse : La clé est {nom, regionUs} et il y a un attribut primaire, soit nomUs qui dépend de
equipement lequel nʹest pas une clé. Donc R nʹest pas en FNBC.

31- Soit R (A, B, C) avec F = { A, B, C -> A; A, B, C -> B; A, B, C -> C}. Est-ce que {A, B} est une superclé
?
Réponse : Si {A, B} est une superclé, il faut que A ou B ou A, B soit une clé. Or, comme A, B -/-> C, et
A, B -/-> B et A, B -/-> A, alors il faut en conclure que A, B nʹest pas une clé (infirmation de la
dépendance fonctionnelle).

32- Est-ce que C est une clé candidate dans la relation R (A, B, C) avec lʹensemble F suivant : {AB->
C; C -> A} ?
Réponse : Non, car si C -> C par réflexivité, la DF C -> B est impossible à dériver à partir de F.

33. Soit la relation Marketing pour représenter les test de commercialisation effectués dans différentes
régions du Québec et à diverses périodes de lʹannée.
Marketing (produit*, region*, mois*, prix, score)

Les DF sont regroupées dans F = {produit, region, mois -> prix, score; produit --> prix}. Est-ce que
cette relation est en FN3 ?

Réponse : Non, puisquʹun attribut non primaire, soit prix, dépend de l’attribut produit qui nʹest pas
une clé. Est-elle en FNBC? Non, puisquʹelle nʹest pas en FN3.

34- Soit R (A, B, C, D) avec F = {A -> B; B -> C; C -> D}. Est-ce que A --> D ?
Réponse : De F, on a que A --> B; B --> C; par transitivité, on obtient la DF A --> C; et C --> D; alors A
--> D (par transitivité).

35- Soit R (A, B, C) avec F = { A --> B; B --> C; C --> A}. Est-ce que A est la seule clé candidate dans R ?
Réponse : De F, on a les DF suivantes dans F = {A --> B; B --> C}, donc par transitivité on obtient que A
--> C; B --> A; A--> A; et B --> B; donc B est aussi une clé candidate.
*** Quelques exercices non résolus***

36- En supposant que lʹextension ci-dessous soit représentative de toutes les DF possibles dans R (A,
B, C, D), quelles sont les DF non triviales qui existent dans R ?

R: A B C D
1 1 1 2
3 2 3 1
2 2 3 1
1 1 2 3

37- Soit la BD académique suivante pour la gestion des études :

Acad (matric*, noCours*, nomEtud, pgm, horaire, bat)
matric : matricule étudiant
noCours : numéro du cours
nomEtud : nom de lʹélève
pgm : programme dʹétude
horaire : heure hebdomadaire de cours
bat : bâtiment de salle de cours

Les dépendances fonctionnelles de lʹensemble F sont les suivantes :

matric -> nomEtud; et noCours -/-> nomEtud.
matric -> pgm; et no-cours -/-> pgm
noCours -> horaire; et matric -/-> horaire
noCours -> bat; et matric -/-> bât

Lorsquʹun étudiant se retire de tous ses cours, toutes les données le concernant doivent être
supprimées de la BD. Les domaines sont réputés atomiques.
Transformez la relation Acad pour obtenir des relations en FN3.

38- Voici une BD composée dʹune seule relation pour représenter le transport maritime :
TransMmar ( bat*, date*, cap, cargo, valeur). La sémantique des attributs est al suivante :

bat : le libellé du bateau

date : date de départ du port
cap : capacité des caves du vrac
cargo : nature du vrac à livrer
valeur : valeur de la cargaison de vrac
Lʹensemble F = { les DF définies par la clé; bat, date -> cargo; cargo, cap -> valeur; bat -> cap}
38.1- Quelle est la plus grande forme normale de cette relation ?

38.2- Donnez quelques anomalies possibles avec cette relation.

38.3- Normalisez cette relation en FNBC.
39- Voici la relation Univ et ses dépendances fonctionnelles F. Notez que dans cet exemple avec sept
attributs, la recherche de la clé à partir seulement de F nʹest pas triviale.

Univ ( fac, doy, dep, dir, prof, rang, etudiant)

a b c d e f g
La sémantique des attributs est la suivante:
fac: faculté doy: doyen
dir: directeur de département prof: nas du professeur
rang: rang académique etudiant: nas de lʹétudiant(e)

Lʹensemble F est le suivant (avec son pendant simplifié) :

fac -> doy; qui est codée ainsi : a -> b;
doy -> fac; b -> a;
dep -> dir; c -> d;
prof -> rang, dir; e -> f, d;
dep -> fac; c -> a;
etudiant -> dep, fac, doy; g ->c, a, b;
prof, rang -> dep, fac; e, f -> c, a;

39.1- Quelle est la clé de cette relation ?

39.2- Normalisez cette relation en FN3.

40- Soit un schéma de BD dans laquelle lʹensemble F est le suivant: F = { A, B, C, --> G;

D, B --> A; H, C --> F}. Dérivez de lʹensemble F la dépendance H, C, D --> G?

41- Démontrez que les ensembles de dépendances F et G ci-dessous sont équivalents.

F = { A --> B, C; B --> A, D; C, D --> E; E --> C, D}
G = { A --> B, E; B --> A; C, D --> E; E --> C, D }
Pour prouver cette équivalence il faut démontrer que F |=G et que G |= F.

42- Calculez la fermeture de lʹensemble dʹattributs {B, C, E} dans la relation R(A, B, C, D, E, G, H, I}

dont le F = {C, E --> A, C, H; B, C --> A, D; A, C, H --> A, D, G;
A, D, G --> G, I}. Donnez une superclé de R.

43- Soit F = {A -> C; B -> C; C, D -> E; C, D-> F; E, F -> A}. Est-ce que les dépendances de F sont
vérifiées directement ou non dans les tables de la base de données ci-dessous ?

A D E A B C E F B D F
0 0 0 0 3 0 0 0 3 0 0
1 2 0 1 4 4 2 0

44- Soit la relation R (A, B, C, D, E, J, K) avec F ={A, B -> C; A, C ->B; A, D ->E; B -> D; B, C -> A; E -> J}.
Quelles sont les décompositions de R, parmi les suivantes, qui conservent les dépendances ?
a) { (A, B); (B, C); (A, B, D, E); (E, K)}
b) { (A, B, C); (A, B, D, E, K)}
c) {(A, B, C); (A, C, D, E); (A, D, K)}

Série C Synthèse relationnelle (cas particuliers)

45- Démontrez que le schéma de la BD formé par les relations R1(A, B) et R2(B, C) et dont le F = { B--
>A} est un schéma de BD qui conserve les données.
Les exercices proposés sont résolus avec lʹalgorithme de synthèse et concernent le traitement des cas
particuliers :
1- Obtenez un schéma de relations avec F = {A, B, X −> G; A −> X}.
(Attention : il y a présence d’un attribut étranger).

2- Obtenez un schéma de relations avec F = {X −> Y; X −> Z; Y −> Z} (Attention : présence d’une DF
redondante).

3- Obtenez un schéma de relations avec F = {X −> A; Y−>B; Y −> X; X −> Y}

(Attention : présence de clés équivalentes).

4- Obtenez un schéma de relations avec F = {X −> A; Y−>X; A −> Y}

(Attention : clé équivalente et DF redondante)

Série D Cyclicité du schéma, dépendance multivaluée et FN4/FN5

1- Vérifiez ou infirmez la cyclicité des schémas ci-dessous. Justifiez votre réponse.

a) R1(A, B, D), R2(A, C, D), R3(D, E, G), R4(D, F, G), R5(G, I, J);
b) R1(A, B, C), R2(B, C, D), R3(A, C, D), R4(A, B, D);
c) R1(A, B), R2(B, D), R3(C, D), R4(C, E), R5(D, E);
d) R1(A, B, C), R2(B, C, D), R3(A, D).

2- Soit R(A, B, C, H, E)
avec D ={ (1) A -->> B, C; (2) H, E -->> C. Démontrez que D |= A, H -->> B, E.
Solution :
Par complémentarité de (1) on a : (3) A-->> H, E
Par transitivité de (3) et (2) : A-->> C – { E, H}. Donc (4) A-->> C.
Augmentation de (4) avec l’attribut H : (6) A, H -->> C, H
Par complémentarité de (6); A, H -->> B, E
CQFD

3- Soit R(A, B, C, H, E) avec D = { (1) A-->B, C ; (2) C --> H}. Démontrez que A-->> H, E ne peut pas être
valide dans R.
Réponse :
Il est possible de le démontrer soit par un contre-exemple, soit par dérivation.
- Contre-exemple :
Voici une instance de R dans laquelle les DF de D sont vérifiées :

R: A B C H E
a1 b2 c1 h3 e0
a1 b2 c1 d3 e2
a2 b2 c1 h3 e1
a3 b3 c2 h5 e2
a1 b2 c1 h3 e1
a2 b2 c1 h3 e1

Par contre, A-->> H, E n’est pas vérifiée, car (a1, h3, e2) et (a1, d3, e0) ne sont pas deux tuples dans
l’extension de R. Par conséquent, cette extension vérifie toutes les dépendances énoncées et invalide
celle recherchée.

4- Démontrez que dans R (A, B, C, H. E) avec D = {A-->> B, C ; H--> C} la DMV A --> C est aussi valide.
Solution :
Par dérivation : (1) A-->> B, C;
(2) H -->> C;
par la propriété de coalescence :
de (1) on a que A--> C s’il existe un déterminant qui détermine C.
Or, H --> C; Donc la DF est valide. De plus A-->> C.
CQFD.

5- Soit R(A, B, C, H, E) avec D = {C-->> H, E; A --> B, C}. Décomposez s’il y a lieu la relation R pour
obtenir une base de données en FN4.
Solution :
R n’est pas en FN4 puisque la DMV C-->> H, E est valide et qu’elle n’est pas triviale. En Effet, l’union
du déterminé et du déterminant ne donne pas le schéma complet. De plus, le déterminé n’est pas un
sous-ensemble du déterminant.
La décomposition fournit donc deux nouvelles relations qui s’avèrent en FN4 :
R1(C, H, E) et R2(A, B, C) .

6- Soit R (A, B, C, H, E) avec D = {A-->> B, C; H, E -->> C} Démontrez que D |= A -->> C, H, E.

Réponse :
(1) A -->> B, C
(2) A -->> H, E par complémentarité de (1)
(3) H, E -->> C
(4) A -->> C par transitivité
Addition de (2) et (4) A -->> C, H, E
CQFD

7- Donnez un contre-exemple pour illustrer que les DMV ci-dessous sont invalides dans la relation
R(A, B, C) :
7.1 Si D= {A -->> B, C} pour R alors A -->>B;
Solution :
R: A B C
a1 b1 c1
a1 b2 c2

On a alors que A -->> B, C dans R : car (a1, b2, c2) et (a1, b1, c1) sont des tuples de R. Par contre, A -/-
>>B, car (a1,b2, c1) et (a1, b1, c2) ne sont pas des tuples de cette extension.
7.2 Si D= {A -->> B} pour R alors A -->B;
Solution :
R: A B C
a1 b1 c1
a1 b2 c1

Dans cette extension, A-->> B, car (a1, b2, c1) et (a1, b1, c1) sont des tuples présents. Toutefois, la
dépendance fonctionnelle A-> B n’est pas validée.

D’une DMV, on ne peut pas déduire la DF correspondante. Comme nous l’avons vu, d’une DF, il est
possible de déduire la DMV correspondante.

7.3 Si D= {A, B -->> C} pour R alors A -->C;

Réponse :
L’extension ci-dessous vérifie la DMV seule dépendance valide dans R.
La DMV est vérifiée puisque les tuples (a1, b1, c2) et a1, b1, c1) sont dans l’extension de R. Par
contre, la DF A--> C n’est pas vérifiée.

R: A B C
a1 b1 c1
a1 b1 c2

8- Voici deux relations R(A, B, C) et S(H, E) avec F = { H --> E; B --> C}.

R: A B C S H E
:
1 2 5 7 2
1 3 6 2 3
2 3 6 9 11

Par la suite, la dépendance d’inclusion DIN = {R [A, B] ⊆ S [H, E] est ajoutée au schéma de cette base
de données. Au départ, la base est cohérente par rapport à F; suite à l’ajout de la DIN, la base de
données doit demeurer cohérente.

8.1 Quels sont les tuples à ajouter dans la base pour qu’elle soit cohérente ?
Réponse :
Pour que la cohérence soit vérifiée, il faut que la DIN soit validée. Il faudra donc ajouter les tuples (1,
2) et (1, 3) à l’extension S.

8.2 Quelle règle faudrait–il ajouter à R pour que la vérification de l’inclusion soit une procédure finie?
Réponse :
Il faut ajouter dans R la DF suivante : A--> B.

Références chapitre 10

1CODD, E. F., Normalized Data Base Structure: A Brief Survey, Proceedings of 1971 SIGFIDET a
Workshop on Data Description, Access, and Control, CA, USA, 1971.
2 BEERI, C., BERNSTEIN, P. A., GOODMAN, N., A sophisticate’s introduction to database normalization
theory , Proceedings of International Conference on Very Large Databases, 1980, p. 126-136.
3HEATH, I. J.,Unacceptable File Operations in a Relational Database, Proceedings of the ACM SIGFIDET,
1971.
4 ARMSTRONG, W. W.,Dependency Structures of Database Relationships , Proceedings of the
International Federation of Information Processing Societies (IFIP), 1974, p. 580-583.
5 Ullman, J., Principles of Database and Knowledge Base Systems, Computer Science Press, 1988, p. 380.
6BEERI, C., BERNSTEIN, P.A., Computational Problems Related to the Design of Normal Form Relational
Schemas , ACM Transactions on Database System, v. 4, no 1, 1979, p. 30-59.
7NUMMENMAA, J., TANISCH, P., Yet Another Note on Minimal Covers , SIGMOD Record, v. 19, no 3,
1990, p.30.
8 MAIER, D., The Theory of Relational Databases, Computer Science Press, 1983.
9DIEDERICH, J., M., J., New methods and Fast Algorithms for Database Normalization , Transaction on
Databases, v. 13, no 3, Sept 1988, p. 339-365.
10MANNILA, H., RAIHA, K.-J.,The Design of Relational Databases, Addison-Wesley, 1992, ISBN 0-201-
56523-4.
11DUTKA, A. F., HANSON, H. H., Fundamentals of Data Normalization, Addison-Wesley, 1989, ISBN
201-06645-9.
12 GARDARIN, Georges, Les systèmes et leurs langages, Eyrolles, 1983.
13BERNSTEIN, P. A., Synthesizing Third Normal Form Relations FROM Functional Dependencies, ACM
Trans. on Database Systems, v. 1, no 4, 1976.

14SMINE, H., ORACLE, Architecture, administration et optimisation, Eyrolles, 1993, ISBN 2-212-08016-6,
284 p.
15 MOULIN, Bernard, Méthodologie EPAS, Département d’Informatique, Université Laval, 1990, p. 190.
16ABITEBOUL, Serge, HULL, Richard, VIANU, Victor, Foundations of Databases, Addison-Wesley,
1995, ISBN-0-201-53771-0.
17DATE C.J., FAGIN R., Simple Conditions for Guaranteeing Higher Normal Forms in Relational Databases,
ACM Transactions on Database v. 17, no 3, Sept 1992, pp. 465-476.

Vous aimerez peut-être aussi

+cours - Du - Chapitre2 - 5-44-56
Pas encore d'évaluation
+cours - Du - Chapitre2 - 5-44-56
13 pages
Théorie de la Normalisation
Pas encore d'évaluation
Théorie de la Normalisation
12 pages
Modèle Relationnel et Normalisation des Bases de Données
Pas encore d'évaluation
Modèle Relationnel et Normalisation des Bases de Données
79 pages
Support
Pas encore d'évaluation
Support
41 pages
Dépendances Fonctionnelles et Normalisation
Pas encore d'évaluation
Dépendances Fonctionnelles et Normalisation
7 pages
Dépendances Fonctionnelles en Normalisation
Pas encore d'évaluation
Dépendances Fonctionnelles en Normalisation
49 pages
CH 06
Pas encore d'évaluation
CH 06
53 pages
Dependance Fonctionnelle
0% (1)
Dependance Fonctionnelle
20 pages
Normalisation des bases de données relationnelles
Pas encore d'évaluation
Normalisation des bases de données relationnelles
20 pages
0-Rappel 1
Pas encore d'évaluation
0-Rappel 1
36 pages
05.chapitre5 NiveauLogique
Pas encore d'évaluation
05.chapitre5 NiveauLogique
50 pages
Base de Données Et SQL
Pas encore d'évaluation
Base de Données Et SQL
4 pages
Normalisation des données en 3FN
Pas encore d'évaluation
Normalisation des données en 3FN
50 pages
Cours Notes
Pas encore d'évaluation
Cours Notes
33 pages
Dépendances Fonctionnelles Et Normalisation
Pas encore d'évaluation
Dépendances Fonctionnelles Et Normalisation
7 pages
Dépendances Fonctionnelles en BD
100% (1)
Dépendances Fonctionnelles en BD
17 pages
Conception des Bases de Données
Pas encore d'évaluation
Conception des Bases de Données
127 pages
Dépendances Fonctionnelles en BD
Pas encore d'évaluation
Dépendances Fonctionnelles en BD
127 pages
td3 SI
Pas encore d'évaluation
td3 SI
3 pages
Modèle Relationnel et Normalisation
Pas encore d'évaluation
Modèle Relationnel et Normalisation
13 pages
Normalisation et Dépendances Fonctionnelles
Pas encore d'évaluation
Normalisation et Dépendances Fonctionnelles
7 pages
Normalisation des bases de données relationnelles
Pas encore d'évaluation
Normalisation des bases de données relationnelles
5 pages
Chapitre 4
Pas encore d'évaluation
Chapitre 4
22 pages
Normalisation
Pas encore d'évaluation
Normalisation
31 pages
TDs 1 MERISE 23-24
Pas encore d'évaluation
TDs 1 MERISE 23-24
7 pages
CM 1 DF
Pas encore d'évaluation
CM 1 DF
87 pages
Exercice 1:: BD: TD N°1 (Dépendances Fonctionnelles Et Formes Normales)
Pas encore d'évaluation
Exercice 1:: BD: TD N°1 (Dépendances Fonctionnelles Et Formes Normales)
3 pages
Merise Chap5e6
Pas encore d'évaluation
Merise Chap5e6
4 pages
Conception et Normalisation BDD
Pas encore d'évaluation
Conception et Normalisation BDD
110 pages
3 Le Modèle Relationnel
Pas encore d'évaluation
3 Le Modèle Relationnel
4 pages
CHP 6
Pas encore d'évaluation
CHP 6
82 pages
Serie BDD RO
Pas encore d'évaluation
Serie BDD RO
15 pages
7-Concevoir Une Base de Données
Pas encore d'évaluation
7-Concevoir Une Base de Données
45 pages
DF & Normalisation
Pas encore d'évaluation
DF & Normalisation
20 pages
CM2 ForNorm
Pas encore d'évaluation
CM2 ForNorm
26 pages
Chapitre 4 La Normalisation
Pas encore d'évaluation
Chapitre 4 La Normalisation
10 pages
Section3 3-Merise
Pas encore d'évaluation
Section3 3-Merise
7 pages
BDD Chap2
Pas encore d'évaluation
BDD Chap2
4 pages
ch4 BD
Pas encore d'évaluation
ch4 BD
15 pages
DTGFD
Pas encore d'évaluation
DTGFD
31 pages
TD 01
Pas encore d'évaluation
TD 01
4 pages
Cours de BD L3 - Chapitre 5
Pas encore d'évaluation
Cours de BD L3 - Chapitre 5
6 pages
Normalisation et dépendances fonctionnelles
Pas encore d'évaluation
Normalisation et dépendances fonctionnelles
11 pages
Normalisation
Pas encore d'évaluation
Normalisation
6 pages
Enoncé Série TD5-2024
Pas encore d'évaluation
Enoncé Série TD5-2024
3 pages
2.chap2 Modele EA
Pas encore d'évaluation
2.chap2 Modele EA
22 pages
TD1 INF322 DF Et Normalisation 23-24
Pas encore d'évaluation
TD1 INF322 DF Et Normalisation 23-24
2 pages
Comprendre la Normalisation BD
Pas encore d'évaluation
Comprendre la Normalisation BD
10 pages
7 - Notion de Clés Et Des Trois Formes Normales
Pas encore d'évaluation
7 - Notion de Clés Et Des Trois Formes Normales
20 pages
Normalisation Dune Base de Données Relationnelle
Pas encore d'évaluation
Normalisation Dune Base de Données Relationnelle
6 pages
Chapitre 6 MI2 2022 4p
Pas encore d'évaluation
Chapitre 6 MI2 2022 4p
10 pages
Td4solution 1
Pas encore d'évaluation
Td4solution 1
8 pages
SI Chapitre2-1
Pas encore d'évaluation
SI Chapitre2-1
45 pages
2.4.2 Dépendance Fonctionnelle
Pas encore d'évaluation
2.4.2 Dépendance Fonctionnelle
2 pages
Tous-TD TP
Pas encore d'évaluation
Tous-TD TP
47 pages
Schéma relationnel en SQL
Pas encore d'évaluation
Schéma relationnel en SQL
15 pages
TD N°4: Application Pratique de La Modélisation Des Données Et Transformation MCD en MLD Dans Un Système D'information
Pas encore d'évaluation
TD N°4: Application Pratique de La Modélisation Des Données Et Transformation MCD en MLD Dans Un Système D'information
3 pages
2009 - 2010 Chapitre 2 La Budgetisation Des Ventes
Pas encore d'évaluation
2009 - 2010 Chapitre 2 La Budgetisation Des Ventes
8 pages
Compta-Gen L1 2015-2016 Chap 1
Pas encore d'évaluation
Compta-Gen L1 2015-2016 Chap 1
16 pages
2009 - 2010 Chapitre 3 La Budgetisation de La Production)
Pas encore d'évaluation
2009 - 2010 Chapitre 3 La Budgetisation de La Production)
6 pages
Chapitre1-Les Bases de La communication-TEC
Pas encore d'évaluation
Chapitre1-Les Bases de La communication-TEC
23 pages
Cours Economie Generale Iseg Family 08h10h
Pas encore d'évaluation
Cours Economie Generale Iseg Family 08h10h
30 pages
Compta-Gen L1 2015-2016 Chap 2
Pas encore d'évaluation
Compta-Gen L1 2015-2016 Chap 2
20 pages
Chapitre III La T.V.A W
Pas encore d'évaluation
Chapitre III La T.V.A W
4 pages
2009 2010 Chapitre 1 Les Outils de La Gestion Budgetaire
Pas encore d'évaluation
2009 2010 Chapitre 1 Les Outils de La Gestion Budgetaire
5 pages
Partie 4
Pas encore d'évaluation
Partie 4
13 pages
Partie 2
Pas encore d'évaluation
Partie 2
5 pages
Partie 1
Pas encore d'évaluation
Partie 1
17 pages
BD Dépendances Fonctionnelles
Pas encore d'évaluation
BD Dépendances Fonctionnelles
72 pages
Partie 3
Pas encore d'évaluation
Partie 3
8 pages
Externalite
Pas encore d'évaluation
Externalite
24 pages
Gestion 2
Pas encore d'évaluation
Gestion 2
4 pages
Securité Reseaux Et Systèmes
Pas encore d'évaluation
Securité Reseaux Et Systèmes
140 pages
Chap 11
Pas encore d'évaluation
Chap 11
38 pages
CAFG
Pas encore d'évaluation
CAFG
1 page
Table QN
Pas encore d'évaluation
Table QN
1 page
Chap13 1
Pas encore d'évaluation
Chap13 1
35 pages
Vocabulaire Anglais Affaires-05
Pas encore d'évaluation
Vocabulaire Anglais Affaires-05
3 pages
Ipv 6
Pas encore d'évaluation
Ipv 6
41 pages
Guide Creation Entreprise New
Pas encore d'évaluation
Guide Creation Entreprise New
22 pages
07 Mouhoub
Pas encore d'évaluation
07 Mouhoub
10 pages
Gestion Tresorerie
Pas encore d'évaluation
Gestion Tresorerie
58 pages
Chapitre Introductif + Premi+¿re Partie de L'approche Analytique
Pas encore d'évaluation
Chapitre Introductif + Premi+¿re Partie de L'approche Analytique
90 pages
Repertoirecor 0108
Pas encore d'évaluation
Repertoirecor 0108
66 pages
Rapport Final Projection BECPD
Pas encore d'évaluation
Rapport Final Projection BECPD
175 pages
FINANCE
Pas encore d'évaluation
FINANCE
9 pages
Bulletin Septembre2013
Pas encore d'évaluation
Bulletin Septembre2013
14 pages
TD Evn MP Topo 2022
Pas encore d'évaluation
TD Evn MP Topo 2022
5 pages
Maternelle Petite Moyenne Section
Pas encore d'évaluation
Maternelle Petite Moyenne Section
229 pages
Chapitre 1 Euromed
100% (1)
Chapitre 1 Euromed
10 pages
1928 Marcotoune Science Secrete Des Inities PDF
100% (10)
1928 Marcotoune Science Secrete Des Inities PDF
343 pages
Introduction aux EDP par Zoubir Amine
Pas encore d'évaluation
Introduction aux EDP par Zoubir Amine
87 pages
Stochastiques
Pas encore d'évaluation
Stochastiques
220 pages
Cours Proportionnalite
Pas encore d'évaluation
Cours Proportionnalite
9 pages
TD Logique Mathématiques
Pas encore d'évaluation
TD Logique Mathématiques
2 pages
Étude et Analyse de Graphes Biologiques
Pas encore d'évaluation
Étude et Analyse de Graphes Biologiques
2 pages
Activités de Mathématiques de 4ème Année ANNEE FRACTION PDF
Pas encore d'évaluation
Activités de Mathématiques de 4ème Année ANNEE FRACTION PDF
8 pages
Auto Évaluation DS 1 - À Compléter
Pas encore d'évaluation
Auto Évaluation DS 1 - À Compléter
4 pages
1 - Chapitre 1 MPSI
Pas encore d'évaluation
1 - Chapitre 1 MPSI
8 pages
10 Problèmes Par Semaine CP
Pas encore d'évaluation
10 Problèmes Par Semaine CP
20 pages
Critères de Divisibilité des Nombres
Pas encore d'évaluation
Critères de Divisibilité des Nombres
9 pages
Correction TD: Champ Magnétostatique
Pas encore d'évaluation
Correction TD: Champ Magnétostatique
6 pages
DM1-BT3 Elect-Cesa
Pas encore d'évaluation
DM1-BT3 Elect-Cesa
2 pages
Devoir02 S2 2020-2021
Pas encore d'évaluation
Devoir02 S2 2020-2021
1 page
Calculs algébriques : Sommes et produits
Pas encore d'évaluation
Calculs algébriques : Sommes et produits
11 pages
Techniques de Calage Statistique
Pas encore d'évaluation
Techniques de Calage Statistique
31 pages
Limites et continuité en mathématiques
Pas encore d'évaluation
Limites et continuité en mathématiques
2 pages
Devoir 1s1
Pas encore d'évaluation
Devoir 1s1
2 pages
Transformations Conformes et Projection Stéréographique
Pas encore d'évaluation
Transformations Conformes et Projection Stéréographique
1 page
Types D'équations
Pas encore d'évaluation
Types D'équations
5 pages
Corrige (23 TD2Topologie)
100% (2)
Corrige (23 TD2Topologie)
5 pages
TD-No-1-Systèmes de Numérations Et Codage
Pas encore d'évaluation
TD-No-1-Systèmes de Numérations Et Codage
6 pages
Fonctions de Deux Variables
Pas encore d'évaluation
Fonctions de Deux Variables
11 pages
2020TD1 8086
Pas encore d'évaluation
2020TD1 8086
1 page
Corrigé & Barème - Test - Rep1 1BAC - 2025 - 250109 - 160552
Pas encore d'évaluation
Corrigé & Barème - Test - Rep1 1BAC - 2025 - 250109 - 160552
4 pages
Expose Methode Difference Finies
Pas encore d'évaluation
Expose Methode Difference Finies
14 pages
Devoir
Pas encore d'évaluation
Devoir
3 pages

Chap 10

Transféré par

Chap 10

Transféré par

16/04/2004

Schéma canonique d’une table

10.1 Dépendance fonctionnelle dans une relation R

Importance des DF dans une base de données

Quelles sont les DFT dans R ?

Normalisation du modèle relationnel

Operateur 1,n 1,m Machine

Operateur (nas*, nom)

machine : noMachine marque debit totServ categorie

r1 : noMachine* marque categorie totServ

r2 : marque* categorie* debit

Équivalence des relations

Décomposition dʹune relation

Voici une décomposition invalide d’une relation au plan des données :

Propriétés des dépendances fonctionnelles

1- Réflexivité et dépendances fonctionnelles triviales

2- Augmentation du déterminant dʹune DF

Cas particulier : addition de la dépendance triviale Z --> Z

5- Union des déterminés (ayant le même déterminant) de F

MachineOutil (noMachine*, marque*, debit)

machineOutil: noMachine * marque debit

(1) X --> Y, Z par hypothèse : une DF de F

7- Projectabilité dʹune dépendance fonctionnelle

8- Addition de deux dépendances

Sommaire des propriétés des DF

Exemples : Soit R(A, B, C, D), une relation avec des DF valides:

c) Les triviales suivantes sont aussi valides dans R :

Dérivabilité d’une dépendance fonctionnelle : F |- f

Exemples d’une suite de d’inférences :

En supposant que F = {A --> B; B, C --> D; B, D, E --> J}, dérivez la DF suivante A, C, E --> J

10.2 Fermeture F+ dʹun ensemble de dépendance fonctionnelles

Calcul détaillé de la fermeture F+

Exemple : R(A, B, C) avec F ={A -->B; A --> C}

10.2.1 Fermeture dʹun ensemble dʹattributs A+

Calcul de la fermeture dʹun ensemble dʹattributs A+

10.2.2 Couverture non redondante C*

Exemple : Soit R(X, Y, Z) avec F = {X --> Y; Y --> Z; X --> Y, Z}.

Quelques propriétés de la fermeture

Algorithme pour le calcul de C*

10.2.3 Problème de lʹappartenance à une fermeture

Théorème de la fermeture dʹun ensemble dʹattributs

Calcul de la couverture minimale de F

Voici un exemple de l’application de cet algorithme pour trouver la couverture minimale :

Recherche des clés : primaire, candidate et étrangère dans une relation

Soit la relation R(A, B, C, D, E) avec le F suivant :

b) Est-ce que E une clé ? Si E --> A, B, C, D; alors A, B, C, D ⊆ E+.

c) Test avec C, D : C, D --> A, B, E;

d) Test avec B : B --> A, C, D, E?

e) Test avec B, C : B, C --> A, D, E ?

10.2.4 Attribut redondant dans une DF

F |- A --> D i.e. que de F, il est possible de dériver la DF A --> D

Cas 2 Vérifions maintenant si l’attribut A est étranger dans A, B --> D.

Il suffit donc de démontrer les dérivations suivantes :

10.3 Conception dʹun schéma de BD

Algorithme simplifié de synthèse du schéma de BD avec CDF

- Pour chaque déterminant X partagé par toute DF de F :

10.4 Hypothèse de la relation universelle

client : nas* nom date

livraison : article* qte date* nas

nas --> date (de F1)

F1 = {nas --> dateClient ; nas --> nom

Il devient impossible de faire la dérivation impliquant la l’attribut qte.

U: nas * nom date* article* qte

n12 Cyr 12-2-85 a7 2

Empl : nas* telephone Gerant : nas* telephone

Base de dépendances dʹune relation : G(Ri) ou Gi

Définition formelle de la conservation des dépendances (CDF)

Algorithme de vérification de la conservation des dépendances dans S

Algorithme de décomposition du schéma avec CDF

Décomposition sans CDF d’une relation

Conservation des données (CD)

R = R1 |x| R2 |x| R3 |x| ... |x| Rn

Exemple R = r1 |x| r2 avec F = {B --> C, D + les DF de la clé A, B}

Jointure sans conservation des données

10.5 Contraintes dʹinclusion (DIN)

Définition de la dépendance dʹinclusion (DIN)

MachineOutil (noMachine, marque, debit)

Exemple : R (fournisseur, article, ville, qte)

R1 (societe, metier) R2 (metier, salaire)

Autre exemple : Soit la relation Code(ville, adresse, codePostal)