BAZE DE DATE SI FORME NORMALE

BAZE DE DATE SI FORME NORMALE

1. Introducere

Normalizarea datelor poate fi privita ca un proces pe durata caruia, schemele de relatie care nu satisfac anumite restrictii sunt descompuse in scheme mai mici care poseda proprietatile dorite. De fapt, obiectivele proceselor de normalizare sunt de a obtine scheme de relatii bine proiectate care sa elimine anomaliile intalnite la actualizare. Formele normale sunt pentru proiectantii de baze de date metode formale de analiza a schemelor relationale, ce se bazeaza pe chei si dependente. Ele stau la baza unor algoritmi de normalizare, ce se aplica schemelor componente ale bazei de date. Este important, sa se observe ca, formele normale cand sunt considerate izolat, nu garanteaza o buna proiectare a bazei de date. De exemplu, numai cand se considera impreuna forma normala trei si forma normala Boyce-Codd, se obtin proprietati suplimentare ca; unirea fara pierderi de informatii, conservare a dependentelor etc. Daca exista o redundanta, formele normale raspund la urmatoarele intrebari:

Cum trebuie sa descompunem relatia?

Daca exista informatii care se pierd prin descompunere?

Exista algoritmi care permit sa determinam o descompunere adecvata?

Inainte de a incepe studierea detaliata a bazelor de date relationale, sa analizam notiunea de cheie si super-cheie folosind dependentele functionale. Astfel, pentru o schema de relatie data R, o cheie pentru R este o submultime K R, astfel ca pentru oricare relatie admisibila r(R) nu exista doua tupluri diferite t₁ si t₂ in r, astfel ca t₁(K)=t₂(K) si nici o submultime proprie K^' K nu poseda aceasta proprietate. Amintim ca, pentru anumite relatii admisibile de schema R submultimea K^' poate fi cheie, dar noi vom considera toate relatiile admisibile de schema R. Supercheie este orice multime de atribute care contine o cheie.

Exemplul 1. Relatia decolare din tabelul 1 contine lista decolarilor de pe o multime de aeroporturi. La prima vedere s-ar parea ca este cheia pentru relatia decolare. Dar, in orar pot exista concomitent doua curse dintr-un oras in acelasi timp (de exemplu , daca in tabelul 1 se adauga inca un tuplu <234 Iasi 21,30 Cluj>. In realitate, pentru relatia decolare avem drept cheie in limbajul dependentelor functionale, cheia pentru schema R este o submultime K R cu proprietatea ca, orice relatie admisibila r(R) satisface K R, si nici o submultime proprie K^' K nu poseda aceasta proprietate. Daca K este cheie pentru r, atunci nu exista doua tupluri diferite t₁ si t₂ in r avand aceleasi K-valori. in acest fel, conditia de verificare dependentei functionale K R este urmatoarea: daca t₁(K)=t₂(K), atunci, t₁=t₂, cu alte cuvinte t₁(R)=t₂(R). Supercheia este submultimea K R, astfel ca K R in care lipseste conditia de minimizare.

decolare CURSA PUNCT-DE-DECOLARE ORA-DECOLARII PUNCT- DE- ATERIZRE )

70 Bucuresti 9 : 10 Cluj

75 Iasi 10 : 32 Cluj

77 Iasi 21 : 30 Bucuresti

80 Arad 13 : 15 Craiova

85 Timisoara 16:30 Bucuresti

Tabel 1. Relatia decolare

2. Baze de date si scheme de baze de date

In cele ce urmeaza se presupune ca schema de relatie R se compune din doua parti S si K, unde S este o multime de atribute, iar K este o multime de d-chei (designate, definite, privelegiate, etc.). Introducem notatia R=(S, K). Uneori, analizand multimea de atribute, in loc de S se va folosi totusi R, de exemplu vom scrie X R in loc de X S.

Definitia 1. Fie U o multime de atribute care descriu un univers.

i) Se numeste schema de relatie a bazei de date in raport cu U, notata cu R, o

multime de scheme de relatie R= R₁,..,R_p unde R_i=(S_i, K_i 1 i p, S_i U,

si S_i S_j cand i j

ii) Se numeste baza relationala de date de schema R o multime de relatii

d= asfel ca, pentru orice schema (S, K) din R, exista o relatie rId de

schema S care satisface fiecare cheie din K.

Exemplul 2. Fie baza de date d= de schema R= din tabelul 2. Relatiile cursa si orar sunt proprietati relatiei grafic .

Cursa (PILOT CURSA DATA ) orar CURSA ORA_DECOLARII)

Costin 83 9 aug. 83 10 : 15

Costin 116 10 aug. 116 13 : 25

Mihai 281 8 aug. 281 5 : 50

Mihai 301 12 aug. 301 18 : 35

Mihai 83 11 aug. 412 13 : 25

Dragos 83 13 aug.

Dragos 116 12 aug.

Mircea 281 9 aug.

Mircea 281 13 aug.

Mircea 412 15 aug.

Tabel 2. Baza de date formata relatiile cursa si orar.

Definitia 2. Schema de relatie R=(S,K) incorporeaza F-dependenta K R, daca K este o d-cheie din K.

Definitia 3. Schema bazei de date R= este reprezentata de multimea de dependente functionale G=.

Schema bazei de date R caracterizeaza complet multimea dependentelor functionale F, daca F≡G.

Grafic (PILOT CURSA DATA ORA DECOLARII)

Costin 83 9 aug. 10 : 15

Costin 116 10 aug. 13 : 25

Mihai 281 8 aug. 5 : 50

Mihai 301 12 aug. 8 : 35

Mihai 83 11 aug. 10 : 15

Dragos 83 13 aug. 10 : 15

Dragos 116 12 aug. 13 : 25

Mircea 281 9 aug. 5 : 50

Mircea 281 13 aug. 5 : 50

Mircea 412 15 aug. 13 : 25

Tabel 3. Realatia grafic (PILOT CURSA DATA ORA-DECOLARII)

Exemplul 3. Schema bazei de date R din exemplul 2. este reprezentata de multimea de F-dependente G Schema bazei de date R caracterizeaza complet multimea: F Se pot stabili si alte restrictii pentru relatiile din baza noastra de date, diferite de cele care sunt date de d-cheile din schemele de relatie. in unele cazuri, cand se stabileste totalitatea F-dependentelor pe care trebuie sa satisfaca relatiile din baza de date. Nu orice F-dependenta din F este aplicabila la fiecare relatie din baza de date. Cum se poate asigura aplicarea F-dependentei AB C la relatia r(AC)? Pentru aceasta trebuie schimbata astfel definitia notiunii de 'satisface' astfel ca sa fie adecvata bazei de date.

Definitia 4. Fie R o schema de relatie. F-dependenta X Y este aplicabila in R daca X R si Y R.

Definitia 5. Fie d= o baza de date de schema R= pe U si F o multime de F-dependente pe U. Baza de date d satisface F daca fiecare F-dependenta X Y din F⁺ este aplicabila la o schema oarecare R_i din R si relatia r_i o satisface. Fie G multimea tuturor F-dependentelor din F⁺ care sunt aplicabile la o schema R_i din R. Orice F-dependenta din G⁺ se numeste realizabila in raport cu R. Orice F-dependenta in F⁺-G⁺ este nerealizabila pe R. Multimea F este realizabila in raport cu schema bazei de date R daca orice F-dependenta din F⁺ este realizabila pe R, adica G F

Pentru a arata ca multimea F este realizabila in raport cu schema bazei de date R, este suficient sa se gaseasca o multime F' , F' F astfel ca fiecare F-dependenta din F' sa fie realizabila in raport cu o schema oarecare R din R.

Definitia 6. Baza de date d, de schema R este determinata de multimea F-dependentelor F, daca F este realizabila in raport cu schema R si d satisface F⁺.

Daca F' este multimea F-dependentelor in sensul celor descrise mai sus, d este determinata de F, daca d satisface F'.

Exemplul 4. Fie schema data R= unde R₁=ABC, R₂=BCD, R₃=DE si

F F-dependentele A D si A E nu sunt aplicabile in nici o schema de relatie din R. Dar F e determinata de schema R, deoarece G= si F sunt echivalente si orice F-dependenta din G este aplicabila la o schema de relatie din R. Multimea F' nu este realizabila pe R.

3. Forme normale

Fiind data o schema a unei baze de date, se spune ca este in FN1, FN2, FN3, FNBC daca oricare din schemele sale de relatie sunt in forma normala dorita.

Vom da definitiile unor forme normale pentru baze de date. Forma normala reprezinta in sine o restrictie a schemei bazei de date care scuteste baza de date de unele calitati nedorite. La inceput vom stabili forme normale pentru o schema de relatie din schema bazei de date, iar apoi vom extinde aceasta definitie la schema bazei de date in intregime. Problema normalizarii consta in a inlocui schema bazei de date prin alta echivalenta care este in forma normala. Exista doua criterii care trebuie respectate prin normalizare:

conservarea continutului bazei de date;

conservarea dependentelor functionale.

3.1. Prima forma normala

Schema de relatie R se afla in prima forma normala (FN1) daca valorile din dom(A) sunt atomice pentru orice atribut A din R. Cu alte cuvinte, valorile din domeniu nu sunt nici liste, nici multimi de date simple sau complexe. Schema bazei de date R se gaseste in prima forma normala daca fiecare schema de relatie din R se gaseste in prima forma normala. Toate exemplele aratate pana in prezent au fost in prima forma normala.

Exemplul 5. Mai jos este prezentata relatia data_nasterii, unde sunt trecute zilele de nastere, luna si anul.

data_nasterii NUMELE DATA-NASTERII

Dorel 7 iunie 1949

Dragos 21 martie 1983

George 30 aprilie 1959

Alina 12 mai 1963

Daca ar fi fost necesar sa se indice doar luna sau anul nasterii, atunci relatia data_nasterii nu s-ar fi gasit in FN1 deoarece valorile necesare sunt doar o parte a valorilor atributului DATA_NASTERII. Pentru ca relatia sa se gaseasca in prima forma normala in, atributul DATA_NASTERII trebuie sa fie divizat asa cum se arata mai jos.

nastere NUMELE ZIUA LUNA ANUL

Dorel 7 iunie 1949

Dragos 21 martie 1983

George 30 aprilie 1959

Alina 12 mai 1963

Exemplul 6. Relatia gen, prezentata mai jos, nu se gaseste in prima forma normala deoarece ea include valori care nu sunt valori atomice.

Gen(NUME    SEX

ION,VASILE,MIHAI masculin

FLOAREA, MARIA feminin

Pentru ca relatia gen sa se gaseasca in FN1 ea trebuie prezentata astfel:

gen NUME SEX

ION masculin

VASILE masculin

MIHAI    masculin

FLOAREA feminin

MARIA feminin

In ce consta avantajul primei forme normale? In aceea ca, permite sa se exprime F-dependentele cu un grad de detaliere care ne trebuie, ce ar fi imposibil fara FN1. Presupunem ca trebuie sa fie adaugat atributul SEMN, acesta fiind semnul zodiacal al individului in prima relatie data_nasterii in exemplul 5 SEMN-ul depinde functional doar de luna si ziua in care s-a nascut si nu depinde de an. Dar tot ce se poate face in aceasta situatie, este sa se stabileasca F-dependenta DATA-NASTERII SEMN (zodiacal), care permite ca doi indivizi nascuti in aceeasi zi dar in ani diferiti sa aiba semne zodiacale diferite. in cea de-a doua relatie data_nasteri nu se ridica asemenea greutati, deoarece se poate scrie F-dependenta ZIUA-NASTERII LUNA-NASTERII SEMN si atunci problema ridicata de relatia functionala anterioara, cade.

La actualizarea datelor, pot exista de asemeni, anumite greutati, daca schema nu se gaseste in prima forma normala. Presupunem ca trebuie executata urmatoarea operatie de actualizare:

CH (gen;VASILICA, masculin, SEX=feminin)

In relatia gen a exemplului 6 rezultatul unei asemenea actualizari este nedeterminat. Ce trebuie facut: sa se transfere numele VASILICA dintr-o multime in alta sau sa se inlocuiasca sexul masculin cu feminin? Pentru cea de a doua varianta, relatia gen din exemplul 6 nu ridica o asemenea problema.

3.2. Anomalii si redundante

A doua si a treia forma normala au aparut ca rezultat al dorintei de a evita anomaliile de la actualizarea datelor si de a scapa de redundante in relatii. Anomaliile actualizarii sunt un efect colateral, nedorit, conditionat de modificarea relatiei. Examinam relatia grafic din figura urmatoare:

Grafic (CURSA DATA PILOT CULOAR

112 6 iunie Albu 7

112 7 iunie Negru 7

203 9 iunie Albu 12

Tabel 4 Relatia Grafic

Atributele CURSA DATA formeaza cheia relatiei grafic si aceasta relatie trebuie sa satisfaca de asemeni F-dependenta CURSA CULOAR. Sa admitem ca trebuie actualizata relatia, indicand valoarea cheii si dand valori celorlalte atribute. Daca executam operatia:

CH (grafic; 112, 6 iunie; PILOT= Albu CULOAR= 8), atunci relatia va inceta sa satisfaca F-dependenta CURSA CULOAR. Pentru a evita incalcarea F-dependentei, este necesar ca, dupa executarea fiecarei operatii de actualizare sa se examineze relatia obtinuta pentru toate tuplurile unde apare numarul cursei indicat in operatie, sa inlocuim numarul culoarului cu cel indicat in operatie. Desi a trebuit sa se schimbe doar un singur tuplu. in afara de aceasta informatia despre legatura intre numarul cursei si numarul culoarului se dubleaza in relatia examinata, ceea ce duce la redundanta.

Din punct de vedere al actualizarii ca si din cel al eliminarii redundantei este mai bine sa se prezinte aceeasi informatie sub forma unei baze de date, frmata din doua relatii pilot-grafic si culoar-grafic:

pilot-grafic (CURSA DATA PILOT )

112 6 IUNIE ALBU

112 7 IUNIE NEGRU

203 9 IUNIE ALBU

culoar-grafic (CURSA CULOAR)

112 7

203 12

Se poate restabili relatia initiala grafic, luand pilot-graficculoar-grafic. Anomalia de actualizare nu mai exista, deoarece trebuie modificata doar un tuplu pentru a schimba destinatia culoarului. Astfel, am scapat, de redundanta, deoarece fiecare pereche ( numarul cursei, numarul culoarului ) se scriu doar odata.

3.3. A doua forma normala

Definitia Fie o multime data de dependente functionale F si X,Y submultimi ale lui R, multimea Y se numeste partial dependenta de X in raport cu F, daca X Y nu este redusa la stanga. Cu alte cuvinte exista o submultime proprie X' a multimii X, astfel incat relatia X' Y apartine de F⁺. Daca X Y este redusa la stanga, atunci Y se numeste complet dependenta de X.

Exemplul Fie F=(CURSA DATA PILOT CULOAR, CURSA CULOAR). Aici atributul CULOAR depinde partial de CURSA DATA, iar PILOT depinde total de CURSA DATA.

Definitia 8. Fie schema de relatie R, atributul A in R si o multimii de dependente functionale F pe R, atributul A se numeste prim in R in raport cu F, daca A este continut intr-o cheie a schemei R. in caz contrar A se numeste neprim in R.

Observatie: Cheile in aceasta relatie nu trebuie confundate cu d-cheile (chei privilegiate) pentru R, deoarece, cele din urma, pot fi in fapt superchei. in afara de aceasta pot exista chei pentru R care sa nu fie d-chei.

Exemplul 8 Fie R= [CURSA DATA PILOT CULOAR] si multimea F aceeasi ca in exemplul 7 CURSA si DATA sunt prime, PILOT si CULOAR sunt neprime ( este admis ca un pilot sa aiba doua curse in aceeasi zi, deoarece PILOT DATA nu formeaza o cheie.

Definitia 9. Schema de relatie R se gaseste in a doua forma normala (FN2) in raport cu multimea dependentelor functionale F, daca ea se gaseste in prima forma normala si fiecare atribut neprim depinde complet de o cheie din R. Schema bazei de date R este in a doua forma normala relativ la F, daca fiecare schema de relatie R_i din R se gaseste in a doua forma normala in raport cu F.

Exemplul 9. Fie R si F aceleasi ca in exemplul 8 si R=. Schema R nu se gaseste in FN2, deoarece CULOAR depinde partial de CURSA DATA. Daca punem R=(CURSA DATA PILOT, CURSA CULOAR ), atunci R se va gasi in a doua forma normala. Atributul CURSA este acum cheie pentru schema cu relatia CURSA CULOAR.

3.4. A treia forma normala

Sa examinam relatia grafic prezentata in tabelul 4 aceasta seamana cu relatia cu acelasi nume prezentate in tabelul 1.

grafic ( CURSA DATA COD-PILOT NUME

112 6 iunie 31174 Albu

112 7 iunie 30046 Negru

203 9 iunie 31174 Albu

Tabel 4. Relatia grafic

Presupunem din nou ca relatia grafic are cheie CURSA ZIUA si satisface in acelasi timp dependentele functionale (COD-PILOT NUME) si (NUME COD-PILOT). Daca se executa operatiunea de schimbare

CH (grafic, 112, 6 iunie; COD-PILOT , NUME=Albu)

atunci se schimba dependenta functionala NUME COD-PILOT in afara de aceasta mai avem informatia redundanta sub forma perechilor COD si PILOT. Aici problema nu este deloc cauzata de dependenta partiala a atributului secundar, desi rezolvarea este aceeasi. Aceasta relatie trebuie prezentata sub forma bazei de date, in felul urmator :

pilot-grafic CURSA DATA COD-PILOT

112 6.06 31174

112 6.07 30046

cod (COD-PILOT NUME)

31174 Albu

30046 Negru

Se poate restabili relatia initiala prin unire.

Definitia 10. Fie X o submultime a lui R, atributul A din R si multimea de dependente functionale F, atributul A se numeste tranzitiv dependendent de X in raport cu F daca exista o submultime Y R, asfel incat X Y, Y X, Y A si A X Y.

Exemplul 10. Fie R = (CURSA DATA COD-PILOT NUME) si F = (CURSA DATA COD-PILOT NUME, COD-PILOT NUME, NUME COD-PILOT). Atributul NUME este tranzitiv dependent de CURSA DATA deoarece CURSA DATA COD-PILOT, COD-PILOT CURSA DATA si COD-PILOT NUME. Aici COD-PILOT joaca rolulul lui Y din definitia 10.

Definitia 11. Schema de relatie R se gaseste in forma normala trei FN3 in raport cu multimea de dependente functionale F, daca ea se gaseste in FN1 si nici unul din atributele neprime din R nu este tranzitiv dependent de o cheie din R. Schema bazei de date R se gaseste in forma normala trei relativ la F daca fiecare schema de relatie R_i din R are proprietatea FN3 in raport cu F.

Exemplul 11 . Fie R si F aceleasi ca in exemplul 10 si R=. Schema bazei de date R nu are proprietatea FN3 relativ la F, deoarece NUMELE este tranzitiv dependent de CURSA DATA Daca R = (CURSA DATA COD-PILOT, COD-PILOT NUME) atunci R are proprietatea FN3 in raport cu F.

Lema 1. Orice schema de relatie care are proprietatea FN3 in raport cu F, are proprietatea FN2 in raport cu F.

Demonstratie: Vom arata ca dependenta partiala implica dependenta tranzitiva. Sa presupunem ca atributul secundar A in R este partial dependent de cheia K R. Atunci exista o submultime proprie K' a multimii K astfel ca F K' A. Aici K'K astfel ca atunci K' trebuie sa fie cheie pentru R, iar cheile nu pot contine chei in calitatea de submultime proprie. De asemeni avem A K, deoarece K este cheie iar atributul A este secundar. in consecinta K K', K'K si A K, K'=K. Astfel, A este tranzitiv dependent de K.

3.5. Normalizare prin descompunere.

Intotdeauna se poate incepe prin aceea ca, luand o schema oarecare de relatie R, ce nu se gaseste in FN3 in raport cu multimea F-dependentelor F, o vom descompune in scheme ale bazei de date avand FN3 in raport cu F. Descompunerea schemei de relatie inseamna impartirea schemei de relatie intr-o pereche de scheme R₁ si R₂ (care este posibil sa se intersecteze) astfel incat orice relatie r(R) care satisface F sa se descompuna fara pierderi in R₁ si R₂. Cu alte cuvinte, π_R1(r) π_R2(r)=r. E posibil sa repetam procesul de descompunere a relatiilor R₁ si R₂ daca vreuna dintre ele nu are proprietatea FN3. Vom continua descompunerea pana cand toate relatiile obtinute vor avea proprietatea FN3 in raport cu F.

Sa presupunem ca exista o dependenta tranzitiva de o cheie in R. Exista cheia

K R, multimea Y R si atributul secundar A in R in asa fel ca K Y, YK Y A in raport cu F si A KY. Fie R₁= R-A si R₂= YA. Daca pentru schema noastra de relatie exista d-chei sa zicem R=(S,K), atunci fie K multimea cheilor pentru R₁ si (Y)=multimea de chei pentru R₂. Nu este exclus ca vreo d-cheie K din K sa contina pe A. in acest caz K este cheie pentru R. Fie K'=K-A. Atata timp cat K' ramane subcheie pentru R, nu poate fi parte a nici unei chei pentru R. Vom pune K' in locul lui K in K .Am eliminat o dependenta tranzitiva din R si pentru orice r(R) care satisface F avem _R1(r) _R2(r)=r. Daca au ramas unele dependente tranzitive in R₁ sau in R₂, se poate continua descompunerea inca o data. De fapt procesul de descompunere nu este infinit. De fiecare data cand descompunem schema de relatie, cele doua scheme obtinute ca rezultat devin mai mici, iar schema de relatie care contine doar doua atribute nu poate contine nici o dependenta data tranzitiva.

Procesul de descompunere poate fi accelerat , verificand daca exista alte atribute neprime in R-(KY), dependendente de Y. Daca exista asemenea atribute, atunci ele depind tranzitiv de K si ele pot fi eliminate concomitent. Sa presupunem ca A₁,A₂,,A_m se gasesc in R-(KY) si depind de Y. Presupunem ca R₁=R-( A₁,A₂,,A_m) si R₂=YA₁,A₂,,A_m. Din nou, ca si anterior, orice relatie r(R), care satisface F, se poate descompune fara pierderi pe R₁ si R₂.

Exemplul 12. Fie R=. Sa presupunem ca in acelasi timp, nu pot fi doua curse cu aceleasi puncte de plecare si de sosire. Fie ca toate d-cheile sa fie intr-adevar chei si fie urmatoarele F-dependente in multimea F:

TIPUL-AVIONULUI CLASA-I CLASA-II NUMARUL-DE-LOCURI

ORA-DECOLARII DURATA-ZBORULUI ALIMENTARE

ORA-SOSIRII DURATA-ZBORULUI ALIMENTARE

CLASA-I CLASA-II NUMARUL-DE-LOCURI

CLASA-I NUMARUL-DE-LOCURI CLASA-II

CLASA-II NUMARUL-DE-LOCURI CLASA-I

S-ar parea ca ORA-SOSIRII DURATA-ZBORULUI ar trebui sa fie, de asemeni, F-dependente dar, pentru ca orele de decolare si sosire sunt ore locale, DURATA-ZBORULUI depinde de fusurile orare carora le apartin aeroporturile respective. Mai intai vom elimina dependenta tranzitiva a atributului ALIMENTARE de CURSA prin ORA-DECOLARII DURATA-ZBORULUI.Vom obtine urmatoarele scheme de relatii :

R₁=CURSA PUNCT-PLECARE PUNCT-DESTINATIE ORA-SOSIRII DURATA-ZBORULUI TIPUL-AVIONULUI CLASA-I CLASA-II NUMARUL-DE-LOCURI cu d-cheile K₁

si schema de relatie R₂=ORA-DECOLARII DURATA-ZBORULUI ALIMENTARE cu d-cheie K₂

Schema R₂ se gaseste in FN3 iar schema R₁ nu deoarece CLASA-I CLASA-II si NUMARUL-DE-LOCURI depind tranzitiv de CURSA prin TIPUL AVIONULUI. Schema R₁ se descompune in schema :

R₁₁=CURSA PUNCT-PLECARE PUNCT-DESTINATIE ORA-SOSIRII DURATA-ZBORULUI TIPUL-AVIONULUI cu d-cheile:

K₁₁ si schema

R₁₂=TIPUL-AVIONULUI CLASA-I CLASA-II NUMARUL-DE-LOCURI cu d-cheia K₁₂

Schema de relatie R₁₁ se gaseste acum in FN3 in raport cu F, iar R₁₂ nu, deoarece NUMARUL-DE-LOCURI depinde tranzitiv de TIPUL-AVIONULUI prin CLASA-I CLASA-II. Schema R₁₂ se descompune in :

R₁₂₁=TIPUL-AVIONULUI CLASA-I CLASA-II cu d-cheia K₁₂₁= si schema de relatie :

R₁₂₂=CLASA-I CLASA-II NUMARUL-DE-LOCURI cu d-cheia K₁₂₂

Descompunerea relatiei R este realizata pana la acel stadiu cand fiecare schema de relatii se gaseste in FN3 in raport cu F. in consecinta schema bazei de date R= se gaseste in FN3. in afara de aceasta, orice relatie r(R) care satisface F-dependentele din F se poate reprezenta corect prin proiectile pe schemele de relatii din R, deoarece

r=( _R11(r) _R121(r) _R122(r) _R2(r) )

Aici parantezele nu sunt obligatorii, deoarece unirea este comutativa si asociativa. Ele evidentiaza doar etapele descompunerii fara pierderi lui r. Daca se schimba ordinea de unire, rezultatele intermediare pot fi irationale, de exemplu :

_R122(r) _R2(r) _R122R2(r).

Daca se face un calcul conform parantezelor, atunci fiecare rezultat intermediar va fi o proiectie a lui r.Schema bazei de date R nu este unica. Sunt diverse variante in care se pot alege o descompunere a unei relatii determinate de atributul tranzitiv dependent care se considera . Astfel, la primul pas al descompunerii se putea alege :

R₂=ORA-SOSIRII DURATA-ZBORULUI ALIMENTARE deoarece ALIMENTARE depinde, de asemeni, tranzitiv de CURSA prin ORA SOSIRII DURATA-ZBORULUI. La al treilea pas al descompunerii exista trei variante ale descompunerii R₁₂. Unele chei pentru schemele de relatii nu sunt realizabile, de exemplu: CLASA-I NUMARUL-DE-LOCURI si CLASA-II NUMARUL-DE-LOCURI pentru R₁₂₂. Dam in continuare algoritmul de normalizare prin descompunere.

0. START [FN3]

1. INPUT

2. i

3. FOR fiecare X YIF

3.1 i i +1

3.2 R_i XY

4. IF nici o schema R_j cu 1 j i nu contine o d-cheie

THEN

4.1 i i +1

4.2 R_i K // K cheie designata pe R

5. IF R_j≠R

THEN

5.1 R_i+1 R-R_j

5.2 i i +1

6. OUTPUT

STOP

3.6. Greutati in normalizarea data de descompunere

La normalizarea schemei de relatie cu ajutorul descompunerii apar probleme noi. in primul rand, timpul de complexitate al algoritmului nu este polinomial si poate avea un numar exponential de chei. in afara de aceasta, verificarea ca atributul schemei este secundar, constituie o problema NP completa. in al doilea rand, numarul de scheme generat de metoda de descompunere poate fi mai mare decat este necesar in realitate, pentru FN3.

Exemplul 13. Fie schema data R= ABCDE si F=. Cheile pentru R in raport cu F sunt AB si AC. Folosind dependenta tranzitiva D de la AB prin C, descompunem pe R astfel :

R₁=ABCE    K₁=

R₂=CD    K₂=

Mai departe, in R₁ folosim faptul ca E e tranzitiv dependent de AB prin B se obtine

R₁₁=ABC K₁₁=

R₁₂=BE K₁₂=

Schema finala a bazei de date in FN3 este :

R=

Exista o descompunere a lui R in FN3 cu doua scheme de relatii si anume :

R₁=ABC K₁=

R₂=BDE K₂=

A treia problema consta in aceea ca, la descompunerea schemei de relatii pot exista dependente partiale. Aceste dependente pot da nastere la o schema finala a bazei de date cu mai multe scheme decat este necesar in realitate.

Exemplul 14. Pentru schema de relatii R = ABCD si F= atributul A este singura cheie in R in raport cu F. Atributul D este tranzitiv dependent de A prin BC. Descompunand obtinem :

R₁=ABC K₁=

R₂=BCD K₂=

De fapt, cheia pentru R₂ este BC, dar B depinde partial de ea. in consecinta D este tranzitiv dependent de B C. Schema R₂ trebuie descompusa in :

R₂₁=BC K₁₂=

R₂₂=CD K₂₂=

Schemele R₁,R_{21 si} R₂₂ formeaza schema bazei de date in FN3 pentru R. Dar schemele de relatii R₁ si R₂₂ formeaza si ele o schema a bazei de date in FN3 pentru R.

Aceste neplaceri se pot evita, daca la descompunere se va urmari ca multimea intermediara de atribute in dependenta tranzitiva ce se descompune, sa fie minimala. in exemplul 14 atributul D a depins tranzitiv de A prin BC, dar BC nu este minimala. Atributul D depinde tranzitiv de A doar prin C. A patra problema consta in aceea ca, pentru construirea schemei bazei de date, multimea data de F-dependente poate fi nerealizabila.

Exemplul 15. Fie schema data R =ABCDE si F=. Eliminand dependenta tranzitiva E din A prin CD, obtinem :

R₁=ABCD K₁=

R₂=CDE K₂=

Multimea F e nerealizabila pentru schema bazei de date R= din cauza ca dependenta EC B nu este dedusa din F-dependente din F⁺ aplicate la R₁ sau R₂. in sfarsit, a cincea problema. Cu ajutorul descompunerii pot apare scheme cu dependente tranzitive 'ascunse'.

Exemplul 16. Fie schema data R=ABCD si F=. Atributele AD sunt chei pentru F, iar B depinde partial de AD. La descompunere obtinem :

R₁=ACD K₁=

R₂=AB K₂=

Cu toate ca R_{1 si} R₂ se gasesc formal in FN3, in R₁ se gaseste dependenta tranzitiva 'ascunsa' C de AD.

4. Normalizarea prin sinteza

In acest paragraf se examineaza o alta metoda de obtinere a formei normale 3 care nu da nastere la problemele descrise de la descompunere. O problema esentiala este de a gasi FN3 a schemei bazei de date plecand de la o schema de relatie care nu este in aceasta forma. Presupunem ca la inceput este data o schema de relatie R si o multime de F-dependente F pe R din care trebuie creata o schema a bazei de date R=R₁,R₂,,R_p pe R care trebuie sa satisfaca urmatoarele patru cerinte:

Multimea F este complet caracterizata de R, adica : F=;

Fiecare schema de relatie R_i din R se gaseste in FN3 in raport cu F;

Nu exista o schema a bazei de date cu un numar mai mic de scheme ca R, care sa satisfaca proprietatile 1 si 2;

Pentru orice relatie r(R) care satisface F,

r= _R1(r) _R2(r) _Rp(r) .

Schema bazei de date R, care satisface primele trei cerinte formulate anterior, o vom numi schema completa a bazei de date in raport cu F. Sa judecam semnificatia acestor cerinte. Proprietatea 1 arata ca F este realizabila in R si ca aceasta poate fi verificata fara calcularea lui F⁺. Proprietatea 1 garanteaza de asemeni, ca singurele F-dependente care trebuie sa fie realizabile si satisfacute pe R, sunt cele care se obtin din d-chei . Proprietatea 3 ne apara de redundanta. Proprietatea 4 arata ca o relatie este corect reprezentata de schema R prin proiectiile sale determinate de schemele din R.

Incepem elaborarea algoritmului cu calculul acoperirii inelare, generata din F a unei scheme complete a bazei de date. Deoarece algoritmul construieste schema bazei de date direct din F-dependentele lui F, se numeste algoritm de sinteza. Mai departe vom arata alte cateva proprietati utile pe care le poseda schemele bazelor de date sintezate cu ajutorul acestui algoritm. Apoi modificam algoritmul astfel ca iesirea lui sa satisfaca proprietatea 4 si vom arata, de asemenea, caile de imbunatatire ulterioare.

Deoarece partea cea mai grea a algoritmului este gasirea acoperirii inelare, reduse si minimale pentru o multime de F-dependente, atunci acesta are o complexitate polinomiala.

4.1. Algoritmul de sinteza

Lema 2. Daca R este schema bazei de date reprezentata de multimea F-dependentelor G, atunci ea contine cel putin scheme de relatii. Aceasta inseamna ca in R sunt cel putin tot atatea scheme, cate clase de echivalenta sunt in

Demonstratie . Toate F-dependentele incluse intr-o schema de relatii R din R, trebuie sa aiba parti din stanga echivalente. Daca K₁ si K₂ sunt cheile lui R, atunci este corect K₁ R si K₂ R, in consecinta K₁ K_{2 si} K₂ K₁. Astfel, fiecare schema poate include in sine F-dependente nu mai multe decat dintr-o clasa de echivalenta . Pentru reprezentarea tuturor F-dependentelor din G in R vor fi necesare cel putin scheme.

Corolar1. Fie F o multime de F-dependente. Orice schema a bazei de date caracterizata complet de F, trebuie sa aiba cel putin scheme, unde G este acoperire neredundanta pentru F.

Demonstratie. Din lema 1 stim ca daca G este multimea F-dependentelor reprezentate de R atunci │_{G F}│, deoarece F G si G este neredundanta.

Lema 2 da o metoda de sinteza unei scheme complete a unei baze de date pentru o multime data de F-dependente F. Calculam acoperirea neredundanta F' a lui F si clasele de echivalenta . Pentru fiecare din , construim shema de relatie constand din toate atributele aparute in fiecare F-dependenta din . Fie -multimea d-cheilor pentru R. Schema bazei de date R se compune din toate schemele sintetizate in acest fel. Conform consecintei ce decurge din lema 2 , ea cuprinde un numar minim de scheme. Se poate arata ca R caracterizeaza complet pe F. Dar, asa cum se vede in exemplul urmator schemele obtinute pot sa nu fie de tipul FN3 in raport cu F.

Exemplul 17 Fie F=F'= si R=ABC. Procedeul descris mai sus de schema de relatie R₁=ABC cu d-cheia K₁= si schema de relatie R₂=BC cu d-cheia K₂=. Relatia R₁ nu se gaseste in FN3 in raport cu F. In exemplul 17 apar complicatii din cauza nereducerii lui F. Exemplul urmator arata ca si multimea redusa a F-dependentelor nu garanteaza obtinerea bazei de date in FN3.

Exemplul 18. Fie F compusa din urmatoarele F-dependentele

B₁B₂ A D₁D₂ C₁C₂

B₁ C₁ B₂ C₂

D₁ A D₂ A

AB₁C₂ D₂ AB₂C₁ D₁

si fie R=AB₁B₂C₁C₂D₁D₂

Singurele F-dependente dintr-o clasa de echivalenta sunt: B₁B₂ A si D₁D₂ B₁B₂. Schema redusa, determinata de aceasta clasa de echivalenta este: R=AB₁B₂D₁D₂. cu d-cheile K=. Deoarece A depinde tranzitiv de B₁B₂ prin D₁, R nu se gaseste in FN3. Din exemplul 18 se vede ca gasirea acoperirii minimale a lui F nu rezolva problema. Problema o constitue atributul A. Daca vom folosi ca mai inainte acoperirile inelare, problema este rezolvata. Sinteza care foloseste acoperirile inelare este data de algoritmul 1.Procedura ACM calculeaza acoperirea minimala a lui F notata cu G. Fiecare dependenta functionala compusa da nastere la o schema de relatie.

0. START [SYNTHESE]

1. INPUT

2. CALL ACM(F;G)

3. p

4. FOR fiecare CF-dependenta din G

4.1 p p +1

4.2 R_p X₁X₂X_hY

5. OUTPUT

6. STOP

Exemplul 19. Fie F' multimea de F-dependente urmatoare

si fie Multimea F-dependentelor, chiar cu schimbarea denumirilor este aceeasi ca si in exemplul 12. Multimea F este minimala, dar neredusa. Reducand pe F, obtinem: F'

Calculand acoperirea inelara si redusa avem: G Transformand fiecare CF-dependenta in schema de relatie cu d-cheile respective, obtinem:

Schema finala a bazei de date este:   

Lema 3. Fie R schema bazei de date obtinuta din multimea de F-dependente cu algoritmul SYNTHESE. Pentru o schema arbitrara din R, fiecare d-cheie din este cheie.

Demonstratie. Fie o CF-dependenta din care este sintetizata Fie K o d-cheie din , care nu este cheie. Fie K=X_j pentru un termen oarecare din partea stanga a CF-dependentei. Deoarece K nu este cheie, K contine un atribut transferabil. Prin urmare relatia nu este redusa, ceea ce contrazice constructia.

Teorema1. Algoritmul SYNTHESE creaza din multimea de F-dependente F o schema completa a bazei de date cu complexitatea O(n²) unde n este lungimea intrarii.

Demonstratie. La inceput vom arata ca, complexitatea algoritmului SYNTHESE este O(n²). Timpul folosit pentru pasul 4 este mai mic decat timpul executarii pasului 2. Din rationamentele anterioare se stie ca pasul 2 poate fi realizat in timpul O(n²):

Fie R rezultatul aplicarii algoritmului SYINTHESE. Schema R caracterizeaza complet pe F, deoarece multimea F-dependentelor incluse in schema arbitrara R din R este multimea caracteristica a tuturor CF-dependentelor din care a fost sintetizat R. Din consecintele lemei 2 rezulta ca din toate schemele bazei de date caracterizate complet de F, schema R are numar minim de scheme de relatii. Ramane sa aratam ca toate schemele R se gasesc in FN3, in raport cu F: sa examinam relatia R_i din R cu d-cheile Y sintetizate din CF-dependenta (X₁,X₂,,X_k) Y. Daca atributul A in este neprim, atunci A intra in Y, deoarece conform lemei 3, fiecare din este cheie pentru . Fie X cheie pentru (nu obligatoriu d-cheie). Presupunem ca exista submultimea Z din astfel ca F determina XZ si ZA, dar de aici nu rezulta ZX si A XZ. Din multimea G a CF-dependentelor din SYNTHESE, cu ajutorul multimilor caracteristice pentru fiecare CF-dependententa din G formam multimea F'. Sa examinam pentru ZA, H graful aciclic orientat derivat din F'. U(H) nu contine F-dependente din E_F'(X), deoarece multima utila pentru (X₁,X₂,,X_k) Y nu este redusa. in caz contrar am fi obtinut ca ZXIF. Prin urmare excludem A din Y, deci (X₁,X₂,,X_k) Y nu este redusa. Pentru demonstrarea teoremei 1 sunt folosite ambele conditii de reducere a CF-dependentelor: eliminarea atributelor transferabile din partea stanga si atributelor redundante din dreapta. Din algoritmul SYNTHESE nu se poate exclude nici un pas de reducere.

Din exemplul urmator se vede ca exista scheme ale bazei de date in FN3, unde conditia de reducere nu se realizeaza.

Exemplul 20. Fie R=ABCDE si F=. Sa consideram schema bazei de date dedusa din F, compusa din schemele de relatii : R₁= ABCD cu d-cheia si R₂= ABE cu d-cheile Deoarece atributul B este prim (BC este cheie), schema R₁ se gaseste in FN3 desi B depinde partial de AC.

Lema 4. Fie R-schema bazei de date construita din multimea F-dependentelor F cu algoritmul SYNTHESE. Nu exista o alta schema completa a bazei de date dedusa din F cu un numar mai mic de d-chei .

Sa connsideram schema de relatie R in FN3 compusa din:

R₁=ABD, R₂=AC, R₃=BCD

unde atributele subliniate sunt d-chei si alte F-dependente nu sunt. Sa observam ca ABBC, BCAB si BCD. Deoarece atunci R₁ se gaseste in FN3. Dar, din R₁ fara sa schimbam inchiderea multimii de F-dependente aplicabile pe R, se poate elimina D.

Definitia 12. Fie R o schema de relatie din schema bazei de date R pe U , F o multime de F-dependente ,X R si AIR Atributul A depinde exterior de X in raport cu F, daca in U exista o submultime Y astfel ca Y nu este submultime a lui R, in F si A XY .

Dependenta exterioara are sensul care in exemplul 16 este denumit dependenta tranzitiva ascunsa. Pentru schemele bazelor de date in FN3 nu se pot evita intotdeauna.

Exemplul 21 Fie R schema bazei de date compusa din schemele de relatii:

R₁=AB cu d-cheia K₁= si R₂=BC cu d-cheile K₂=

Fie F multimea F-dependentelor reprezentate in R. Deoarece A C, CA, C B atunci B depinde exterior de A, dar B nu se poate elimina din R₁ fara a schimba inchiderea multimii de F-dependente reprezentate in R.

Definitia 13. Fie R schema bazei de date in FN3 in raport cu U, G o multime de F-dependente reprezentate in R iar R o schema de relatie din R. Atributul A din R se numeste eliminabil, daca eliminarea sa nu schimba inchiderea lui G. (Eliminarea lui A atrage dupa sine eliminarea tuturor d-cheilor care contin A).

Schemele complete ale bazei de date in FN3 formate prin metoda descompunerii, nu contin atribute eliminabile. Aceasta este valabil pentru schemele bazei de date sintetizate.

Lema 5. Daca R este schema bazei de date sintetizata din multimea F-dependentelor F, atunci nici o schema din R nu contine atribute eliminabile.

Demonstratie. Presupunem ca R contine un atribut eliminabil A. Fie (X₁,X₂,.,X_h) Y CF-dependenta din care a fost sintetizat R. Atributul A nu poate intra in nici o partea stanga a CF-dependentei. Daca A ar intra in , deoarece A-este eliminabil, atunci X_i poate fi eliminat complet din (X₁,X₂,.,X_h) Y, ceea ce contrazice lema 4 . De unde rezulta ca A intra in Y. Dar atunci A se prezinta ca atribut strain in Y, si (X₁,X₂,.,X_h) Y nu este redusa. in consecinta A nu intra in (X₁,X₂,.,X_h) Y, ceea ce contrazice constructia lui R.

Imbunatatirea algoritmului de sinteza.

Cu toate ca in sinteza se rezolva problemele ce apar la descompunere, exista o deficienta a sintezei care nu se intalneste la descompunere. Daca R este schema bazei de date in FN3 obtinuta dintr-o schema de relatie R unica si din multimea F-dependentelor F cu ajutorul descompunerii, atunci orice relatie r(R), care satisface F, se descompune fara pierderi, in raport cu proiectiile determinate de schemele de relatie din R. Daca R este obtinut cu ajutorul sintezei, aceasta afirmatie nu este adevarata.

Exemplul 22 Fie F=. Algoritmul SYNTHESIZE (F) creaza schemele de relatii :

R₁=A C si R₂=B C

unde atributele subliniate inseamna d-cheile. Totusi relatia de mai jos nu se descompune fara pierderi in raport cu R₁ si R₂

r ( A B C )

a b c

a' b' c

Definitia 14. Schema bazei de date R pe U poseda proprietatea de unire fara pierderi in raport cu o multime de F-dependente F, daca orice relatie care satisface F se descompune fara pierderi in raport cu schemele de relatie din R.

in proprietatea 4 la inceputul subcapitolului 5 se afirma ca schema bazei de date sintetizata trebuie sa posede proprietatea de unire fara pierderi in raport cu multimea de F-dependente reprezentate in R. Din exemplul 22 se vede ca schema bazei de date obtinuta cu algoritmul de sinteza, nu poseda intotdeauna proprietatea unirii fara pierderi. O alta problema este legata de atributele din R care nu intra in dependentele din F. Ele nu apar in schema bazei de date sintetizate din F. Cu ajutorul unei modificari nu prea mari algoritmul SYNTHESE poate rezolva ambele probleme.

Definitia 15. Fie R o schema a bazei de date pe U si G o multime de F-dependente, reprezentate in R. Submultimea X din U se numeste cheie universala a lui R in raport cu G, daca GX U Nu facem ipoteze despre minimizarea lui X.

Daca o schema oarecare de relatie din schema bazei de date R contine o cheie universala, atunci R poseda proprietatea unirii fara pierderi in raport cu F-dependentele prezentate si invers. Problema algoritmului de sinteza consta in aceea ca in R poate sa nu se gaseasca o schema care sa contina cheia universala. Exact aceasta s-a intamplat in exemplul 22 . Problema se poate rezolva daca se adauga o schema constand exclusiv din atributele unei chei universale. in acest caz, trebuie sa recunoastem ca un asemenea adaos, de fapt, incalca minimizarea pe R.

Primul pas al modificarii algoritmului SYNTHESE consta din adaugarea la F, a F-dependentei , unde C este un atribut care nu e continut in U prin aflarea acoperirii inelare G , F -dependenta adaugata nu va fi eliminata. Cand se afla acoperirea minimala a lui F , F-dependenta U C se poate combina cu F-dependenta X Y dar atunci X U si X trebuie sa fie cheie universala. In momentul cand se calculeaza reducerea lui G multimea U poate fi inlocuita cu U', care nu contine atribute transferabile (sau X poate fi redus la X' prin aceeasi metoda). Dar , in consecinta U' este cheie universala. La sintetizarea CF-dependentei care contine ca parte stanga multimea U', apare o schema oarecare de relatie si, in consecinta, U poseda o cheie universala intr-una din schemele sale si are proprietatea de unire fara pierderi in raport cu F. La sfarsitul algoritmului, atributul C se poate eliminat din schema in care el a aparut (el a aparut numai intr-una din ele).

Exemplul 23. Fie F= Adaugam ABC D la F, trecem la acoperirea inelara si dupa reducere avem:

G= CF-dependenta (AB) D se foloseste pentru sinteza schemei.

Schema R₁ contine cheia universala AB. Atributul D poate fi eliminat din R₁ .

5. Atribute eliminabile

S-a aratat ca algoritmul SYNTHESE (F) creaza din F o schema de relatie completa a bazei de date R, care nu contine atribute eliminabile. Prin inlocuirea multimii d-cheilor, este posibil ca schema de relatie R sa nu contina atribute eliminabile.

Exemplul 24 Fie F=. Algoritmul SYNTHESIZE (F) genereaza schema bazei de date R, compusa din schemele de relatii R₁=AB cu d-cheile K₁= si R2=ABCDE cu d-cheile K₂ Atributul B nu-l vom elimina din R2 deoarece el intra intr-o d-cheie din K2.

Daca se inlocuieste K₂ cu , R continua sa caracterizeze complet pe F si B devine eliminabil.

Definitia 16. Fie R o schema completa a bazei de date in raport cu multimea de F-dependente F, o schema de relatie din R si B atribut in R_i . Atributul B este eliminabil in R_i , daca la inlocuirea d-cheilor din R_i , atributul B devine eliminabil din R_i .

Atributul eliminabil din schema bazei de date este obtinut cu ajutorul sintezei si trebuie sa apartina d-cheii unei scheme oarecare; in caz contrar el este eliminat. Daca schema R e generata de algoritmul SYNTHESE, atunci multimea cheilor alternative, daca ea exista, poate fi gasita fara a gasi toate multimile de chei ale lui R. D-cheile din R corespund partilor din stanga ale CF-dependentelor din aceeasi clasa de echivalenta a acoperirii minimale a lui F. Fie schema de relatie R din schema bazei de date R sintetizata din CF-dependenta care apartine acoperirii inelare minimale reduse G a lui F. Astfel, multimea de d-chei a lui R este . Multimile sunt partile din stanga ale F-dependentelor din aceeasi clasa de echivalenta pentru o acoperire minimala oarecare F' a lui F. La fel, stim ca la pastrarea proprietatii de unire orice multime alternativa de chei , are m> k. Daca m> k atunci pentru unele i si j. Atunci se poate elimina din K' fara schimbarea inchiderii F-dependentelor reprezentate in R. in acest fel vom considera ca oricare multime alternativa de chei cautate, are exact k elemente. Fie multimea alternativa a d-cheilor ale lui R. Se cunoaste ca determinarea directa induce intre elementele K si K' o corespondenta bijectiva deoarece ambele pot servi ca parti stanga ale clasei de echivalenta ale unei acoperiri minimale oarecare F. Sa admitem ca sunt numerotate astfel ca si in F. .Se repeta procesul. Cu ajutorul multimii, obtinuta prin inlocuirea d-cheilor din R, care nu contin pe B, se verifica posibilitatea eliminarii atributului B. Fie K' aceasta multime determinata mai sus. Daca , se poate presupune in continuare ca . Daca nu este asa, atunci, deoarece , in K' se poate inlocui X_i , neintroducand in continuare pe B si pastrand R ca schema completa a bazei de date pentru F.

Acum, problema s-a redus mult. incepem cu multimea a d-cheilor din R si pentru fiecare din K care contine B, trebuie gasita cheia inlocuitoare care nu contine B, in raport cu F, pentru care si . Observam ca Z_i trebuie sa fie continut in R, in caz contrar el nu poate fi folosit drept cheie care inlocuieste X_i . Algoritmul AVOID gaseste multimea d-cheilor R, care nu contin pe B, daca ele exista. Algoritmul foloseste procedeul DCLOSURE (X,F) (determina inchierea directa) care gaseste multimea maximala X' astfel ca in F. Procedura INLOCUIE pe X_i in K' cu submultimea minimala Z din M' astfel ZX_i.

0. START [AVOID]

1. INPUT

2. K' K

3. RZ False

4. FOR fiecare X_iIK

4.1 IF BIX_i

THEN

.1 M DCLOSURE(X_i,F)

.2 M' M (R-B)

.3 IF DCLOSURE(M',F) X_i

THEN

.3.1 CALL INLOCUE(X_i, K',Z) / Inlocuie peX in K' cu subset. minim Z

ELSE

.3.2 RZ True

5. IF RZ=False

THEN

5.1 OUTPUT

ELSE

5.2 OUTPUT

6. STOP

Exemplul 25 Fie F, si acelasi ca si in exemplul 24. Algoritmul AVOID _la substituire a lui K2 se va examina doar B si D. Ca multime M apare ca AB D si M' este egal cu AD. in F se realizeaza , astfel in se poate inlocui BD cu AD.

Complexitatea algoritmului este polinomiala. Algoritmul se foloseste pentru in departarea atributelor eliminabile ale schemei de relatie R din schema bazei de date R, creata de algoritmul SYNTHES (F). Algoritmul AVOID (R,B,F) se foloseste pentru fiecare atribut B din R. Daca rezultatul nu este vid, multimea de d-chei din R se inlocuieste cu multimea alternativa obtinuta prin aplicarea algoritmului AVOID.

Se stie ca, daca exista o asemenea multime de chei, la folosirea ei se elimina atributul B. Din RB B se poate extrage o noua multime de F-dependente, reprezentate in R astfel ca, pentru R trebuie sa existe o noua d-cheie K, pentru care (K este una din cheile de schimb gasite de AVOID).

Schema completa a bazei de date fara atribute care pot fi eliminate se gaseste in forma normala LTK (de la Ling, Tomp, Kamed)/ /.

6. Forma normala Boyce-Codd (FNBC)

S-a aratat ca algoritmul de sinteza da nastere la scheme de relatii care se gasesc intr-o forma mai tare decat FN3, in sensul ca nici una din d-chei nu depinde tranzitiv de nici o cheie. intrebarea care se pune este: Se pot elimina toate dependentele tranzitive ? La aceasta intrebare se da un raspuns pozitiv. Plecand de la schema de relatie R si multimea de F-dependente F, se poate gasi pentru R o schema a bazei de date R, lipsita de dependente tranzitive. Sa vedem de ce este de dorit sa se elimine si atributele prime, ce depinde tranzitiv de cheie.

Exemplul 26. Sa consideram relatia cont de schema AEROPORT FIRMA AGENTIE Semnificatia tuplului < a, f, ag > in relatia cont consta din aceea ca, daca cineva pleaca din aeroprtul a cumpara un bilet de la agentia ag, contul trebuie trimis firmei f. Astfel, avem doua F-dependente: AEROPORT FIRMA si AGENTIE FIRMA. Multimea este cheia schemei de relatie, iar FIRMA, este dependenta tranzitiv de AEROPORT AGENTIE. Cu toate ca FIRMA este atribut prim, este de preferat ca el sa fie eliminat din schema deoarece exista o dublare a perechii FIRMA-AGENTIE.

Definitia 1 Schema de relatie R se gaseste in forma normala cu Boyce-Codd (FNBC) in raport cu multimea de F-dependete F, daca ea se gaseste in FN1 si nici un atribut din R nu este tranzitiv dependent de nici o cheie din R. Schema bazei de date R se gaseste in forma normala Boyce-Codd (FNBC) in raport cu multimea de F-dependente F, daca fiecare schema de relatie RIR se gaseste in FNBC in raport cu F.

Observatie. FNBC implica FN3. Schema de relatie din exemplul 26 nu se gaseste in FNBC.

Definitia 28. Schema de relatie R se gaseste in forma normala Boyce-Codd (FNBC) in raport cu multimea de F-dependente F, daca pentru orice submultime Y din R si orice atribut din rezulta in raport cu F, adica, daca Y determina netrivial orice atribut din R, atunci Y este supercheie pentru R.

Se demonstreaza usor ca definitiile 18 si 1 sunt echivalente. Definitia 18 ne permite sa elaboram un algoritm pentru a crea o schema a bazei de date de tip FNBC determinata de multimea de F-dependente F pe schema R.

0. START [FNBC- Algoritm de normalizare Boyce-Codd]

1. INPUT

2. d

3. i

4. R_i R

R

6. CALL Inchidere(F;F⁺)

WHILE d=0

IF exista R_iIR care nu este FNBC

then

OUTPUT

R=(R-R_i) (R_i-X)

else

d

CONTINUE

8. OUTPUT

STOP

Orice schema de relatie care nu este in FNBC se poate oricand descompune intr-o schema a bazei de date in FNBC. Daca pentru schema R are loc Y A in raport F, si si daca Y nu este cheie a lui R, aceasta se va descompune in: si . D-cheile pentru si se gasesc de asemenea, ca si in cazul schemei bazei de date, in FN3.

Exemplul 2 Fie schema de relatie R=AEROPORT FIRMA AGENTIE si F-dependentele, aceleasi ca si in exemplul 26 . Folosind F-dependenta AGENTIE FIRMA, sa descompunem pe R in si d-cheia si cu d-cheia . Din pacate, metoda de sinteza nu garanteaza FNBC.

Exemplul 28. Fie R=ABCDE si F= . Algoritmul SYNTHEZE creeaza urmatoarea acoperire inelara a lui F:

. A doua CF-dependenta din G determina schema de relatie R₂=BCDE cu d-cheia K₂=BCD. Deoarece E C si E nu este cheia lui , schema nu se gaseste in FNBC. Alegand acoperirea inelara echivalenta: , obtinem schema bazei de date FNBC. Din cele aratate anterior rezulta ca, pentru o multime data de F-dependente pe R se poate gasi o schema a bazei de date in FN3 caracterizand complet pe F. Pentru o schema in FNBC aceasta nu este adevarata. Studierea atenta a exemplului 26 arata ca in acest caz nu exista o schema a bazei de date in FNBC, care sa caracterizeze complet multimea data de F-dependente. Astfel suntem pusi in fata alegerii intre FNBC sau a caraterizarii complete a F-dependentelor. Multimea F-dependentelor poate sa nu determine o schema completa si FNBC a bazei de date, in plus, verificarea proprietatii FNBC pentru schema bazei de date propuse, este o problema NP-completa.

A patra forma normala

in capitolul VI am aratat ca orice relatie care satisface MV-dependenta X--Y, se descompune fara pierderi in relatii cu schemele XY si XZ unde Z=R-XY. In cazul cand X--Y este unica in R atunci R se afla in FN3. Prin urmare FN3 nu defineste toate descompunerile posibile.

Definitia 19. MV-dependenta X--Y se numeste triviala pentru schema R care contine XY, daca orice relatie r(R) satisface X--Y.

S-a aratat ca X--Y este triviala daca X Y sau R=XY.

Definitia 20. MV-dependenta X--Y este aplicabila la schema R daca XY R.

Definitia 21. Fie F o multime de F- si MV- dependente pe U. Schema de relatie R U se afla in a patra forma normala (FN4) in raport cu F, daca orice MV- dependenta X--Y dedusa din F si aplicabila la schema R, este fie triviala fie X este o supercheie. Schema bazei de date R, este in a patra forma normala (FN4) in raport cu F daca fiecare schema componenta este in a patra forma normala (FN4) in raport cu F.

Exemplul 28. Fie F= si schema R=ABCDE care nu este in patra forma normala in raport cu F din cauza MV- dependentei C--DE. Schema bazei de date R formata din relatiile R1=ABC si R2=CDE este in a patra forma normala (FN4) in raport cu F. Multimea de F- si MV- dependente pe U poate fi folosita la constructia schemelor bazelor in a patra forma normala analog ca la a treia forma normala. Fie schema R , F o multime de dependente F si X--Y o dependenta ne triviala si pentru care X nu este supercheie. Descompunem R in R₁=XY si R₂=XZ, unde Z=R-XY. Procesul de descompunere se repeta pentru acele scheme R1 si R2 care nu sunt in a patra forma normala (FN4) in raport cu F. Deoarece se folosesc numai MV- dependente ne triviale ambele scheme de relatie care se obtin contin mai putine atribute decat schemele initiale. Prin urmare procesul de descompunere se termina.

Fie R schema bazei de date in a patra forma normala (FN4) in raport cu multimea de F- si MV- dependente F obtinuta prin descompunere. Orice reltie r(R) care stisface F se descompune fara piederi de informatie in relatii dupa schemele din R.

Dam algoritmul FN4 de aducere la forma normala 4 a unei scheme in raport cu o multime de F-dependente si MV- dependente.

0 START[FN4]

1 INPUT}

2 p=1

3 R_p=R

4 R=

5 d=0

6 WHILE d=0

6.1 IF( R_iIR, R_i FN4, X--Y X∩Y= X R_i triviala)

then

6.1.1 R=(R-R_i) (R_i-X) XY

6.2 CONTNUE

7 OUTPUT

8 STOP

Exemplul 29. Fie F= o multime de dependente pe schema R=ABCDEI. Deoarece A--BCD este ne triviala si A nu este cheie descompunem R in schemele R₁ = ABCD si R₂ =AEI. Schema R₂ nu se afla in a patra forma normala in raport cu F. Din F rezulta MV- dependenta B--AC pe R dar aceasta MV- dependenta nu este candidata pentru folosire in descompunere deoarece C BD este cheie pentru R₁. Totus din C D rezulta MV- dependenta C--D care poate fi folosita in descompunerea lui R₁. Astfel se obtine R₁₁=ABC si R₁₂=CD. Ambele scheme se afla in a patra forma normala in raport cu F. Prin urmare schema bazei de date R = se afla in a patra forma normala in raport cu F.

Lema 3. Daca schema R se afla in a patra forma normala (FN4) in raport cu multimea de F- si MV- dependente F atunci R se afla in forma normala Boyce-Codd.

Demonstratie: Presupunem ca R nu se gaseste in forma normala Boyce-Codd. Atunci exista submultimile K, Y, si A din R astfel ca, K este cheie pe R , A KY si K Y , Y/ K, Y A. Din F-dependenta Y A rezulta MV-dependenta Y--A. Deoarece Y nu determina A rezulta ca Y nu este cheie in R. Dependenta Y--A este ne triviala deoarece A nu este continut in Y si YA R prin urmare exista un atribut oarecare B care nu este continut in Y. Prin urmare R nu se afla in a patra forma normala in raport cu F.

8 Forma normala de proiectie-unire

Scopul gasiri unei descompuneri fara pierderi de informatii este eliminarea redundantei din relatii. MV-dependentele reprezinta un procedeu important de realizare a descompunerilor fara pierderi de informatii. Totusi exista MV depndente care nu sunt complet adecvate. O relatie poate sa fie descompusa fara pierderi in trei scheme dar sa nu posede aceasta proprietate pentu oricare doua dintre ele. Descompunerile introduse mai sus care nu corespund MV-depndentelor nu satisfac a patra forma normala si prin urmare nu sunt intotdeauna solutii.

Exemplul 29. Fie relatia din figura 1 se descompune fara pierderi in schemele AB , BC, AC. r(A B C ) r₁( A B ) r₂( A C ) r₃( B C )

a₁ b₁ c₁ a₁ b₁ a₁ c₁ b₁ c₁

a₁ b₂ c₂ a₁ b₂ a₁ c₂ b₂ c₂

a₃ b₃ c₃ a₃ b₃ a₃ c₃ b₃ c₃

a₄ b₃ c₄ a₄ b₃ a₄ c₄ b₃ c₄

a₅ b₅ c₅ a₅ b₅ a₅ c₅ b₅ c₅

a₆ b₅ c₆ a₆ b₅ a₆ c₆ b₅ c₆

Figura 1 Descompunerea relatiei r

Se observa ca r nu satisface nici o MV-dependenta triviala prin urmare nu se descompune fara pierderi de informatii in relatiile r₁, r₂ de scheme AB si BC.

Definitia 22. Fie multimea de scheme de relatie R= din U. Relatia r(U) satisface J-dependenta [R₁,R₂,,. . .R_p], daca r se descompune fara pierderi de informatii, pe R₁,R₂,,R_p adica;

r=p_R1(r)p_R2(r) p_Rp(r) .

in loc [R₁,R₂,,. . .R_p] vom scrie pe scurt [R].

Exemplul 30. Relatia r din figura 1 satisface J-dependenta [AB, AC, BC]. O conditie necesara ca relatia r(U) sa satisfaca J-dependenta [R₁,R₂,,. . .R_p] este ca U = R₁,R₂,. . .R_p. Pe de alta parte J-dependenta aR₁,R₂s are acelasi sens ca MV-dependenta. J-dependenta poate fi definita anolog cu MV-depenndenta. Relatia r satisface J-dependenta [R₁,R₂,. . .,R_p] daca r contine tuplurile t₁, t₂, . . . ,t_p astfel ca pentru toti i, j t_i(R_i R_j)=t_j(R_i R_i) atunci r contine t astfel ca t(R_i)=t_i(R_i), 1<i<p.

Definitia 2. J-dependenta [R₁,R₂,. . .,R_p] pe R se numeste triviala deca ea e satisfacuta de orice relatie r(R).

Definitia 3. J-dependenta [R₁,R₂,. . .,R_p] este aplicabila la schema de relatie R daca R= R₁R₂. . .R_p.

Definitia 4. Fie schema de relatie R si F o multime de F- si J- dependente pe R. Schema R se afla in forma normala PJ in raport cu F daca orice J-dependenta dedusa din F si aplicabila pe R este fie triviala fie fiecare R_i este supercheie pe R. Schema bazei de date R se afla in FNPJ in raport cu F daca fiecare schema R_iIR se afla in aceasta forma.

Observatie : FNPJ implica FN4.

Exercitii

1. Se considera relatia furnizori de schema

R=(NUMEF, ADRESAF, COMBUSTIBIL,PRET) Creati o instanta a bazei si puneti

in evidenta urmatoarele probleme:

a) Redundanta: ( se repeta adresa fiecarui furnizor),

b) Posibilitatea de a avea inconsistenta (anomalii la schimbari ),

c)      Anomalii la inserare (inserati adresa unui furnizor care nu furnizeaaa nimic),

d)      Anomalii la stergere (Daca un furnizor nu furnizeaza nimic se pierde adresa sa).

2. Aratati ca solutia problemei 1 este formata din shemele af(NUMEF, ADESAF) si

fcp(NUMEF, COMBUSTIBIL, PRET).

3. Explicati semantica dependentelor urmatoare:

NUMEF ADRESAF si NUMEF COMBUSTIBIL PRET.

4. Sa se arate ca J-dependenta [R₁,R₂,. . .,R_p] pe R este triviala daca si numai daca

R=R_i pentru un i anumit.

5. Aratati ca FNPJ implica FN4.

6. Fie [R₁,R₂,. . .,R_p] si [S₁,S₂,,S₄] astfel ca pentru orice R_i exista S_j care cuprinde pe R_i. Aratati ca [S₁,S₂,,S₄] implica [R₁,R₂,. . .,R_p].