Adatbázisok - Normalizálás gyakorlat

Az aktuális tematika és feladatsor elérhető a tárgyhonlapon.

Definíciók

• Wikipédia: 1NF
• Wikipédia: 2NF
• Wikipédia: Kulcs
• Wikipédia: Szuperkulcs
• Wikipédia: Funkcionális függőség
• Wikipédia: Armstrong axiómák

Keretmese

Egy szerszámkölcsönző adatbázisában a következő adatokat tároljuk: milyen termékkódú, felhasználási célú és méretű eszközből mekkora fajlagos kölcsönzési díjért milyen igazolványszámú ügyfélnél hány darab van kölcsönben, összesen mekkora készletből, amelynek mekkora része található még szabad, kikölcsönözhető állapotban a kölcsönző melyik polcán. Tudjuk továbbá, hogy a termékkód egy eszköztípust (adott gyártó adott terméke) egyedileg azonosít; az azonos felhasználási célú (kalapács, hegesztő, stb.) és méretű (12 hüvelykes, 400 Wattos, stb.) eszközöket típustól függetlenül azonos díjért adják bérbe, és mindig egyazon polcon tárolják; egy polcon pedig csak egyféle célú eszközök sorakoznak.

Kezdeti, univerzális séma

R(Igazolványszám, Termékkód, Kölcsönzött, Összes, Szabad darabszám, Cél, Méret, Polc, Díj)
R(ITKOSCMPD), F = { IT → K, T → OSCM, CM → PD, P → C }

Feladatok

1. Van-e a tárolásban a jelen állapotban redundancia?

• Van, többféle is. Például ha egy adott termékkódú szerszámból három embernél is van kölcsönben, akkor a szerszám adatait mind a három sorban tároljuk (sérti a 2NF-t). Azt, hogy egy adott típusú és méretű szerszámfajtát melyik polcon tároljuk, azt is több sorban tároljuk (sérti a 3NF-t), stb.

2. A redundanciacsökkentés érdekében ellenőrizzük, hogy milyen legmagasabb normálformában van a séma!

• Atomi értékeket tárolunk, ezért biztosan legalább 1NF. A 2NF teljesüléséhez szükséges, hogy másodlagos attribútum (ami nem része egy kulcsnak sem) ne függjön részkulcstól, hanem mindig az egésztől. Ehhez először keressük meg a kulcsokat. Nyilván minden olyan attribútum a kulcs része kell legyen, ami nem szerepel függőség jobb oldalán (mivel kulcs csak szuperkulcs lehet, az pedig olyan attribútumhalmaz, amiknek az értékéből minden másnak az értékét is ki lehet találni; ha pedig nincs olyan függőség, ami által másra lehetne visszavezetni, akkor csak saját magából lehet kitalálni). Így I, T biztosan a kulcs része, és más nem is kell bele, mert csak ebből közvetve vagy közvetlenül minden más kikövetkeztethető (bizonyítás: {I, T} attribútumhalmaz lezártját kiszámítjuk). Innen látszik, hogy nem 2NF, mert a kulcs részétől, T-től függnek pl. O, S, C, M másodlagos attribútumok.

3. Sémafelbontással emeljük legalább 2NF szintre az adatbázissémát! Válasszuk a lehető legegyszerűbb, legkevesebb vizsgálatot igénylő módszert! Mi lesz a baj?

4. Találjunk veszteségmentes sémafelbontást minél kevesebb számú, legalább 2NF részsémába! R1=(ITK)->BCNF R2=(ITOSCMPD)->2NF

5. A megalkotott adatbázisséma 3NF-ben van-e? Ha nem, mutassunk példát redundanciára, és a redundancia további csökkentése érdekében találjunk veszteségmentes sémafelbontást minél kevesebb számú, legalább 3NF részsémába! Redundancia: CMPD

R2_1=(TOSCM)->BCNF R2_2=(CMPD)->3NF

6. A megalkotott adatbázisséma BCNF-ben van-e? Ha nem, mutassunk példát redundanciára, és a redundancia további csökkentése érdekében találjunk veszteségmentes sémafelbontást minél kevesebb számú, legalább BCNF részsémába!

R2_2_1=(CP)->BCNF R2_2_2=(MPD)->BCNF

7. Lehet-e funkcionális függés alapú redundancia az így létrejött felbontás alapján elkészített adatbázisban? Függőségőrző-e a sémafelbontás? Ha nem, ennek milyen hátrányos következményei vannak?

8. At eredeti relációs sémát a tanult módszerrel bontsuk fel veszteségmentes és függőségőrző módon legalább 3NF részsémákba! Törekedjünk arra, hogy minél kevesebb számú részséma keletkezzen!

Gondolkodtató kérdések

1. Ugyanezt a szerszámkölcsönző példát alapul véve, van-e olyan (nyilván nem funkcionális függőség alapú) redundancia az adatbázisban, amit egyik felbontás se küszöbölt ki (tehát még a BCNF sem)? Hogyan küszöbölhető ki? Megéri?

2. Adott egy séma. Milyen függőségtípusokra lehet a pillanatnyi állapotból következtetni, és milyen feltételekkel? A Relációs sémák függőségtípusai a Normálformákkal állnak kapcsolatban.

1. Funkcionális függőség: A->B ,ekkor A egyértelműen meghatározza a B-t 2. Tranzitív függőség: F={A->B B->C} ekkor A-ból 'tranzitíven' meg tudjuk határozni C-t.

3. Hányféle "kulcs" fogalom került eddig elő a tantárgyban? Mik a különbségek?

• kulcs*: X kulcs az R reláción, ha X->R és X-nek nincs X' részhalmaza, hogy X'->R.

(tehát X halmazban szereplő összes attribútum szükséges, hogy meghatározzuk a Relációt)

• szuperkulcs*: X kulcs az R reláción, ha X->R

(mint az előző, csak lehetnek benne + attribútumok.. )

• egyszerű kulcs*: olyan kulcs, ami egyetlen attribútumból áll
  
• összetett kulcs*: minimum két attribútumból áll
  
• elsődleges kulcs*: egy R relációnál létezhet két egymástól különböző kulcs X és Z,ahol X!=Z és X és Z is meghatározza egyértelműen R-t.

ekkor ezek közül egyet kiválasztunk, ez lesz az elsődleges kulcs, a többi pedig a kulcsjelölt.

• idegen kulcs*: R1 és R2 relációs sémák. R1!=R2. Van egy D attribútumunk, ami eleme R1 és R2nek. Ha pl. D->R1 és minimális, akkor D R2-ben idegen kulcs. (olyan attribútuma egy sémának, ami egy tőle különböző sémában kulcs)

4. Hányféle "lezárt" fogalommal találkoztunk? Különböznek-e egymástól? Mi a kapcsolat köztük? Hogyan számíthatóak?

• Attribútumhalmaz lezárása*: azt szeretnénk megtudni, hogy a funkcionális függőségek rendszerén keresztül esetleg más attribútumok is meghatározhatóak-e.
  X attribútumhalmaz lezárása F függéshalmaz mellett az a legbővebb halmaz, amelyre az X->A függőség adott függéshalmaz mellett fennáll. jelölése: X+(F)

pl: R(A,B,C,D) F={A->B, B->D} attributumhalmazunk: X=AC X+?
kiindulunk Xből, és F függőségek alapján megnézzük miket tudunk kifejezni:
X(0)=AC
X(1)=AC{B} (A->B)
X(2)=ACB{D} (B->D)

ABCD teljes halmaza R-nek, ezért AC szuperkulcs is.

• Függéshalmaz lezárása*: Azon függőségek halmaza, amelyek az F függéshalmaz elemeiből az Armstrong axiómák alapján következnek.
  

Armstrong axiómák:

• X ∈ Y, akkor Y->X
• X->Y és Y->Z akkor X->Z
• X-> akkor XZ->YZ

5. Egy sémájával adott relációs adatbázis hogy lesz ténylegesen eltárolva? Találjunk kapcsolatot a fizikai szervezés témakörében megismert fogalmakkal!

6. Az adatbázis sémájának felbontása hogyan érinti az adatmanipulációt? Találjunk kapcsolatot a lekérdezések témakörében megismert fogalmakkal! Írjunk fel néhány több táblát érintő lekérdezést relációs algebra vagy sor/oszlopkalkulus segítségével!

7. Hogyan kell EK modellekből relációs adatbázissémát készíteni?

8. Egy EK modellből milyen funkcionális függőségek olvashatók le? Ha ezeken kívül más függőség nem adott, akkor mit mondhatunk az ilyen módon származtatott adatbázisséma normálformájáról?

9. Találjunk ki olyan (értelmes) adatbázissémát, amelyik nem 1NF!

10. Adatbázisunk összes relációjának sémája mindössze két számértékű és egy karakterlánc attribútumból áll. Biztosan állíthatjuk-e, hogy az adatbázis legalább 1NF?

• Nem feltétlenül; ugyanis akkor 1NF, ha minden attribútum "atomi". A stringeket általában egyben kezeljük, de nem kizárt, hogy valamelyik táblában a "karakterlánc" voltaképp nem egy logikai egység, hanem több független dolgoból (pl. szavakból) áll össze (és különállóként is kezeljük). Az egy mezőben lévő "különállóként kezelés" az, ami a megkülönböztetés alapja. Pl. ha a tábla egy könyv adott oldalán, adott sorban található szavak listáját tárolja szóközökkel elválasztva, akkor az nem 1NF, ha viszont egy nevet (ami állhat több tagból is) tárol, és azt (az adatbázissal foglalkozás közben) mindig egyben kezeli, akkor igen.

11. A BCNF-fel ellentétben a csupán 3NF séma okozhat funkcionális függőség alapú redundanciát. Tudunk-e érveket felhozni amellett, hogy ezen redundancia jelentősége és hatása várhatóan kisebb a csak alacsonyabb normálformák esetében felbukkanó redundanciánál?

12. Milyen hatással lehet az adatbázisséma különböző tanult tulajdonságaira, ha egy meglévő sémafelbontást egy újabb részsémával bővítünk? Továbbá, milyen a hatása annak, ha egyik részsémáját sémafelbontással tovább bontjuk?

13. Adott ugyanannak a sémának két különböző felbontása. A két új adatbázisséma normálformában megegyezik. Milyen szempontok alapján érdemes közülük választani?

14. A relációs sématervezés témakörben kimondott matematikai tételek közül melyiknek van a legtöbb közvetlen gyakorlati jelentősége?

Gyakorló feladatok

Funkcionális függések

1. Bizonyítsa be, hogy az alábbi három szabálybül következnek az Armstrong axiómák. (Azaz csak ezen három szabályt használva axiómaként levezethetők az Armstrong axiómák mint "tételek")

• Ha X,Y,Z,C egy relációséma attribútúmhalmazai, akkor:*
• $X\rightarrow X$
• $X\rightarrow YZ$ és $Z\rightarrow C$ akkor $X\rightarrow YZC$
• $X\rightarrow YZ$ akkor $X\rightarrow Y$.

2. Mutassa meg, hogy igaz a tranzitivitási axióma!

3. Bizonyítsa be a bővítési axiómát!

4. Igaz-e, hogy a következő axiómarendszer teljes, azaz levezethető-e felhasználásukkal minden logikai következmény?

• Ha $X\subseteq R$ akkor $X\rightarrow X$.
• Ha $X,Y\subseteq R$ és $X\rightarrow Y$, akkor $XW\rightarrow YW$ igaz tetszőleges $W\subseteq R$-re
• Ha $X,Y,Z\subseteq R$, $X\rightarrow Y$ és $Y\rightarrow Z$, akkor $X\rightarrow Z$.

5. Adjon egy R(A,B,C) sémára illeszkedő r relációt, melynek 4 sora van és nem teljesül rá semmilyen nemtrivilális funkcionális függés!

6. Adott egy (R,F) séma, ahol R=ABCGWXYZ és $F=\{XZ\rightarrow BGYZ;AY\rightarrow CG;C\rightarrow W;B\rightarrow G\}$.

• Adja meg F-nek egy minimális fedését! Igaz-e, hogy $AXZ\rightarrow BY\in F^{+}$?*

7. Igazak-e az alábbi szabályok? (A,B,C,D tetszőleges attribútumhalmazok egy R sémán.)

• $A\rightarrow B,C\rightarrow D\Rightarrow A\cup (C-B)\rightarrow BD,$
• $A\rightarrow B,C\rightarrow D\Rightarrow C\cup (D-A)\rightarrow BD.$

8. Adott egy R(A,B,C) sémára illeszkedő r reláció, melynek 3 sora van. Bizonyítsa be, hogy meg lehet adni olyan nemtriviális funkcionális függést, amit r kielégít!

Normál formák

1. Mutassa meg, hogy egy 2NF sémára illeszkedő reláció is lehet redundáns. Magyarázza el, hogyan lehet megszüntetni. Adjon példát legalább 3 elemű 2NF sémára illeszkedő relációra, mely nem redundáns.

2. Bizonyítsa be, hogy F és G függéshalmaz pontosan akkor ekvivalens, ha $F\subseteq G^{+}$ és $G\subseteq F^{+}$!

3. Hányadik legmagasabb normál formában van az R(A,B,C,D) relációs séma, ha $F=\{C\rightarrow B;B\rightarrow D;AB\rightarrow AC;CD\rightarrow B\}$?

4. Vizsgálja meg, hogy hányadik legmagasabb normál formában van az R(I,S,T,Q) relációs séma az $F=\{I\rightarrow Q,ST\rightarrow Q;IS\rightarrow T;QS\rightarrow I\}$ függéshalmaz esetén!

5. Bizonyítsa be, hogy ha az R relációs séma nem BCNF, akkor $\exists A,B$ hogy $A,B\in R$ és $R-AB\rightarrow A$!

6. Állapítsa meg, hogy tartalmazhat-e erdundanciát (funkcionális függések következtében) az (R,F) sémára illeszkedő reláci, és ha igen, akkor milyen jelegűt? R(X,Y,Z,W), $F=\{XY\rightarrow Z,YZ\rightarrow W,X\rightarrow W,WY\rightarrow X\}$.

Relációs sémafelbontás

1. Adott egy (R,F) séma, ahol R=(A,B,C,D,E) és $F=\{AB\rightarrow C;D\rightarrow A;AE\rightarrow B;CD\rightarrow E;BE\rightarrow D\}$.

• BCNF-ben van-e ez a séma?
• Ha igen bizonyítsa be, ha nem, akkor adja meg a séma egy veszteségmentes felbontását BCNF sémákra!
  • Könnyen belátható, hogy AB nem szuperkulcs (pl. az ismert algoritmussal kiszámítjuk a lezártját; szuperkulcsnál az összes attribútumot kellene kapnunk), mégis szerepel egy (nemtriviális) függőség bal oldalán, tehát nincs BCNF-ben a séma.
  • A felbontás algoritmusa, ha a BCNF és a veszteségmentesség van megkövetelve, de a függőségőrzés nincs: vesszük R-nek egy BCNF-et sértő függőségét, legyen ez $X\rightarrow Y$, ahol X, Y attribútumhalmazok, és létrehozunk két táblát, az egyikben az $X\cup Y$ attribútumhalmaz lesz, a másikban $R\setminus Y$. Könnyen belátható, hogy veszteségmentes a felbontás. Majd ezt addig ismételgetjük, amíg még valamelyik tábla nem BCNF. Mivel minden felbontott táblának kevesebb attribútuma lesz, mint az eredetinek, és egy kétattribútumú tábla már biztosan BCNF, ezért valamikor biztosan véget ér az algoritmus.
  • A lépések: $(ABCDE)\Rightarrow (ABC),(ABDE)$, itt az első már BCNF, a másodikban megmaradó függőségek $\{D\rightarrow A;AE\rightarrow B;BE\rightarrow D\}$, itt $D\rightarrow A$ sérti a követelményt, ezért tovább bontunk: $(ABDE)\Rightarrow (AD),(BDE)$ és ezek már BCNF-ben vannak. Így a teljes felbontás: (ABC), (AD), (BDE).

2. Adott az R(L,M,N,O,P) relációs séma és a séma attribútumain értelmezett $F=\{MOP\rightarrow L,LN\rightarrow ON,NO\rightarrow M,OP\rightarrow N,PN\rightarrow LP\}$ funkcionális függéshalmaz. Az R sémaegy veszteségmentes felbontását szeretnénk elkészíteni tetszőleges formában, de nemtriviális módon úgy, hogy az egyik részséma R(L,M,O) legyen.

• Először határozzunk meg egy minimális függéshalmazt. Ehhez szedjük szét az $X\rightarrow A_{1}A_{2}...A_{n}$ függőségeket $X\rightarrow A_{1},\,X\rightarrow A_{2},...$-ra, és vegyük ki a triviális függőségeket. Így ezt kapjuk: $F=\{MOP\rightarrow L,LN\rightarrow O,NO\rightarrow M,OP\rightarrow N,PN\rightarrow L\}$ Innen megnézzük, elhagyható-e valamelyik összefüggés, úgy, hogy az új függéshalmaz lezártja ugyanaz legyen (azaz, levezethető-e valamelyik függőség a többiből). Könnyen látható, hogy $\{OP\rightarrow N,\,PN\rightarrow L\}$-ből következik $MOP\rightarrow L$, tehát ez utóbbi elhagyható. Végül, végignézzük, elhagyható-e a függőségek bal oldaláról attribútum, ilyen itt nem lesz. Tehát a minimális függéshalmaz: $F=\{LN\rightarrow O,NO\rightarrow M,OP\rightarrow N,PN\rightarrow L\}$
• Egy séma két alsémára történő felbontása akkor veszteségmentes, ha a két séma attribútumhalmazának metszetéből az egyik különbéghalmaz kikövetkeztethető. Vagyis itt, ha az első lépésben LMO-ra és egy X halmazra bontunk, akkor $\{LMO\}\cap X\rightarrow \{LMO\}\setminus X$ és $\{LMO\}\cap X\rightarrow X\setminus \{LMO\}$ közül legalább az egyiknek teljesülnie kell.
• Könnyen ellenőrizhető, hogy LMO bármelyik részhalmazának lezártja csak önmagát tartalmazza. Mivel a kívánt függőség jobb oldalán biztosan nem szerepel a baloldalon szereplő egyik attribútum sem, más pedig nem szerepelhet, ezért valamelyiknek a jobb oldalán üres halmaznak kell lennie, ez akkor lehet, ha $\{LMO\}\subseteq X$ vagy $X\subseteq \{LMO\}$
• A felbontásnál követelmény továbbá, hogy $\{LMO\}\cup X=\{LMNOP\}$ teljesüljön (mindegyik attribútum kerüljön bele valamelyik táblába), ez csak akkor lehet, ha X minden attribútumot tartalmaz. Tehát gyakorlatilag a felbontás első lépésében létrehozunk egy fölösleges, de megkövetelt LMO táblát, és mellé meghagyjuk az eredetit LMNOP-t is. Innen a megkövetelt normálforma szerint folytatható.

3. Adott az R(A,B,C,D,E,F) relációs séma és az $F=\{A\rightarrow B,AC\rightarrow DB,C\rightarrow AD,AF\rightarrow ECB\}$, csak funkcionális függőségeket tartalmazó függéshalmaz. Adja meg a séma egy veszteségmentes, függőségörző felbontását 2NF sémákba, törekedve minél kevesebb relációs séma definiálására!

4. Adott az R(G,H,J,K,L) séma. Adjon egy veszteségmentes, függőségőrző felbontást 3NF részsémákra, ha az ismert funkcionális függések halmaza $F=\{HJ\rightarrow J,GH\rightarrow IJ,HI\rightarrow JG,G\rightarrow J\}$!

5. Vizsgálja meg, hogy lehet-e az S(L,M) relációs séma résza az R(L,M,N,O) relációs séma valamely veszteségmentes felbontásának az $F=\{MN\rightarrow O;NO\rightarrow L;N\rightarrow M;M\rightarrow N\}$ függéshalmaz esetén!

6. Adott a következő relációs séma: R(A,B,C,D,E), $F=\{AB\rightarrow C,A\rightarrow E,B\rightarrow D\}$. Adja meg R egy veszteségmentes felbontását BCNF részsémákra!

7. Vizsgálja meg, hogy az R(A,B,C,D,E,F,G) relációs séma $\sigma =(ACEFG,BCDE)$ felbontása az $F=\{AB\rightarrow C,AC\rightarrow D,C\rightarrow F,D\rightarrow B,E\rightarrow G\}$ függéshalmaz mellett veszteségmentes-e!

8. Tekintsük a következő (R,F) ésémát, ahol R=(A,B,C,D,E) és $F=\{B\rightarrow E;E\rightarrow A;A\rightarrow D;D\rightarrow E\}$.

• Igaz-e, hogy a $\rho =(AB,BCD,ADE)$ felbontás veszteségmentes?

9. Bizonyítsa be, hogy egy reláció tetszőleges vertikális felbontása után a részrelációknak a természetes illsztésével sorok nem tűnhetnek el, csak újak jelenhetnek meg.

10. Van egy relációnk, és annak egy nem függőségörző felbontása. Ha a felbontásban az egyik relációhoz hozzáadunk egy új elemet, melyen nem érvényesül(nek) az "elveszett" függőség(ek), akkor a relációba egy helytelen elem kerülhet. Ezután ha vesszük a felbontásban szereplő relációk természetes illesztését, akkor az eredeti relációnál bővebb relációt kapunk, tehát a nem függőségörző felbontás nem veszteségmentes. Hol a hiba a gondolatmenetben?

11. Vizsgálja meg, hogy igaz-e a következő állítás: minden r(R,F)-re Értelmezés sikertelen (ismeretlen „\Join” függvény): {\displaystyle \pi _{R_1} (r) \Join \pi _{R_2} (r) \Join \pi _{R_3} (r) = r } , ahol R(A,B,C,D,E,H,G) relációs séma, $F=\{AB\rightarrow C,AC\rightarrow D,C\rightarrow H,D\rightarrow B,E\rightarrow G\}$ függéshalmaz és $\sigma =\{R_{1}(ACE),R_{2}(EHG),R_{3}(BCDE)\}$ egy sémafelbontás.

-- G - 2008.11.06.