Sapientia - Erdélyi Magyar Tudományegyetem (EMTE) Csíkszereda
9. Előadás tartalma Függőségek vetítése. Normalizálás Normálformák. A relációs adatmodellt először E. F. Codd határozta (Codd 1970). Ő vezette be a normalizált reláció kifejezést. Amikor megalkotta a relációs modellt, 13 szabályt adott meg a relációk táblákkal való bemutatására. 1
Sapientia - Erdélyi Magyar Tudományegyetem (EMTE) Csíkszereda Egy relációban az attribútumok közötti függőségek generálhatnak olyan többletinformációt, amit redundanciának nevezünk. Ezek anomáliákhoz vezetnek. A beszúrási, törlési és módosítási anomáliákat ki tudjuk küszöbölni azzal, hogy a kiinduló relációt (táblát) több táblára bontjuk fel. Ezen táblák felbontását úgy végezzük el, hogy a táblák összekapcsolásából visszakaphassuk az eredeti relációt. Általában idegen kulcsok és gyenge egyedhalmazok (gyenge relációk) keletkezése történik, vagy éppen kapcsolat-relációk (ld. Egyed/Kapcsolat modell). 2
3
Sapientia - Erdélyi Magyar Tudományegyetem (EMTE) Csíkszereda
A normálforma: Tábla újrarendezése a benne levő funkcionális függőségek alapján Funkcionális függőség: A→B, ha ismerjük egy (vagy több) tulajdonság értékét, akkor ebből meg tudjuk határozni egy másik tulajdonság értékét Többértékű függőség: A→→B Ha ismerjük egy (vagy több) tulajdonság értékét, akkor mindig meg tudjuk határozni egy másik tulajdonság értékeinek HALMAZÁT. Pl: Ha tudom egy tanár nevét, akkor meg tudom határozni a tanítványainak a névsorát. 4
Funkcionális függőségek vetítése R reláció egy S funkcionális függőséghalmazzal, ahol elkészítjük R egy vetítését: R1=πL(R) R néhány attribútumára. Milyen függőségek állnak fel R1-ben? S funkcionális függőségeinek vetítése adja meg, amelyek: a) S-ből levezethetők b) csak R1 attribútumait tartalmazzák.
R1 funkcionális függőségeinek kiszámítási ideje legrosszabb esetben az R1-beli attribútumok számának exponenciális függvénye (Ullman)
5
BEMENET: R, R1 (az R vetítése), S függőséghalmaz R-ben KIMENET: Az R1-ben fennálló funkcionális függőségek (FF) halmaza 1. Legyen T a végül előálló FF-ek halmaza. Kezdetben üres. 2. Minden olyan X attribútumhalmazra, amely R1 része, számítsuk ki az X+-t. Adjuk hozzá T-hez az összes nem triviális függőséget, amelyek X→A formátumúak, ahol A eleme az X+ és az R1 attribútumhalmaznak is. 3. Ezután a kapott T bázisa az R1-beli funkcionális függőségeknek, de nem biztos a minimalitás. a) Ha szerepel F funkcionális függőség, amely más T-beli függőségekből következik, akkor töröljük a T halmazból b) Y→B egy T-beli funkcionális függőség, ahol Y legalább két attribútumot tartalmaz, és legyen Z az a halmaz, amelyet úgy kapunk, hogy Y-ból egy attribútumot elhagyunk. Ha Z→B függőség következik a T-beli funkcionális függőségekből (beleértve Y→B), akkor cseréljük ki Y→B-t 6 Z→B-re.
R(A,B,C,D) reláció és A→B, B→C és C→D FF-ek. Keressük R1(A,C,D) reláció FF halmazát Elvileg {A,C,D} mind a 8 részhalmazát kellene vizsgálni 1. Az üres, vagy a minden attribútumot tartalmazó halmaz lezárása nem vezet nem triviális függőséghez 2. Ha X halmaz lezárása tartalmazza az összes attribútumot, akkor nem tudunk újabb FF-hez jutni az X szuperhalmazai-nak lezárásával. {A}+={A,B,C,D}, azaz A→C és A→D fennáll R1-ben. {C}+={C,D}, amelyből következik a C→D {D}+={D} {A} szuperhalmazaival nem kell foglalkozni a 2 pont szerint Egyetlen 2 elemű halmaz {C,D}+={C,D}. A megtalált FF-ek: A→C, A→D és C→D. Tranzitivitás miatt kiküszöbölhetjük az A→D FF-et Maradtak: A→C és C→D FF-ek. 7
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.
A normalizálás az a folyamat, amellyel kialakítjuk a relációk normálformáját. A normálformák: 1NF, 2NF, 3NF, BCNF, 4NF, 5NF, egymásba skatulyázottak, logikusan egymásra épülnek.
8
Első normál forma (1NF) Értelmezés: Egy R reláció 1NF –ban van, ha az attribútumoknak csak elemi (nem összetett vagy ismétlődő) értékei vannak. Nincsenek ismétlődő csoportok és minden oszlop SKALÁRIS. Nincsenek TÖBÖK, Kapcsolt Listák, Beágyazott Táblák és rekordszerkezetek. Példa egy olyan relációra, mely nincs 1NF-ben:
Alkalmazottak: SzemSzám
Név
Cím Helység
Gyerek1 Utca
SzülDát1
… Gyerek5
SzülDát5
Szám 9
1NF-re alakítás 1. Összetett attribútum esetén: az összetett attribútum helyett beírjuk az azt alkotó elemi attribútumokat. 2. Ismétlődő attribútum esetén felbontjuk két relációra: az egyik relációban a kulcs attribútum mellett az ismétlődő attribútumok (csak egyszer) fognak szerepelni, a másikban pedig a kulcs mellett azon attribútumok melyek nem ismétlődőek Példa: Alkalmazott (SzemSzám, Név, Helység, Utca, Szám) AlkalmGyerekei (SzemSzám, GyerekNév, SzülDátum) Ebben az esetben látjuk, hogy az alkalmazott gyerekeinek nyilvántartása egy olyan relációba kerül, amelyik gyenge egyedhalmazként definiálható az Egyed/Kapcsolat modellben. 10
Sapientia - Erdélyi Magyar Tudományegyetem (EMTE) Csíkszereda Parciális függőség: Ha X és Y oszlopok és X kulcs, akkor bármely Z-re, amely részhalmaza X-nek igaz, hogy Z nem határozhatja meg funkcionálisan Y-t
A második normálforma (2NF) Egy második normálformában levő tábla úgy jellemezhető, hogy NEM tartalmaz parciális függőségeket.
A1
A2
A3
A4
A5
A6
Ha {A1,A2} KULCS, akkor ez a reláció NINCS 2NF-ben mert A2→A3 11
SzállID SzállNév SzállCím
ÁruID ÁruNév
MértEgys
Ár
111
Rolicom
A.Iancu 15
45
Milka csoki
tábla
25000
222
Sorex
22 dec. 6
45
Milka csoki
tábla
26500
111
Rolicom
A.Iancu 15
67
Heidi csoki
tábla
17000
111
Rolicom
A.Iancu 15
56
Milky way
rúd
20000
222
Sorex
22 dec. 6
67
Heidi csoki
tábla
18000
222
Sorex
22 dec. 6
56
Milky way
rúd
22500
A reláció kulcsa {szállID,ÁruID}
Nincs 2NF-ben, mert
Varga Ibolya példája
SzállID→{SzállNév, SzállCím}
ÁruID→{ÁruNév, MértEgys} {SzállID,ÁruID}→Ár
12
Sapientia - Erdélyi Magyar Tudományegyetem (EMTE) Csíkszereda
Definíció: Egy R reláció akkor és csakis akkor van 2NFben ha R 1NF-ben van és minden nem-kulcs attribútuma funkcionálisan függ a kulcstól és csakis a kulcstól. A
relációkat
2NF-ra
olyan
formán
hozzuk,
hogy
megkeressük az összes lehetséges kulcsot, majd annál amelyiket
kiválasztottuk
elsődleges
kulcsként
megvizsgáljuk az összes PARCIÁLIS függőséget, majd
ezeket külön relációkba tesszük. A kapott relációkban is megvizsgáljuk ugyanazt.
13
Az R(A) relációt felbontjuk két relációra, melyek sémái: T(D, B) és S(A-B) Első lépésben B = {SzállNév, SzállCím}, D = {SzállID}. Felbontás után kapjuk: Szállítók (SzállID, SzállNév, SzállCím) SzállInf (SzállID, ÁruID, ÁruNév, MértEgys, Ár) nincs 2NFben, mert ÁruID→{ÁruNév, MértEgys} parciális kulcsfüggőség
Továbbá S(X) felbomlik U(C,E) es V(X-E) E= {ÁruNév, MértEgys}, C= {ÁruID}, X-E={SzállID, ÁruID,Ár} Áruk (ÁruID, ÁruNév, MértEgys), Szállít (SzállID, ÁruID, Ár).
14
Szállítók:
Szállít:
SzállID SzállNév SzállCím 111 Rolicom A.Iancu 15 222
Sorex
22 dec. 6
Áruk: ÁruID ÁruNév 45 Milka csoki
MértEgys tábla
67 56
tábla rúd
Heidi csoki Milky way
SzállID
ÁruID Ár
111
45
25000
222 111 111
45 67 56
26500 17000 20000
222 222
67 56
18000 22500
15
Harmadik normálforma 3NF (a nem kulcs attribútumok közötti függőség) Definíció: Egy R reláció harmadik normál formában 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. Definíció: Egy tábla 3NF-ben van, ha minden X→Y, ra ahol X és Y a tábla oszlopai X kulcs, vagy Y része egy kulcsnak. Értelmezés: Minden olyan oszlop, amely nem kulcs, meghatározható a kulccsal, az egész kulccsal és csak a kulccsal. Magyarázat függőségek X→Y és Y→Z
a
3NF-hez:
Nincsenek
benne
TRANZITÍV
16
Cím
Év
Hossz
műfaj
stúdióNév
stúdióCím
Csillagok háborúja
1977
124
sci-fi
Fox
Hollywood
Kutyahideg
2005
120
dráma
Disney
Buena Vista
Wayne világa
1992
95
vígjáték
Paramount Hollywod
Cím év→stúdióNév stúdióNév→stúdióCím Tranzitivitás miatt következik Cím év→stúdióCím 17
stúdióNév
stúdióCím
Fox
Hollywood
Disney
Buena Vista
Paramount
Hollywood
Cím
Év
Hossz
műfaj
stúdióNév
Csillagok háborúja
1977
124
sci-fi
Fox
Kutyahideg
2005
120
dráma
Disney
Wayne világa
1992
95
vígjáték
Paramount
18
A tanárok, hallgatók, osztálytermeket leíró adatbázis a következő képpen nézhet ki: Kurzustartas(kurzusID, szakID, profID, terem, teremméret, időpont) Kurzusfelvétel(Törzsszám, kurzusID, évfolyam) Hallgató(törzsszám, név, főszak) Professzor(profID, név, tanszék, fokozat) Kurzus(kurzusID, megnevezés) {kurzusID,szakID}→terem terem→teremméret A Kurzustartas a következő relációkra bontható, hogy 3NF-ben legyen Terem(teremID, teremméret) Kurzustartas(kurzusID, szakID, profID, teremID, időpont)19
Boyce-Codd normálforma (BCNF) Egy tábla BCNF-ban van, ha minden nem triviális (X→A) funkcionális függőségre X szuperkulcs az egész sémára nézve. Minden nem triviális függőség bal oldalának szuperkulcsnak kell lennie. Ekvivalens def.: R reláció BCNF-ben van akkor és csak akkor, ha bármikor fenáll az R-ben az A1A2..An→B1B2...Bm nem triviális függőség, akkor az {A1,A2...An} halmaz R szuperkulcsa kell legyen 2 attribútumból álló reláció BCNF-ben van. Akkor bontsunk minden relációt 2 tagra ?????!!!!!! Ez sem működik, mivel nem biztos, hogy a relációk összekapcsolásából vissza tudjuk kapni az eredeti relációt. 20
Boyce-Codd normálformájú felbontás Bármely relációsémát fel tudunk bontani az attribútumaiból álló részhalmazok összességére, amelyre az alábbi fontos tulajdonságok teljesülnek: 1. Ezek a részhalmazok BCNF-ben levő relációsémák 2. A felbontott relációkból összekapcsolásokon keresztül vissza lehet állítani az eredeti relációt. Felbontási stratégia: Felveszünk egy A1A2..An→B1B2...Bm nem triviális funkcionális függőséget, amelyik megsérti a BCNF-t, azaz {A1,A2…An} nem szuperkulcs.
21
BCNF dekompozíció algoritmusa R relációra és S függőségi halmazra alkalmazható rekurzívan. Kezdetben R=R0 és S=S0. 1. Ellenőrizzük, R BCNF-ben van-e. Ha igen, kész. 2. Ha vannak BCNF – t megsértő függőségek, pl. X→Y. Kiszámítjuk X+-t. Legyen R1=X+ az egyik relációséma, R2-ben legyenek benne az X attribútumai és azok az R-beli attribútumok, amelyek nincsenek az X+-ban. 3. Használjuk az algoritmust az R1 és R2 függőségeinek meghatározásához, melyek S1 és S2. 4. Rekurzívan bontsuk fel R1-et és R2-t ennek az algoritmusnak a használatával. A végeredmény a dekompozíciók uniója lesz. 22
Nem teljesül a B→C funkcionális függőség R vetítései az {A, B} és {B, C} sémájú relációkra A 1
B 2
C 3
4
2
5
A 1 1 4 4
B 2 2 2 2
C 3 5 3 5
A 1
B 2
B 2
C 3
4
2
2
5
Kaptunk 2 hamis sort is, mivel a B mindkét sorban 2 volt. 23
Az előzőleg normalizált (3NF-re hozott) tabla NINCS BCNFben. Kurzustartas(kurzusID, szakID, profID, teremID, időpont) Mivel 1 tanár 1 időben NEM tarthat órát 2 teremben, érvényes a következő funkcionális függőség (teremID, időpont)→(kurzusID, szakID, profID) Mivel a bal oldal NEM szuperkulcs, ezért a következő lehetőségeink vannak: 1. UNIQUE-nek definiáljuk a (teremID, időpont) párost 2. A relációt felbontjuk a következő relációkra TeremBeosztás(teremID, időpont, kurzusID) Kurzustartás(kurzusID, szakID, profID ) 24
{filmcím, év, stúdióNév, elnök, elnökCím} Feltételezzük a következő funkcionális függőségeket: filmcím, év→stúdióNév(1) stúdióNév→elnök(2) elnök→elnökCím(3) jobb oldalon nincs filmcím és év (2) és (3) megsértik a BCNF-t. {filmcím,év}+=(1){filmcím,év,stúdióNév}+=(2){filmcím,év, stúdióNév,elnök}+=(3){filmcím,év,stúdióNév,elnök,elnökCím} stúdióNév→elnök (3) stúdióNév→elnök, elnökCím {filmcím, év, stúdióNév} {stúdióNév, elnök, elnökCím} Az első relációban filmcím, év→stúdióNév áll fenn, BCNF A második relációban stúdióNév a kulcs stúdióNév→elnök elnök→elnökCím – megszegi a BCNF feltételt {filmcím, év, stúdióNév} {stúdióNév, elnök} {elnök, elnökCím} 25
Sziklaszilárd Bank tárolja a nála vezetett számlák adatait, a számláknál a következő információkat vesszük figyelembe: • Ügyfél Adatok (személyi szám, név, cím, státus), Számlaszám, Egyenleg. • A számlák lehetnek betéti számlák és folyószámlák. • Az ügyfeleknek tetszőleges számlájuk lehet.
• A számlaszámok teljes mértékben azonosítanak egy számlát. • Egy számla több ügyfélhez is tartozhat
• Minden ügyfél rendelkezik egyedi személyi számmal • Az egyes számlákat a bank egy meghatározott fiókja vezeti • A fiókok adatai: FiókNév, Cím és Fiókvezető
• Két bankfióknak nem lehet ugyanaz a neve 26
1NF: BankFiók(Fióknév, cím, vez_szám, számlaszám, egyenleg, tipús) Ügyfél(személyiszám, név, cím, státus, számlaszám) 2 NF fióknév→fiókcím fióknév→vezérszám fióknév→fiókcím,vezérszám számlaszám→egyenleg számlaszám→tipús számlaszám→egyenleg, tipús számlaszám→Fióknév, fiókCím, vez_szám
BankFiók(Fióknév, cím, vez_szám, számlaszám, egyenleg, tipús) 2 NF-ben van, mert a többi attribútum mind függ a számlaszámtól személyiszám→név, cím, státus 27
Ügyfél(személyiszám, név, cím, státus, számlaszám) személyiszám→név, cím, státus Az ügyfél reláció felbontása, hogy megfeleljen a 2NF-nek Ügyfél1(személyiszám, név, cim, státus) Ügyfél2(személyiszám, számlaszám) 3 NF BankFiók(Fióknév, cím, vez_szám, számlaszám, egyenleg, tipús) Fióknév→(Cím, vez_szám) tranzitív függőség áll fenn (számlaszám)→Fióknév→(Cím, vez_szám) ezért felbontjuk BankFiók1(Fióknév, Cím, vez_szám) BankFiók2(számlaszám, egyenleg tipús, Fióknév) 28
Többértékű függőségek: Az attribútumfüggetlenségből származó redundancia
Név
Város
Utca
Cím
Év
C. Fisher
Hollywood
Maple St. 123
Csillagok háborúja
1977
C. Fisher
Malibu
Locust Ln. 5
Csillagok háborúja
1977
C. Fisher
Hollywood
Maple St. 123
A birodalom visszavág
1980
C. Fisher
Malibu
Locust Ln. 5
A birodalom visszavág
1980
C. Fisher
Hollywood
Maple St. 123
Jedi visszatér
1983
C. Fisher
Malibu
Locust Ln. 5
Jedi visszatér
1983
Többértékű függőség: A→→B Ha ismerjük egy (vagy több) tulajdonság értékét, akkor mindig meg tudom határozni egy másik tulajdonság értékeinek HALMAZÁT. 29
SzínészLakhely(név, város, utca, filmcím, gyártév) Reláció felbontása, hogy 4NF-ben legyen
Lakcímek{név, város, utca} Szereplő{név, cím, év}
Név C.Fisher C.Fisher
Város
utca
Hollywood Maple St. 123 Malibu
Locust Ln. 5
Név
Cím
C.Fisher Csillagok háborúja
Év 1977
C.Fisher A birodalom visszavág 1980
C.Fisher Jedi visszatér
1983
30
HSZÁM
HNÉV
TANFSZ ÁM
TANFNÉV
ELŐADÓ
1
J.Smith
1264
Francia 1.
J. LeClerc
4
S. Abdul
1564
Spanyol 3.
F.Rodriguez
7
K. Chan
1264
Francia 1.
J. LeClerc
11
J. Jones
1265
Francia 2.
13
M. Jones
1265
Francia 2.
16
K. Saunders 1264
Francia 1.
18
J. Ngugih
Francia 2.
1265
J. LeClerc
tanfszám→tanfnév, előadó hszám→hnév 31
Sapientia - Erdélyi Magyar Tudományegyetem (EMTE) Csíkszereda HSZÁM
HNÉV
TANFSZ ÁM
1
J.Smith
1264
4
S. Abdul
1564
7
K. Chan
1264
11
J. Jones
1265
13
M. Jones
1265
16
K. Saunders 1264
18
J. Ngugih
TANFS TANFNÉV ZÁM
ELŐADÓ
1264
Francia 1.
J. LeClerc
1265
Francia 2.
1266
Francia 3.
1562
Spanyol 1. K.Lopez
1563
Spanyol 2. K.Lopez
1564
Spanyol 3. K.Rodrigues
P.Simpson
1265
32
Sapientia - Erdélyi Magyar Tudományegyetem (EMTE) Csíkszereda
Összefoglaló kérdések 1. 1NF 2. 1NF-re alakítás 3. Parciális függőségek 4. 2 NF definició 5. 2NF-re való hozás 6. 3NF definíció
7. Boyce-Codd normálforma 8. Sziklaszilárd bank adatbázisának normalizálása 33
