cap6_normalizarea_relatiilor

Prof. Felicia Ionescu Cap. 6 - Normalizarea relatiilor 1

CapitolulCapitolul 6:6: NormalizareaNormalizarea relatiilorrelatiilor

Dependentele de date si formele normale ale relatiilor Redundanta datelor si anomaliile de actualizare a relatiilor Dependentele functionale (DF)

Tipuri de DF Multimi de DF DF si cheile relatiilor

Descompunerea relatiilor Descompunere fara pierdere de informatie la jonctiune Descompunere cu conservarea DF

Formele normale ale relatiilor determinate de DF: FN1 FN2 FN3 FNBC

Dependente multivalorice forma normala FN4 Dependente de jonctiune forma normala FN5


DependenteleDependentele de datede date Dependenele de date (data dependencies) reprezint constrngeri care se

impun valorilor atributelor unei relaii i care determin proprietile relaiei nraport cu operaiile de inserare, tergere i actualizare a tuplurilor.

O form normal a unei relaii (normal form) presupune anumite condiii pecare le ndeplinesc valorile atributelor i dependenele de date definite peacea relaie

Dependentele de date: Dependente functionale: E.F. Codd a propus trei forme normale: FN1, FN2, FN3;

apoi a fost introdus forma normal Boyce-Codd (FNBC) Dependenelor multivalorice: forma normala 4 (FN4) Dependenelor de jonciune: forma normala 5 (FN5)

Formele normale ale relaiilor formeaz o colecie ordonat (FN1, FN2, FN3, FNBC, FN4, FN5), i ele impun condiii din ce n ce mai restrictive asupradependenelor de date

Ordonarea formelor normale de la FN1 la FN5 nseamn c orice relaieaflat n FN2 este n FN1, orice relaie n FN3 este n FN1 i FN2 etc.

Normalizarea relaiilor (normalization) const n descompunerea lor, astfelnct relaiile s fie in forme normale ct mai avansate


RedundantaRedundanta datelordatelor sisi anomaliileanomaliile de de actualizareactualizare

IdAngajat Nume Prenume Adresa IdProiect Ore

1 Ionescu Ion Bucuresti P1 100

2 Popescu Petre Ploiesti P1 80

3 Marinescu Marin Craiova P3 200

1 Ionescu Ion Bucuresti P2 100

2 Popescu Petre Ploiesti P3 120

In relatia AP, cu cheia primara PK={IdAngajat, IdProiect} sunt valoriredundante ale atributelor: Nume, prenume, Adresa Anomalii de inserare: nu se pot introduce date despre un angajat (numele,

prenumele, adresa) dac nu exist cel puin un proiect la care acesta s lucreze Anomalii de tergere: dac se terg toate tuplurile referitoare la un anumit

proiect, se pot pierde toate datele referitoare la acei angajai care lucreaz doar la proiectul respectiv

Anomalii de actualizare: dac se modific ntr-un tuplu valoarea unuia din atributele care au valori redundante, starea relaiei poate deveni inconsistent


EliminareaEliminarea anomaliiloranomaliilor datoratedatorate redundanteiredundantei Eliminarea anomaliilor provocate de redundanta datelor se poate face:

Fie prin prevederea unor proceduri stocate (sau triggere) care sa verificecorectitudinea fiecarei operatii de actualizare a relatiilor

Fie prin descompunerea relatiilor care prezinta redundante in relatii mai simple; exemplu: descompunerea relatiei AP in 2 relatii, A si P

A P

IdAngajat Nume Prenume Adresa IdAngajat IdProiect Ore

1 Ionescu Ion Bucuresti 1 P1 100

2 Popescu Petre Ploiesti 2 P1 80

3 Marinescu Marin Craiova 3 P1 200

1 P2 100

2 P2 120

Relatiile A si P au un grad de normalizare mai ridicat si nu mai au anomalii Dar unele interogari sunt mai ineficiente in A si P decat in APz Exemplu: Care este numrul de ore lucrate de Ionescu la proiectul P1 ?:

Q1 = Ore Nume ='Ionescu' AND IdProiect ='P1 (AP)Q2 = Ore Nume ='Ionescu' AND IdProiect ='P1 (A P)


DependenteDependente functionalefunctionale (1)(1) Dependentele funcionale (functional dependencies) sunt constrangeri in

relatii, prin care valoarea unui anumit set de atribute determina in mod unicvaloarea altor atribute

Fie R o schema de relatie si doua submultimi ale atributelor sale:X R and Y R . Dependenta functionala (DF) X Y

exista in R daca si numai daca pentru orice stare a relatiei r(R), egalitateavalorilor atributelor X din doua tupluri t1 si t2 din r (t1 r si t2 r) implicaegalitatea valorilor atributelor Y din acele tupluri, adica:

t1[X] = t2 [X] t1[Y ] = t2 [Y ] Atributul din stnga se numete determinant, cel din dreapta, determinat Dependentele functionale sunt generalizarea notiunilor de chei ale relatiilor:

orice cheie determina o DF in acea relatie Daca Y = R, atunci X este o cheie a relatiei Reciproc, daca X este o cheie, Y = R (X R) In acest caz t1[X] = t2 [X] t1 = t2 ,dar, cum intr-o relatie nu pot exista doua

tupluri identice, rezulta ca t1 si t2 sunt unul si acelasi tuplu

Cheile relaiilor: se pot preciza explicit (i atunci ele implic DF corespunztoare) pot fi deduse din mulimea DF stabilite de proiectant, folosind diferiti algoritmi


DDependenependenee funcfuncionaleionale (2)(2) O multime F de dependente functionale in R defineste constrangerile

pe care trebuie sa le respecte orice relatie r(R) pentru a fi legala(corecta) Se spune ca F se mentine in R daca toate relatiile legale pe R ( r(R))

satisfac multimea de dependente functionale F Reciproc, o relatie r este legala in raport cu o multime de dependente

functionale F, daca r satisface F

Proiectantul bazei de date specific acele DF pe care le doreste s fie respectate i care sunt evidente din punct de vedere semantic;

De exemplu, n relaia AP se pot defini DF: a) IdAngajat Nume(b) IdAngajat Prenume(c) IdAngajat Adresa(d) {IdAngajat, IdProiect} Ore

Primele 3 impun ca un identificator IdAngajat s identifice un singur angajat, iar ultima impune ca un angajat efectueaz un anumit numar de ore la fiecare din proiectele la care lucreaz


TipuriTipuri de de dependendependenee funcfuncionaleionale Atributele care aparin unei chei se numesc atribute prime, iar celelalte

se numesc atribute neprime Dependene funcionale triviale si ne-triviale

O dependenta functional este trivial daca este satisfacuta de orice stare a relatiei; in general X Y este triviala daca Y este o submultime (proprie sau nu) a lui X, adic Y X; ex. {IdAngajat, IdProiect} IdAngajat sauNume Nume

Celelalte dependente (in care Y nu este o submultime a lui X) sunt ne-triviale; ex: IdAngajat Nume

Dependenele funcionale pariale si totale O dependen funcional X Y este parial dac exist o submulime

proprie Z a lui X (Z X i Z X) care determin funcional pe Y (Z Y); ex: {IdAngajat,IdProiect} Nume este partiala deoarece IdAngajat Nume

O dependen funcional X Y este total, dac nu exist nici o submulime proprie Z a lui X care s determine funcional pe Y

Cazuri particulare: dac atributul X este simplu, dependena funcional X Y este total;

ex: IdAngajat Nume dac X este o cheie candidat a lui R, atunci dependena X Y este total;

ex: {IdAngajat, IdProiect} Ore


MultimiMultimi de de dependentedependente functionalefunctionale (1)(1) Dintr-o mulime dat de DF se pot deduce si alte DF, folosind

regulile de deducere (inferen - inference rules) ale lui Armstrong: 1. Reflexivitatea (reflexivity): dac Y X, atunci X Y; prin

aceast regul se deduc DF triviale; de ex. n relaia AP n care au fost definite DF:

(a) IdAngajat Nume(b) IdAngajat Prenume(c) IdAngajat Adresa(d) {IdAngajat,IdProiect} Ore

se pot deduce prin reflexivitate si DF:(e) {IdAngajat, IdProiect} IdAngajat(f) {IdAngajat, IdProiect} IdProiect

2. Augmentarea (augmentation): dac X Y, atunci (X Z) (Y Z); urmtoarele DF (g i h) sunt deduse prin augmentare, pornind de la dependenele funcionale (a) i respectiv (b), augmentate cu Z = {Nume}, respectiv Z = {Prenume} (se stie ca Nume Nume = Nume etc.)

(g) {IdAngajat, Nume} Nume(h) {IdAngajat, Prenume} Prenume


MultimiMultimi de de dependentedependente functionalefunctionale (2)(2) 3. Tranzitivitatea (transitivity): dac XY i YZ, atunci XZ. De

exemplu, din DF (e) i (a) rezult:{IdAngajat,IdProiect} Nume

Aceste trei reguli sunt suficiente pentru calculul tuturor dependenelor funcionale pe care le implic o mulime dat de DF

Din aceste reguli de baz se pot deduce i alte reguli; de exemplu: Proiecia (projection): dac X(Y Z), atunci XY i XZReuniunea (union): dac XY i XZ, atunci X(Y Z)Pseudo-tranzitivitatea (pseudo-transitivity): dac XY i (W Y) Z, atunci

(W X) Z. Reprezentarea dependentelor functionale:

IdAngajat

IdProiect

Nume

Prenume

Adresa

Ore


InchidereaInchiderea uneiunei multimimultimi de DF de DF Fiind dat o mulime F de DF, mulimea tuturor DF care sunt implicate de F

se numete nchiderea mulimii F (closure set of F) i se noteaz F+

F+ se poate deduce prin aplicarea repetat a regulilor de inferen asupra DF din F

Pentru a testa daca o DF XY poate fi dedus dintr-o mulime F de DF, se aflanchiderea F+ a mulimii F i se testeaz dac (XY)F+

Dou mulimi de DF, E i F sunt echivalente dac nchiderile lor sunt egale(E+ = F+); adica: DF E DF F+ i DF F DF E+

O mulime G de DF este minim dac satisface urmtoarele condiii: membrul drept al oricrei DF din G este un atribut simplu;

orice dependen funcional din G este total;

mulimea G este ireductibil, adic, dac se exclude o DF din G, mulimea rezultat H nu este echivalent cu G (adic H+ G+).

Acoperirea minim a unei mulimi F de DF (minimal cover of a set F of DFs) este o mulime minim de dependene funcionale G care este echivalent cu F, adic G+ = F+

Pot exista mai multe acoperiri minime ale unei mulimi de DF


DependenDependeneleele funcfuncionaleionale ii cheilecheile relarelaiiloriilor In orice relaie pot exista dou categorii de DF:

DF determinate de cheile (candidate) ale relaiei; astfel de DF nu produc redundana datelor i nici anomalii de actualizare a relaiei; de ex. {IdAngajat, IdProiect} Ore

DF n care atributul determinant nu este o cheie a relaiei; astfel de DF produc redundana datelor i anomalii de actualizare a relaiei; de ex. IdAngajat Nume

DF determinate de cheile candidate sunt constrngeri implicite, coninute n definiia relaiei i sunt verificate i impuse automat de SGBD Proiectantul bazei de date nu trebuie s prevad nimic suplimentar pentru ca aceste

constrngeri s fie satisfcute de orice stare a relaiei

DF n care atributul determinant nu este o cheie sunt constrngeri explicite, care nu sunt verificate i nici impuse de SGBD

Pentru DF n care atributul determinant nu este o cheie, se aplica una din urmatoarele solutii:

(a) Se accepta astfel de DF, dar se asigura verificarea i impunerea lor procedurala, prin triggere, proceduri stocate, sau funcii n programele de aplicaii

(b) Se descompune relatia in relatii mai simple, in care nu mai exista astfel de DF, dartrebuie fcut o descompunere corecta (cel puin fr pierdere de informaie la jonciune sau, dac se poate, reversibil)


InchidereaInchiderea unuiunui atributatribut fatafata de o de o multimemultime de DFde DF (1)(1) nchiderea unui atribut fa de o mulime F de DF (the closure of an

atribute under F). Fie un atribut X al unei relaii pe care este definit mulimea F de DF; mulimea X+ a tuturor atributelor determinate de X (XX+) se numete nchiderea lui X n raport cu F

Algoritmul prin care se poate deduce inchiderea unui atribut:1. se seteaz X+ = X i P_F = F2. repet

se extrage o DF YZ din P_F (adica se alege o DF YZ din P_F si se seteaza P_F = P_F (YZ) )

dac Y X+ atunci X+ = X+ Z pn cnd P_F =

Se aplic acest algoritm pentru dependenele funcionale din relatia AP:FAP = {IdAngajat Nume, IdAngajat Prenume, IdAngajat Adresa,

{IdAngajat, IdProiect} Ore} Se obtin inchiderile atributelor astfel:

{IdAngajat}+ = {IdAngajat, Nume, Prenume, Adresa}{IdAngajat, IdProiect}+ = {IdAngajat, IdProiect, Nume, Prenume, Adresa, Ore}{Nume}+ = {Nume}, {Prenume}+ = {Prenume}, {IdProiect}+ = {IdProiect}; {Adresa}+ = {Adresa}, {Ore}+ = {Ore}


InchidereaInchiderea unuiunui atributatribut fatafata de o de o multimemultime de DFde DF (2)(2) Din algoritmul de mai sus se poate deduce c nchiderea unui atribut care

nu determin funcional nici un alt atribut (nu apare n partea stng a nici unei DF) este chiar atributul respectiv:

{Nume}+ = {Nume}, {Prenume}+ = {Prenume}, {Adresa}+ = {Adresa}, {Ore}+ = {Ore}

Acest algoritm poate fi folosit pentru a verifica dac o DF dat XY este consecina logic a mulimii F (daca (XY) F+) Pentru aceasta, se calculeaz X+ fa de F; dac Y X+, atunci (XY) F+, deci

XY este consecina logic a lui F Acest algoritm poate fi folosit i pentru a verifica dac un atribut K (simplu

sau compus) este supercheie a relaiei R cu mulimea F de DF Pentru aceasta se calculeaz K+ n raport cu F; daca K+ = R, atunci K este

supercheie n R

Pentru aflarea cheilor candidate ale unei relaii din mulimea DF: se consider o supercheie a relaiei se testeaza condiia de ireductibilitate pentru fiecare din atributele componente

ale supercheii si se elimin orice atribut care poate fi eliminat fr s se piard proprietatea de unicitate a cheii

Acest algoritm de aflare a cheilor candidate ale unei relaii din mulimea DF este prezentat in continuare


AflareaAflarea cheilorcheilor uneiunei relarelaiiii din din multimeamultimea DFDF Fiind dat o relaie cu schema R i mulimea F a DF pe aceast relaie, cheile

candidate K ale relaiei se pot afla cu urmatorul algoritm:1. Se seteaz supercheia K = R 2. Pentru fiecare atribut X din K se testeaza daca (K X) este supercheie n R3. Dac (K X) este supercheie, atunci K = (K X), altfel K nu se modifica

Prin parcurgerea repetat a pailor 2 i 3, se gsete una din cheile candidate ale relaiei; dac exist mai multe chei candidate, atunci ordinea gsirii cheilor candidate depinde de atributul selectat n pasul 2 al algoritmului

De exemplu, se aplic algoritmul de mai sus pentru gsirea unei chei candidate a relaiei AP cu mulimea FAP a DF (definita la inceputul capitolului)

Se pornete cu K = R = {IdAngajat, Nume, Prenume, Adresa, IdProiect, Ore}, se selecteaz X = Nume; {K X} = {IdAngajat, Prenume, Adresa, IdProiect, Ore} {K X}+ = {IdAngajat, Nume, Prenume, Adresa, IdProiect, Ore} = R, deci K - X este supercheie in R, deci se repet paii 2 i 3 pentru alte atribute

Se repeta pasii 2 si 3 pentru X = Prenume, apoi X = Adresa si X = Ore; acesteatribute pot fi eliminate, si se obtine K = {IdAngajat, IdProiect}

Atributele IdProiect, IdAngajat nu se pot elimina din K, deci {IdProiect, IdAngajat} e cheie candidat (chiar primar)


DescompunereaDescompunerea relatiilorrelatiilor O descompunere D = {R1, R2,..Ri,...Rk} a schemei de relaie R (relation

schema decomposition) este format din submulimi proprii ale lui R (R1 R, R2 R,Rk R a caror reuniune este egala cu R (R = R1 R2 Rk)

Proiectiile relatiei r(R) pe submultimile R1, R2,...Ri, Rk (r1 = R1(r), r2 = R2(r), .. ri = Ri(r), rk = Rk(r)) reprezinta descompunerea relaiei r(R) pe aceste submulimi de atribute

Fie o relaie cu schema R i mulimea F de DF ale acesteia; o descompunere a relaiei r(R) este reversibil dac are proprietile de: Conservarea informatiei (descompunere fr pierdere de informaie la jonciune)

inseamna ca r = r1 r2 ri rk Conservarea dependenelor funcionale: dac oricare din dependenele din F se

regsete sau poate fi dedus din DF ale relaiilor cu schemele R1,R2,...Ri,Rk

Teorema lui Ullman. Descompunerea D = {R1, R2} a unei scheme de relaieR este o descompunere fr pierdere de informaie la jonciune n raport cu mulimea F de DF, dac i numai dac este ndeplinit una din condiiile: (a) ((R1 R2) (R1 - R2)) F+, sau (b) ((R1 R2) (R2 - R1)) F+ Dac R1 R2 este o supercheie a uneia dintre relaiile R1 sau R2, atunci

descompunerea este fr pierdere de informaie la jonciune; Demonstratie: dac (R1 R2) este o supercheie n R1, atunci ea determina functional

orice submultime de atribute din R1, inclusiv (R1 - R2) adic (R1 R2) (R1 - R2); La fel se demonstreaza daca (R1 R2) este o supercheie n R2


Descompunere Descompunere ffrr pierdere de informapierdere de informaieie la jla jonctiuneonctiune Lipsa acestei proprieti se manifest n mod paradoxal prin apariia unor

tupluri noi (parazite) n relaia obinut prin jonciunea relaiilor r1,r2,...ri,...rk, tupluri care nu existau n relaia r(R)

Exemplu: descompunerea relaiei AP n relaiile A i P:A P = {IdAngajat}, A P = {Nume,Prenume,Adresa}; P A = {IdProiect,Ore}

Din DF IdAngajatNume, IdAngajatPrenume, IdAngajat Adresa Se deduce: IdAngajat{Nume, Prenume, Adresa} (cf. regulii de reuniune a DF) Rezult: ((A P)(A P)) F+Deci, conform teoremei lui Ullman desc. este fr pierdere de informaie la jonciune

Descompunerea succesiv fr pierdere de informaie la jonciune Dac o descompunere D = {R1,R2,...Ri,...Rk} a unei scheme R este fr pierdere

de informaie la jonciune n raport cu mulimea F de DF i D1 = {Q1,Q2,...Qm} este o descompunere fr pierdere de informaie la

jonciune a lui R1 n raport cu proiecia lui F pe R1, atunci descompunerea D2 = {Q1,Q2,...Qm,R2,...Rk} este o descompunere fr

pierdere de informaie a lui R n raport cu F

Aceast proprietate permite descompunerea fr pierdere de informaie la jonciune a unei relaii n mai multe etape (mai nti in dou relaii, apoifiecare dintre acestea se descompune n alte dou relaii, .a.m.d)


ConservareaConservarea dependendependenelorelor funcfuncionaleionale O descompunere D = {R1, R2, ...Ri,...Rk} a unei scheme de relaie R prezint

proprietatea de conservare a mulimii F de DF, dac reuniunea proieciilor lui F pe schemele de relaii Ri (unde 1 i k) este echivalent cu F, adic: ((R1(F)) (R2(F)) ... (Rk(F)))+ = F+

Proiecia unei mulimi de dependene funcionale. Fiind dat mulimea Fde DF definite pe R, i o descompunere D = {R1,R2,..Rk} a lui R, proiecia lui F pe Ri (unde 1 i k), notat Ri(F), este mulimea de DF XY F+, astfel nct X Ri i Y Ri

Exemplu: descompunerea relaiei AP in relaiile A i P:FAP = {IdAngajatNume, IdAngajatPrenume,

IdAngajatAdresa,{IdAngajat,IdProiect}Ore}Proieciile mulimii FAP pe A si P sunt:A(FAP) = {IdAngajatNume, IdAngajatPrenume, IdAngajatAdresa}P(FAP) = {{IdAngajat,IdProiect}Ore}

Dat fiind c A(FAP) P(FAP) = FAP, rezult c aceast descompunere conserv DF Dac, prin descompunerea unei relaii, se pierd una sau mai multe DF, pentru

verificarea lor, trebuie s se efectueze mai nti jonciunea relaiilor obtinute Cele dou proprieti ale unei descompuneri, conservarea informaiei i

conservarea dependenelor funcionale, sunt independente


FormeleFormele normalenormale ale ale relatiilorrelatiilor (FN1 (FN1 sisi FN2)FN2) O relaie este normalizat n prima form normal (FN1) dac fiecare atribut

ia numai valori atomice i scalare din domeniul su de definiie Sistemele SGBD relaionale nu admit relaii care s nu fie cel puin n FN1, dar

proiectarea relaiilor normalizate n FN1 este intotdeauna posibila Fie o schema de relatie R si multimea F de DF definite pe aceasta. O relaie

r(R) este normalizat n FN2, dac este n FN1 i dac n F+ nu exist nici o DF parial a unui atribut neprim fa de o cheie a relaiei

Exemplu: relatia AP cu multimea FAP de DF este in FN1, dar nu este in FN2:FAP = {IdAngajat Nume, IdAngajat Prenume,

IdAngajat Adresa, {IdAngajat, IdProiect} Ore} Cheia primara este {IdAngajat, IdProiect}, deci {IdAngajat, IdProiect}Nume Aceast DF se poate deduce din FAP; cf. reflexivitatii, {IdAngajat, IdProiect}

IdAngajat; cf.tranzitivitatii, daca IdAngajatNume, {IdAngajat, IdProiect}Nume DF {IdAngajat, IdProiect}Nume este parial deoarece exista: IdAngajatNume Rezult c relaia AP nu este n FN2, deci prezinta redundante si anomalii

Anomaliile se pot evita prin (a) normalizare sau (b) prin impunerea DF Normalizarea relatiei AP prin descompunere in relatiile A si P:

A(IdAngajat, Nume, Prenume, Adresa) P(IdAngajat, IdProiect, Ore), S-a demonstrat ca aceasta descompunere prezinta proprietatile de jonctiune fara

pierdere de informatie si conservarea DF si se poate arata ca A si P sunt in FN2


ImpunereaImpunerea DF in DF in relatiarelatia nenormalizata nenormalizata AP (1)AP (1) Dac relaia AP nu se normalizeaz, atunci trebuie s se prevad proceduri

speciale care s impun DF care nu sunt determimate de chei De exemplu, daca la inserare nu se admit doi sau mai muli angajai cu acelasi

identificator (IdAngajat) dar cu nume, prenume, adres diferite se defineste urmatorul trigger (trigger_AP)

Trigger-ul trigger_AP arata astfel:DELIMITER $$ DROP TRIGGER IF EXISTS `normalizare`.`trigger_AP`$$ CREATE TRIGGER `trigger_AP` BEFORE INSERT ON `normalizare`.`AP` FOR EACH ROW BEGIN DECLARE done INT DEFAULT 0;

DECLARE error INT DEFAULT 0; DECLARE l_nume, l_prenume, l_adresa VARCHAR(20);DECLARE cursor_AP CURSOR FOR SELECT Nume, Prenume, Adresa FROM AP

WHERE IdAngajat = NEW.IdAngajat;DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;OPEN cursor_AP;REPEAT FETCH cursor_AP INTO l_nume, l_prenume, l_adresa;

IF NEW.Nume l_nume OR NEW.Prenume != l_prenume OR NEW.Adresa l_adresaTHEN SET error = 1; END IF;

UNTIL done = 1 OR error = 1END REPEAT; CLOSE cursor_AP;IF error = 1 THEN SET NEW.IdAngajat = NULL;

END IF;END $$ DELIMITER ;


ImpunereaImpunerea DF in DF in relatiarelatia nenormalizata nenormalizata AP(2)AP(2) Trigger-ul este de tip BEFORE INSERT, astfel ca linia dorita se insereaza in

tabel numai daca verificarile facute de trigger permit inserarea

In trigger se citesc intr-un cursor toate liniile care au valoarea atributului IdAngajat egal cu valoarea de inserat (NEW.IdAngajat)

Se parcurg liniile cursorului si daca valorile de inserat ale atributelor Nume, Prenume, Adresa (NEW.Nume, NEW.Prenume, NEW.Adresa) difera de celeexistente in tabel, se seteaza error = 1. Daca dupa parcurgerea cursorului: error = 0, se termin triggerul (instructiunea END), apoi se introduce linia noua error=1, se seteaza SET NEW.IdAngajat = NULL, apoi se termin triggerul

(instructiunea END); dup aceasta SGBD-ul nu va introduce linia noua deoarece un atribut al cheii primare este NULL (IdAngajat)

Exemplu: Fie tabelul AP cu liniile (1,Ionescu,Ion, Bucuresti,1,50), (1,Ionescu,Ion,

Bucuresti,2,100) si (1,Ionescu,Ion,Bucuresti,3,80)

Se observa redundanta datelor: valorile Ionescu, Ion, Bucuresti sunt memorate pentru fiecare proiect la care lucreaza angajatul cu IdAngajat = 1

Anomalia de inserare: daca nu se activeaza trigger-ul, se poate insera si linia(1,Marinescu,Mihai,Bucuresti,4,60), ceea ce inseamna ca angajatul cu IdAngajat =1 este nedeterminat (este Ionescu Ion sau Marinescu Mihai?)

Aceasta linie nu se poate insera daca s-a activat trigger-ul trigger_AP


A A treiatreia forma forma normalanormala (FN3)(FN3) Fie o schema de relatie R si multimea F de DF definite pe aceasta. O relaie

r(R) este normalizat n FN3, dac este n FN2 i dac oricare DF din F+ a unuiatribut neprim este determinata de o cheie a relatiei

Exemplu: AFS(IdAngajat, Nume, Prenume, Adresa, Functie, Salariu)FAFS={IdAngajatNume, IdAngajatPrenume, IdAngajat Adresa,

IdAngajatFunctie, FunctieSalariu}. Cheia primar a relaiei este IdAngajat, i poate fi dedus din FAFS DF fa de cheia primar (primele patru DF) sunt totale, deci relaia este n FN2 Relaia nu este n FN3 datorita DF FunctieSalariu; prezinta redundante si anomalii

Normalizare prin descompunere in: AF(IdAngajat, Nume, Prenume, Adresa, Functie) FS(Functie, Salariu)

Se demonstreaza ca AF si FS sunt in FN3 si ca descompunerea este reversibila Proiectiile multimii FAFS:

FAF={IdAngajatNume,IdAngajatPrenume,IdAngajat Adresa,IdAngajatFunctie}FFS = {FunctieSalariu} si se deduc (sau se verifica) cheile relatiilor

PKAF={IdAngajat}, PKFS={Functie}, deci AF si FS sunt in FN3 FAF FFS = FAFS deci descompunerea conserva DF AF FS = {Functie} si ( Functie Salariu) FAFS, deci, cf. regulii lui Ullman,

descompunerea este fara pierdere de informatie la jonctiune


ImpunereaImpunerea DF in DF in relatiarelatia nenormalizata nenormalizata AFS (1)AFS (1) Dac relaia AFS nu se normalizeaz, atunci trebuie s se prevad proceduri

speciale care s verifice i s impun DF care nu sunt determinate de chei Se poate inlocui operatia de INSERT cu apelul unei proceduri stocate care

verifica mai intai valorile si executa INSERT numai daca acestea respecta DF

Procedura stocata pentru relatia AFS arata astfel: DELIMITER $$ DROP PROCEDURE IF EXISTS sp_AFS $$CREATE PROCEDURE `sp_AFS`(OUT error INT, s_id INT, s_nume VARCHAR(20), s_prenume

VARCHAR(20), s_adresa VARCHAR(20), s_functia VARCHAR(20), s_salariu DECIMAL) BEGIN DECLARE done INT DEFAULT 0;

DECLARE l_salariu DECIMAL;DECLARE cursor_AFS CURSOR FOR

SELECT Salariu FROM AFS WHERE Functia = s_functia;DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;SET error = 0; OPEN cursor_AFS;REPEAT FETCH cursor_AFS INTO l_salariu;

IF s_salariu l_salariu THEN SET error = 1; END IF;UNTIL done = 1 OR error = 1END REPEAT;CLOSE cursor_AFS;IF error = 0 THEN

INSERT INTO AFS VALUES (s_id, s_nume, s_prenume, s_adresa, s_functia, s_salariu);END IF;END$$ DELIMITER ;


ImpunereaImpunerea DF in DF in relatiarelatia nenormalizata nenormalizata AFS (2)AFS (2) Fie tabelul AFS care contine liniile: (1, Ionescu,Ion,Bucuresti,inginer,2000),

(2, Popescu,Petre,Craiova,inginer,2000)

Se observa redundanta datelor: valoarea salariului este memorata de fiecaredata pentru o functie anume, desi trebuie sa fie aceeasi (conform DF Functie Salariu)

Datorita redundantei pot apare anomalii: se poate insera linia (3, Mateescu,Viorel,Bucuresti,inginer, 2100), care este admis de SGBD, dei nu respect DF Functie Salariu: pentru functia inginer se admite si salariul 2000 si salariul 2100; (se sterge apoi linia inserata eronat, pentru ca ulterior sa functioneze bine procedura stocata)

Inserarea liniilor in tabelul AFS prin apelul procedurii stocate sp_AFS inlatura aceasta anomalii

De exemplu, la apelul procedurii stocate cu aceleasi valori: call sp_AFS(@error, 7, Mateescu', Irinel', 'Bucuresti','inginer', 2100);

select @error;

se obtine @error=1 si linia respectiva nu va fi introdusa in tabelul AFS


Forma Forma normalanormala BoyceBoyce--CoddCodd (FNBC) (FNBC) Fie schema de relatie R si multimea F de DF definite pe aceasta. O relaie

r(R) este n forma normal Boyce-Codd (FNBC) n raport cu F dac este n FN1 i dac orice DF netrivial din F+ este determinata de o cheie a relaiei

Este evident c o relaie n FNBC este n FN3, dar o relaie n FN3 poate sfie sau nu n FNBC

Exemplu: relaia EDP(IdElev, IdDisciplina,IdProfesor), cu cheia PK= {IdElev, IdDisciplina} i cu mulimea FEDP de DF:FEDP = {{IdElev,IdDisciplina}IdProfesor, IdProfesorIdDisciplina}

Se consider c relaia este n FN1; din FEDP se observ c nu exist DF pariale fa de cheia relaiei (deci relaia este n FN2) i nu exist nici o DF a unui atribut neprim fa de un alt atribut neprim, deci relaia este n FN3

Relaia EDP nu este n FNBC, datorit DF a atributului prim IdDisciplina fade atributul neprim IdProfesor; aceasta relatie prezint redundante de date i anomalii de actualizare

Exemplu: fie starea in care tabelul EDP contine liniile (1,1,1) si (2,1,1) redundanta: disciplina (1) predata de profesorul 1 este memorata de doua ori in

tuplurile (1,1,1) si (2,1,1)

anomalie de inserare: se poate insera si tuplul (1,2,1) care nu respecta DF IdProfesorIdDisciplina (profesorul 1 preda si disciplina 1 si disciplina 2)


ImpunereaImpunerea DF in DF in relatiarelatia nenormalizata nenormalizata EDP EDP Dac relaia EDP nu se normalizeaza, atunci trebuie s se prevad o

procedura care s verifice i s impun DF (IdProfesorIdDisciplina) care nueste determinata de cheia relatiei, pentru operatiile de INSERT si UPDATE

De ex: se inlocuieste operatia INSERTcu apelul unei proceduri stocate care verifica mai intai valorile si executa INSERT numai daca acestea respecta DFDELIMITER $$

DROP PROCEDURE IF EXISTS `sp_EDP`$$CREATE PROCEDURE `sp_EDP`(INOUT error INT, s_Elev INT, s_Disciplina INT, s_Profesor INT)BEGIN DECLARE done INT DEFAULT 0; DECLARE l_Disciplina INT;

DECLARE cursor_EDP CURSOR FOR SELECT IdDisciplina FROM EDP WHERE IdProfesor = s_Profesor;

DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;SET error = 0; OPEN cursor_EDP;REPEAT FETCH cursor_EDP INTO l_Disciplina;

IF s_Disciplina l_Disciplina THEN SET error = 1; END IF;UNTIL done = 1 OR error = 1END REPEAT; CLOSE cursor_EDP;IF error = 0 THEN INSERT INTO EDP VALUES (s_Elev, s_Disciplina, s_Profesor);END IF; END$$ DELIMITER ;

Pentru verificare: se sterge linia(1,2,1) (daca exista) si se executa: call sp_EDP(@error,1,2,1); select @error; se obtine @error = 1 si nu s-a inserat acest tuplu


NormalizareaNormalizarea relatieirelatiei EDPEDP Normalizarea relaiei EDP astfel nct relaiile obinute s fie n FNBC se

poate face prin descompunerea acesteia. Se pot ncerca trei descompuneri:D1 = {EP,PD}, unde EP = {IdElev, IdProfesor},

PD = {IdProfesor, IdDisciplina};

D2 = {ED,PD}, unde ED = {IdElev, IdDisciplin},PD = {IdProfesor, IdDisciplina};

D3 = {EP,ED}, unde EP = {IdElev, IdProfesor},

ED = {IdElev, IdDisciplina}.

Se poate observa c relaiile rezultate n oricare din aceste descompuneri sunt relaii n FNBC (fiind relaii formate din dou atribute).

Dintre cele trei descompuneri, descompunerea D1 prezint proprietatea de jonciune fr pierdere de informaie. ntr-adevr, EP PD = {IdProfesor}, PD EP = {IdDisciplina} i IdProfesorIdDisciplina, deci este ndeplinit condiia lui Ullman de conservare a informaiei.

Celelalte descompuneri, D2 i D3, nu ndeplinesc aceast condiie. In oricare din aceste descompuneri se pierde dependena funcional

{IdElev,IdDisciplina}IdProfesor, deci relaia EDP nu poate fi descompus n mod reversibil n relaii FNBC.


ImpImpunerea constrangerilor pierdute prin descompunere (1)unerea constrangerilor pierdute prin descompunere (1) Dac relaia EDP se normalizeaza prin descompunerea (EP, PD) atunci trebuie

s se prevad o procedura care s verifice i s impun constrangerea pierduta Se pot inlocui operatiile de INSERT in tabelele EP, PD cu apelul unei proceduri

stocate care verifica mai intai valorile si executa INSERT numai daca acestearespecta constrangerea: {IdElev, IdDisciplina} IdProfesorDELIMITER $$ DROP PROCEDURE IF EXISTS `sp_EP_PD`$$

CREATE PROCEDURE `sp_EP_PD`(OUT error INT, s_Elev INT, s_Disciplina INT, s_Profesor INT)BEGIN DECLARE done INT DEFAULT 0;

DECLARE l_Elev, l_Profesor, l_Disciplina INT; DECLARE cursor_EP_PD CURSOR FOR

SELECT IdElev, EP.IdProfesor, IdDisciplina FROM EP, PD WHERE EP.IdProfesor = PD.IdProfesor ;

DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;SET error = 0; OPEN cursor_EP_PD;REPEAT FETCH cursor_EP_PD INTO l_Elev, l_Profesor, l_Disciplina;

IF s_Elev = l_Elev AND s_Disciplina = l_Disciplina AND s_Profesor l_Profesor THEN SET error = 1; END IF;UNTIL done = 1 OR error = 1END REPEAT; CLOSE cursor_EP_PD;IF error = 0 THEN

INSERT INTO EP VALUES (s_Elev, s_Profesor);INSERT INTO PD VALUES (s_Profesor, s_Disciplina);

END IF; END$$ DELIMITER ;


ImpImpunerea constrangerilor pierdute prin descompunere (2)unerea constrangerilor pierdute prin descompunere (2) Procedura sp_EP_PD primete ca argumente un flag de eroare i valorile

celor trei atribute IdElev, IdDisciplin, IdProfesor care trebuie sa respecteconstrngerea {IdElev, IdDisciplina} IdProfesor

n aceast procedura se creeaz un cursor n care se ncarc rezultatul jonciunii naturale ntre relaiile EP i PD pe atributul comun IdProfesor

Pentru fiecare linie a rezultatului jonciunii EP PD se verific respectareaconstrngerii dorite, testnd valorile existente n linia respectiv cu noile valoricare urmeaz s fie introduse: daca aceast constrngere este respectat, atunci se execut dou instruciuni

INSERT, cate una in foiecare din tabelele EP si PD

daca aceast constrngere nu este respectat, nu se introduce nici o linie

Exemplu: daca tabelul EP contine linia (1,1) si tabelul (PD) contine linia (1,1), prin INSERT se pot introduce si valorile (1,1,2) pentru (IdElev, IdDisciplina, IdProfesor) adica liniile: (1,2) in EP si (2,1) in PD; dar aceste valori nu respecta constrangerea {IdElev, IdDisciplina} IdProfesor deoarece: in liniile existente (IdElev, IdDisciplina) = (1,1), iar IdProfesor = 1 in valorile de inserat (IdElev, IdDisciplina) = (1,1), iar IdProfesor = 2

In schimb apelul procedurii: call sp_EP_PD(@error, 1,1,2); select @error;produce @error=1 si nu se introduce nici o linie


DependenteDependente multivaloricemultivalorice O dependen multivaloric - DMV- (multivalued dependency) XY

specificat pe schema de relatie R = {X,Y,Z} stabilete urmtoarele constrngeri pe care trebuie s le respecte orice relaie r(R): dac exist dou tupluri t1 i t2 n r astfel ca t1[X] = t2[X]= x, atunci vor exista i tuplurile t3 i t4 cu urmtoarele proprieti:

t3[X] = t4[X] = t1[X] = t2[X] = x;

t3[Y] = t1[Y] = y1 i t4[Y] = t2[Y] = y2 ;t3[Z] = t2[Z] = z2 i t4[Z] = t1[Z] = z1 .

Datorit simetriei egalitilor de mai sus, rezulta c, dac ntr-o relaie cu schema R exist DMV XY, atunci exist i XZ, unde Z = R(XY)

O DF este un caz particular al unei DMV: DF XY este o DMV X Y cu restricia c unei valori a lui X i corespunde o singur valoare a lui Y

O relaie cu schema R este n a patra form normal (FN4) n raport cu o mulime F de DF i DMV dac este n FN1 i dac, pentru orice DMV netrivial XY din F+, X este cheie a relaiei r(R).

Asemnarea acestei definiii cu definiia FNBC: pentru FNBC se impun restricii DF, iar pentru FN4 se impun restricii DMV

Dac o schem de relaie respect condiia de FN4, atunci nseamn c ea respect i condiia de FNBC


DependenteDependente de de jonctiunejonctiune Fie o schema de relaie R i R1,R2,...Rk submulimi de atribute ale lui R,

unde R1 R2 ... Rk = R. Se spune c exist o dependen de jonciune(DJ) pe R, notat *(R1,R2,...Rk), dac i numai dac orice relaie r(R) este egal cu jonciunea proieciilor relaiei pe submulimile R1,R2,..Rk, adicr = R1(r) R2(r)... Rk(r).

Rezulta ca: *(R1,R2,...Rk) este o DJ pe R dac i numai dac descompunerea lui R n

proieciile pe R1,R2,...Rk este fr pierdere de informaie la jonctiune

Relaia r(R) este k-decompozabil fr pierdere de informaie dac exist o DJ*(R1,R2,...Rk)

Tipuri de DJ (dupa valoarea lui k): Cazul k = 1 reprezint o DJ trivial

Cazul k = 2 al unei DJ este o DMV; o DMV XY n relaia r(R) reprezint o DJ*(XY, XZ), unde Z = R(X Y).

In cazul k > 2, DJ nu mai sunt echivalente cu DMV

DJ sunt dificil de identificat i nu exist reguli de deducere (inferen) care s genereze toate DJ pornind de la o mulime dat

Datorit acestor aspecte, analiza DJ are un pronunat caracter intuitiv


Forma Forma normalanormala FN5FN5

O relaie cu schema R este n a cincea form normal (FN5) n raport cu o mulime F de dependene funcionale, multivalorice sau de jonciune daceste n FN1 i dac, pentru orice dependen de jonciune *(R1,R2,... Ri,...Rk) din F+, Ri (unde 1 i k) este o cheie a relaiei r(R)

Avnd n vedere faptul c o dependen multivaloric este un caz special de dependen de jonciune, iar o dependen funcional este un caz special de dependen multivaloric, se poate afirma c o relaie care este n FN5, esteimplicit n FN4, deci i n FNBC, .a.m.d.

S-a demonstrat c orice relaie poate fi transformat n relaii FN5 (sau FN4, sau FNBC) printr-o descompunere fr pierdere de informaie la jonciune, darnu se asigura conservarea tuturor DF

Conditiile de normalizare in FNBC, FN4 si FN5 se pot rezuma la faptul c ntr-o relaie normalizat nu exist dect dependene determinate de chei: O relaie este n FNBC dac orice DF este determinat de o cheie a relaiei O relaie este n FN4 dac orice DF sau DMV este determinat de o cheie a relaiei O relaie este n FN5 dac orice DF, DMV sau DJ este determinat de o cheie a

relaiei


ProiectareaProiectarea relatiilorrelatiilor normalizatenormalizate Normalizarea relaiilor asigur un proiect al bazei de date mai concis i de

aceea se consider c a normaliza este avantajos, chiar dac normalizareanu este o garanie c s-a realizat cel mai bun model

Proiectarea bazelor de date pornind de la diagrama Entitate-Asociereconduce, n general, la relaii normalizate, deoarece: Relaiile corespunztoare mulimilor de entiti sunt, de regul, relaii

normalizate, dat fiind c toate atributele descriu tipul de entitate respectiv. Relaiile de asociere binar, care conin dou chei strine care refer cheile

primare din cele dou relaii pe care le asociaz, rezult tot ca relaii normalizate Relaiile care modeleaz asocierile multiple pot s rezulte nenormalizate i

necesit operaii de normalizare suplimentare

Dar, cu ct nivelul de normalizare crete, cu att se obin mai multe relaiicu grad mai mic i pentru fiecare interogare sunt necesare mai multeoperaii de jonciune, ceea ce face ca timpul de execuie a interogrilor screasc; in general, se recomand ca: relaiile asupra crora se efectueaz operaii de actualizare frecvente s fie

normalizate ntr-o form normal ct mai avansat relaiile asupra crora se efectueaz interogri frecvente pot fi pstrate ntr-o

form de normalizare mai redus

Mentinerea unei relaii ntr-o form de normalizare mai redus se numetedenormalizare, i are scopul de a obine performane ridicate la interogri


AlgoritmiAlgoritmi de de normalizarenormalizare Analiza normalizrii relaiilor trebuie s fie facuta pentru orice proiect de

baze de date, pentru a asigura funcionarea corect a acesteia: Dac o relaie se pstreaz ntr-o form de normalizare mai redus, atunci

trebuie s se prevad proceduri de verificare i impunere a dependenelor de date care nu sunt determinate de cheile relaiei (ca si constrngeri explicite)

Dac se normalizeaza o relaie, dar prin descompunere se pierd unele DF, acestea pot fi impuse explicit prin proceduri stocate sau funcii n programele de aplicaie, care execut jonciunea ntre relaiile rezultate i impun constrngerearespectiva

S-a demonstrat si exista algoritmi prin care orice relatie poate fidescompusa reversibil (cu conservarea informatiei si conservarea DF) in relatii in formele normale FN2 sau FN3

S-a demonstrat si exista algoritmi prin care orice relatie poate fidescompusa in relatii FN2, FN3, FNBC, FN4 sau FN5 fara pierdere de informatie la jonctiune, dar se pot pierde unele dependene


DescompunereaDescompunerea farafara pierderepierdere de de informatieinformatie la la jonctiunejonctiune (1)(1)

Fiind dat o relaie cu schema R i mulimea F de DF, o descompunere D fr pierdere de informaie la jonciune n relaii ntr-una din formele normale FN2, FN3 sau FNBC se poate obine aplicnd algoritmul urmtor:

1. se seteaz D = {R};2. att timp ct n D exist o relaie Q (cu mulimea FQ a DF) care nu se afl n

forma normal dorit:- se alege o DF X W din FQ care nu respecta forma normala dorita i se construiete nchiderea X+ a atributului X i mulimea Y = X+ X;- n D se nlocuiete relaia Q cu dou relaii: Q1 = X Y i Q2 = X Z, unde

Z = Q (X Y); Demonstraie:

La fiecare pas de execuie a algoritmului, o relaie Q se descompune n dou relaii Q1 i Q2, astfel nct Q1 Q2 = X, i Q1 Q2 = Y

Din definiia nchiderii unui atribut rezult c XY, deci, conform teoremei lui Ullman, aceast descompunere este fr pierdere de informaie la jonciune

Astfel de descompuneri succesive pstreaz caracterul de descompuneri fr pierdere de informaie la jonciune

Exist algoritmi similari pentru descompunerea far pierdere de informatie la jonciune a unei relaii in relaii n forme normale FN4 sau FN5


DescompunereaDescompunerea farafara pierderepierdere de de informatieinformatie la la jonctiunejonctiune (2)(2) Exemplu de aplicare a algoritmului pentru descompunerea in relatii FNBC a

relatiei R = {dAngajat, Nume, Prenume, Adresa, Functie, Salariu, IdProiect,Ore} cu PK = {IdAngajat, IdProiect}, aflata n FN1 i cu mulimea F de DF

F = {IdAngajatNume,IdAngajatPreume, IdAngajatAdresa,IdAngajatFunctie,FunctieSalariu, {IdAngajat,IdProiect}Ore}

Executia algoritmului: Se seteaz D = {R} Din F se alege DF IdAngajatNume care nu respect condiia impus de FNBC nchiderea atributului X=IdAngajat este [IdAngajat]+= {IdAngajat, Nume,

Prenume, Adresa, Functie, Salariu} i rezult Y = X+ X = {Nume,Prenume, Adresa, Functie, Salariu} i Z = R (X Y) = R - X+ = {IdProiect,Ore}.

Se obtine descompunerea D a relaiei R: D = {R11, R12}, undeR11 = X Y = {IdAngajat, Nume, Prenume, Adresa, Functie, Salariu}; in FN2R12 = X Z = {IdAngajat, IdProiect, Ore}; in FNBC

In acelasi mod se descompune relaia R11, in relatiile R111 si R112:R111 = {Functie, Salariu}; este in FNBCR112 = {IdAngajat, Nume, Prenume, Adresa, Functie}; este in FNBC

Se poate demonstra usor ca descompunerea obtinuta D= (R111, R112, R12) conserva si dependentele functionale


Capitolul 6: Normalizarea relatiilorDependentele de dateRedundanta datelor si anomaliile de actualizareEliminarea anomaliilor datorate redundantei Dependente functionale (1)Dependene funcionale (2)Tipuri de dependene funcionaleMultimi de dependente functionale (1)Multimi de dependente functionale (2)Inchiderea unei multimi de DF Dependenele funcionale i cheile relaiilor Inchiderea unui atribut fata de o multime de DF (1)Inchiderea unui atribut fata de o multime de DF (2)Aflarea cheilor unei relaii din multimea DF Descompunerea relatiilor Descompunere fr pierdere de informaie la jonctiuneConservarea dependenelor funcionale Formele normale ale relatiilor (FN1 si FN2) Impunerea DF in relatia nenormalizata AP (1)Impunerea DF in relatia nenormalizata AP(2)A treia forma normala (FN3) Impunerea DF in relatia nenormalizata AFS (1)Impunerea DF in relatia nenormalizata AFS (2)Forma normala Boyce-Codd (FNBC) Impunerea DF in relatia nenormalizata EDP Normalizarea relatiei EDPImpunerea constrangerilor pierdute prin descompunere (1) Impunerea constrangerilor pierdute prin descompunere (2)Dependente multivaloriceDependente de jonctiuneForma normala FN5Proiectarea relatiilor normalizate Algoritmi de normalizareDescompunerea fara pierdere de informatie la jonctiune (1)Descompunerea fara pierdere de informatie la jonctiune (2)

cap6_normalizarea_relatiilor

Documents