Normalizarea bazelor de date

Normalizarea bazelor de date

Normalizarea unei baze de date consta in principal in descompunerea modelului bazei de date in mai multe relatii astfel incat sa se reduca la maxim redundanta datelor si implicit sa elimine anomaliile de actualizare. Operatia de normalizare se bazeaza pe dependentele functionale care exista intre datele unei aplicatii.

Concret, pasii care trebuie facuti la proiectarea unei baze de date sunt urmatorii:

Analiza aplicatiei: analiza circuitului informational, studierea intrarilor si iesirilor, stabilirea claselor de utilizatori;

Analiza semanticii atributelor din entitati: identificarea atributelor si a sensului lor functional, gruparea atributelor in relatii pe entitati, stabilirea cheilor primare si externe;

Normalizarea relatiilor obtinute la punctul anterior: micsorarea redundantei prin gruparea atributelor in relatii conform definitiilor pentru formele normale, stabilirea de constrangeri pentru eliminarea anomaliilor de actualizare;

Scoaterea din relatiile principale a atributelor care au peste 70% valori nule.

Dependente functionale (FD)

Reducerea redundantei in baza de date si eliminarea anomaliilor de actualizare (adaugare, stergere) se face riguros prin normalizarea BD pe baza analizei dependentelor functionale. Prin definitie daca se considera un model de BD descrisa printr-o singura relatie universala R(A₁,A₂,A₃,A_n), nu este obligatoriu  sa fie memorata printr-o singura tabela.

O dependenta functionala, notata X Y, intre doua seturi de atribute a unei relatii R, specifica o constrangere asupra n-upletilor posibili. Ea se defineste in felul urmator:

t_1,  t₂ I R, t₁(X) = t₂(X) T t₁(Y) = t₂(Y)

Se spune in acest caz ca X determina functional pe Y sau ca Y este dependent functional de X. Faptul ca X nu determina functional pe Z se va nota X | Z.

O dependenta functionala FD este o proprietate a sensului semantic al atributelor din relatia R. Notam cu F setul dependentelor functionale existente intre atributele relatiei R. Din acestea se pot deduce prin inferenta (deductie) altele.

O dependenta functionala FD care face parte din setul F al relatiei R, se poate deduce ca exista pentru orice realizare (instanta) a relatie r R.

Notam cu F⁺ setul dependentelor functionale deduse din F.

Notam cu F |=  X Y dependenta functionala dedusa din F.

Reguli de inferenta (IR)

Notam  concatenarea atributelor intr-o dependenta functionala XY Z in sensul ca atributele X si Y concatenate determina pe Z. Pentru determinarea dependentelor functionale se pot aplica urmatoarele reguli de inferenta:

1) Regula reflexiva:                    X Y  T X Y

2) Regula de marire:                 T XZ Y

3) Regula tranzitiva:                  T X Z

4) Regula de decompozitie:    T X Y

5) Regula de reuniune:             T X YZ

6) Regula pseudotranzitiva:    T WX Z

Normalizarea relatiilor

Normalizarea bazei de date presupune aducerea relatiilor gradual pe diverse forme normale. Fiecare forma normala preia constrangerile formei anterioare la care adauga noi conditii. Formele normale impun constrangeri dar nu dau solutii. Structura BD se proiecteaza de administratorul BD si proiectantul aplicatiei pe baza experientei si se verifica daca fiecare tabela respecta cerintele de normalizare.

Forma normala 1 (1NF) cere:

• domeniul atributelor sa cuprinda valori atomice (indivizible);  se interzic campurile compuse sau “relatii in relatie”
• fiecare atribut din N-uplet trebuie sa aiba o singura valoare in domeniu.

Exemple

Nu se permite ca la o persoana sa se introduca mai multe numere de telefon. Se pot adauga noi campuri ca Tel_mobil, Tel_serv, Tel_acasa, Fax.

Daca o persoana poate avea mai multe masini se va schimba structura BD, eliminand campul Nrm (numar masina) din tabela Pers si se va introduce CodP (cod proprietar) in tabela Masini. Pentru campul Codp se poate crea un fisier index prin care se vor gasi toate masinile ce apartin unei persoane

Forma normala 2 (2NF) cere ca  relatia sa fie in 1NF si se bazeaza pe dependenta functionala completa (full) fata de cheia primara.

Y este complet dependent functional de X, X Y daca prin eliminarea unui atribut oarecare A din X  (X –A) | Y nu mai determina functional pe Y.

O relatie R este in 2NF daca orice atribut neprim (care nu face parte din cheia primara) este complet dependent functional de cheia primara.

Varianta: Se cere sa nu existe atribute care sa depinda numai de o parte a cheii primare.

Daca nu este indeplinita conditia se vor plasa acele atribute in alta relatie la care se va adauga atributul din cheia primara care le determina.

Exemplu. Se considera o tabela de comenzi  care are Cheia primara NRC +CodP. Campul CodP determina DenP si UM (unitate de masura). Deci cele doua campuri depind numai de o parte a cheii primare si tabela nu este in forma normala 2.

Comanda

Pentru a ajunge in 2NF se vor elimina campurile DenP si UM din tabela Comada, care vor fi plasate intr-o alta tabela Produse in care cheia primara va fi campul CodP.

Comanda

Forma normala 3 (3NF) este bazat pe conceptul de dependenta tranzitiva.

O dependenta X Y din R  este tranzitiva, daca exista un set de atribute Z care nu este cheie in R si exista X Z si  Z Y

O relatie R este in 3NF daca este in 2NF si nu exista nici un atribut neprim din R care sa fie dependent tranzitiv de cheia primara.

Varianta: nu se permit atribute ale relatiei care nu fac parte din cheia primara si care determina alte atribute (fac exceptie cheile candidat). Atributele care determina alte atribute se numesc determinanti.

Definitie generalizata pentru forma 3NF. Orice atribut al relatiei indeplineste:

• este complet dependent functional de orice cheie din R;
• este dependent netranzitiv de orice cheie din R.

Exemplu: Se considera o tabela Comanda in care campul CodV nu face parte din cheia primara si determina campurile NumeV si ComV  (comision)

Comanda

Pentru a aduce relatia in 3NF se vor elimina campurile NumeV si ComV din tabela Comanda si se va crea o alta tabela Vanzator, care va avea cheia primara CodV. Se observa ca pentru a ajunge la forma 3NF dintr-o tabela Comanda s-a ajuns la 3 tabele. Prin normalizare se fragmenteaza BD dar se elimina redundanta  si anomaliile de actualizare.

Comanda

BCNF – Boyce Codd Normal Form este varianta mai restrictiva. O relatie este in BCNF daca, pentru orice dependenta X Y din R, X este o cheie candidat a lui R.

Forma normala 4 (4NF) elimina anomaliile datorate dependentelor functionale multivaloare.

Relatia R(A,B,C…) contine o dependenta multivaloare daca:

- A nu determina univoc pe B si C (A | B si A | C)

- A conduce la valori multiple a lui B (A B)

- A conduce la valori multiple a lui C (A C)

- B si C sunt independente intre ele.

O relatie este in 4NF daca este in BCNF si nu are dependente multivaloare.

Aducerea unei baze de date intr-o forma normala superioara presupune extragerea unor atribute din relatiile existente si crearea pe baza lor a unor noi relatii, astfel incat rezultatul sa respecte conditiile de normalizare. Acest lucru duce la fragmentarea bazei de date, dar elimina din anomaliile de actualizare si reduce spatiul pierdut datorita redundantei datelor.