capitolul 5 normalizarea relaŢ - webbut.unitbv.rowebbut.unitbv.ro/carti...

Cap.5 Normalizarea relaţiilor

142

CCAAPPIITTOOLLUULL 55

NNOORRMMAALLIIZZAARREEAA RREELLAAŢŢIIIILLOORR

La proiectarea bazelor de date relaţionale se stabileşte mulţimea relaţiilor, prin selectarea tipurilor relevante de entităţi din realitatea modelată şi a asocierilor dintre acestea. Modul în care se pot stabili relaţiile unei baze de date nu este unic şi de aceea este necesar să existe criterii de evaluare a calităţii relaţiilor, astfel încât acestea să asigure atât integritatea datelor cât şi performanţe de interogare cât mai bune. Criteriul de evaluare a relaţiilor se bazează pe conceptul de dependenţe de

date.

Dependenţele de date (data dependencies), reprezintă

constrângeri care se impun valorilor atributelor unei relaţii şi

care determină proprietăţile relaţiei în raport cu operaţiile de

inserare, ştergere şi actualizare a tuplurilor. Pe baza dependenţelor de date se pot stabili reguli de definire a relaţiilor, astfel încât acestea să prezinte anumite proprietăţi, proprietăţi care caracterizează formele normale ale relaţiilor (sau gradele de normalizare ale acestora).

O formă normală a unei relaţii (normal form) presupune

anumite condiţii pe care trebuie să le îndeplinească valorile

atributelor şi dependenţele de date definite pe acea relaţie.

Iniţial, E.F. Codd a propus trei forme normale, numite prima formă (FN1), a doua formă (FN2) şi a treia formă normală (FN3). Ulterior, a fost introdusă o definiţie mai completă a celei de-a treia forme, care a primit numele de forma normală Boyce-Codd (FNBC). Toate aceste forme normale se referă la condiţiile pe care trebuie să le îndeplinească dependenţele funcţionale între atributele unei relaţii. Forme normale superioare, cum sunt a patra formă normală (FN4) şi a cincea formă normală (FN5) impun condiţii


143

dependenţelor multivalorice, respectiv dependenţelor de

joncţiune între atributele unei relaţii. Formele normale ale relaţiilor formează o colecţie ordonată

(FN1, FN2, FN3, FNBC, FN4, FN5) şi impun condiţii din ce în ce mai restrictive asupra dependenţelor de date admise, minimizând astfel redundanţa şi anomaliile de actualizare a relaţiilor. Ordonarea formelor normale de la FN1 la FN5 înseamnă că orice relaţie aflată în FN2 este, de asemenea, în FN1, orice relaţie în FN3 este în FN1 şi FN2 etc.

Normalizarea relaţiilor (normalization), constă în

descompunerea lor, astfel încât relaţiile rezultate să

îndeplinească condiţii din ce în ce mai restrictive în ceea ce

priveşte dependenţele de date, adică să corespundă unor forme

normale cât mai avansate.

Prin normalizare se elimină (sau se micşorează) redundanţa datelor memorate în relaţii şi anomaliile care provin din această redundanţă. Totuşi, după normalizare, o parte din interogări vor necesita joncţiuni între relaţiile rezultate prin descompunere, joncţiuni care nu erau necesare dacă relaţia nu ar fi fost descompusă şi care conduc la creşterea duratei de execuţie a acestor operaţii de interogare.

De aceea, în practica proiectării bazelor de date, normalizarea relaţiilor nu se face întotdeauna până în forma normală cea mai înaltă. Proiectanţii pot păstra relaţiile într-o formă de normalizare mai scăzută (de obicei în forma FN3 sau FNBC) cu condiţia ca aceste situaţii să fie bine cunoscute şi documentate, pentru a se trata în mod corespunzător operaţiile în care ar putea să apară anomalii de actualizare a relaţiilor.

5.1. Redundanţa datelor şi anomaliile de actualizare a

relaţiilor

Problemele legate de redundanţa datelor memorate în relaţii vor fi studiate în cadrul unui exemplu.


144

Fie relaţia: AP(IdAngajat,Nume,Prenume,Adresa,IdProie

ct,Ore). Fiecare tuplu al relaţiei conţine informaţii despre un angajat

şi numărul de ore aferente fiecăruia dintre proiectele la care acesta lucrează. Semnificaţia atributelor este destul de clară. Atributul IdAngajat este numărul de identificare (unic) al unui angajat; Nume, Prenume şi Adresa sunt date ale angajatului. Atributul IdProiect este identificatorul (numărul) unui proiect la care lucrează angajatul; se poate considera că este o cheie străină care referă cheia primară cu acelaşi nume dintr-o altă relaţie, care descrie proiectele instituţiei, dar acest lucru nu are importanţă în acest moment. Atributul Ore reprezintă numărul de ore lucrate de angajat la proiectul respectiv.

Dacă se admite că un angajat lucrează la mai multe proiecte, atunci cheia primară a relaţiei AP este PK =

{IdAngajat,IdProiect}. O stare a relaţiei AP este dată în fig. 5.1, a.

Se observă că datele despre fiecare angajat (Nume, Prenume, Adresa), se repetă în fiecare tuplu corespunzător fiecărui proiect la care acesta lucrează, ceea ce reprezintă un grad ridicat de redundanţă a datelor. Această redundanţă are ca efect atât creşterea spaţiului de memorare a relaţiei, cât şi anomalii de actualizare a relaţiei. Anomaliile de actualizare a relaţiei apar la inserarea, ştergerea sau actualizarea tuplurilor relaţiei.

Anomalii de inserare. În relaţia AP nu se pot introduce date despre un angajat (identificatorul angajatului, numele, prenumele, adresa) dacă nu există cel puţin un proiect la care acesta să lucreze. Într-adevăr, nu se poate introduce un tuplu cu valoare NULL a atributului IdProiect, deoarece acest atribut face parte din cheia primară a relaţiei.


145

O altă anomalie de inserare în relaţia AP este aceea că se poate introduce un nou tuplu care conţine alte valori ale atributelor Nume, Prenume sau Adresa, pentru aceeaşi valoare a identificatorului IdAngajat. De exemplu, se poate introduce tuplul: (1,Dragomir,Eugen,Bucuresti,P3,110).

Acest tuplu este acceptat de SGBD, deoarece are cheia primară (1,P3), care nu mai există în relaţia AP. Dar în acest moment starea relaţiei AP nu este consistentă din punct de vedere semantic deoarece există doi angajaţi (Ionescu Ion şi Dragomir Eugen) care au acelaşi număr de identificare (IdAngajat = 1).

Fig. 5.1. a - Relaţia AP; b - descompunerea relaţiei AP în relaţiile A şi P.

Anomalii de ştergere. Dacă se şterg toate tuplurile

referitoare la un anumit proiect din relaţia AP, atunci se pot pierde toate datele referitoare la acei angajaţi care lucrează doar la proiectul respectiv. De exemplu, dacă se şterg tuplurile referitoare la proiectul:


146

P2(1,Ionescu,Ion,Bucuresti,P2,150),(2,Popescu,Petre,Craiova,P2,50),(3,Marin,Mihai,Ploieşti,P2,120), atunci se pierd toate informaţiile despre angajatul Marin Mihai (identificatorul angajatului, numele, prenumele, adresa).

Anomalii de actualizare. Dacă se modifică valoarea unuia din atributele care au valori redundante (Nume,Prenume sau Adresa) într-un tuplu al relaţiei AP, starea relaţiei poate deveni inconsistentă. De exemplu, dacă în tuplul (1,

Ionescu,Ion,Bucuresti,P2,150) se modifică atributul Nume la valoarea Gheorghiu, atunci în relaţie vor exista tuplurile: (1,Ionescu,Ion, Bucuresti,P1,100) şi (1,Gheorghiu,Ion,Bucuresti,P2,150), adică doi angajati cu nume diferite (Ionescu şi Gheorghiu) au acelaşi număr de identificare (1). De asemenea, pot să apară numeroase alte situaţii de inconsistenţă atunci când se fac actualizări într-o astfel de relaţie care prezintă date redundante. Dacă se doreşte păstrarea consistenţei relaţiei AP, trebuie să fie luate măsuri speciale, care constau în realizarea unor proceduri care să verifice datele la fiecare operaţie de actualizare a relaţiei şi să interzică operaţiile care produc inconsistenţă.

Anomaliile descrise mai sus se pot elimina dacă relaţia AP se descompune în două relaţii echivalente: relaţia A(IdAngajat,Nume,Prenume,Adresa), cu cheia primară IdAngajat şi relaţia P(IdAngajat,IdProiect,Ore), cu cheia primară {IdAngajat,IdProiect}, iar atributul IdAngajat este o cheie străină care referă cheia primară cu acelaşi nume din relaţia A (fig. 5.1, b).

Aceste relaţii nu mai prezintă redundanţă şi nici anomalii la actualizarea lor (se poate verifica uşor acest lucru).


147

De exemplu, nu se admite inserarea tuplulului (1,Dragomir,Eugen,Bucureşti) în relaţia A cu starea din fig. 5.1, deoarece sistemul de gestiune refuză introducerea unui nou tuplu cu aceeaşi valoare (1) a cheii primare (IdAngajat).

Relaţiile A şi P sunt “mai bune” din punct de vedere al volumului de date memorate şi sunt, de fapt, relaţii cu un grad de normalizare mai ridicat, aşa cum se va demonstra în secţiunile următoare.

În schimb, interogările asupra acestor două relaţii A, P sunt mai costisitoare (ca timp de execuţie) faţă de interogările similare executate numai în relaţia AP. Fie, de exemplu, interogarea “Care este numărul de ore pe care le lucrează angajatul cu numele Ionescu la proiectul P1 ?”. Expresiile de algebră relaţională pentru realizarea acestei interogări în relaţia AP şi respectiv, în relaţiile A şi P sunt: Q1 = Π

Ore σNume ='Ionescu' AND IdProiect ='P1'

(AP)

Q2 = Π

Ore σNume ='Ionescu' AND IdProiect ='P1'

(A><P)

Pentru realizarea interogării Q2

este necesară o operaţie de

joncţiune între cele două relaţii A şi P în care a fost descompusă relaţia iniţială AP, operaţie care, în general, este mai costisitoare ca timp de execuţie decât operaţia de restricţie aplicată unei singure relaţii.

Cum se poate şti care este cea mai bună alegere a relaţiilor? Răspunsul la această întrebare nu este foarte simplu, deoarece necesită numeroase informaţii privind exploatarea ulterioară a bazei de date (ce spaţiu de memorare a relaţiilor va fi disponibil, ce interogări se vor efectua asupra relaţiilor, în ce situaţii este important să se obţină o viteză de execuţie mare etc.).

Principial, o relaţie trebuie să corespundă unui singur tip de entitate (sau asociere) precis definită şi atributele acesteia să


148

corespundă numai acelui tip de entitate şi să nu fie combinate cu atribute ale altor tipuri de entităţi. Această cerinţă corespunde unei definiţii semantice simple, concise şi clare a relaţiei.

În exemplul de mai sus, relaţia A corespunde tipului de entitate “angajat” şi are ca atribute numai pe acelea care se referă la acest tip de entitate. La fel, relaţia P corespunde asocierii M:N între tipul de entitate “angajat” şi tipul de entitate “proiect” (care nu apare explicit în acest exemplu), iar atributele acesteia se referă numai la acest aspect (numărul de ore lucrate de un angajat la un anumit proiect).

Definiţia semantică a acestor relaţii este simplă şi concisă: “A este relaţia care conţine date despre angajaţii instituţiei”; “P este relaţia care conţine numărul de ore lucrate de angajaţi la proiecte”.

În schimb, relaţia iniţială AP conţine atribute amestecate despre angajaţi şi proiectele la care aceştia lucrează, iar definiţia ei semantică nu mai este atât de simplă şi clară: “AP este o relaţie care conţine date despre angajaţii instituţiei şi câte ore lucrează la fiecare proiect”.

O abordare mai precisă a problemei definirii relaţiilor bazelor de date se poate face pe baza analizei dependenţelor de date şi a normalizării relaţiilor.

5.2. Dependenţe funcţionale

O dependenţă funcţională - DF - (functional dependency) în relaţia cu schema R = {A

1,A

2,...A

n} între două mulţimi

de atribute X şi Y (care sunt submulţimi ale lui R) există dacă şi numai dacă, în orice stare a relaţiei R, fiecărei valori a atributului (simplu sau compus) X îi corespunde o singură valoare a atributului (simplu sau compus) Y.

O dependenţă funcţională este deci o constrângere între două submulţimi de atribute X şi Y ale unei relaţii şi se


149

notează X→Y. Ca exprimare, se mai spune că există o dependenţă funcţională de la X la Y sau că atributul Y este dependent funcţional de X.

Noţiunea de dependenţă funcţională este o extindere a noţiunilor de superchei şi chei ale relaţiilor: atât supercheile (implicit şi cheile) relaţiilor cât şi dependenţele funcţionale sunt constrângeri pe care trebuie să le respecte valorile atributelor relaţiilor.

După cum s-a definit în Capitolul 2, o submulţime K a unei mulţimi de atribute R (care este schema relaţiei cu acelaşi nume), este supercheie a relaţiei R dacă nu există două tupluri diferite în relaţia R care să aibă aceleaşi valori ale atributelor din mulţimea K. Aceasta înseamnă că, dacă t

1[K]=t

2[K],

atunci t1[R]=t

2[R], adică t

1 şi t

2 sunt identice şi

reprezintă un singur tuplu în relaţia R. Dependenţa funcţională X→Y este satisfăcută de relaţia R

atunci când, pentru orice pereche de tupluri t1 şi t

2, t

1[X] =

t2[X] implică t

1[Y] = t

2[Y]. Aşadar, fiind dată o

dependenţă funcţională X→Y în relaţia cu schema R, atributul X este o supercheie a relaţiei dacă atributul determinat (Y) este chiar mulţimea R.

O dependenţă funcţională X→Y impune condiţia ca unei valori (x) a atributului determinant X să îi corespundă o singură valoare (y) a atributului determinat Y. Adică, toate tuplurile care au valoarea (x) a atributului X, trebuie să aibă aceeaşi valoare (y) a atributului Y. Întrucât, în cazul unei superchei, atributul determinat este chiar mulţimea R a atributelor relaţiei şi într-o relaţie nu pot exista două sau mai multe tupluri identice, înseamnă că nu pot exista două sau mai multe tupluri cu aceeaşi valoare (k) a supercheii; această


150

condiţie este cunoscută ca fiind condiţia de unicitate a supercheii.

Deoarece, oricare valoare a supercheii este unică într-o relaţie, valorile atributelor determinate de aceasta sunt absolut necesare şi unice şi nu produc redundanţa datelor. În schimb, fiecare pereche de valori (x,y) ale atributelor X şi Y ale dependenţei funcţionale X→Y poate să apară de mai multe ori în aceeaşi relaţie, indicând faptul că valoarea y este determinată în mod unic de valoarea x, dar acest lucru se repetă de mai multe ori în relaţie, deci reprezintă o redundanţă a datelor.

Aceeaşi proprietate, de a determina funcţional mulţimea de atribute ale relaţiei R, o are şi orice cheie CK (primară sau secundară) a relaţiei date (CK→R), dat fiind că o cheie este o supercheie cu proprietatea de ireductibilitate.

Fiind dată o relaţie şi o mulţime de dependenţe funcţionale care trebuie să fie satisfăcute de orice stare a relaţiei, o parte din dependenţele funcţionale pot fi determinate de chei ale relaţiei (şi acestea sunt constrângeri implicite, care nu produc redundanţa datelor şi nici anomalii de actualizare a relaţiei şi sunt impuse automat de sistemul de gestiune), iar altă parte pot fi determinate de alte atribute care nu sunt chei ale relaţiei (acestea sunt constrângeri explicite care produc redundanţa datelor şi anomalii de actualizare a relaţiei, nu sunt impuse de sistemul de gestiune şi necesită proceduri speciale pentru verificarea şi impunerea lor).

Această diferenţă de comportare a dependenţelor funcţionale în funcţie de tipul atributului determinant (cheie sau non-cheie) face ca analiza lor să necesite cunoaşterea cheilor relaţiei. Cheile relaţiilor se pot preciza explicit (atunci ele implică dependenţele funcţionale corespunzătoare) sau pot fi deduse din mulţimea dependenţelor funcţionale stabilite de proiectant, folosind algoritmi de găsire a cheilor din mulţimea


151

dependenţelor funcţionale. Un astfel de algoritm va fi prezentat într-o secţiune următoare.

Tipuri de dependenţe funcţionale şi atribute. Dependenţele

funcţionale pot fi parţiale sau totale. O dependenţă funcţională

X→Y este parţială (partial dependency), dacă există o

submulţime proprie Z a mulţimii X (adică Z ⊂ X) care

determină funcţional pe Y (Z→Y). O dependenţă funcţională

X→Y este totală (full dependency), dacă nu există nici o

submulţime proprie Z a lui X care să determine funcţional pe

Y. Din această definiţie rezultă că, dacă atributul X este

simplu, dependenţa funcţională X→Y este totală. Dependenţa funcţională X→Y (unde X ⊆ R, Y ⊆ R) este

satisfăcută de orice relaţie R dacă Y ⊆ X. O astfel de

dependenţă funcţională se numeşte dependenţă funcţională

trivială.

Dacă atributul (simplu sau compus), CK este o cheie

candidată a relaţiei R, atunci, conform proprietăţii de

ireductibilitate a cheii candidate, dependenţa CK→R este

totală, adică nu există o submulţime proprie CK’ a lui CK

care să prezinte proprietatea CK’→R.

Atributele care aparţin unei chei se numesc atribute prime,

iar celelalte se numesc atribute neprime.

Exemple de dependenţe funcţionale. Se consideră relaţia AP definită mai sus, în care se pot stabili următoarele dependenţe funcţionale, pe baza semnificaţiei atributelor acesteia:

a) IdAngajat→Nume

b) IdAngajat→Prenume

c) IdAngajat→Adresa

d) {IdAngajat,IdProiect}→Ore

Aceste dependenţe funcţionale specifică faptul că identificatorul angajatului determină în mod unic numele, prenumele şi adresa acestuia (dependenţele a, b şi c) şi că


152

numărul de identificare al angajatului şi identificatorul proiectului determină în mod unic numărul de ore pe care le lucrează respectivul angajat la acel proiect (dependenţa d). Cheia primară a relaţiei {IdAngajat,IdProiect} poate fi definită explicit sau poate fi dedusă din dependenţele funcţionale de mai sus.

5.2.1. Mulţimi de dependenţe funcţionale

În mod obişnuit, proiectantul bazei de date specifică acele dependenţe funcţionale între atribute care sunt evidente din punct de vedere semantic. În afara acestor dependenţe funcţionale, mai există un număr destul de mare de dependenţe funcţionale care se menţin pentru orice stare a relaţiei şi care se pot deduce din mulţimea celor specificate, folosind regulile de deducere (inferenţă - inference rules) ale lui Armstrong. Aceste reguli sunt următoarele:

1) Reflexivitatea (reflexivity): dacă Y ⊆ X, atunci X→Y. Prin această regulă se deduc numai dependenţe funcţionale triviale, care nu aduc informaţii suplimentare, dar care sunt utile în combinaţie cu alte reguli de inferenţă. Următoarele dependenţe funcţionale se deduc prin reflexivitate în relaţia AP:

e) {IdAngajat,IdProiect}→IdAngajat

f) {IdAngajat,IdProiect}→IdProiect

2) Augmentarea (augmentation): dacă X→Y, atunci (X ∪

Z)→(Y ∪ Z). Următoarele dependenţele funcţionale (g şi h) sunt deduse prin augmentare, pornind de la dependenţele funcţionale (a) şi respectiv (b), augmentate cu mulţimea Z = {Nume} (şi tinând seama de faptul că Nume ∪ Nume =

Nume): g) {IdAngajat,Nume}→Nume

h) {IdAngajat,Prenume}→Prenume

3) Tranzitivitatea (transitivity): dacă X→Y şi Y→Z, atunci X→Z. De exemplu, din dependenţele (a) şi (e) rezultă:


153

i) {IdAngajat,IdProiect}→Nume

Armstrong a demonstrat aceste trei reguli (demonstraţia este foarte simplă şi se bazează pe definiţia dependenţelor funcţionale, (Arm74)), precum şi faptul că ele sunt suficiente pentru calculul tuturor dependenţelor funcţionale pe care le implică o mulţime dată de dependenţe funcţionale. În afara acestor trei reguli de bază se mai pot folosi şi alte reguli, care se pot deduce din acestea, şi anume:

4) Proiecţia (projection): dacă X→Y ∪ Z, atunci X→Y şi X→Z.

5) Reuniunea (union): dacă X→Y şi X→Z, atunci X→(Y ∪

Z). 6) Pseudo-tranzitivitatea (pseudo-transitivity): dacă X→Y şi

(W ∪ Y)→Z, atunci (W ∪ X)→Z. Reprezentarea grafică a dependenţelor funcţionale se poate

face ca în fig. 5.2 pentru relaţia AP. Notaţiile folosite sunt uşor de înţeles.

Fig. 5. 2. Dependenţele funcţionale ale relaţiei AP.

Închiderea unei mulţimi de dependenţe funcţionale

(closure of a set of functional dependencies). Fiind dată o

mulţime F de dependenţe funcţionale, mulţimea tuturor

dependenţelor funcţionale care sunt implicate de F se numeşte

închiderea mulţimii F şi se notează F+

. Ca exprimare, se mai spune că dependenţele funcţionale din

F+

reprezintă consecinţa logică a dependenţelor funcţionale


154

din F. Mulţimea tuturor dependenţelor funcţionale F+

se poate deduce prin aplicarea repetată a regulilor de inferenţă ale lui Armstrong asupra dependenţelor funcţionale din F.

De multe ori este necesar să se verifice dacă o anumită dependenţă funcţională X→Y poate fi dedusă dintr-o mulţime dată F de dependenţe funcţionale. Pentru aceasta se poate afla

închiderea F+

a mulţimii F şi se testează dacă (X→Y) ∪ F+

. Această metodă este, însă, destul de laborioasă, deoarece

mulţimea F+

este o mulţime de dimensiune mare, chiar pentru mulţimi F cu un număr mic de elemente. Exista o metodă mai rapidă de a afla dacă o anumită dependenţă funcţională X→Y poate fi dedusă dintr-o mulţime dată F de dependenţe

funcţionale, care se bazează pe noţiunea de închidere (X+

) a

unui atribut X în raport cu o mulţime F de dependenţe

funcţionale. Mulţimi echivalente de dependenţe funcţionale (equivalent

sets of functional dependencies). Două mulţimi de dependenţe

funcţionale E şi F sunt echivalente dacă închiderile lor sunt

egale (E+

=F+

; acest lucru înseamnă că: ∀ DF ∈ E ⇒ DF ∈

F+

şi ∀ DF ∈ F ⇒ DF ∈ E+

). Mulţime minimă de dependenţe funcţionale (minimal set

of functional dependencies). O mulţime de dependenţe

funcţionale G este minimă dacă satisface următoarele

condiţii: (a) membrul drept al oricărei dependenţe funcţionale

din G este un atribut simplu; adică, pentru orice dependenţă

funcţională X→Y din G, Y este un atribut simplu; (b) orice

dependenţă funcţională din G este totală; (c) mulţimea G este

ireductibilă, adică, dacă se exclude o dependenţă funcţională

din G, mulţimea rezultată H nu este echivalentă cu G (adică

H+

≠ G+

).


155

Se poate observa că mulţimea dependenţelor FAP

definite

pentru relaţia AP este o mulţime minimă de dependenţe funcţionale, deoarece satisface cele trei condiţii impuse.

Acoperirea minimă a unei mulţimi F de dependenţe funcţionale (minimal cover of a set F of functional dependencies) este o mulţime minimă de dependenţe

funcţionale G care este echivalentă cu F, adică G+

= F+

. S-a demonstrat că pot exista mai multe acoperiri minime ale unei mulţimi de dependenţe funcţionale şi că întotdeauna se poate găsi cel puţin una dintre acestea folosind algoritmul (Elm00).

5.2.1.1. Dependenţele funcţionale şi cheile relaţiilor

Aşa cum s-a mai arătat, în orice relaţie pot exista două categorii de dependenţe funcţionale:

• Dependenţe funcţionale determinate de cheile relaţiei; astfel de dependenţe funcţionale nu produc redundanţa datelor şi nici anomalii de actualizare a relaţiei.

• Dependenţe funcţionale în care atributul determinant nu este o cheie a relaţiei; astfel de dependenţe funcţionale produc redundanţa datelor şi anomalii de actualizare a relaţiei.

Constrângerile de cheie (primară sau secundară) sunt constrângeri implicite, conţinute în definiţia relaţiei (constrângerile PRIMARY KEY sau UNIQUE din comanda CREATE TABLE) şi sunt verificate şi impuse automat de sistemul de gestiune; proiectantul bazei de date nu trebuie să prevadă nimic suplimentar pentru ca aceste constrângeri să fie satisfăcute de orice stare a relaţiei.

În schimb, dependenţele funcţionale în care atributul determinant nu este o cheie a relaţiei, sunt constrângeri explicite, care nu sunt verificate şi nici impuse de sistemul de gestiune. Verificarea şi impunerea acestor dependenţe funcţionale se poate face numai procedural, prin triggere, proceduri stocate sau funcţii incluse în programele de aplicaţie.


156

De exemplu, în relaţia A, singurele dependenţe funcţionale sunt cele determinate de cheia primară a relaţiei IdAngajat: IdAngajat→Nume,IdAngajat→Prenume,IdAngajat→Adresa. La fel, în relaţia P, dependenţa funcţională {IdAngajat,IdProiect}→Ore este determinată de cheia primară a relaţiei. Aceste dependenţe sunt evidente, rezultate din semnificaţia atributelor definite iniţial pentru relaţia AP (din care provin relaţiile A şi P), dar pot fi şi deduse prin proiecţia mulţimii dependenţelor funcţionale ale relaţiei AP, modalitate care va fi prezentată ulterior. Toate aceste dependenţe funcţionale sunt verificate şi impuse automat de către SGBD la fiecare operaţie de actualizare a acestor relaţii şi nu necesită nici o procedură specială.

În relaţia AP, pe lângă dependenţa {IdAngajat,IdProiect}→Ore care este determinată de cheia primară (este deci verificată automat de sistemul de gestiune), mai există dependenţele: IdAngajat→Nume,IdAngajat→Prenume, IdAngajat→Adresa, care nu sunt determinate de o cheie a relaţiei (IdAngajat nu este cheie în relaţia AP). Pentru astfel de dependenţe funcţionale trebuie să se prevadă proceduri care să verifice şi să impună respectarea constrângerilor respective. Pentru relaţia AP, este necesar ca la orice operaţie de actualizare a relaţiei să se verifice valorile care urmează să fie introduse (sau modificate) şi să nu se admită doi sau mai mulţi angajaţi cu acelaşi număr de identificare dar cu nume, prenume sau adresă diferite, ceea ce înseamnă impunerea dependenţelor funcţionale care nu sunt determinate de cheia relaţiei (IdAngajat→Nume,IdAngajat→Prenume,IdAngajat→Adresa). Astfel de proceduri de verificare vor fi prezentate într-o secţiune următoare.


157

5.2.2. Descompunerea relaţiilor

O descompunere D a schemei de relaţie R (relation schema decomposition) este formată din submulţimi ale lui R (D = {R

1,R

2,...R

k}, unde R

1 ⊂ R, R

2 ⊂ R, ...R

k ⊂ R şi

R = R1

∪ R2... ∪ R

k). Relaţiile cu schemele R

1,R

2,...R

k

sunt proiecţii ale relaţiei R pe submulţimile de atribute corespunzătoare şi reprezintă descompunerea relaţiei R.

Descompunerea unei relaţii, efectuată în scopul normalizării, nu poate fi făcută oricum, ci trebuie să fie respectate anumite condiţii de conservare a semnificaţiei atributelor şi a dependenţelor dintre ele, aşa cum erau definite în relaţia iniţială. În această secţiune şi în cele care urmează se va exprima în mod frecvent o schemă de relaţie ca mulţime a atributelor sale, ceea ce permite notaţii şi definiţii mai simple. Din punct de vedere semantic, descompunerea relaţiilor urmăreşte o separare a conţinutului de informaţie din relaţia dată, astfel încât fiecare dintre relaţiile rezultate să reprezinte un singur tip de entitate sau o asociere între două tipuri de entităţi. Dintre toate descompunerile posibile, numai o parte au proprietatea că pot reconstitui prin joncţiune naturală relaţia iniţială R.

Ca terminologie, se poate considera strict descompunerea

unei scheme de relaţie, ca descompunere a unei mulţimi de atribute (R) în submulţimi ale acesteia (R

1,R

2,...R

k) sau se

poate considera descompunerea relaţiei R prin proiecţia relaţiei R pe submulţimile de atribute corespunzătoare. Ambele expresii pot fi considerate corecte deoarece, chiar dacă există o diferenţă de nuanţă între ele, este clar la ce se referă şi nu pot să apară confuzii. O situaţie asemănătoare se poate observa şi la alte noţiuni legate de normalizare. De exemplu, se poate folosi expresia de normalizare a schemei unei relaţii,


158

prin descompunerea schemei de relaţie date sau normalizarea

relaţiei, prin descompunerea relaţiei date. Fiind dată o relaţie cu schema R şi mulţimea F a

dependenţelor funcţionale ale acesteia, o descompunere D a relaţiei R se numeşte descompunere reversibilă dacă are proprietăţile de joncţiune fără pierdere de informaţie şi de conservare a dependenţelor funcţionale.

5.2.1.2. Proprietatea de joncţiune fără pierdere de

informaţie Fie r extensiunea (starea) unei relaţii cu schema R (adică

r(R) este valoarea la un moment dat a relaţiei cu schema R) şi Π

Ri(r) proiecţia acestei relaţii pe mulţimea de atribute R

i

⊂ R. Descompunerea D = {R1,R

2,...R

i,..R

k} are

proprietatea de joncţiune fără pierdere de informaţie - lossless join) dacă r=Π

R1(r)><Π

R2(r)...><Π

Ri(r)..><Π

Rk(r).

Proprietatea de joncţiune fără pierdere de informaţie (sau de conservare a informaţiei) a unei descompuneri se referă la posibilitatea de a obţine aceeaşi valoare a relaţiei prin joncţiunea relaţiilor rezultate din acea descompunere. Acest lucru înseamnă că, dacă prin joncţiunea proiecţiilor relaţiei date iniţial se obţine o relaţie identică cu aceasta, descompunerea are proprietatea de joncţiune fără pierdere de informaţie.

Lipsa acestei proprietăţi se manifestă în mod paradoxal prin apariţia unor tupluri noi în relaţia obţinută prin joncţiunea relaţiilor R

1,R

2,...R

i,...R

k, tupluri care nu existau în

relaţia R. Aceste tupluri parazite apar ca o pierdere de informaţie din relaţia R şi provin din pierderea unor constrângeri care existau în R şi care s-au pierdut prin descompunerea D = {R

1,R

2,..R

i,..R

k}.


159

Teorema lui Ullman. Descompunerea D = {R1,R

2} a

unei relaţii R este o descompunere fără pierdere de informaţie la joncţiune în raport cu mulţimea F a dependenţelor funcţionale, dacă şi numai dacă este îndeplinită una din

condiţiile: (a)((R1

∩ R2)→(R

1 − R

2)) ∈ F

+

sau (b) ((R1

∩ R2)→(R

2 − R

1)) ∈ F

+

.

Această teoremă oferă o modalitate de descompunere a unei relaţii în două relaţii fără pierdere de informaţie la joncţiune. Din teorema lui Ullman se vede că o descompunere a unei relaţii în două relaţii este fără pierdere de informaţie la joncţiune dacă atributul comun al celor două relaţii rezultate (atributul R

1 ∩ R

2, pe care se va executa joncţiunea naturală),

determină funcţional una din diferenţele dintre mulţimile atributelor celor două relaţii, (R

1 − R

2) sau (R

2 − R

1).

Din condiţiile impuse în teorema lui Ullman, se poate deduce cu uşurinţă că, dacă intersecţia atributelor celor două relaţii rezultate este sau conţine o cheie a uneia dintre aceste relaţii, atunci descompunerea este fără pierdere de informaţie la joncţiune. Într-adevăr, dacă (R

1 ∩ R

2) este o supercheie în

R1, atunci acest atribut determină funcţional orice submulţime

de atribute din R1, inclusiv submulţimea de atribute (R

1 − R

2)

adică (R1

∩ R2)→(R

1 −R

2). În mod asemănător se raţionează

în situaţia în care (R1 −R

2) este o supercheie în R

2.

Reciproc, dacă descompunerea unei relaţii R în două scheme de relaţie R

1 şi R

2 respectă teorema lui Ullman, atunci

atributul comun al celor două relaţii rezultate (adică intersecţia R1

∩ R2) este supercheie fie în relaţia R

1, fie în relaţia R

2.


160

Demonstraţia este foarte simplă. Dacă (R1

∩ R2)→(R

1 −R

2),

atunci, prin augmentare cu (R1

∩ R2) se obţine (R

1 ∩

R2)→((R

1 − R

2) ∪(R

1 ∩ R

2)), rezultă (R

1 ∩ R

2)→R

1 şi

deci (R1

∩ R2) este supercheie în relaţia R

1. Un raţionament

asemănător se poate face pentru cazul în care (R1

∩ R2)→(R

2

−R1) şi rezultă că atributul comun este supercheie în relaţia

R2.

Revenind la exemplele prezentate în secţiunile precedente, se va analiza dacă descompunerile efectuate (în mod intuitiv) prezintă proprietatea de joncţiune fără pierderi de informaţie. Pentru analiza descompunerii relaţiei AP în relaţiile A şi P se calculează: A ∩ P={IdAngajat},A−P={Nume,Prenume,Adresa} P−A={IdProiect,Ore}

Din dependenţele funcţionale: IdAngajat→Nume,IdAngajat→Prenume,IdAngajat

→Adresa se poate deduce dependenţa funcţională IdAngajat→{Nume,Prenume,Adresa} prin regula de reuniune a dependenţelor funcţionale. Rezultă că ((A ∩

P)→(A−P)) ∈ F+

, deci această descompunere îndeplineşte prima condiţie din teorema lui Ullman şi este o descompunere fără pierdere de informaţie la joncţiune.

5.2.1.3. Proprietatea de conservare a dependenţelor

funcţionale

Informal, descompunerea unei relaţii cu schema R în relaţiile cu schemele R

1,R

2,...R

k prezintă proprietatea de

conservare a dependenţelor funcţionale definite de mulţimea F (dependency-preservation), dacă oricare din dependenţele din


161

F se regăseşte sau poate fi dedusă din dependenţele funcţionale ale relaţiilor R

1,R

2,...R

k.

Conservarea dependenţelor funcţionale este necesară pentru ca verificarea şi impunerea constrângerilor definite de dependenţele funcţionale respective să poată fi efectuată la nivelul unei singure relaţii.

Dacă una sau mai multe dependenţe funcţionale se pierd prin descompunerea unei relaţii, atunci constrângerile (definite de dependenţele funcţionale respective), pot fi impuse numai dacă se calculează joncţiunea naturală a relaţiilor rezultate. O astfel de modalitate de verificare este posibilă, dar ineficientă (operaţia de joncţiune fiind o operaţie costisitoare ca timp de execuţie) şi de aceea, în proiectarea bazelor de date se folosesc, pe cât posibil, descompuneri care conservă dependenţele funcţionale.

Înainte de a da o definiţie formală a proprietăţii de conservare a dependenţelor funcţionale, se va defini proiecţia unei mulţimi de dependenţe funcţionale pe o relaţie.

Proiecţia unei mulţimi de dependenţe funcţionale. Fiind dată mulţimea dependenţelor funcţionale F pe relaţia cu schema R, şi o descompunere D = {R

1,R

2,..R

i,...R

k} a

lui R, proiecţia lui F pe Ri

(unde 1 ≤ i ≤ k), notată ΠRi(F),

este o mulţime de dependenţe funcţionale X→Y din F+

, astfel încât X ⊆ R

i şi Y ⊆ R

i.

Această definiţie semnifică faptul că o dependenţă funcţională aparţine proiecţiei lui F pe R

i dacă atât atributele

din partea stângă cât şi atributele din partea dreaptă ale dependenţei funcţionale date aparţin relaţiei R

i. De asemenea

se observă că dependenţele funcţionale ale proiecţiei lui F pe


162

Ri

pot să aparţină nu neapărat lui F, ci închiderii lui F (adică

mulţimii F+

). Pe baza acestor observaţii, se poate da definiţia proprietăţii

de conservare a dependenţelor funcţionale. Conservarea dependenţelor funcţionale. O descompunere

D = {R1,R

2, ...R

i,...R

k} a unei relaţii cu schema R

prezintă proprietatea de conservare a dependenţelor funcţionale definite de mulţimea F, dacă reuniunea proiecţiilor lui F pe relaţiile R

i (unde 1 ≤ i ≤ k) este echivalentă cu F, adică:

((ΠR1(F)) ∪ (Π

R2(F)) ∪... ∪ (Π

Rk(F)))

+

= F+

.

Ca exemplu de descompunere cu conservarea dependenţelor funcţionale, se analizează descompunerea prezentată la începutul acestui capitol, a relaţiei AP={IdAngajat,Nume,Prenume,Adresa,IdProiect,Ore} în relaţiile A={IdAngajat,Nume,Prenume,Adresa} şi P={IdAngajat,IdProiect,Ore}. Mulţimea F

AP a

dependenţelor funcţionale definite pe AP este: FAP

= {IdAngajat→Nume,IdAngajat→Prenume,

IdAngajat→Adresa,{IdAngajat,IdProiect}→Ore

}

Proiecţia mulţimii FAP

pe relaţia A este:

ΠA(F

AP)={IdAngajat→Nume,IdAngajat→Prenume,I

dAngajat→Adresa} deoarece toate atributele implicate de aceste dependenţe funcţionale aparţin relaţiei A: IdAngajat ∈ A,Nume ∈ A,Prenume ∈ A,Adresa ∈ A.

Proiecţia mulţimii FAP

pe relaţia P este:

ΠP(F

AP)={{IdAngajat,IdProiect}→Ore} deoarece

toate atributele implicate de această dependenţă funcţională


163

aparţin relaţiei P: IdAngajat ∈ P,IdProiect ∈ P,Ore

∈ P. Dat fiind că Π

A(F

AP) ∪ Π

P(F

AP) = F

AP, rezultă că această

descompunere conservă dependenţele funcţionale date. Nu întotdeauna este posibilă efectuarea unei descompuneri

cu conservarea tuturor dependenţelor funcţionale. Dacă, prin descompunerea unei relaţii, se pierde una sau mai multe dependenţe funcţionale, constrângerile impuse de acestea nu mai pot fi verificate la nivelul nici uneia din relaţiile rezultate. În această situaţie, procedurile de verificare şi impunere a respectării unor astfel de dependenţe funcţionale trebuie să efectueze mai întâi joncţiunea relaţiilor, pentru a obţine o relaţie în care să se poată verifica acele dependenţe. Un astfel de exemplu va fi prezentat în secţiunea 5.2.6, dedicată formei normale Boyce-Codd.

Cele două proprietăţi ale unei descompuneri, conservarea informaţiei şi conservarea dependenţelor funcţionale sunt independente. Este posibil ca o descompunere să fie fără pierdere de informaţie, dar să nu conserve dependenţele funcţionale, sau invers.

5.2.3. Prima forma normală a relaţiilor (FN1)

O relaţie este normalizată în prima formă normală (FN1), dacă fiecare atribut ia numai valori atomice şi scalare din

domeniul său de definiţie.

Caracterul de atomicitate se referă la faptul că valoarea unui atribut are semnificaţie numai în ansamblul ei şi nu permite descompunerea în componente care să poată fi manevrate separat. Chiar dacă tipul de date peste care este definit domeniul unui atribut este reprezentat prin mai multe componente, acestea nu au semnificaţie luate individual.


164

Valoarea scalară a unui atribut se referă la faptul că un atribut nu poate avea decât o valoare (din domeniul de definiţie pe care este definit) pentru fiecare tuplu.

Sistemele SGBD relaţionale nu admit relaţii care să nu fie cel puţin în prima formă normală, dar proiectarea relaţiilor normalizate în prima formă normală este simplă şi întotdeauna posibilă şi a fost deja prezentată în Capitolul 2.

5.2.4. A doua formă normală a relaţiilor (FN2)

O relaţie este normalizată în a doua formă normală (FN2), în raport cu o mulţime de dependenţe funcţionale F, dacă este

în FN1 şi dacă în F+

nu există nici o dependenţă funcţională

parţială a unui atribut neprim faţă de o cheie a relaţiei.

Din această definiţie rezultă că, dacă orice cheie a unei relaţii este formată dintr-un singur atribut, relaţia este în FN2. Acest lucru este evident, deoarece orice dependenţă funcţională faţă de un atribut simplu este o dependenţă funcţională totală. De asemenea, este evident faptul că o relaţie compusă din două atribute este în FN2, deoarece, fie cheia este formată din ambele atribute şi atunci nu există atribute neprime, fie cheia este formată dintr-unul din atribute iar dependenţa funcţională a celuilalt atribut (care este atribut neprim) faţă de cheie este totală.

Ca exemplu de normalizare în FN2, se va relua relaţia AP prezentată la începutul acestui capitol (fig. 5.4). Schema relaţiei este: AP(IdAngajat,Nume,Prenume,Adresa,IdProiect

,Ore), iar mulţimea dependenţelor funcţionale FAP

stabilite

pe baza semnificaţiei atributelor este cea specificată deja, adică: FAP

= {IdAngajat→Nume,IdAngajat→Prenume,


165

IdAngajat→Adresa,{IdAngajat,IdProiect}→Ore

}

Fig. 5.4. a - Dependenţe funcţionale în relaţia AP (AP nu este în FN2);

b, c -descompunerea relaţiei AP în relaţiile A şi P. Cheia primară este {IdAngajat,IdProiect} şi se

poate deduce din mulţimea dependenţelor funcţionale. Această relaţie este în FN1, deoarece toate atributele iau valori atomice şi scalare. Atributele prime sunt IdAngajat, IdProiect iar atributele neprime sunt Nume,Prenume,Adresa,Ore. Pentru a verifica dacă relaţia este în FN2 trebuie să fie testat tipul dependenţei funcţionale (totală sau parţială) a fiecărui atribut neprim faţă de cheia primară (care este singura cheie a relaţiei în acest exemplu).

Se va testa pentru început tipul dependenţei funcţionale a atributului Nume faţă de cheia primară a relaţiei, adică {IdAngajat,IdProiect}→Nume. Această dependenţă există în virtutea proprietăţii cheii primare. De altfel, ea se poate deduce din dependenţele funcţionale ale relaţiei, prin aplicarea regulilor de inferenţă ale lui Armstrong. Conform proprietăţii de reflexivitate, există dependenţa funcţională {IdAngajat,IdProiect}→IdAngajat şi aplicând regula de tranzitivitate între această dependenţă funcţională şi


166

dependenţa funcţională IdAngajat→Nume, rezultă {IdAngajat,IdProiect}→Nume.

Dependenţa funcţională,{ IdAngajat,IdProiect

}→Nume este parţială, datorită faptului că submulţimea {IdAngajat} a atributului compus cheie primară determină funcţional atributul Nume: IdAngajat→Nume. Rezultă că relaţia AP nu este în FN2. Redundanţa datelor şi anomaliile de actualizare pe care acestea le produc au fost descrise la începutul capitolului. Tot în această parte s-a arătat că relaţia AP se poate descompune în relaţiile A(IdAngajat,Nume,Prenume,Adresa)

şi P(IdAngajat,IdProiect,Ore), care nu mai prezintă redundanţă a datelor şi anomalii de actualizare a tuplurilor. Pentru a determina proprietăţile acestei descompuneri se studiază cele două relaţii rezultate A şi P.

Mulţimea dependenţelor funcţionale din relaţia A este: FA=Π

A(F

AP)={IdAngajat→Nume,IdAngajat→Prenume,Id

Angajat→Adresa}, din care se deduce cheia primară IdAngajat. În toate dependenţele funcţionale din F

A

atributele neprime Nume,Prenume,Adresa sunt total dependente faţă de cheia primară a relaţiei, deci relaţia A este în FN2.

Mulţimea dependenţelor funcţionale din relaţia P este FP=Π

P(F

AP)= {IdAngajat,IdProiect}→Ore}, din care

se deduce cheia primară {IdAngajat,IdProiect}. În dependenţa funcţională din F

P atributul neprim Ore este total

dependent faţă de cheia primară a relaţiei, deci relaţia P este în FN2.

În secţinile anterioare s-a demonstrat că descompunerea relaţiei AP în relaţiile A şi P are proprietatea de conservare a informaţiei (secţiunea 5.2.2.1) şi proprietatea de conservare a


167

dependenţelor funcţionale (secţiunea 5.2.2.2), aşadar această descompunere este o descompunere reversibilă în relaţii FN2.

5.2.5. A treia formă normală a relaţiilor (FN3)

O relaţie este normalizată în a treia formă normală (FN3), în raport cu o mulţime de dependenţe funcţionale F dacă este

în FN2 şi dacă în F+

nu există nici o dependenţă funcţională

netrivială a unui atribut neprim faţă de alt atribut neprim al

relaţiei.

Orice relaţie formată din două atribute este în FN3 deoarece ea se află în FN2 (s-a demonstrat în secţiunea precedentă) şi nu poate exista nici un atribut neprim care să determine funcţional un alt atribut neprim, deoarece o relaţie cu două atribute nu poate avea decât cel mult un atribut neprim.

Ca exemplu de normalizare a unei relaţii în a treia formă normală, se consideră schema relaţiei AFS(IdAngajat,Nume,Prenume,Adresa,Functie,

Salariu), cu mulţimea dependenţelor funcţionale FAFS

={IdAngajat→Nume,IdAngajat→Prenume,

IdAngajat→Functie,Functie→Salariu} (fig. 5.5). Cheia primară a relaţiei este atributul IdAngajat, şi ea poate fi dedusă din mulţimea F

AFS a dependenţelor funcţionale.

Se consideră că fiecare atribut ia numai valori atomice şi scalare, deci relaţia este în FN1. Primele patru dependenţe funcţionale sunt dependenţele funcţionale totale ale unor atribute neprime faţă de cheia primară a relaţiei, deci relaţia este în FN2.

Dependenţa funcţională (Functie→Salariu), semnifică faptul că în instituţia respectivă toţi salariaţii cu aceeaşi funcţie au acelaşi salariu (adică funcţia determină salariul, ceea ce este plauzibil). Această dependenţă funcţională a atributului neprim


168

Salariu faţă de alt atribut neprim (Functie), arată că relaţia nu este în a treia formă normală (FN3)

Fig. 5.5. a- Dependenţele funcţionale ale relaţiei AFS (AFS nu este în

FN3); b, c - descompunerea relaţiei AFS în relaţiei AF şi FS.

Chiar dacă relaţia AFS este în FN2, în aceasta încă mai există redundanţă a datelor, deoarece valoarea salariului corespunzător unei funcţii se înregistrează de mai multe ori, pentru fiecare salariat care deţine acea funcţie. Această redundanţă provoacă anomalii de inserare, ştergere şi actualizare a tuplurilor. De exemplu, nu se poate înregistra valoarea salariului corespunzător unei anumite funcţii, dacă nu se înregistrează cel puţin un salariat cu acea funcţie. Aceasta este anomalia de inserare. Ca anomalie de ştergere, se poate observa că, dacă se şterg tuplurile corespunzătoare tuturor salariaţilor care deţin o anumită funcţie, atunci se pierde informaţia referitoare la salariul corespunzător funcţiei respective. Anomalii de actualizare apar atunci când se actualizează valoarea salariului unui angajat: dacă se modifică salariul fără să se modifice corespunzător şi funcţia, atunci pot exista în relaţie două sau mai multe tupluri care au aceeaşi valoare a atributului Functie, dar valori diferite ale


169

atributului Salariu, deci nu este respectată dependenţa funcţională Functie→Salariu.

Astfel de redundanţe şi anomaliile de actualizare pe care le provoacă se pot elimina dacă se descompune relaţia în două (sau mai multe) relaţii, care să nu conţină date redundante.

Relaţia AFS se poate descompune în relaţiile AF(IdAngajat,Nume, Prenume,Adresa,Functie)

şi FS(Functie,Salariu). Se poate verifica uşor că fiecare din aceste relaţii se află în FN3.

Dependenţele funcţionale ale relaţiei AF reprezintă proiecţia dependenţelor funcţionale date iniţial (F

AFS) pe relaţia

AF:FAF

=ΠAF(F

AFS)={IdAngajat→Nume,IdAngajat→Pr

enume,IdAngajat→Functie}. Cheia primară a relaţiei AF este IdAngajat, şi se poate deduce uşor din dependenţele funcţionale ale relaţiei AF (F

AF). Se observă că

toate dependenţele funcţionale ale relaţiei AF determinate de cheia primară sunt totale şi că nu există nici o dependenţă a unui atribut neprim faţă de alt atribut neprim, deci relaţia AF este în FN3.

Dependenţele funcţionale ale relaţiei FS reprezintă proiecţia dependenţelor funcţionale date iniţial (F

AFS), pe

relaţia FS: FFS

=ΠFS(F

AFS)={Functie→Salariu}. Cheia

primară a relaţiei este atributul Functie şi se deduce cu uşurinţă din mulţimea F

FS a dependenţelor funcţionale ale

acestei relaţii. Singura dependenţă funcţională a relaţiei FS este o dependenţă funcţională totală determinată de cheia primară a relaţiei, deci relaţia FS este în FN3. Pentru verificarea proprietăţii de joncţiune fără pierdere de informaţie se calculează AF ∩ FS = {Functie} şi FS−AF={Salariu}. Deoarece dependenţa funcţională


170

(Functie→Salariu) ∈ FAFS

, rezultă (conform teoremei lui

Ullman) că descompunerea relaţiei AFS în relaţiile AF şi FS este o descompunere fără pierdere de informaţie la joncţiune.

Pentru verificarea conservării dependenţelor funcţionale, se calculează mai întâi reuniunea dependenţelor funcţionale ale relaţiilor AF şi FS: FAF

∪ FFS

={IdAngajat→Nume,IdAngajat→Prenume,

IdAngajat→Functie,Functie→Salariu}

Se observă că FAFS

= FAF

∪ FFS,

deci descompunerea

realizată conservă dependenţele funcţionale stabilite iniţial. Aşadar, descompunerea relaţiei AFS în relaţiile AF şi FS are atât proprietatea de conservare a informaţiei cât şi proprietatea de conservare a dependenţelor funcţionale, deci este o descompunere reversibilă.

S-a demonstrat că orice schemă de relaţie poate fi descompusă reversibil în scheme de relaţii FN3 şi există un astfel de algoritm de descompunere.

5.2.6. Forma normală Boyce-Codd (FNBC)

O relaţie cu schema R este în forma normală Boyce-Codd

(FNBC), în raport cu o mulţime F de dependenţe funcţionale

dacă este în FN1 şi dacă, pentru orice dependenţă funcţională

netrivială X→Y din F+

, X este o cheie a relaţiei R.

Se poate observa asemănarea dintre formele normale FN3 şi FNBC, ambele impunând condiţia ca atributul care determină funcţional alte atribute să fie o cheie a relaţiei. Forma normală Boyce-Codd este mai restrictivă decât FN3, deoarece în FNBC se impune această condiţie tuturor atributelor, prime sau neprime, pe câtă vreme în FN3 condiţia se impune numai atributelor neprime. Este evident faptul că o relaţie în FNBC este, de asemenea în FN3, dar o relaţie în FN3 poate să fie sau nu în FNBC.


171

Orice relaţie formată din două atribute este în FNBC. Explicaţia este similară cu explicaţia dată pentru faptul că orice relaţie formată din două atribute este în FN2 sau în FN3.

5.2.7. Algoritmi de descompunere a relaţiilor

În general, scopul normalizării este acela de a obţine relaţii într-o formă de normalizare cât mai avansată, care elimină toate sau majoritatea anomaliilor de actualizare.

Orice relaţie se poate descompune în relaţii FN2, FN3 sau FNBC fără pierdere de informaţie la joncţiune cu ajutorul unui algoritm care este prezentat şi demonstrat în continuare. Deşi acest algoritm nu garantează conservarea dependenţelor funcţionale, în multe situaţii este posibil ca să se obţină o descompunere care să prezinte şi această proprietate.

O descompunere care să asigure atât conservarea informaţiei cât şi a dependenţelor funcţionale nu poate garanta decât obţinerea unor relaţii în FN3 şi un astfel de algoritm (prezentat în manual). În multe situaţii, cu acest algoritm se pot obţine chiar relaţii FNBC, dar forma normală garantată este doar FN3.

5.2.8. Verificarea şi impunerea constrângerilor explicite

Analiza normalizării relaţiilor trebuie să fie realizată

pentru orice proiect de baze de date, pentru a asigura funcţionarea corectă a acesteia. După ce se decide forma normală cea mai potrivită a unei relaţii, este necesar să se prevadă procedurile de verificare a tuturor constrângerilor explicite rămase.

Dacă relaţia se păstrează într-o formă de normalizare mai redusă, atunci trebuie să se prevadă proceduri de verificare şi impunere a dependenţelor de date care nu sunt determinate de cheile relaţiei (constrângeri explicite).


172

Dacă prin descopmunerea unei relaţii se pierde o dependenţă funcţională, aceasta poate fi impusă explicit printr-o procedură stocată sau o funcţie în programul de aplicaţie, care execută joncţiunea între relaţiile rezultate şi impune constrângerea respectivă.

5.3. Dependenţe multivalorice

O dependenţă multivalorică - DMV- (multivalued

dependency), X→→Y specificată pe o relaţie cu schema R = {X,Y,Z} stabileşte următoarele constrângeri pe care trebuie

să le respecte orice stare r a relaţiei R: dacă există două

tupluri t1 şi t

2 în r astfel ca t

1[X] = t

2[X]= x, atunci

vor exista şi tuplurile t3 şi t

4 cu următoarele proprietăţi:

• t3[X] = t

4[X] = t

1[X] = t

2[X] = x;

• t3[Y] = t

1[Y] = y

1 şi t

4[Y] = t

2[Y] = y

2 ;

• t3[Z] = t

2[Z] = z

2 şi t

4[Z] = t

1[Z] = z

1 .

Datorită simetriei egalităţilor de mai sus, se poate spune că, dacă într-o relaţie R există dependenţa multivalorică X→→Y, atunci există şi dependenţa X→→Z, unde Z = R−(X ∪ Y).

Definiţia de mai sus arată că, fiind dată o valoare particulară a atributului X, mulţimea de valori ale lui Y determinate de această valoare a lui X este complet determinată numai de X şi nu depinde de valorile atributelor rămase (Z) ale relaţiei. De aici rezultă că, atunci când două tupluri au valori distincte ale atributului Y dar aceeaşi valoare a atributului X, aceste valori ale lui Y trebuie să fie repetate pentru orice valoare distinctă a lui Z care apare pentru această valoare a lui X.

O relaţie cu schema R este în a patra formă normală

(FN4), în raport cu o mulţime F de dependenţe funcţionale şi


173

multivalorice dacă este în FN1 şi dacă, pentru orice

dependenţă multivalorică netrivială X→→Y din F+

, X este

cheie a relaţiei R.

Se poate observa asemănarea acestei definiţii cu definiţia FNBC: pentru FNBC se impun restricţii dependenţelor funcţionale, iar pentru FN4 se impun restricţii dependenţelor multivalorice. Dar, dat fiind că o dependenţă funcţională este un caz particular al unei dependenţe multivalorice, dacă o schemă de relaţie respectă condiţia de FN4, atunci înseamnă că ea respectă şi condiţia de FNBC. Restricţiile impuse se pot rezuma la faptul că într-o relaţie nu trebuie să existe decât dependenţe determinate de chei ale relaţiei.

5.4. Dependenţe de joncţiune şi a cincea formă normală

Teorema lui Ullman, ca şi generalizarea acesteia pentru dependenţele multivalorice, precizează condiţiile de descompunere fără pierdere de informaţie la joncţiune a unei relaţii R în două relaţii R

1 şi R

2. Există totuşi situaţii în care

nu se poate efectua descompunerea fără pierdere de informaţie la joncţiune a unei relaţii în două relaţii, dar se poate efectua în trei sau mai multe relaţii. Astfel de cazuri sunt studiate pe baza dependenţelor de joncţiune şi a celei de-a cincea forme normale (FN5). Este de reţinut că astfel de cazuri sunt foarte rare şi, în acelaşi timp, foarte dificil de studiat.

Dependenţă de joncţiune (join dependency). Fie o relaţie

cu schema R şi R1,R

2,...R

k submulţimi de atribute ale

mulţimii R, unde R1

∪ R2

∪...∪ Rk = R. Se spune că

există o dependenţă de joncţiune pe R, notată

*(R1,R

2,...R

k), dacă şi numai dacă orice stare r a

relaţiei R este egală cu joncţiunea proiecţiilor relaţiei pe


174

submulţimile R1,R

2,..R

k, adică r = Π

R1(r)><

ΠR2(r)...>< Π

Rk(r).

Cu alte cuvinte, *(R1,R

2,...R

k) este o dependenţă de

joncţiune pe R dacă şi numai dacă descompunerea lui R în proiecţiile pe R

1,R

2,...R

k este fără pierdere de informaţie.

Se poate spune că relaţia R este k-decompozabilă fără pierdere de informaţie dacă există o dependenţă de joncţiune *(R

1,R

2,...R

k).

Cazul k = 1 reprezintă o dependenţă de joncţiune trivială, deoarece o astfel de descompunere este posibilă pentru orice schemă de relaţie şi nu reprezintă nici o constrângere asupra relaţiei.

Cazul k = 2 al unei dependenţe de joncţiune este o dependenţă multivalorică. Într-adevăr, s-a demonstrat că o relaţie în care există o dependenţă multivalorică se poate descompune fără pierdere de informaţie în două relaţii, deci o dependenţă multivalorică îndeplineşte condiţia de dependenţă de joncţiune cu k = 2. Cu alte cuvinte, o dependenţă multivalorică X→→Y în relaţia R reprezintă o dependenţă de joncţiune *(XY,XZ), unde Z = R–(X ∪ Y).

Pentru cazul k > 2 dependenţele de joncţiune nu mai sunt echivalente cu dependenţele multivalorice, sunt mult mai dificil de identificat şi nu există reguli de deducere (inferenţă) care să genereze toate dependenţele de joncţiune pornind de la o mulţime dată.

Datorită acestor aspecte, analiza dependenţelor de joncţiune are un pronunţat caracter intuitiv. Aşa cum o dependenţă multivalorică permite reprezentarea în aceeaşi relaţie a două asocieri independente, o dependenţă de joncţiune permite reprezentarea în aceeaşi relaţie a unui număr de k asocieri independente (k > 2).


175

A cincea formă normală (FN5). O relaţie cu schema R

este în a cincea formă normală (FN5) în raport cu o mulţime F

de dependenţe funcţionale, multivalorice sau de joncţiune dacă

este în FN1 şi numai dacă, pentru orice dependenţă de

joncţiune *(R1,R

2,... R

i,...R

k) din F

+

, Ri

(unde 1 ≤

i ≤ k) este o cheie a relaţiei R. Având în vedere faptul că o dependenţă multivalorică este

un caz special de dependenţă de joncţiune, iar o dependenţă funcţională este un caz special de dependenţă multivalorică, se poate afirma că o relaţie care este în FN5, este implicit în FN4, deci şi în FNBC ş.a.m.d.

Se poate observa că orice relaţie poate fi transformată în relaţii FN5 printr-o descompunere fără pierdere de informaţie.

5.5. Decizii de normalizare a relaţiilor

La proiectarea unei baze de date, proiectantul defineşte schemele relaţiilor şi constrângerile de integritate care trebuie să fie satisfăcute de orice stare a relaţiilor (constrângeri de domeniu, constrângeri de tuplu, constrângeri de integritate referenţială, dependenţe de date, aserţiuni).

Normalizarea relaţiilor are ca scop transformarea relaţiilor definite iniţial în alte relaţii, astfel încât toate (sau majoritatea) dependenţele de date impuse să fie păstrate, dar ele să fie determinate de chei ale relaţiilor nou obţinute.

Acest deziderat al operaţiei de normalizare provine din faptul că dependenţele faţă de cheile relaţiei sunt constrângeri implicite care nu produc redundanţă a datelor, nici anomalii de actualizare şi sunt verificate automat de SGBD atunci când relaţia este actualizată, în timp ce dependenţele care nu sunt determinate de chei sunt constrângeri explicite, care produc redundanţa datelor şi anomalii de actualizare. Aceste din urmă dependenţe (care nu sunt determinate de cheile relaţiei) nu sunt verificate automat de SGBD, iar pentru evitarea unora din


176

anomaliile produse, sunt necesare proceduri speciale de calcul (triggere, proceduri stocate sau funcţii în programele de aplicaţii).

Normalizarea relaţiilor se realizează prin descompunerea acestora, iar la fiecare pas de descompunere trebuie să se verifice conservarea informaţiei şi conservarea dependenţelor de date. Descompunerile care nu conservă informaţia sunt inacceptabile, dar se pot admite descompuneri care nu conservă dependenţele de date. Dacă se efectuează o descompunere care nu conservă dependenţele funcţionale, atunci pentru fiecare dependenţă pierdută trebuie să se prevadă proceduri care să verifice şi să impună constrângerile prevăzute de aceasta. Dacă o relaţie se păstrează într-o formă de normalizare mai redusă, atunci trebuie să se prevadă proceduri de verificare a dependenţelor de date care nu sunt determinate de chei ale relaţiei.

Normalizarea relaţiilor asigură un proiect al bazei de date mai concis şi mai portabil şi de aceea, ca regulă generală, se consideră că a normaliza este avantajos, chiar dacă normalizarea în sine nu este o garanţie că s-a realizat cel mai bun model al realităţii modelate. Mai mult, cu cât nivelul de normalizare creşte, cu atât se obţin mai multe relaţii cu grad mai mic (cu număr mai mic de atribute), iar pentru realizarea fiecărei interogări sunt necesare mai multe operaţii de joncţiune, ceea ce face ca timpul de execuţie a interogărilor să crească.

În general, se recomandă ca relaţiile asupra cărora se efectuează operaţii de actualizare frecvente să fie normalizate într-o formă normală cât mai avansată, iar relaţiile asupra cărora se efectuează interogări frecvente pot fi păstrate într-o formă de normalizare mai redusă. O astfel de soluţie, de a păstra (sau de a aduce) unele relaţii într-o formă de normalizare mai redusă se numeşte “denormalizare” şi se efectuează cu


177

scopul de a obţine performanţe cât mai ridicate la execuţia unor interogări.

Proiectarea bazelor de date pornind de la diagrama Entitate-Asociere conduce, în general, la relaţii normalizate, deoarece:

• Relaţiile corespunzătoare mulţimilor de entităţi sunt, de regulă, relaţii normalizate, dat fiind că toate atributele descriu tipul de entitate respectiv.

• Relaţiile de asociere binară, care conţin două chei străine care referă cheile primare din cele două relaţii pe care le asociază, rezultă, de asemenea, ca relaţii normalizate.

• Relaţiile care modelează asocierile multiple pot să rezulte nenormalizate, aşa cum s-a putut observa din ultimele două secţiuni (5.3 şi 5.4), şi necesită operaţii de normalizare suplimentare.

Aspectele teoretice şi exemplele prezentate în acest capitol au scopul de a convinge proiectanţii şi programatorii din domeniul bazelor de date că este practic imposibil să se obţină o funcţionare corectă a unui sistem de baze de date fără să se facă analiza normalizării relaţiilor. Fără analiza normalizării poate exista oricând redundanţă a datelor care, mai devreme sau mai târziu, se va manifesta ca o inconsistenţă a datelor, a cărei cauză este greu de identificat şi de localizat.

capitolul 5 normalizarea relaŢ - webbut.unitbv.rowebbut.unitbv.ro/carti...

Documents