NORMALIZAREA RELATIILOR. FORME NORMALE

NORMALIZAREA RELATIILOR. FORME NORMALE

Normalizarea - tehnica obligatorie in proiectarea conceptuala a oricarei b.d., dar in mod special in b.d. relationale

Concepte fundamentale

Dependenta functionala (FN1, FN2, FN3, FNBC/F.N. Boyce-Codd)

Dependenta multivalorica (FN4)

Dependenta de cuplare (FN5)

Schema de relatie = tupla care cuprinde: (a) numele relatiei si

(b) atributele asociate

Problema proiectarii robuste a unei b.d. relationale:

(a) alegerea schemelor de relatie si

(b)   modul de grupare a atributelor in relatii pt. a reprezenta tipuri de entitati sau legaturi intre tipurile de entitati

Criteriul central de proiectare: Dependenta Datelor

Dependenta Functionala (Def.)

Fie: - schema de relatie R(A₁, A₂,, A_n)

X si Y - atribute simple sau compuse, submultimi ale multimii de atribute

Spunem ca atributul X determina functional atributul Y (sau Y depinde functional de X) ddca oricarei valori a atributului X ii corespunde o singura valoare a atributului Y.

Nouatie: X Y.

Dependenta Functionala Totala & D. F. Partiala (Defs.)

Dependenta functionala X Y este totala daca nu exista nici un subset Z al atributului X ( Z X) a. i. Z Y.

In caz contrar dependenta se numeste partiala

OBS1: Daca X Y, atunci pt. orice subset Z al lui Y avem X Z.

OBS2: Daca X Y si X este un atribut simplu, atunci Y este dependent functional total fata de X.

OBS3: Daca Y este dependent functional total fata de Z, atunci X Y pt. orice atribut compus X care contine pe Z.

Axiomele lui ARMSTRONG: (set de reguli pt. deducerea dependentelor functionale care sunt consecinte ale unui set de dependente functionale date initial)

Ipoteza: Fie X Y si Z submultimi ale multimii de atribute

(A1) - reflexivitate: Daca Y X atunci X Y.

(A2) - augmentare: Daca X Y, atunci X Z Y Z.

(A3) - tranzitivitate: Daca X Y si Y Z, atunci si X Z.

OBS. A3 este singura axioma care conduce la dependente noi si netriviale. Celelalte doua axiome sunt utile in combinatie cu A3.

Inchidere Tranzitiva a setului de dependente functionale F (notata F*) = =multimea dependentelor functionale care se pot obtine prin aplicarea repetata, in toate modurile posibile, a regulilor A1-A3 asupra unui set initial de dependente functionale F

Dependente Multivalorice

mai putin restrictive decat dep. Functionala

au implicatii in normalizarea relatiilor

Def.

Fie schema de relatie R(X,Y,Z)

unde X,Y si Z sunt atribute simple sau compuse.

Notam cu x, y si z valori ale atributelor X, Y si Z.

Spunem ca exista o Dependenta Multivalorica a atributului Z fata de Y (sau Y multidetermina pe Z) si notam Y Z daca pt. orice valori x₁, x₂,y, z₁ si z₂,    cu x₁ x₂ si z₁ z_{2 ,} astfel incat tuplele (x₁,y, z₁) si (x₂,y, z₂) fac parte din relatia R, atunci si tuplele (x₁,y, z₂) si (x₂,y, z₁) fac parte din relatia R.

OBS1: Dependenta multivalorica Y Z implica si dependenta multivalorica complementara Y X (acest lucru rezulta direct din simetria definitiei dependentei multivalorice).

OBS2: In particular, unele dependente multivalorice pot fi de fapt dependente functionale.

Axiomele lui Armstrong pentru dependentele functionale si multivalorice, precum si pt. legatura dintre acestea: (set de reguli pt. determinarea sistematica a tuturor dependentelor multivalorice care sunt o consecinta logica a unui set initial)

Ipoteza: Fie X Y si Z submultimi ale multimii de atribute U=

(A1) - reflexivitate pt. dep. functionale:

Daca Y X atunci X Y.

(A2) - augmentare pt. dep. functionale:

Daca X Y, atunci X Z Y Z.

(A3) - tranzitivitate pt. dep. functionale:

Daca X Y si Y Z, atunci si X Z.

(A4) - complementare pentru dep. multivalorice:

Daca X Y, atunci X U-(X Y) ,

unde U-(X Y) este atributul complementar lui Y in raport cu atributul X (aceasta regula deriva din caracterul simetric al dependentelor multivalorice)

(A5) - augmentare pentru dep. multivalorice:

Daca X Y, si V W, atunci W X W Y.

(A6) - tranzitivitate pt. dep. multivalorice:

Daca X Y si Y Z, atunci X Z-Y.

(A7) - Daca X Y atunci X Y (orice dependenta functionala este in acelasi timp si o dependenta multivalorica)

(A8) - Daca X Y, Z Y si pt. W disjunct fata de Y avem: W Z, atunci X Z.

OBS1: Aceste axiome extind setul de axiome date pentru dependenta functionala, constituind un set complet si sigur de reguli de inferenta, adica permit deducerea tuturor dependentelor functionale si multivalorice care sunt logic deductibile din setul initial de dependente <==> orice relatie care satisface setul initial de dependente va satisface de asemenea orice dependenta din inchiderea tranzitiva a acestui set.

OBS2: Axiomele (A5) si (A6) pun in legatura dependentele functionale cu cele multivalorice.

Descompunerea Schemelor de Relatie

Conventie:

Schema de Relatie == Multimea atributelor relatiei

R(A₁, A₂,, A_n) echivalent cu R =

Def. 1: Descompunerea unei Scheme de Relatie R = inseamna inlocuirea acesteia printr-o colectie r

de submultimi ale lui R , a.i.

R = R₁ R₂ R_k

unde R₁, R₂,, R_k nu sunt neaparat disjuncte.

OBS.1: Printr-o astfel de descompunere se realizeaza o separare a continutului de informatie din relatia initiala a.i. fiecare din schemele de relatie rezultate sa reprezinte un singur tip de entitate sau o legatura intre doua tipuri de entitati.

OBS.2: Numai o parte dintre descompunerile de acest tip au proprietatea ca din relatiile corespunzatoare schemelor descompunerii se poate reconstitui relatia initiala; pt. o astfel de reconstituire se foloseste operatorul de cuplare.

Def. 2: Descompunere echivalenta a relatiei R, notata cu r

Descompunerea r a relatiei R este echivalenta cu relatia R daca satisface urmatoarele doua proprietati:

cuplare fara pierdere de informatie ( lossless join property )

conservarea dependentelor ( dependency preservation )

(1) Cuplarea fara pierdere de informatie (LJP) = proprietatea unei descompuneri de a conserva continutul de informatie al oricarei relatii asupra careia se aplica aceasta descompunere.

Formalizarea matematica:

Fie R o schema de relatie descompusa in schemele R₁, R₂, , R_k.

Aceasta descompunere are proprietatea LJP daca pt. orice relatie r reprezentand valoarea actuala a relatiei R, avem:

r = P_R1(r) P_R2(r) P_Rk(r)

( deci r este rezultatul cuplarii proiectiilor sale dupa schemele de relatie

R₁, R₂, , R_k

Caz particular: Teorema lui ULLMAN

Fie r = o descompunere a schemei de relatie R. In acest caz particular, r conctituie o descompunere fara pierdere de informatie in raport cu un set dat de dependente functionale initiale, daca in urma descompunerii obtinem una din urmatoarele dependente functionale:

(R₁ R₂ (R₁- R₂ ),

(R₁ R₂ (R₂ - R₁) .

COROLAR:

Daca intersectia celor doua proiectii ale unei descompuneri, R₁ R₂ este sau contine o cheie a uneia dintre componentele R₁ sau R₂ , atunci descompunerea este fara pierdere de informatie. Acest lucru se verifica prin existenta cel putin uneia din dependentele:

(R₁ R₂ R₁ (R₁ - R₂ ),

(R₁ R₂ R₂ (R₂ - R₁ ).

OBS:

Proprietatea de conservare a informatiei depinde nu numai de descompunerea r , ci si de setul initial de dependente functionale existente in schema de relatie R.

(2) Conservarea dependentelor (DP) = proprietatea unei descompuneri de a permite deducerea tuturor dependentelor din relatia initiala pe baza dependentelor existente in descompunere.

Formalizarea matematica:

Fie R o schema de relatie si r o descompunere a sa:

o parte dintre dependentele functionale existente in R se vor regasi in cadrul schemelor de relatie R_i din descompunerea sa

dependentele care implica atribute din componente diferite R_i si R_j ale descompunerii nu vor fi regasite in cadrul schemelor individuale R_i, ca atare se pierd.

Obs: Proprietatea DP este importanta d.p.d.v. al integritatii bazei de date, deoarece dependentele din cadrul unei scheme de relatie R pot fi privite ca si constrangeri de integritate a datelor din cadrul schemei.

FN1: Forma Normala 1.

Def: O relatie R este in forma normala FN1 ddaca toate atributele sale iau numai valori atomice. (valori atomice = valori care nu pot fi descompuse in elemente constitutive mai fine; ex: atributul Adresa nu are valoare atomica).

Obs: Conditia ca o relatie sa se afle in FN1 impune ca domeniile pe care se definesc atributele relatiei R sa contina doar elemente atomice <== > toate tuplele unei relatii au acelasi numar de campuri, cu aceeasi dimensiune

FN2: Forma Normala 2.

Def: O relatie R este in forma normala FN2 daca este in FN1 si orice atribut neprim este total dependent fata de orice cheie a relatiei.

FN3: Forma Normala 3.

Def: O relatie R este in forma normala FN3 daca este in FN2 si nici un atribut neprim nu este functional dependent fata de un alt atribut neprim al relatiei.

Forma Normala BOYCE - CODD FNBC

Def: O relatie R este in forma normala FNBC daca pentru orice dependenta functionala X A din cadrul relatiei R, unde A este un atribut care nu face parte din X, atributul X (care poate fi si un atribut compus) este o cheie in R sau include o cheie din R

OBS: O relatie care este in FNBC, se afla si in FN3, FN2 si FN1.

Dependenta Multivalorica (v. detaliile la pag. 9) si Forma Normala FN4:

Def: O relatie R este in forma normala FN4 daca oricare ar fi dependenta multivalorica X Y, unde Y nu este un subset al lui X si X Y nu contine toate atributele lui R, atunci atributul simplu sau compus X este o cheie sau contine o cheie a lui R

DEPENDENTA DE CUPLARE. FORMA NORMALA FN5:

OBS1: Rezolvarea neredondantei datelor in contextul bazei de date necesita analiza atat a dependentelor functionale si multivalorice, cat si a asa-numitor dependente de cuplare.

Def:

Fie R(A₁, A₂, , A_n) o schema de relatie si R₁, R₂, , R_k submultimi ale multimii . Spunem ca exista o dependenta de cuplare , notata cu *( R₁, R₂, , R_k), ddaca orice instantiere r a lui R este rezultatul cuplarii proiectiilor sale pe R₁, R₂, , R_k

< = = >    r = P_R1(r) P_R2(r) P_Rk(r)

Def. echivalenta:

*( R₁, R₂, , R_k) este o dependenta de cuplare pe R ddaca descompunerea lui R dupa componentele R₁, R₂, , R_k este fara pierdere de informatie.

OBS2: Dependentele multivalorice sunt cazuri particulare de dependente de cuplare.

Transcriere matematica: Orice relatie R(X,Y,Z) care satisface dependentele multivalorice X Y si X Z satisface si dependenta de cuplare *(XY,XZ).

FORMA NORMALA FN5:

Def: O relatie R este in forma normala FN5 ddaca toate dependentele de cuplare existente in relatie sunt implicate de o cheie a acesteia.

OBS3:

Forma normala FN5 este o generalizare a formei normale FN4, avand ca punct de pornire conceptul de dependenta de cuplare

Procesul de trecere a unei relatii in forma normala FN5 :

eliminarea dependentelor de cuplare din cadrul relatiei, impreuna cu anomaliile pe care le cauzeaza

selectarea in acest scop a dependentelor de cuplare care prezinta interes d.p. de vedere al generarii de redondante

Ex. de dependente de cuplare care nu conduc la redondanta in memorarea datelor si, ca atare nu cauzeaza anomalii: dependentele de cuplare cauzate de o cheie a relatiei.

CONCLUZII privind NORMALIZAREA RELATIILOR:

FN1 - se obtine prin atomizarea tuturor atributelor relatiei

FN2 = FN1 + eliminarea tuturor dependentelor functionale partiale ale atributelor neprime in raport cu orice cheie a relatiei

FN3 = FN2 + eliminarea tuturor dependentelor functionale dintre toate atributele neprime ale relatiei

FNBC = eliminarea tuturor dependentelor functionale fata de atribute care nu sunt chei sau nu contin o cheie.

DEFINITIE GLOBALA PT. FNBC FN4 si FN5

O relatie este in FNBC (respectiv FN4 sau FN5) ddaca singurele dependente functionale (respectiv multivalorice sau de cuplare) existente sunt cele implicate de o cheie a relatiei R.

OBS: Orice dependenta intre atributele unei relatii, indiferent de tipul acesteia (functionala, multivalorica sau de cuplare), este producatoare de redondante si anomalii, doar atunci cand nu este implicata de o cheie a relatiei.