Bases de Données avancées

Inférence de dépendances
Travaux dirigés

Exercice 1 : Inférence dans les contraintes

Soit R = ABCDE un schéma de relation. Dans chaque cas suivant, démontrez que Σ |= σ, en utilisant
uniquement les règles d’inférences rappelées plus loin.
1. Σ = {ABC → E ; BE → D; BD → C }
1. σ = BE → C
2. σ = ABE → C
3. σ = ABDE → C
4. σ = ABC  D
2. Σ = {A → E ; B → D; A  BC ; A  BD}
1. σ = A → D
2. σ = A  CE
3. Soit S = FGHIJ un deuxième schéma de relation. Σ = {ABE ⊆ FJH; H → J; E → AC ; B → D}
1. σ = E → R (E est une clé de R).
4. Refaites la question 1 en vous appuyant sur l’opérateur de fermeture dans les DF (X + = {A ∈ R |
Σ |= X → A}).
5. En vous appuyant cette fois sur la technique de la poursuite, refaites les questions 1.1 - 1.4 - 2.1 et
2.2.

Exercice 2 : Propriétés de la fermeture

Soit (R, Σ) un ensemble d’attributs munis d’un ensemble de DF. On rappelle l’opérateur de fermeture
défini par :
+
: P(R) −→ P(R) X 7→ X + = {A ∈ R | Σ |= X → A}
1. Justifier que la fermeture .+ est bien une fermeture au sens algébrique du terme, c’est à dire qu’elle
respecte les propriétés suivantes :
Extensive X ⊆ X +
Croissante X ⊆ Y ⇒ X + ⊆ Y +
Idempotente (X + )+ = X +
2. Prouver que pour tout ensemble d’attributs Y , si X ⊆ Y ⊆ X + alors Y + = X +
3. En vous appuyant sur la propriété précédente, calculer l’ensemble des fermés Cl(Σ) = {X + | X ⊆ R}
pour l’ensemble des DF Σ donné ci-dessous en évitant d’énumérer des éléments « inutiles » parmi les
25 possibles.
BC → A D → BE
AC → B B → DE
AE → C C →E

Exercice 3 : comparaisons des couvertures minimales

1. Soient Σ1 = {A → C , AC → D, E → AD, E → F } et Σ2 = {A → CD, E → AF }. Déterminer si
chaque DF de Σ2 peut être inférée par Σ1 et réciproquement.
2. En utilisant l’algorithme vu en cours déterminer une couverture minimale de Σ1 . Comparer la couverture
ainsi obtenue à Σ2 .
3. En utilisant le même algorithme déterminer si Σ = {A → BC , D → E , C → D} est minimal.

Exercice 4 : couverture minimale et réduite

Soit Σ l’ensemble de DFs Σ = {A → B; A → C ; D → E ; C → D; B → C ; BC → A}
1. Donner une couverture minimale de Σ en utilisant l’algorithme vu en cours.
2. Réduire la couverture minimum en appliquant l’algorithme de réduction des parties droites et gauches
vu en cours.

Exercice 5 : couverture minimale et réduite

Soit l’ensemble F de DF suivant le schéma R = ABCDEFG :

D→A D→C D→E

D→F CE → G AG → F
ADG → B BG → ADE BF → DG

1. Démontrer que F n’est ni optimum, ni minimum, ni non-redondante.

2. Calculer une couverture minimale et réduite de F .

Règles d’inférences pour les DI

Règles d’inférences pour les DF Réflexivité

R[X ] ⊆ R[X ]
Y ⊆X
σR (réflexivité)
X →Y R[A1 ...An ] ⊆ S[B1 ...Bn ]
Permutation et projection
X →Y R[Aσ(1) ...Aσ(k) ] ⊆ S[Bσ(1) ...Bσ(k) ]
σA (augmentation)
WX → WY
R[X ] ⊆ S[Y ] S[Y ] ⊆ T [Z ]
X →Y Y → Z σ (transitivité) Transitivité
T R[X ] ⊆ T [Z ]
X →Z
Interactions DF et DMV
Règles d’inférences pour les DMV
X →Y
Y ⊆X Généralisation ou Promotion
Réflexivité X Y
X Y
X Y Y →Z
X Y X Z Quasi-transitivité mixte
Union X →Z −Y
X  YZ
Interactions DF et DI
X Y Complémentation
X  R \ XY R[XY ] ⊆ S[TU] S:T →U
Pullback
R:X →Y
X Y Y Z
Quasi-transitivités
X Z −Y R[XY ] ⊆ S[TU] R[XZ ] ⊆ S[TV ] S:T →U
Collection
R[XYZ ] ⊆ S[TUV ]
Corrections

Solution de l’exercice 1
BE → D aug.
1. 1. BE → BD BD → C
trans.
BE → C

BE → D aug.
BE ⊆ ABE BE → BD BD → C
2. Ref. trans.
ABE → BE BE → C
trans.
ABE → C

BE → D aug.
BE ⊆ ABDE BE → BD BD → C
3. Ref. trans.
ABDE → BE BE → C
trans.
ABDE → C

ABC → E aug.
ABC → BE BE → D
4. trans.
ABC → D promotion
ABD  D

Autre solution (qui utilise moins d’hypothèses) :

ABC → E promotion
ABC  E Complémentation
ABC  D

B → D aug. D ⊆ CD
Refl.
2. 1. BC → CD CD → D
trans.
A  BC BC → D
Quasi-transitivité mixte
A→D

A→E A  BC A  BD
Promotion Difference
2. AE AC
Union
A  CE

3. On commence par utiliser l’interaction DF/DI pour faire apparaître E → B

ABE ⊆ FJH
Projection
BE ⊆ JH H→J
Pullback
E →B
Puis on peut faire l’inférence dans les DF.
E → B Augm. E → AC Augm
E → BE BE → ABC B→D Augm.
Trans.
E → ABCE ABCE → ABCDE
Trans.
BE → ABCDE
4. 1. AB + = BCDE , donc Σ |= AB → C
2. ABE + = ABCDE , donc Σ |= ABE → C
3. ABDE + = ABCDE , donc Σ |= ABCE → C
4. ABC + = ABCDE donc Σ |= ABC → D Puis utilisation de la promotion pour Σ |= ABC  D
5. 1. On souhaite démontrer que Σ |= BE → C . On va consuire une relation r par la poursuite.
Initialisation :
r A B C D E
0 0 0 0 0
1 0 1 1 0
Puisque les deux tuples sont égaux sur BD, on peut "appliquer" la DF BE → D et remplacer ainsi
un "1" par un "O". (rappelons que les 0 sont des valeurs arbitraires, alors que les autres chiffres
sont des variables qu’on peut fixer à "O" si besoin) :
r A B C D E
0 0 0 0 0
1 0 1 0 0
Puisque maintenant les deux tuples sont égaux sur BD, on déclenche BD → C :
r A B C D E
0 0 0 0 0
1 0 0 0 0
Puisque l’attribut C est entièrement à 0, on conclut que Σ |= BE → C .
2. On souhaite démontrer que Σ |= ABC  D.
Initialisation de la relation r 0 pour la poursuite (on rappelle que cette MVD peut s’écrire :o
n
[ABCD, ABCE ] et on applique donc l’initialisation d’une DJ :
r0 A B C D E
t1 0 0 0 0 1
t2 0 0 0 2 0
Puisque t1 [ABC ] = t2 [ABC ], et que r 0 |= ABC → E , on déduit que t1 [E ] = 0.
r0 A B C D E
t1 0 0 0 0 0
t2 0 0 0 2 0
On constate que le tuple (0, 0, 0, 0, 0) est apparu, donc Σ |= ABC  D.
3. On souhaite démontrer que Σ |= A → D (avec Σ de la question 2).
Initialisation de la poursuite :
r 00 A B C D E
t1 0 0 0 0 0
t2 0 1 1 1 1
Puisque t1 [A] = t2 [A], et que r 0 |= A  BC , on doit créer les tuples qui montrent l’indépendance
entre BC et DE pour un même A. Cela se fait en intervertissant les valeurs de BC sur les deux
tuples, ce qui crée deux nouveaux tuples.
r 00 A B C D E
0 0 0 0 0
0 1 1 1 1
0 1 1 0 0
0 0 0 1 1
Puisque t1 [B] = t2 [B] et r 0 |= B → D, on déduit que t2 [D] = t3 [D] = 0.
r 00 A B C D E
t1 0 0 0 0 0
t2 0 1 1 0 1
t3 0 1 1 0 0
t4 0 0 0 0 1
Puisque l’attribut D est entièrement à 0, on conclut que Σ |= A → D.
4. On démontre que Σ |= A  CE .
Initialisation
r 000 A B C D E
0 1 0 1 0
0 0 2 0 2
 On applique A  BD en inversant les valeurs sur BD et CE des tuples qui ont la même valeur sur
A. Cela crée deux nouveaux tuples.
r 000 A B C D E
0 1 0 1 0
0 0 2 0 2
0 0 0 0 0
0 1 2 1 2
On voit que cette règle suffit pour obtenir un tuple égal à 0. Donc Σ |= A  CE .

Solution de l’exercice 2
1. Extensive Soit A ∈ X , par l’axiome de réflexivité on a |= X → A et donc A ∈ {A | Σ |= X → A}.
Croissante Soit X ⊆ Y , il faut montrer que X + ⊆ Y + . Considérons A ∈ X + , par définition, il existe
une preuve de Σ |= X → A. Comme X ⊆ Y , par l’axiome de réflexivité on a |= Y → X . Par
transitivité on a une preuve de Σ |= Y → A, c’est-à-dire A ∈ Y + .
Idempotente On montre la double inclusion. Pour la première direction, on a X ⊆ X + et par mo-
notonie X + ⊆ (X + )+ . Pour la seconde direction, il faut prouver que (X + )+ ⊆ X + . On prouve
d’abord que Σ |= X → X + . Supposons sans perte de généralités que X + = A1 ... An , pour tout
indice 1 ≤ i ≤ n, par définition, si Ai ∈ X + alors on a une preuve que Σ |= X → Ai . Or on peut
concaténer toutes ces preuves puis répéter la règle de composition 1 {X → Y , X → Z } |= X → YZ
pour obtenir une preuve de Σ |= X → X + . Considérons A ∈ (X + )+ , par définition, on a une
preuve Σ |= X + → A (notez le X + ), comme on a prouvé que Σ |= X → X + , on peut conclure par
transitivité.
2. D’une part, par hypothèse X ⊆ Y et donc par monotonie on a X + ⊆ Y + . D’autre par, par hypothèse,
Y ⊆ X + et donc par monotonie puis par idempotence on a Y + ⊆ (X + )+ = X + . On a donc
X + ⊆ Y + ⊆ X + et on conclut par antisymétrie de la relation d’inclusion.
3. On procède par niveaux : calculer les fermetures de tous les singletons, puis des couples d’attributs,
puis des ensembles de trois attributs etc. Au total, il y a 25 = 32 sous-ensembles dont il faudrait
calculer la fermeture. On rappelle que le nombre de combinaisons de k parmi n est kn = k!(n−k)!
n!

niveau 1
A+ = A
B + = BDE
C + = CE
D + = BDE
E+ = E
niveau 2
AB + = R
AC + = R
AD + = R
AE + = R
BC + = R
BD + = BDE (1)
BE + = BDE (2)
CD + = R
CE + = CE (3)
Pour (1) et (2), comme B ⊆ BD ⊆ B = BDE , on déduit que BD + = BDE . De la même façon
+

pour (3), en remarquant que C ⊆ CE ⊆ C + = CE , on déduit CE + = CE . Pour le niveau 3, on doit

5


énumérer les 2 = 10 ensembles de taille 3, mais en remarquant que AB + = AC + = AD + = AE + on
peut éliminer tous ceux qui contiennent A. Il en reste donc 43 = 4, à savoir {BCD, BDE , BCE , CDE }

1. cette dernière étant simplement une combinaison d’augmentation et de transitivité.

 niveau 3
BCD + = R (4)
BDE + = BDE (5)
BCE + = R (6)
CDE + = R (7)
Pour (4) et (7), on remarque que BCD + et CDE + contiennent CD et donc leur fermeture est R. Pour
(5), on le connait déjà, et enfin pour (6), on utilise le fait que BC + = R. On a terminé, car il ne
reste que BCDE à tester (le seul sous-ensmeble de taille 4 qui ne contienne pas A) et on sait que
BCDE + = R. En conclusion, on a :

Cl(Σ) = {A, E , CE , BDE , R}

Solution de l’exercice 3
1. Pour la première question, on calcule A+ = ACD via Σ1 et donc Σ1 |= A → CD. De même E + =
ACDEF et Σ1 |= E → AF . Comme Σ1 |= A → CD et Σ1 |= E → AF on en déduit que si
Σ2 |= X → Y , alors, Σ1 |= X → Y également. On a donc Σ+ +
2 ⊆ Σ1 . Dans l’autre sens c’est
également le cas : toute dépendance de Σ2 peut être prouvée depuis Σ1 , ainsi on prouve que Σ+ +
1 ⊆ Σ2
+ +
et donc que les deux ensembles Σ1 et Σ2 sont équivalents, Σ1 = Σ2 .
2. Après la première boucle de l’algorithme ??, on obtient la couverture {A → ACD, AC → ACD, E →
ACDEF }. Après la deuxième boucle, on supprime AC → ACD et on obtient {A → ACD, E →
ACDEF }. On remarque que ces DFs sont minimales à gauche car composée d’un singleton mais qu’on
peut les simplifier à droite pour obtenir A → CD et E → AF , soit exactement Σ2 .
3. On utilise l’algorithme on obtient Σ0 = {A → ABCDE ; D → DE , C → CDE } qui a le même nombre
de DFs et l’ensemble est bien minimal.

Solution de l’exercice 4
1. On obtient la couverture minimum {B → ABCDE ; D → DE ; C → CDE ; A → ABCDE }
2. On obtient {B → A; D → E ; C → D; A → BC }

Solution de l’exercice 5
1. Nous savons que qu’une couverture optimale est minimale et qu’une couverture minimum est non-
redondante. Clairement, F n’est pas minimal, car on peut regrouper D → A, D → C , D → E et
D → F en une seule DF D → ACEF . N’étant pas minimal, on est pas optimal non plus. Concernant
la redondance, il faut prouver que qu’il existe f ∈ F telle que F \ {f } |= f . Pour cela, nous pouvons
exhiber la DF D → F qui peut être retrouvée à l’aide des autres DFs de F .
2. Calculons d’abord la couverture minimum. Pour cela, il faut reécrire les règles sous la forme X → X + ,
soit l’ensemble Σ suivant :
D→R
CE → CEG
AG → AGF
ADG → R
BG → R
BF → R
Notons que la DF D → R n’apparait qu’une seule fois et pas quatre car nous adoptons une vision
ensembliste (les 3 autres occurences supprimées). Il faut maintenant supprimer les DFs de Σ inutiles.
Ici, il n’y en a qu’une seule : ADF → R. Il faut donc réduire l’ensemble suivant :
D → ABCDEFG
CE → CEG
AG → AGF
BG → ABCDEFG
BF → ABCDEFG
Attention la réduction va dépendre de l’ordre dans lequel on traite les DFs.
— BF → ABCDEFG simplifié en BF → D puisque D → R.
— Idem pour BG → ABCDEFG simplifié en BG → D.
— AG → AGF , il faut supprimer A et G qui apparaissent déjà en partie gauches.
— Idem pour CE → CEG.
— D → ABCDEFG : on peut supprimer le D (apparait à gauche), le G (car CE → G), le F (AG → F ) :
D → ABCE
Ce qui donne le résultat final (un parmi d’autre) :
D → ABCE
CE → G
AG → F
BG → D
BF → D