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:*
• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow X }
• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow YZ } és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle Z \rightarrow C } akkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow YZC}
• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow YZ } akkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \subseteq R } akkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow X } .
• Ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X,Y \subseteq R } és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow Y } , akkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle XW \rightarrow YW } igaz tetszőleges Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle W \subseteq R } -re
• Ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X,Y,Z \subseteq R } , Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow Y } és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle Y \rightarrow Z } , akkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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.)

• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle A \rightarrow B,C \rightarrow D \Rightarrow A \cup (C-B) \rightarrow BD, }
• Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle F \subseteq G^+ } és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G \subseteq F^+ } !

3. Hányadik legmagasabb normál formában van az R(A,B,C,D) relációs séma, ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \exists A,B } hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle A,B \in R } és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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), Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow Y } , ahol X, Y attribútumhalmazok, és létrehozunk két táblát, az egyikben az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X\cup Y } attribútumhalmaz lesz, a másikban Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (ABCDE) \Rightarrow (ABC),(ABDE) } , itt az első már BCNF, a másodikban megmaradó függőségek Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{D \rightarrow A;AE \rightarrow B;BE \rightarrow D\} } , itt Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D \rightarrow A } sérti a követelményt, ezért tovább bontunk: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow A_1A_2...A_n } függőségeket Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X \rightarrow A_1,\,X\rightarrow A_2,... } -ra, és vegyük ki a triviális függőségeket. Így ezt kapjuk: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{ OP \rightarrow N,\, PN \rightarrow L\} } -ből következik Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{LMO\} \cap X \rightarrow \{LMO\} \setminus X } és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{LMO\}\subseteq X } vagy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle X\subseteq \{LMO\} }
• A felbontásnál követelmény továbbá, hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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.