A = {A1, A2

Normalizálás

Funkcionális függıségek

Adott: R (A₁, A₂,..., A_n) reláció ; A = {A₁, A₂,..., A_n}, X, Y ⊂ A

X funkcionálisan meghatározza Y-t, (Y funkcionálisan függ X-tıl):

− ha R bármely két sora megegyezik az X attribútumain, akkor meg kell egyezniük az Y attribútumain is.

Jelölés : X →Y

Relációs algebrai mőveletekkel:X →Y ,

ha ∀t,r∈ R sor esetén, melyre π_X (t) = π_X (r), akkor π_Y (t) = π_Y (r).

t

r

X Y

Ha t és r megegyezik ezen

Akkor itt is meg kell egyezniük

Száll ID

Száll Név

SzállCím Áru ID

ÁruNév Mért Egys

Ár

111 Rolicom A. Iancu 15 45 Milka csoki tábla 2.5 222 Sorex 22 dec. 6 45 Milka csoki tábla 2.6 111 Rolicom A. Iancu 15 67 Heidi csoki tábla 1.7 111 Rolicom A. Iancu 15 56 Milky way rúd 2.1 222 Sorex 22 dec. 6 67 Heidi csoki tábla 1.8 222 Sorex 22 dec. 6 56 Milky way rúd 2.3

Funkcionális függıségek:

SzállID ^→ SzállNév ÁruID ^→ ÁruNév SzállID ^→ SzállCím ÁruID ^→ MértEgys

ÁruID ^→ MértEgys (azzal a feltevéssel, ha más mértékegységben árulják az árut, más ID-t is kap).

egy sorban:

SzállID ^→ {SzállNév, SzállCím}

ÁruID ^→ {ÁruNév, MértEgys}

} , , ,

{C₁ C₂ … C_k halmaz a reláció kulcsa, ha:

– Ezek az attribútumok funkcionálisan meghatározzák a reláció minden más attribútumát, azaz nincs az R-ben két különbözı sor, amely mindegyik {C₁,C₂,…,C_k}-n megegyezne.

– Nincs olyan valódi részhalmaza {C₁,C₂,…,C_k}-nak, amely funkcionálisan meghatározná az R összes többi attribútumát, azaz a kulcsnak minimálisnak kell lennie.

Szuperkulcsoknak nevezzük azon attribútumhalmazokat, melyek tartalmaznak kulcsot.

– A szuperkulcsok eleget tesznek a kulcs definíció elsı feltételének, de nem feltétlenül tesznek eleget a minimalitásnak.

Tehát minden kulcs szuperkulcs.

• Az R (A₁, A₂,..., A_n) reláció esetén A_i attribútum prim, ha létezik egy C kulcsa az R-nek, úgy hogy A_i ∈C.

• Ha egy attribútum nem része egy kulcsnak, akkor nem prim attribútumnak nevezzük.

• Triviális funkcionális függıségrıl beszélünk, ha Y ⊂ X , akkor Y

X → .

példa: Triviális funkcionális függıség: {SzállID, ÁruID}^→SzállID

• Nem triviális egy X X_{1 2}…X _p →Y Y_{1 2}…Y_s funkcionális függıség, ha

, [1, ] Y jj s

∃ ∈ j ∈{1,2,..., s} úgy, hogy Y_j ≠ X_k,∀k ∈{1,2,..., p}.

• Teljesen nem triviális egy X X_{1 2}…X _p →Y Y_{1 2}…Y_s funkcionális függıség, ha

, [1, ] Y jj s

∀ ∈ j ∈{1,2,..., s} -re Y_j ≠ X_k,∀ k ∈{1,2,..., p}.

• Parciális függıség: Ha C egy kulcsa az R relációnak, Y ⊂ C, B∉Y, Y → B egy parciális függıség. (B függ a kulcs egy részétıl.)

példa: parciális függıségre: SzállID → SzállNév.

SzállításiInformációk kulcsa {SzállID, ÁruID}

{SzállID, ÁruID}→SzállNév,

Tranzitív függıség: Y ⊂ A, B∉Y . Y → B tranzitív függıség,

− ha Y nem szuperkulcs R relációban

− Y nem valódi részhalmaza R egy kulcsának.

Honnan a tranzitív elnevezés?

Y nem kulcs, nem része a kulcsnak, tehát

C →Y és Y → B, és erre mondhatjuk, hogy B tranzitív függıséggel függ C-tıl.

példa:

Rendelések (RendelésSzám, Dátum, VevıID, VevıNév, Részletek), RendelésSzám elsıdleges kulcs

RendelésSzám →VevıID.

VevıID→VevıNév

Problémák: (anomáliák)

– Redundancia: Az információk feleslegesen ismétlıdnek több sorban, mint például a SzállításiInformációk reláció esetében a szállító címe ismétlıdik.

– Módosítási problémák: Megváltoztatjuk az egyik sorban tárolt információt, miközben ugyanaz az információ változatlan marad egy másik sorban. Például, ha a szállító címe változik, de csak egy sorban változtatjuk meg, nem tudjuk, melyik a jó cím. Jó tervezéssel elkerülhetjük azt, hogy ilyen hibák felmerüljenek.

– Törlési problémák: Ha az értékek halmaza üres halmazzá válik, akkor ennek mellékhatásaként más információt is elveszthetünk. Ha például töröljük a Rolicom által szállított összes árut, az utolsó sor törlésével elveszítjük a cég címét is.

– Illesztési problémák: Ha hozzáilleszteni akarunk egy szállítót, amely nem szállít egy árut sem, a szállító címét kitöltjük úgy, hogy az áruhoz

„null” értékeket viszünk be, melyet majd utólag ki kell törölni, ha el nem felejtjük.

Relációk felbontása

Az anomáliák megszüntetésének elfogadott útja a relációk felbontása (dekompozíció-ja). Legyen R egy reláció, felbontása:

− R attribútumait szétosztjuk úgy, hogy ezáltal két új reláció sémáját alakítjuk ki belılük.

− R sorait is szétosztjuk a két új relációba

R reláció { ,A A_{1 2},…,A_n} sémával, R-et felbonthatjuk S és T relációkra, S sémája: { ,B B_{1 2},…,B_m}, T sémája {D₁, D₂, ..., D_k} úgy, hogy

1. { ,A A_{1 2},…,A_n}={ ,B B_{1 2},…,B_m}⋃{D₁, D₂, ..., D_k}, ahol { ,B B_{1 2},…,B_m}∩ {D₁, D₂, ..., D_k}≠∅.

2. S =

Bm

B B₁, ₂,…,

π _{(R); T =}

1, 2, , _k

D D D

π _{… (R);}

Veszteségmentes felbontás

R reláció felbontása S és T relációkra veszteségmentes, ha R = S ⋈ T

Fontos, hogy minden felbontás, amit normálformára hozás közben végzünk, veszteségmentes legyen, vagyis ne veszítsünk információt.

Normálformák

• Az adatmodellezés egyik fı célja az optimalizálás, vagyis az adatmodellt alkotó egyedtípusok lehetı legjobb szerkezetének a megkeresése.

• Az optimális adatmodell kialakítására egyéb technikák mellett a normalizálás szolgál. A normalizálás az a folyamat, amellyel kialakítjuk a relációk normálformáját (NF).

• A normálformák: 1NF, 2NF, 3NF, BCNF, 4NF, 5NF egymásba skatulyázottak. 2NF matematikailag jobb, mint 1NF, a 4NF jobb, mint a BCNF, az 5NF a legjobb, 3NF alakú reláció szükségszerően 1NF és 2NF alakú is.

Elsı normál forma (1NF)

Értelmezés: Egy R reláció 1NF –ben van, ha az attribútumoknak csak elemi (nem összetett vagy nem ismétlıdı) értékei vannak. Ez minimális feltétel, melynek egy reláció eleget kell tegyen, hogy a létezı relációs ABKR-ek kezelni tudják.

Példa: A következı reláció nincs 1NF-ben:

Alkalmazottak:

Cím Szem

Szám

Név

Helység Utca Szám

Gye- rek1

Szül Dát1

… Gye- rek5

Szül Dát5 Cím összetett attribútum: Helység, Utca és Szám-ból áll.

A Gyerek1, SzülDát1, Gyerek2, SzülDát2, Gyerek3, SzülDát3, Gyerek4, SzülDát4, Gyerek5, SzülDát5 ismétlıdı attribútum.

1NF-re alakítás

Ha egy reláció nincs 1NF-ben, mivel tartalmaz összetett attribútumokat, elsı normál formára hozhatjuk:

• az összetett attribútum helyett beírjuk az azt alkotó elemi attribútumokat.

Alkalmazott (SzemSzám, Név, Helység, Utca, Szám)

Ha A = {A₁, A₂,..., A_n}; R (A₁, A₂,..., A_n) reláció ismétlıdı attribútumokat tartalmaz, felbontással elsı normál formába hozható.

− C I, ⊂ A,

− C kulcs

− I ismétlıdı attribútumhalmaz, mely k-szor ismétlıdik.

− J ⊂ A, J ∩C = ∅ és J ∩ I = ∅.

− A =C ∪ I₁ ∪ I₂ ∪…I_k ∪ J .

A felbontás után kapjuk a következı két relációsémát:

( , )

S C I és T C J( , ).

példa: A példa esetén:

C = {SzemSzám}

I = {GyerekNév, SzülDátum}

J = {Név, Helység, Utca, Szám}.

AlkalmGyerekei (SzemSzám, GyerekNév, SzülDátum)

Második normál forma (2NF)

Értelmezés: Egy reláció 2NF formában van, ha

− elsı normál formájú (1NF) és

− nem tartalmaz Y → B alakú parciális függıséget, ahol B nem prim attribútum.

Csak akkor tevıdik fel, hogy egy reláció nincs 2NF-ben, ha a kulcs összetett.

példa: SzállításiInformációk relációja nincs 2NF-ben, mivel a reláció kulcsa a {SzállID, ÁruID} és fennáll a SzállID^→SzállNév, tehát SzállNév függ a kulcs egy részétıl is, tehát létezik parciális függıség.

Megoldás: több relációra kell bontani.

2NF-re alakítás

R reláció, attribútumainak a halmaza A = {A₁, A₂,..., A_n} C ⊂ A egy kulcs.

Ha a reláció nincs második normál formában, azt jelenti

− létezik egy B ⊂ A nem kulcs B∩C = ∅ attribútumhalmaz,

− létezik D ⊂ C, úgy hogy D → B

Az R relációt felbontjuk két relációra, melyek sémái:

T(D, B) és S A B( − )

példa: SzállításiInformációk relációjában fennállnak a:

SzállID →{SzállNév, SzállCím}

ÁruID → {ÁruNév, MértEgys}

funkcionális függıségek, a kulcs pedig a C ={SzállID, ÁruID}.

1. B = {SzállNév, SzállCím}, D = {SzállID}.

Szállítók (SzállID, SzállNév, SzállCím)

SzállInf (SzállID, ÁruID, ÁruNév, MértEgys, Ár) A Szállítók reláció 2NF-ben van, mivel a kulcs nem összetett.

2. A SzállInf nincs 2NF-ben, mert fennáll a ÁruID → {ÁruNév, MértEgys}.

B = {ÁruNév, MértEgys}, D = {ÁruID}.

Áruk (ÁruID, ÁruNév, MértEgys),

Szállít (SzállID, ÁruID, Ár).

− Az Áruk 2NF-ben van, mert a kulcs nem összetett és 1NF-ben van.

− A Szállít relációban egyetlen nem kulcs attribútum van: az Ár, és az nem függ csak az ÁruID-tıl, sem a SzállID-tıl

A kapott relációk:

Szállítók:

SzállID SzállNév SzállCím 111 Rolicom A. Iancu 15 222 Sorex 22 dec. 6

Áruk:

ÁruID ÁruNév MértEgys 45 Milka csoki tábla

67 Heidi csoki tábla

56 Milky way rúd

Szállít:

SzállID ÁruID Ár

111 45 2.5

222 45 2.6

111 67 1.7

111 56 2.1

222 67 1.8

222 56 2.2

Harmadik normál forma (3NF)

Értelmezés: Egy R reláció harmadik normál formában (3NF) van, ha

− második normál formában van és

− nem tartalmaz Y → B alakú tranzitív funkcionális függıséget, ahol B nem prim attribútum.

Értelmezés: Egy R reláció harmadik normál formában (3NF) van, ha létezik az R-ben egy Y → B alakú nem triviális funkcionális függıség, akkor

− Y az R reláció szuperkulcsa vagy

− a B prim attribútum (valamelyik kulcsnak része).

A két értelmezés ekvivalens.

− A második nem kéri a második normál formát, de mivel bármely létezı Y → B funkcionális függıség esetén a bal oldal szuperkulcs, nem lehet annak része.

− Tehát elég, ha az összes létezı funkcionális függıség esetén a bal oldal szuperkulcs, akkor a tranzitív függıség nem létezhet, mert a tranzitív függıség esetén a bal oldal nem kulcs és ez nem megengedett.

példa: Rendelések (RendelésSzám, Dátum, VevıID, VevıNév, Részletek), nincs 3NF-ben, mivel tartalmaz tranzitív funkcionális függıséget.

RendelésSzám →VevıID VevıID→VevıNév.

3NF-re alakítás

Legyen R egy reláció, mely 2NF-ben van, viszont nincs 3NF-ben, C ⊂ A elsıdleges kulcs.

Ha a reláció nincs harmadik normál formában, azt jelenti,

− létezik egy B ⊂ A nem kulcs B∩C = ∅ attribútumhalmaz,

− létezik D, úgy hogy C → D és D → B.

Mivel a reláció 2NF-ben van, B nem függ funkcionálisan C-nek egy részétıl, tehát D nem kulcs attribútum.

Az R relációt felbontjuk két relációra, melyek sémái:

T (D, B) és S A B( − ).

példa: Rendelések relációja esetén: B = {VevıNév}, D = {VevıID}, a felbontás után kapott relációk:

Vevık (VevıID, VevıNév)

RendelésInf (RendelésSzám, Dátum, VevıID)

Boyce−Codd normál forma

Értelmezés: Az R reláció Boyce−Codd normál formában (BCNF) van akkor és csak akkor,

− ha minden olyan esetben, ha az R-ben érvényes egy Y → B nem triviális függıség,

− akkor az Y attribútumhalmaz az R reláció szuperkulcsa kell hogy legyen.

A BCNF esetén elmarad a B-re vonatkozó megszorítás, hogy nem prim, tehát B lehet kulcs része.

példa: A következı reláció 3NF-ben van, viszont nincs BCNF-ban:

Postahivatal (Város, UtcaSzám, IrányítóSzám) Egy ország összes postahivatalát tároljuk a fenti relációban, egy városban több postahivatal is lehet. Funkcionális függıségek a relációban:

{Város, UtcaSzám} → IrányítóSzám IrányítóSzám →Város.

Két kulcsa van a Postahivatal relációnak a

{Város, UtcaSzám} és {IrányítóSzám, UtcaSzám}.

A reláció 2NF-ben van,

− fennáll az IrányítóSzám→Város parciális funkcionális függés,

− de IrányítóSzám része az {IrányítóSzám, UtcaSzám} kulcsnak,

− a 2NF esetén, csak azon parciális függıségek nem megengedettek, ahol a jobb oldal nem prim, viszont a Város prim attribútum, része egy kulcsnak.

A Postahivatal reláció 3NF-ben van, (elsı értelmezés)

− 2NF-ben van és nem tartalmaz nem prim attribútumot,

− ha tartalmaz is tranzitív függıséget, a jobb oldalon a nem prim attribútum feltétel nem állhat fenn.

A harmadik normál forma második értelmezése:

− IrányítóSzám→Város funkcionális függıség olyan, ahol a bal oldal nem szuperkulcs, viszont a jobb oldal prim attribútum és épp az amit a BCNF ki akar küszöbölni.

A Postahivatal reláció nincs BCNF-ban, felbontjuk két relációra:

P1 (IrányítóSzám, Város)

P2 (IrányítóSzám, UtcaSzám).

Ha a postahivatalokról szóló információkat a P1 és P2 relációkban tároljuk, nem fogjuk ugyanannak a kis városnak a nevét ismételni minden postahivatala esetében, illetve a nagyvárosok ugyanabban a körzetben levı két postahivatala soraiban nem ismételjük a város nevét.