Lifbdw2 – aide mémoire

Licence informatique – session 1 2020–2021

1 Dépendances Fonctionnelles (DF) Clef de la preuve de complétude Supposant Σ 6` X → Y

exhiber une instance r telle que r |= Σ ∧ r 6|= X → Y . Avec
1.1 Définitions X ? = X1 ... Xn et Z1 ... Zp = R \ X ? , la voici :

Syntaxe R : X → Y ou simplement X → Y lu « X détermine r X1 ... Xn Z1 ... Zp

fonctionnellement Y »
s x1 ... xn z1 ... zp
Sémantique r |= X → Y ⇔ ∀t1 , t2 ∈ r .t1 [X ] = t2 [X ] ⇒ t x1 ... xn y1 ... yp
t1 [Y ] = t2 [Y ]
1.4 Algorithmes de fermeture
Cas dégénérés X → Y est triviale si Y ⊆ X , X → Y est
standard si X 6= ∅
Modèle d’un ensemble de DFs Algorithme 1 : Closure(Σ, X )
1 Cl := X ;
r |= Σ ⇔ ∀f ∈ Σ.r |= f 2 done := false;
3 while (¬done) do
Implication logique de DFs 4 done := true;
5 forall W → Z ∈ Σ do
Σ |= f ⇔ ∀r .(r |= Σ ⇒ r |= f ) 6 if W ⊆ Cl ∧ Z 6⊆ Cl then
7 Cl := Cl ∪ Z ;
Fermeture de DFs Σ+ = {f | Σ |= f } 8 done := false;

1.2 Axiomatisation d’Armstrong 9 return Cl

— Le système d’Armstrong est l’ensembles des règles A =

{Reflex., Aug., Trans.} (fig. 1).
— Les règles {Compo., Decompo., PseudoTrans.} sont dé- Algorithme 2 : Closure 0 (Σ, X ) linéaire
ductibles de A (fig. 2) et donc correctes. 1 for W → Z ∈ Σ do
2 count[W → Z ] := |W |
Preuve formelle une séquence hf0 , ... , fn i de DFs telles que 3 for A ∈ W do
fn = f et ∀i ∈ [0..n] soit fi ∈ Σ ; soit fi est la conséquence d’une 4 list[A] := list[A] ∪ W → Z
règle de A dont toutes les prémisses f0 ... fp apparaissent avant fi
dans la séquence. On note Σ ` f s’il existe une preuve finissant 5 closure := X , update := X
par f avec Σ comme ensemble d’hypothèses. 6 while (update 6= ∅) do
7 update := update \ {A}
8 for W → Z ∈ list[A] do
Fermeture d’un ensemble d’attributs 9 count[W → Z ] := count[W → Z ] − 1
sémantique X + = {A | Σ |= X → A} 10 if count[W → Z ] = 0 then
syntaxique X ? = {A | Σ ` X → A} 11 update := update ∪ (Z \ closure)
12 closure := closure ∪ Z
Lemme 1. Σ |= X → Y ⇔ Y ⊆ X +
13 return closure
Lemme 2. Σ ` X → Y ⇔ Y ⊆ X ?

1.3 Correction et complétude Théorème 3. Les algorithmes 1 et 2 sont corrects pour le calcul
de fermeture des DFs standards 1 :
Le système A est correct et complet.
Closure(Σ, X ) = X ? = X + = Closure 0 (Σ, X )
Théorème 1 (Correction).
Théorème 4 (Résumé).
Σ ` X → Y ⇒ Σ |= X → Y
Y ⊆ Closure(Σ, X )
Théorème 2 (Complétude). ≡ Y ⊆ X? (théorème 3)
≡ Σ`X ⊆Y (lemme 1)
Σ |= X → Y ⇒ Σ ` X → Y ≡ Σ |= X ⊆ Y (théorèmes 1 et 2)
≡ Y ⊆ X+ (lemme 2)
Corollaire 1 (Equivalence des fermetures).

X+ = X? 1. l’algorithme 2 peut être modifié pour traiter les DFs non-standards.

 Y ⊆X X →Y X →Y Y →Z
Reflex. Aug. Trans.
X →Y WX → WY X →Z
Figure 1 – Axiomatisation d’Armstrong pour les DFs

X →Y X → Z Compo. X → YZ Decompo. X →Y WY → Z
PseudoTrans.
X → YZ X →Y WX → Z
Figure 2 – Règles admissibles pour les DFs

1.5 Relation d’Armstrong Lemme 4. Toute DF est une DMV.

Ensemble des fermés l’ensemble des fermés Cl(Σ) d’un en- Théorème 7. L’axiomatisation {Reflex., Aug., Complement.
semble de DFs Σ est défini par Cl(Σ) = {X + | X ⊆ R} , Trans.} est correcte et complète pour l’inférence des DMVs
Définition équivalente Cl(Σ) est défini de façon équivalente (fig. 4).
par Cl(Σ) = {X | X ⊆ R ∧ X + = X }
Théorème 8. L’axiomatisation précédente à laquelle on ajoute
L’algorithme 3 répète la construction clef de la preuve de com- les règles {Gene., Mix.} (fig. 5) est correcte et complète pour
plétude (théorème 2) pour chaque élément de Cl(Σ). l’inférence des DFs et des DMVs considérées ensemble.

Algorithme 3 : Armstrong(Σ, R)
1 r := ∅ ; i := 0 3 Normalisation
2 for A ∈ R do t[A] := 0 ;
3 r := r ∪ {t} 3.1 Définitions
4 for X ∈ Cl(Σ) \ R do
DF élémentaire une DF X → Y est élémentaire ssi ∀.X 0 (
5 for A ∈ R do
X ⇒ X 0 6→ Y
6 if A ∈ X then t[A] := 0 ;
7 else t[A] := i ; DF directe une DF X → Y est directe ssi 6 ∃Z .X → Z ∧Z 6→
X ∧ Z → Y (pas de transivité)
8 r := r ∪ {t}
9 i := i + 1 Clé C’est un ensemble d’attributs X tels que X → R
10 return r Clé minimale C’est une clé X avec X → R élémentaire.
Attribut premier Un attribut A ∈ R est premier s’il appar-
tient à au moins une clé minimale de R.
Théorème 5. Soit r = Armstrong(Σ, R) une instance obtenue Couverture Soient Σ et Γ deux ensembles de DFs, Γ est une
avec l’algorithme 3 : couverture de Σ ssi Γ+ = Σ+ .

∀f .Σ |= f ⇒ r |= f et ∀f .Σ 6|= f ⇒ r 6|= f
Algorithme 4 : Minimize(Σ)
1 G := ∅
2 Autres dépendances /* Fermeture des parties droites */
2 for X → Y ∈ Σ do
2.1 Dépendances d’Inclusion (DI) 3 G := G ∪ {X → X + };
Soient R, S ∈ R, X et Y des séquences d’attributs distincts /* Suppression des redondances */
respectivement de R et de S, avec |X | = |Y |. 4 for X → X + ∈ G do
5 if G − {X → X + } ` X → X + then
Syntaxe R[X ] ⊆ S[Y ]
6 G := G − {X → X + };
Sémantique r , s |= R[X ] ⊆ S[Y ] ⇔ ∀tr ∈ r , ∃ts ∈
[Link] [X ] = ts [Y ] ⇔ πX (r ) ⊆ πY (s) 7 return G

Théorème 6. L’axiomatisation de Casanova pour les DIs C =

{Reflex., Trans., Proj.} (fig. 3) est correcte et complète.
Théorème 9. Soit F = Reduce(Minimize(Σ)) donnés par les
Lemme 3. Les propriétés suivantes d’interactions entre DFs et algorithmes 4 et 5, alors :
DIs sont vérifiées : — F est une couverture de Σ (F + = Σ+ )
— {R[XY ] ⊆ S[TU], S : T → U} |= R : X → Y — F est minimal en nombre de dépendances (∀G.G + =
— {R[XY ] ⊆ S[TU], R[XZ ] ⊆ S[TV ], S : T → U} |= Σ+ ⇒ |F | ≤ |G|)
R[XYZ ] ⊆ S[TUV ] — toutes les parties gauches sont réduites (∀X → Y ∈
F .∀.X 0 .X 0 ( X ⇒ X 0 6→ Y )
— toutes les parties droites sont réduites (∀X → Y ∈
2.2 Dépendances MultiValuées (DMV) F .∀Y 0 ( Y .F \ {X → Y } ∪ {X → Y 0 } 6|= X → Y )
Syntaxe X  Y lu « X multidétermine Y »
Sémantique r |= X  Y ssi ∀t1 , t2 ∈ r tels que t1 [X ] = Pertes d’information et de dépendances
t2 [X ] ∃t3 , t4 ∈ r tels que : Décomposition Une décomposition d’un ensemble d’attri-
— t3 [XY ] = t1 [XY ] et t3 [R \ Y ] = t2 [R \ Y ] S de base de données R = {R1 , ... , Rn }
buts R est un schéma
— t4 [XY ] = t2 [XY ] et t4 [R \ Y ] = t1 [R \ Y ] avec Ri ⊆ R et Ri = R
 R[A1 ... An ] ⊆ S[B1 ...Bn ]
Reflex. R[X ] ⊆ S[Y ] S[Y ] ⊆ T [Z ] Proj.
R[X ] ⊆ R[X ] Trans. R[Aσ(1) ...Aσ(k) ] ⊆ S[Bσ(1) ...Bσ(k) ]
R[X ] ⊆ T [Z ]
Avec σ une permutation d’un sous-ensemble de {1...n}

Figure 3 – Axiomatisation de Casanova pour les DIs

Y ⊆X X Y X Y Compl. X Y Y Z
Reflex. Aug. Trans.
X Y WX → WY X  R \ XY X →Z \Y

Figure 4 – Axiomatisation pour les DMVs

Algorithme 5 : Reduce(Σ) Contre-exemples

— hABC , {AB → C , B → C }i n’est pas 2FN.
1 Min := F
— hABC , {A → B, B → C }i est 2FN mais pas 3FN.
/* Réduction des parties gauches */
— hABC , {AB → C , C → B}i est 3FN mais pas FNBC.
2 for X → Y ∈ Min do
— hABC , {A  B}i est FNBC mais pas 4FN.
3 W := X
4 for A ∈ X do Théorème 10. La 4FN implique la FNBC, la FNBC implique la
5 if Min |= (W − A) → Y then W := W − {A} ; 3FN, la 3FN implique la 2FN et les inclusions sont strictes.
6 Min := (Min − {X → Y }) ∪ {W → Y } Lemme 5. Toute relation en 3FN avec une unique clef minimale
/* Réduction des parties droites */ est en FNBC. Toute relation à deux attributs est en FNBC.
7 for X → Y ∈ Min do
8 W := Y Forme normale d’une base de données Un schéma de base
9 for A ∈ Y do de données R = {R1 ... Rn } et un ensemble de dépendances Σ
10 G := (Min − {X → Y }) ∪ {X → (W − A)} sur ces relations est en 2FN (respectivement 3FN, FNBC, 4FN)
11 if G |= X → Y then W := W − {A}; ssi hRi , (Σ[Ri ])i est en 2FN (resp. 3FN, FNBC, 4FN) pour tout
12 ; 1 ≤ i ≤ n.
13 Min := (Min − {X → Y }) ∪ {X → W };
14 return Min; 3.3 Algorithmes de normalisation

Algorithme 6 : Synthesis(Σ, U)
Perte d’information Une décomposition R = {R1 , ... , Rn }
est sans perte d’information (ou de jointure) ssi ∀r .r = /* 1. minimisation et réduction */
πR1 (r ) o
n ... o
n πRn (r ) 1 F := Reduce(Minimize(Σ))
/* 2. une relation pour chaque DF */
Projection de DFs (1) soit S ⊆ R et Σ en un ensemble de 2 for X → Y ∈ F do
DFs, la projection de Σ sur S est Σ[S] = {X → Y | X → 3 R := R ∪ {XY }
Y ∈ Σ+ ∧ XY ⊆ S}.
/* 3. suppression des non-maximaux */
Projection de DFs (2) La projection
S de Σ sur un schéma de 4 for R ∈ R do
base de données R est Σ[R] = {Σ[R] | R ∈ R} 5 if ∃R 0 .R ( R 0 then R := R \ {R};
Perte de dépendances Une décomposition R est sans perte /* 4. pertes de jointure */
de dépendances ssi (Σ[R])+ = Σ+ 6 Cle := {X | X → U ∧ ∀Z .Z ( X ⇒ Z 6→ U}
7 if ∀R ∈ R. 6 ∃K ∈ Cle.K ⊆ R then
/* ajout d’une clé si nécessaire */
3.2 Formes normales 8 choisir K ∈ Cle
On considère les paires hR, Σi formées d’un schéma de relation 9 R := R ∪ {K }
R et d’un ensemble de DFs Σ sur R. 10 return R
2FN hR, Σi est en 2FN ssi il n’existe pas de DF non-triviale
X → A ∈ Σ+ avec A non-premier et X sous-ensemble
propre d’une clé minimale. Algorithme 7 : Decompose(Σ, U)
3FN hR, Σi est en 3FN, de façons équivalentes 2 : 1 F := Reduce(Minimize(Σ))
— ssi elle est en 2FN et qu’il n’existe pas d’attribut non- 2 R = {U};
premier qui dépende transitivement d’une clé mini- /* tant que tout n’est pas en BCNF */
male ; 3 while (∃R ∈ R.¬BCNF (R)) do
— ssi pour toute DF non-triviale X → A ∈ Σ+ , A n’est /* trouver une DF non-triviale non-clef */
pas-premier implique que X est une (super)clé . 4 let X → Y with Y 6⊆ X and F 6|= X → U;
FNBC hR, Σi est en FN de Boyce-Codd (FNBC) ssi pour /* remplacer R par R1 = X + et
toute DF non-triviale X → A ∈ Σ+ , X est une (super)clé. R2 = (R \ X + ) ∪ X */
5 R := R \ {R} ∪ {X + , (R \ X + ) ∪ X };
4FN hR, Σi est en 4FN ssi pour toute DMV non-triviale X 
A ∈ Σ+ , X est une (super)clé. 6 return R

2. On préfèrera la seconde définition, sans référence à la 2FN.

 X →Y X  Y,Z ⊆ Y W ∩ Y = ∅, W → Z
Gene. Mix.
X Y X →Z
Figure 5 – Axiomes supplémentaires pour les DMVs et DFs considérées ensembles

Théorème 11. La décomposition obtenue par l’algorithme 6 de ...

synthèse termine en 3FN sans perte d’information ni de dépen- WHEN MY_EXCEPTION THEN
dances et en FNBC si c’est possible sans perte de dépendances. ...
WHEN OTHERS THEN −−o p t i o n n e l
Théorème 12. La décomposition obtenue par l’algorithme 7 de ...
décomposition termine en FNBC sans perte d’information, avec END;
éventuellement perte de dépendances. 4.3.2 Procédures

CREATE OR REPLACE PROCEDURE

4 Programmation PL/SQL nomP( a r g 1 IN t y p e 1 , a r g 2 IN OUT t y p e 2 , . . . )
IS
4.1 Exceptions BEGIN
NO_DATA_FOUND aucun résultat (dans un SELECT ...INTO). DECLARE
...
TOO_MANY_ROWS plusieurs résultats. BEGIN
VALUE_ERROR érreur numérique. ...
END;
ZERO_DIVIDE division par zéro END;
OTHERS toutes erreurs non interceptées.
4.3.3 Fonctions

4.2 Structures CREATE OR REPLACE FUNCTION

nomF ( a r g 1 IN t y p e 1 , a r g 2 IN t y p e 2 , . . . )
4.2.1 Branchements RETURN t y p e R e t o u r IS
BEGIN
IF v1 = c1 THEN DECLARE
... ...
ELSIF v1 = c2 THEN BEGIN
... ...
END IF ; END;
END;
v a l := CASE c
WHEN c1 THEN v1 4.3.4 Curseurs
WHEN c1 THEN v2
ELSE v_default DECLARE
END; CURSOR c ( param t y p e ) IS
SELECT . . .
4.2.2 Boucles FROM . . .
WHERE . . . ;
LOOP BEGIN
instructions ; FOR v_c i n c ( 1 0 ) LOOP
EXIT [WHEN c o n d i t i o n ] ; ...
instructions ; END LOOP;
END LOOP; END;

WHILE c o n d i t i o n LOOP 4.3.5 Triggers

instructions ;
END LOOP; CREATE [OR REPLACE ] TRIGGER t r i g g e r _ n a m e
{BEFORE | AFTER}
FOR v a r i a b l e IN [ REVERSE ] d e b u t . . f i n {INSERT [OR] | UPDATE [OR] | DELETE}
LOOP [ OF col_name ] ON table_name
instructions ; [ REFERENCING OLD AS o NEW AS n ]
END LOOP; [FOR EACH ROW]
WHEN ( c o n d i t i o n )
4.3 Déclarations types
BEGIN
4.3.1 Exceptions ...
IF UPDATING( ’ c o l ’ ) THEN
DECLARE ...
MY_EXCEPTION EXCEPTION ; END;
BEGIN
... 4.3.6 Vues
RAISE MY_EXCEPTION ;
... CREATE [OR REPLACE ] VIEW view_name AS
EXCEPTION /∗ SELECT QUERY ∗/ ;
WHEN NO_DATA_FOUND THEN