G˘ asirea cheilor candidat utilizˆ and dependent¸ele funct¸ionale

Baze de date relat¸ionale Normalizarea bazelor de date

Nicolae-Cosmin Vˆarlan

November 11, 2019

2/ 41

Modelul relat¸ional - chei (recapitulare de la primul curs)

I Supercheie- un atribut sau o mult¸ime de atribute care identific˘a unic un tuplu ˆıntr-o relat¸ie

I Cheie candidat - o supercheie cu proprietatea c˘a nici o submult¸ime proprie a sa nu este supercheie

I Cheie primar˘a- o cheie candidat selectat˘a pentru a identifica ˆın mod unic tuplele ˆıntr-o relat¸ie

I Cheie alternativ˘a - Chei candidat care nu au fost selectate pentru a juca rolul de cheie primar˘a

I Cheie str˘ain˘a- un atribut sau o submult¸ime de atribute dintr-o relat¸ie care face referint¸˘a la o cheie candidat a altei relat¸ii

G˘ asirea cheilor candidat utilizˆ and dependent¸ele funct¸ionale

Intuitiv: Cheia candidat, este de fapt format˘a dintr-o combinat¸ie de atribute care pot determina unic linia. Dac˘a pot determina unic linia (deci oricare dintre valorile celorlalte atribute), atunci putem considera c˘a avem o dependent¸a funct¸ionala de laX⊆U c˘atre toate atributele dinU atunciX este cheie ˆın orice relat¸ier construit˘a peste R[U].

Formal: FieR[U]o schem˘a de relat¸ie ¸si Σo mult¸ime de dependent¸e funct¸ionale satisf˘acute deR[U]. X⊆U este cheie candidat d.dac˘aX⁺=U ¸si∀X⁰ ⊆X, X⁰⁺6=U

Un atribut se nume¸steprim dac˘a face parte dintr-o cheie candidat.

Un atribut esteneprim dac˘a nu este parte din nicio cheie candidat.

4/ 41

. . . reminder (din cursul 2)

FieX⊆U siR_Aregulile de inferent¸˘a ale lui Armstrong. Not˘am cu X_R⁺

A ={A|Σ`_RA X→A}

Regulile de inferent¸˘a ale lui Armstrong:

A1: _A

1...An→Ai, i= 1, n A2: ^A1,...A_A ^m→B1,...Br

1...Am→Bj , j = 1, r

A1,...Am→B_j, j=1,r A1...Am→B₁,...Br

A3: ^A1,...Am→B_A^{1,...Br, B1,...Br→C1,...Cp}

1...Am→C₁,...Cp

Revenim - Exemplul 1:

S˘a consider˘am U ={A, B, C}¸siΣ ={A→B, B →C}. Vom construi mult¸imeaX_R⁺

A pentru fiecare dintre atribute:

A⁺_R

A ={A, B, C} (Adin A₁,B dinA→B,

C dinA→B,B →C ¸si folosind A3) B_R⁺

A ={B, C} (B din A1,C din B→C) C_R⁺

A ={C} (C dinA1)

Se observ˘a c˘a A este cheie candidat pentru c˘a de el depind (funct¸ional) celelalte atribute.

Atribute prime: {A}

Atribute neprime: {B, C}

6/ 41

S˘a consider˘am U ={A, B, C}si Σ ={A→B, B →C}. Vom construi mult¸imeaX_R⁺

A pentru fiecare dintre atribute:

Putem organiza atributele t¸inˆand cont de locul unde apar ele ˆın cadrul dependent¸elor dinΣ:

I Stˆanga: Apar numai ˆın partea stang˘a a dependent¸elor dinΣ.

I Mijloc: Apar ¸si ˆın stˆanga ¸si ˆın dreapta dependent¸elor din Σ.

I Dreapta: Apar numai ˆın partea dreapt˘a ˆın dependet¸ele dinΣ.

Stˆanga Mijloc Dreapta

A B C

Regul˘a: ˆıntotdeauna atributele din Stˆanga sunt atribute prime, cele din Dreapta sunt neprime. Cele din Mijloc pot fi ˆın oricare dintre categorii.

Exemplul 2:

FieU ={A, B, C, D, E, F}¸si

Σ ={A→BD, B→C, DE →F}. Care sunt cheile candidat ?

8/ 41

Exemplul 2:

FieU ={A, B, C, D, E, F}¸si

Σ ={A→BD, B→C, DE →F}. Care sunt cheile candidat ? Stˆanga Mijloc Dreapta

A, E B, D C, F A⁺_R

A ={A, B, C, D}- nu e cheie (nu cont¸ine F), dar cu sigurant¸˘a apare ˆın orice cheie.

De fapt, am stabilit c˘a fiecare cheie candidat va cont¸ine toate atributele din “Stˆanga” - ˆın cazul nostru pe A¸si pe E:

AE_R⁺

A ={A, B, C, D, E, F}

AE =cheie multivaluat˘a(este compus˘a din mai multe atribute).

Exemplul 3:

FieU ={A, B}¸siΣ ={A→B, B→A}. Care sunt cheile candidat ?

10/ 41

Exemplul 3:

FieU ={A, B}¸siΣ ={A→B, B→A}. Care sunt cheile candidat ?

Stˆanga Mijloc Dreapta A, B

A⁺_R

A ={A, B}

B_R⁺

A ={A, B}

Ambele sunt chei candidat.

Atribute prime: {A, B}

Atribute neprime: ∅

Dependent¸e pline

FieR[U]o schema de relat¸ie peste o mult¸ime de atributeU ¸siΣo mult¸ime de dependent¸e funct¸ionale ce au loc ˆınR[U]. O

dependent¸aX →A∈Σ⁺ se nume¸steplin˘adac˘a @X⁰⊂X astfel ˆıncˆatX⁰ →A∈Σ⁺.

Exemplu:

R[A, B, C, D]

Σ ={AB→C, B→D, BC →A}

Toate dependent¸ele dinΣsunt pline (e.g. nu avem ˆınΣ⁺ nici una dintre dependent¸ele: A→C,B →C,B →A,C →A).

AB→D nu este plin˘a pentru c˘aB ⊂AB ¸si avemB →D∈Σ⁺

12/ 41

Atribut tranzitiv dependent

FieR[U]o schem˘a de relat¸ie peste o mult¸ime de atribute U ¸siΣo mult¸ime de dependent¸e funct¸ionale ce au loc ˆınR[U]. Un atribut A∈U se nume¸ste tranzitiv dependent de X (X⊂U, A6∈X) dac˘a∃Y ⊂U astfel ˆıncˆat:

I A∈U−Y I X →Y ∈Σ⁺ I Y →A∈Σ⁺ I Y →X6∈Σ⁺ Exemplu:

R[A, B, C, D, E]

Σ ={AB→C, AB →D, CD→E}

E este tranzitiv dependent de AB (X =AB, Y =CD).

Dependent¸e triviale

O dependent¸˘a funct¸ional˘a X→Y este trivial˘a dac˘a ¸si numai dac˘a Y ⊆X

O dependent¸˘a multivaluat˘aXY este trivial˘a dac˘a Y ⊆X sau dac˘aZ =∅(X∪Y =U)

14/ 41

Normalizarea schemelor bazelor de date

Normalizarea este necesar˘a din dou˘a motive:

I Pentru eliminarea redundant¸elor.

I Pentru a p˘astra datele ˆıntr-o manier˘a consistent˘a.

Normalizarea trebuie f˘acut˘a ˆınc˘a din faza de proiectare a bazei de date ¸si din acest motiv este firesc s˘a vorbim despre

NORMALIZAREA SCHEMEIbazei de date ¸si nu despre normalizarea anumitor relat¸ii.

Exist˘a mai multe forme normale (clasice), fiecare aducˆand ceva ˆın plus fat¸˘a de forma precedent˘a: 1NF, 2NF, 3NF, BCNF, 4NF.

S˘a vedem ˆın ce constau. . .

1NF (1971)

FieU o mult¸ime de atribute ¸siR[U]o schema de relat¸ie.

Spunem c˘a schema de relat¸ieR[U]este ˆın Forma Normala 1 (1NF) dac˘a ¸si numai dac˘a domeniile atributelor sunt indivizibile ¸si fiecare valoare a fiec˘arui atribut este atomic˘a.

Pentru a avea o relat¸ie ˆın 1NF, trebuie efectuate urm˘atoarele operat¸ii:

I Eliminarea grupurilor repetitive din fiecare relat¸ie.

I Identificarea tuplelor ce ar putea avea duplicate ˆın coloan˘a printr-o cheie.

I Crearea unei noi scheme de relat¸ie avˆand ca atribute:

identificatorul de la punctul precedent ¸si valoarea repetat˘a ca atribut atomic.

16/ 41

1NF

Exemplu:

Avem schema: Studenti[nr matricol, nume, prenume, an] ˆın care student¸ii ar putea avea cˆate dou˘a prenume:

r :

nr matricol nume prenume an

1 Ionescu Maria Ioana 1

2 Popescu Vasile 1

3 Vasilescu Vali Cristi 2 Pasul 1: Elimin˘am grupul repetitiv:

r:

nr matricol nume an

1 Ionescu 1

2 Popescu 1

3 Vasilescu 2

1NF

Pasul 2: Identificam cheia:

r:

nr matricol nume an

1 Ionescu 1

2 Popescu 1

3 Vasilescu 2

Pasul 3: Creare relat¸ie ˆın care fiecare valoare apare pe un rˆand nou

¸si e legat˘a de relat¸ia principal˘a prin intermediul cheii:

r⁰:

nr matricol prenume

1 Maria

1 Ioana

2 Vasile

3 Vali

3 Cristi

18/ 41

1NF

De¸si ar putea p˘area c˘a am utilizat efectiv relat¸ia care este construita pesteR[U], ˆın fapt nu am facut decˆat s˘a modific˘am schema de realat¸ieR[U]¸si s˘a construim o nou˘a schem˘a de relat¸ie ˆın schema bazei noastre de date denumita R⁰[U].

Pasul 1: de fapt a eliminat atributul “prenume” din mult¸imeaU. Pasul 2: de fapt a identificat o cheie candidat (ce se poate face direct din schem˘a - vezi cum am gasit o cheie candidat din dependent¸ele funct¸ionale).

Pasul 3: de fapt a construit o nou˘a schem˘a de relat¸ie R⁰[U] S-ar putea ca ˆın unele locuri s˘a ˆıntˆalnit¸i ideea c˘a relat¸ia este ˆıntr-o anumit˘a form˘a normal˘a. Aceasta idee este incorect˘a datorit˘a faptului c˘a normalizarea se realizeaz˘a ˆınainte de a crea baza de date, ˆın stadiul de proiectare a acesteia !

2NF (1971)

O schema de relat¸ieR[U]care este ˆın 1NF, ˆımpreun˘a cu o mult¸ime de dependent¸e funct¸ionaleΣeste ˆın a doua form˘a normal˘a (2NF) dac˘a orice atribut neprim dinR[U]este dependent plin de orice cheie a luiR[U].

S˘a relu˘am exemplul de la dependent¸e pline:

R[A, B, C, D]

Σ ={AB→C, B→D, BC →A}

1. Gasit¸i cheile

2. Gasit¸i atributele neprime

3. Atributele neprime sunt dependente plin de cheile g˘asite ?

20/ 41

2NF

Sa reluam exemplul de la dependent¸e pline:

R[A, B, C, D]

Σ ={AB→C, B→D, BC →A}

Posibilele chei: AB,BC Atribute prime: A, B, C Atribute neprime: D

B→D∈Σ⁺. D nu este dependent plin de AB pentru c˘a, de¸si avemAB→D∈Σ⁺, avem ¸si B →D∈Σ⁺ rezult˘a c˘a R[U] ˆımpreun˘a cu Σnu este ˆın 2NF.

Observat¸ie: dac˘a nu avem chei multivaluate, cu sigurant¸˘aR[U] este ˆın 2NF (pentru c˘a avem numai dependent¸e pline de la chei - nu putem g˘asi submult¸imi de atribute atunci cˆand cheia este format˘a dintr-un singur atribut).

2NF

Avˆand o schem˘a de relat¸ie R[U]care nu este ˆın 2NF, putem s˘a o ducem ˆın 2NF urmˆand urm˘atorii pa¸si:

Pasul 1: Identific˘am cheile candidat.

Pasul 2: G˘asim atributele neprime.

Pasul 3: Pentru fiecare din atributele neprimeA identific˘am care sunt atributele dintr-o cheie de care depindeA.

Pasul 4: Cre˘am o nou˘a relat¸ieR⁰ peste acele atribute identificate la pasul anterior ˆımpreun˘a cu atributul neprim pentru care s-a g˘asit dependent¸a.

Urmat¸i cei patru pa¸si pentru exemplul anterior care nu era ˆın 2NF.

22/ 41

2NF

Exemplu: Dac˘a avem schema de relat¸ie OS[nume, versiune, an, companie]

nume versiune an companie

Windows XP 2001 Microsoft

MacOS Sierra 2017 Apple

Ubuntu Bionic Beaver 2018 Ubuntu

Windows 7 2009 Microsoft

MacOS Mojave 2018 Apple

De obicei, cand ne exprim˘am, spunem c˘a Windows XP este facut de Microsoft. Avem dependent¸a: nume,versiune → companie. ˆIn acela¸si timp, ¸stim c˘a Windows este f˘acut numai de Microsoft ¸si MacOS numai de Apple. Deci avem ¸sinume → companie. Fiecare versiune este f˘acut˘a ˆıntr-un anumit an. Avem: versiune→ an.

2NF

dependent¸e:

I nume,versiune → companie I nume → companie

I versiune→ an

Cheie: (nume, versiune) (apar ˆın stˆanga dependent¸elor) Atribute neprime: companie

companienu este dependent plin pentru c˘a, de¸si avem

nume,versiune→ companie, totodat˘a avem ¸sinume→ companie.

Vom elimina din schema OS atributul companie ¸si vom ad˘auga o schem˘a de relat¸ieR⁰[nume, companie].

Vom avea a¸sadar. . .

24/ 41

2NF

nume versiune an

Windows XP 2001

MacOS Sierra 2017

Ubuntu Bionic Beaver 2018

Windows 7 2009

MacOS Mojave 2018

¸si

nume companie Windows Microsoft

MacOS Apple

Ubuntu Ubuntu

Este ˆın 2NF ? Mai avem de verificat dac˘a an este dependent plin sau nu. . . s˘a vedem cum facet¸i asta voi :D

3NF (1971)

Schema de relat¸ie R[U] ˆımpreun˘a cu mult¸imea de dependent¸e funct¸ionaleΣeste ˆın forma a treia normal˘a (3NF) dac˘a este ˆın 2NF ¸si orice atribut neprim din RNU este tranzitiv dependent de nici o cheie a lui R.

(Adic˘a e ˆın 2NF ¸si orice atribut neprim depinde de chei ¸si nu de un alt atribut neprim sau grupare de atribute neprime)

Exemplu:

Consider˘am schema de relat¸ieR[A, B, C]¸si Σ ={AB→C, C →A}

Chei: AB, BC

Atribute neprime: ∅ - deci este ˆın 2NF ¸si ˆın 3NF.

26/ 41

3NF - glumit¸a de pe wikipedia. . . .

An approximation of Codd’s definition of 3NF, paralleling the traditional pledge to give true evidence in a court of law, was given by Bill Kent: [Every] non-key [attribute] must provide a fact about the key, the whole key, and nothing but the key. ¹

A common variation supplements this definition with the oath: so help me Codd².

1Kent, William - A Simple Guide to Five Normal Forms in Relational Database Theory, Communications of the ACM 26 (2), Feb. 1983, pp. 120− 125.

2Diehr, George. Database Management (Scott, Foresman, 1989), p. 331.

3NF

Exemplu de normalizare 3NF

Fie schema: Concursuri[materie, an, castigator, IQ], prin IQ referindu-ne la IQ-ul cˆastig˘atorului.

Se observ˘a c˘a avem dependent¸ele funct¸ionale:

Σ ={(materie, an)→castigator, castigator→IQ}

Cheie primara: (materie, an) Atribute neprime: IQ Se observ˘a c˘a (materie, an)→IQ∈Σ⁺, ¸si ˆın acela¸si timp materie→IQ6∈Σ⁺ respectivan→IQ6∈Σ⁺. Deci schema de relat¸ie se afl˘a ˆın 2NF (atributele neprime fiind dependente plin de chei).

Vom normaliza schema pentru

Concursuri[materie, an, castigator, IQ]prin construirea a dou˘a scheme diferite: Concursuri[materie, an, castigator]¸si

28/ 41

BCNF (Boyce-Codd Normal Form) ≡ 3.5NF (1975)

O schem˘a de relat¸ieR[U]ˆımpreuna cu o mult¸ime de dependent¸eΣ este ˆın BCNF dac˘a este ˆın 1NF ¸si pentru orice dependent¸a

funct¸ional˘a netrivial˘aX→A∈Σ⁺,X estesupercheie ˆınR[U].

Observat¸ie: O schem˘a de relat¸ie ce este ˆın BCNF este ˆın 3NF.

Obs: O schem˘ a ce este ˆın BCNF este ¸si ˆın 3NF.

Consideram(R,Σ)ˆın BCNF - ˆın 1NF este sigur din definit¸ie.

a)PP (RA) c˘a nu e ˆın 2NF, adic˘a exist˘a un atribut neprimA ¸si o cheieK ¸siA nu este dep. plin de K. Adic˘a exist˘aX⊂K a.i.

X→A∈Σ⁺. Deoarece nu consider˘am dep. triviale avem c˘a A6∈K. Atunci X este cheie (pentru c˘a (R,Σ) este ˆın BCNF).

Ceea ce ˆınseamn˘a c˘aK nu este cheie (pentru c˘a trebuia s˘a fie minimal˘a).

b) Deci(R,Σ)ce este ˆın BCNF trebuie s˘a fie ˆın 2NF.PP (RA) c˘a nu ar fi ˆın 3NF: adic˘a exist˘a un atributA tranzitiv dependent de o cheieX. Adica exist˘aY a.ˆı. A6∈X,A6∈Y ¸si avem c˘a:

X→Y ∈Σ⁺,Y →A∈Σ⁺¸siY →X6∈Σ⁺. Y nu cont¸ine nicio cheie pentru c˘a altfel am avea Y → ∀ ∈Σ⁺ deci ¸siY →X∈Σ⁺. Deoarece Y nu este cheie ¸si totusi amY →A∈Σ⁺ avem c˘a

30/ 41

Descompunerea de tip join f˘ ar˘ a pierdere

Consider˘am o schem˘a de relat¸ie R[A₁, A₂, . . . A_n]. Spunem despre o mult¸imeρ={R₁[A_i¹

1, A_i¹

2, . . . A_i¹

k1

], R2[A_i²

1, A_i²

2, . . . A_i²

k2

]. . . R_t[A_it

1, A_it

2, . . . A_it

kt]} c˘a este odescompunere de tip join a lui R[A1, A2, . . . An]dac˘a:

t

[

p=1 kp

[

r=1

A_i^p_r ={A₁. . . A_n}

ρeste o descompunere de tip join f˘ar˘a pierdere cu privire la o multime de dependente functionaleΣdac˘a∀r peste R ce satisface mult¸imea de dependent¸e funct¸ionaleΣ, avem c˘a

r=r[A_i¹

1, A_i¹

2, ..A_i¹

k1

]./ r[A_i²

1, A_i²

2, ..A_i²

k2

]./.. r[A_i^t

1, A_i^t

2, ..A_i^t

kt].

Descompunerea de tip join f˘ ar˘ a pierdere

Teorem˘a: Dac˘aρ={R₁, R₂} este o descompunere a luiR¸siΣ o mult¸ime de dependent¸e funct¸ionale, atunciρ este o decompunere de tip join f˘ar˘a pierdere cu privire la Σdac˘a ¸si numai dac˘a R₁∩R₂→R₁−R₂ ∈Σ⁺ sauR₁∩R₂ →R₂−R₁∈Σ⁺ (operat¸iile sunt de fapt pe atributele peste care sunt construite schemele)

Exemplu: Consider˘am R[A, B, C]¸siΣ ={A→B}.

ρ₁ ={R₁[A, B], R₂[A, C]}este f˘ar˘a pierdere deoarece:

AB∩AC =A, AB−AC =B ¸siA→B ∈Σ⁺ ρ₂ ={R₁[A, B], R₂[B, C]}este cu pierdere deoarece:

AB∩BC =B, AB−BC =A¸siB →A 6∈Σ⁺ AB∩BC =B, BC−AB=C ¸siB →C 6∈Σ⁺

Testati cele doua desc. pentrur={(1,1,2),(1,1,3),(2,1,2)}.

32/ 41

Descompunerea de tip join f˘ ar˘ a pierdere

Putem calculaΣ_i pentruR_i[U_i]¸si continua procesul de

descompunere pˆan˘a cˆand ajungem la scheme de relat¸ie ce sunt ˆın BCNF.Σi={X→Y|X, Y ∈Ui} - adic˘a, pentru Ri[Ui]ce este un element al descompuneriiρ lu˘am acele dependent¸e din Σcare sunt peste atributele ce sunt ˆınU_i.

Pentru exemplul precedent:

Consider˘amR[A, B, C]¸siΣ ={A→B}.

ρ₁ ={R₁[A, B], R₂[A, C]}este f˘ar˘a pierdere deoarece:

AB∩AC =A, AB−AC =B siA→B ∈Σ⁺ avem c˘aΣ1 ={A→B}¸siΣ2 =∅

Alg. pt. descompunerea ˆın join f˘ ar˘ a pierdere de tip BCNF

Intrare: (R,Σ)

Ie¸sire: ρ={(R₁,Σ1), . . .(Rt,Σt)}= descompunere f˘ar˘a pierdere a lui R cu privire laΣ. Unde (Ri,Σi)ˆın BCNF, ∀i∈ {1..t}

Pas 1: ρ=R=R₁; se caculeaz˘a Σ⁺ ¸si cheile dinR (necesare verificarii formei BCNF).

Pas 2: Cˆat timp exist˘a ˆın ρun cuplu (Ri,Σi) ce nu e ˆın BCNF (daca nu e in BCNF atunci existaX→A si X nu esupercheie):

Pas 2.1: AlegeX→A dinΣ_i a.i. A6∈X ¸si X nu cont¸ine cheie Pas 2.2: S1 =X∪ {A}; S2=Ri−A;

Pas 2.3: ρ=ρ−R_i; ρ=ρ∪S₁∪S₂; Pas 2.4: Se caculeaz˘aΣ⁺_S

1,Σ⁺_S

2 ¸si cheile pentruS₁ ¸siS₂.

34/ 41

Exemplu

Schema de relat¸ie:

Absolvent(CNP, aNume, adresa,lCod, lNume, lOras, medie, prioritate)

Σ={CNP → aNume,adresa,medie medie→ prioritate lCod→ lNume, lOras}

Se descompune ˆın:

. . . calculati

Exemplu

Schema de relat¸ie:

Absolvent(CNP, aNume, adresa,lCod, lNume, lOras, medie, prioritate)

Σ={CNP → aNume,adresa,medie medie→ prioritate lCod→ lNume, lOras}

Se descompune ˆın:

ρ={R1[lCod, lNume, lOras], R2[medie, prioritate], R3[CNP, aNume, adresa, medie], R4[CNP, lCol]}

36/ 41

Dependente multivaluate (quick reminder)

Definition

Relat¸iar pesteU satisface dependent¸a multivaluat˘aXY dac˘a pentru oricare dou˘a tuple t₁, t₂∈r satisf˘acˆandt₁[X] =t₂[X], exist˘a tuplele t3 ¸sit4 din r, astfel ˆıncˆat:

I t₃[X] =t₁[X], t₃[Y] =t₁[Y], t₃[Z] =t₂[Z];

I t4[X] =t2[X], t4[Y] =t2[Y], t4[Z] =t1[Z]

undeZ=U−XY (Z mai este denumit˘a ¸sirest).

Relat¸iar pesteU satisface dependent¸a multivaluat˘aXY, dac˘a pentru oricet₁, t₂ ∈r cu t₁[X] =t₂[X]avem c˘a

MY(t1[XZ]) =MY(t2[XZ])

undeMY(t[XZ]) ={t⁰[Y]|t⁰ ∈r, t⁰[XZ] =t[XZ]} .

Dependente multivaluate (exercitiu)

Aratati caACBD:

r:

A B C D E

8 1 2 0 4

8 9 2 2 9

9 3 2 4 9

8 1 2 0 9

8 9 2 2 4

9 3 2 4 4

Candr[AC] ={(8,2)}avemr[BD] ={(1,0),(9,2)}si

r[E] ={(4),(9)}. Gasim toate produsele carteziene dintre cele 3 ? Candr[AC] ={(9,2)}avemr[BD] ={(3,4)} si

r[E] ={(4),(9)}. Gasim toate produsele carteziene ? DA (este MVD)

38/ 41

4NF (Ronald Fagin) (1977)

O schem˘a de relat¸ie Rˆımpreuna cu o mult¸ime de dependent¸e multivaluate∆(delta) este ˆın 4NF dac˘a este ˆın 1NF ¸si pentru orice dependent¸a multivaluat˘a netrivial˘aX A∈∆⁺,X este supercheie pentru R.

Observat¸ie: O schem˘a de relat¸ie ce este ˆın 4NF este ˆın BCNF.

Putem presupune ca nu este in BCNF ceea ce inseamna ca exista d.f. a.i. X →A∈Σ⁺ si X nu este cheie. Atunci exista aceeasi dependenta si multivaluata (X A∈∆⁺ ) si X nu este cheie:

deci nu este 4NF

Descompunere in 4NF

Intrare: (R,Σ,∆)

Ie¸sire: ρ={R₁, . . . , Rt} = descompunere f˘ar˘a pierdere a lui R cu privire laΣ. Unde (Ri,Σi,∆i)ˆın 4NF,∀i∈ {1..t}

Pas 1: ρ=R=R₁; se caculeaz˘a Σ⁺.∆⁺ ¸si cheile dinR (necesare verificarii formei 4NF).

Pas 2: Cˆat timp exist˘a ˆın ρun triplet (Ri,Σi,∆i) ce nu e ˆın 4NF (daca nu e in 4NF atunci existaXA si X nu esupercheie):

Pas 2.1: AlegeXA dinΣ_i a.i. A6∈X ¸si X nu e supercheie Pas 2.2: S1 =X∪ {A}; S2=Ri−A;

Pas 2.3: ρ=ρ−R_i; ρ=ρ∪S₁∪S₂; Pas 2.4: Cacul˘amΣ⁺_S

1,∆⁺_S

1,Σ⁺_S

2,∆⁺_S

2 ¸si cheile pentru S₁ ¸siS₂.

40/ 41

Exemplu de descompunere in 4NF

Consideram schema: Student[cnp, nume, facultate, pasiune]

Studentul poate fi la doua facultati si sa aiba mai multe pasinui:

cnp→ nume;

cnp,nume facultate;

Se descompune in:

ρ= {S1[cnp, nume], S2[cnp, facultate], S3[cnp, pasiune]}.

Bibliografie

I Further Normalization of the Data Base Relational Model. - Frank Edgar Codd; IBM Research Report RJ909 (August, 1971)

I Baze de date relat¸ionale. Dependent¸e - Victor Felea; Univ. Al.

I. Cuza, 1996