Forme normale si mecanismul normalizarii

FORME NORMALE SI MECANISMUL NORMALIZARII

Agenda

1. Consideratii generale

Definitii preliminare

Prima forma normala

Teorema de descompunere

A doua forma normala

Forma a 3-a normala (3nf) si variantele (3 ½ nf)

1. Consideratii generale

Intreprindere = un univers real.

Model - modelele de date, modelul conceptual → schema conceptuala, model logic global → modele arborescente, in retea sau relationale.

Schema de date = imaginea la nivel relational a schemei conceptuale si deci a intreprinderii. Baza de date = schema de date + datele (intenia - extensia)

Problema centrala a proiectarea unei baze de date este: Stabilirea ansamblului relatiilor care descrie corect schema conceptuala, si deci, intreprinderea.

Dupa stabilirea schemei conceptuale - (proiectarea bazelor de date) stabilirea schemei logice globale - structura bazei de date. Pentru stabilirea structurii - diferite tabele. In timpul proiectarii - transformarea tabelelor in relatii corecte.

Exemplu. Fie o tabela cu orarul salilor de curs din Facultatea de Stiinte Economice. Sa consideram deci tabelul:

Probleme:

Atomicitate?

Dependente de tip N:1 (functionale):

Sala → Capacitate

Adica mai multe sali (022, 033) au aceeasi capacitate de 150 de locuri.

→ se pot genera mai multe tipuri de anomalii:

redundanta logica - perechile de forma (026, 100) sau (022,150) apar de mai multe ori;

anomanii de stocare

o       anomalii de inserare - se termina o noua sala de curs; nu poate fi introdusa in tabela orarului pana nu se da o valoare pentru cheia primara Sala# - nu poate fi vida in nici o relatie (nul);

o       anomalii de stergere -sala 022 trebuie scoasa din orar - reparatii; stergerea liniilor → pierde legatura (Sala, Capacitate) - legatura semantica.

o       Anomalii de modificare - s-a extins capacitatea salii 022 la 120 de locuri → sa se urmareasca toate tuplele (022,100) - daca se scapa una dintre ele - anomalie - aceeasi sala apare cu doua capacitati diferite.

probleme de reconexiune:

Sala1:	Sala2:
Sala# Capa citate	Capa citate Orar An Materia Cadru didactic Zi Ora Luni IE III Baze de date Ionesu Luni MF III MRU Popescu Luni CIG III Bazele contabilitatii Georgesu Luni IE III Cap. Spec. Baze de date Ionescu Luni IE III Contabilitate Financiara Georgescu

Recompun prin echijoin → un tabel de forma:

fiecare tuplu din tabelul din stanga se combina cu fiecare tuplu din tabela a doua pe baza egalitatii cheii comune, deci nu se ajunge la tabelul initial.

→ Mecanismul - la dispozitie proiectantul sau administratorul bazei de date pentru rezolvarea acestor probleme - NORMALIZARE

Normalizarea - operatie prin care se urmareste:

transformarea tabelelor in relatii;

inlaturarea redundantelor;

inlaturarea dependentelor interne intre atributele unei relatii, transformandu-le in dependente intre tabele obtinute prin descompunere (intrarelatii → interrelatii);

inlaturarea diferitelor anomalii (de inserare, modificare sau stergere) existente initial sau aparute in urma descompunerii tabelelor;

asigurarea descompunerilor fara pierderi - recompunand tabelele obtinute in urma descompunerilor uni tabel trebuie sa se ajunga la tabelul initial.

Normalizarea - procesul iterativ prin care baza de date se aduce la o forma standard in - dispare fenomenul de redundanta, nu exista anomalii si fiecare tabel contine o singura entitate semantica (nu exista dependente intre atribute).

Forme normale - parcurse piramidal de la Forma 1-a normala (1NF) pana la Forma a 5-a normala (5NF). (Date - forma a 6-a normala). Aducerea la 1NF este obligatorie pentru a aduce o tabela la forma unei relatii. Proiectare - 3NF.

Teoria normalizarii - vast, materialele referitoare la teoria sau proiectarea bazelor de date relationale:

teoretic [Ullmann80, Abitaboul01]

mai pragmatic [Date2004, Connolly&co2001, Nitchi&co2006].

Nu este obligatorie si nici nu se merge de regula pana la ultimul nivel de normalizare (Francoise Pascal).

2. Definitii preliminare

Algoritmul - de la o relatie data intr-o forma normala se ajunge la o relatie in forma imediat superioara - algoritm de descompunere

Dependenta de tip n:1 - o dependenta functionala (DF). Exemplu: Sala → Capacitate. DF - functia din matematica: Sala → Capacitate. Deosebirea - timp ce functia matematica - atemporala, DF depinde de timp. DF se numesc si dependente univoce

Observatie. A si B doua grupuri de atribute dintr-o tabela - DF daca si numai daca din t₁(A) = t₂(A) rezulta t₁(B) = t₂(B), cu t_i(A), respectiv t_i(B) pentru i=1,2 s-au notat subtupluri corespunzatoare lui A respectiv B.

A - domeniul de definitie sau determinantul, B - valorilor sau cel determinat

R o relatie, A si B - doua multimi de atribute → intre A si B - dependenta functionala totala, si de noteaza cu DFT: A→B ↔ au loc urmatoarele 2 conditii:

1. DF: A→B

2. Nu exista nici o submultime proprie A' a lui A ca DF: A'→B.

O DF care nu este totala este o dependenta functionala partiala

Dependenta functionala tranzitiva A→B, B→C → A→C

Observatie. Dependentele multivoce (DM) - unui element din A corespund un ansamblu de elemente din B. Exemplu, (Sala, An_de_Studiu), sau (Sala, Cadru_ Didactic). Dependenta tranzitiva din cadrul DF se poate extinde si pentru DM.

E o multime de dependente (DF sau DM) - E⁺ a tuturor dependentelor tranzitive obtinute din E - numeste inchiderea lui E

E si E' - 2 multimi de dependente si E' contine dependentele din E precum si unele dependente obtinute din E aplicand proprietatile dependentelor → E' - acoperire a lui E ↔ E si E' au aceeasi inchidere.

Proprietati DF - cele mai cunoscute sunt axiomele lui Armstrong - 1974. Fie R o relatie si A,B,C trei multimi de atribute ale ei. Pentru dependentele functionale au loc urmatoarele axiome:

A1. Reflexivitatea A→A, mai general, daca A'A rezulta A→A'.

A2. Cresterea determinantului

daca DF: A→B

A C

→ DF: C→B.

DF: C→B - dependenta functionala partiala.

A3. Tranzitivitatea:

A→B

B→C

→ A→C.

DF:A→C - inchiderea tranzitiva a primelor doua dependente - C depinde tranzitiv de A.

Multimile de axiome - 2 notiuni care permit caracterizarea lor:

o multime de axiome - completa ↔ pornind de la o multime de dependente E→ pe baza axiomelor →toate dependentele E⁺.

o multime de axiome inchisa ↔ pornind de la E nu se pot deduce, cu ajutorul axiomelor, dependente care nu fac parte din E.

→T.Ullman (1980): Multimea axiomelor lui Armstrong este completa si inchisa.

E' - acoperire minimala ↔ acoperire a lui E & nici o parte a lui E' nu este acoperire.

Observatie.

acoperirea minimala - rol important in descompunerea relatiilor;

o multime de aplicatii - mai multe acoperiri minimale.

Descompunere reversibila: fara pierderi - recompunand relatiile obtinute prin descompunere → relatia initiala. Relatie ireductibila nu poate fi descompusa in mod reversibil.

Observatie. Relatie ireductibila - o singura entitate semantica → relatiile ireductibile pot fi considerate module logice pe baza carora se modeleaza intreprinderea.

Descompunere atomica a lui R - descompunere reversibila a lui R in relatii ireductibile.

Prima forma normala

PERSONAL:

Nu este o relatie in 1NF:

Domiciliu = (Judet, Localitate, Strada, Numar) - nu este atomic,

Copil este repetitiv; cate campuri sa se rezerve?

O relatie este in prima forma normala (1NF) - fiecare atribut (camp) este atomic si tabela nu contine grupuri repetitive.

Trecerea unui tabel la 1NF:

atributele care nu sunt atomice se transforma in atribute atomice prin proiectare (descompunere) si eventual redenumire;

pentru campurile repetitive - introduc tuple cate aparitii are campul respectiv, fiecare tuplu continand o aparitie a campului.

Trecerea de mai sus poate fi rezumata astfel:

PERSONAL1:

→ Ionescu are 3 copii, el va avea 3 tuple de forma:

→Tabelul - cantitate mare de informatie redundanta datorita grupului repetitiv. Pentru a inlatura se descompune (prin proiectie) in doua:

PERS1:

si tabelul COPII:

unde MARCA# - cheie straina - asigura legatura cu tabelul PERS1 - restul date proprii copiilor. MARCA# este cheie primara? → cheie primara "Nume si Prenume" + "Data-Nasterii".

→ doua tabele in prima forma normala, iar prin recompunerea tabelelor (prin echijoin) se ajunge la relatia initiala, deci descompunerea este fara pierderi, adica:

PRESONAL = PERS1 [MARCA# = MARCA#] COPII

4. Teorema de descompunere

Descompunerea se utilizeaza pentru a evita anomaliile de stocare.

Teorema de descompunere reversibila (Delobel & Cassey 1973): R o relatie definita pe multimea atributelor Ω, R(Ω) si A,B,C o partitionare a lui Ω, astfel ca DF:A→B. Atunci R(Ω)poate fi descompus fara pierderi, in doua relatii R(Ω₁ ) si R(Ω₂ ), unde

Ω₁=A U B - reuniunea atributelor din DF

Ω₂=A U C- reuniunea atributelor care nu fac parte din DF.

→ Descompunerea - izolarea a doua concepte care initial in acelasi tabel → transforma o dependenta intra-relatie intr-o dependenta inter-relatie.

Dezavantaj - migrare de atribute - atributele din grupul A (in cazul exemplului Marca#) se dubleaza.

5. A doua forma normala

O relatie - in a doua forma normala (2NF), 1NF & orice atribut care nu face parte din cheia primara, DFT de cheia primara → nici un atribut care nu face parte din cheia primara nu depinde functional de o parte a cheii primare

Relatia PERS1 este in 2NF - MARCA# - singur atribut - celelalte atribute DFT de cheia primara. Tabelul COPII nu este in 2NF, (Alocatia DF de Data-Nasterii parte a KP → nu exista DFT: KP (Nume si Prenume, Data Nasterii) si Alocatia.

→ o serie de anomalii:

anomalia de inserare - nu se poate introduce Alocatia, care depinde de Data-Nasterii pana cand nu se introduce si numele copilului, desi alocatia nu depinde de acest parametru;

anomalia de stergere - prin stergerea numelui unui copil (care face parte din cheia primara) - riscul pierderii legaturii dintre data nasterii si alocatie;

anomalii de punere la zi - pentru a pune la zi perechea (Data-Nasterii, Alocatie) - 2 strategii:

o       daca se pune la zi - prima aparitie - inconsistenta;

o       pentru a pune la zi toate aparitiile - analizat fiecare articol → o operatie foarte costisitoare.

→ aducere la 2NF, prin T descompunerii lui Delobel & Cassey → COPII se va descompune in COPIL1 si COPIL2:

COPIL1

  MARCA#

Nume si Prenume

Data-Nasterii

Locul-Nasterii

COPIL2

Se inlatura redundantele & anomaliile - DF: Data-Naterii→Alocatie nu mai este in COPIL1. Descompunere fara pierderi, adica prin recompunere celor doua tabele se regaseste tabela initiala:

COPII = COPIL1 [Data-Nasterii = Data-Nasterii] COPIL2

Schematic:

6. Forma a 3-a normala (3NF) si variantele (3 ½ NF)

3NF - mai multe definitii, dintre care 3 sunt mai importante:

O relatie in 3NF (Codd ,70 - 3NF) - 2NF & intre doua atribute care nu sunt cheie nu exista o dependenta tranzitiva.

Un atribut C depinde tranzitiv de atributul B daca au loc dependentele functionale intre B si C, A si B, respectiv intre A si C - schema dependentelor functionale are forma:

A B

C

Alta formulare: o relatie este in 3NF - 2NF si nu exista dependente functionale intre atributele care nu sunt cheie.

A doua definitie: Codd in 1971 si se numeste forma BCNF sau Boyce-Codd Normal Form: R este in BCNF daca pentru orice multime de atribute A pentru care exista un atribut din C(A), care depinde functional de A, are loc proprietatea ca orice atribut din R depinde functional de A [Miranda&Busta].[Gardarin] R - BCNF ↔singurele DF elementare sunt cele prin care o cheie detrmina 1 atribut.

A treia definitie a 3NF Sharman in 1975: O relatie este in 3NF daca orice determinant este o cheie (primara sau candidat).

Ideea de baza este deci aceea ca: fiecare relatie contine un singur concept semantic.

PERS1:

Este in 2NF, nu este in a 3NF, deoarece intre atributele care nu sunt cheie, Data-Angajarii si Ore-Lucrate, pe de o parte, si Salar-Brut, pe de alta parte, exista o relatie functionala. Izoland aceasta relatie, din PERS1 se obtin tabelele:

PERS11:

  MARCA

Nume si Prenume

Data-Angajarii

Ore-Lucrate

PERS12:   

Se elimina anomalii legate de prezenta

DF: (Data Angajarii, Ore Lucrate → Salar Brut)

& descompunerea este fara pierderi:

PERS1 = PERS11 [Data Angajarii, Ore Lucrate =

Data Angajarii, Ore Lucrate] PERS12

Trecerea de la 2NF la 3NF se realizeaza prin izolarea DF tranzitive si aplicand teorema de descompunere. Schematic are loc fenomenul:

Observatie. A doua si a treia definitie sunt echivalente si sunt mai restrictive decat 3NF.

BNCF - mai generala ca forma 3NF relatia PERS12. Aceasta este in 3NF. Ipoteza: realizarea salarului brut → angajatul lucreaza un numar de ore → apare o

DF: Salar Brut → Ore Lucrate

→ relatia nu este in BCNF - schematic relatiile se poate observa ca au loc dependentele conform figurii:

Aplicand teorema descompunerii si izoland (1) vor rezulta doua tabele:

PERS121:	PERS122:
Data - Angajarii Ore - Lucrate	Ore - Lucrate Salar - Brut

PERS121 este format numai din cheie (ALL KEY) deci nu are nici un atribut care sa nu fie cheie si ca descompunerea este fara pierderi, deci:

PERS12 = PERS121 [Ore lucrate = Ore lucrate] PERS122

Schematic operatia se poate reprezenta astfel:

Observatii.

BCNF fiind mai generala ca 3NF se considera ca este forma 3 ½.

Orice baza de date pentru a fi corect proiectata se aduce cel putin pana la a 3NF.