Adatbázisok/Vizsga feladatok

Ezen az oldalon néhány feladatot találsz témakörönként az új (VITMAB04) Adatbázisokhoz, amik a régi tárgy 1996-2007 közötti ZH feladatsoraiból lettek kiválogatva. Ezek a feladatok az új tárgyban a ZH után kerülnek leadásra, így alapvetően a vizsgán találkozhatsz ezekhez hasonló feladatokat. Az eredeti feladatlapokat megtalálod a régi tárgy oldalán.

Normalizálás

(1996-04-16 4.) Bizonyítsa be, hogy ha az R relációs séma nem BCNF, akkor ∃ A, B (A, B ∈ R), hogy (R \ AB) → A!

Megoldás

Mit jelent az, hogy R nem BCNF? Azt, hogy van egy olyan nemtriviális X → A függőség, amire X nem szuperkulcs. A "nemtriviális" pontosan azt jelenti, hogy A nem részhalmaza X-nek. Ugyanakkor X nem is szuperkulcs, tehát van legalább egy olyan B, amit nem határoz meg. Ebből azt kaptuk, hogy X ⊆ R \ AB, hiszen sem A, sem B nem lehet X része.

Most vegyük sorra bele R \ AB-ből az összes olyan elemet X-be, ami még nincs benne, és nézzük meg mit kaptunk. Az így kapott függőség éppen az amit keresünk, hiszen a bal oldalt addig tuningoltuk, amíg nem lett R \ AB-vel egyenlő. A függőség pedig ugyanakkor igaz, hiszen X meghatározta A-t, és ezt nem tudjuk elrontani azzal, hogy új elemeket veszünk hozzá (axióma). Örülhetünk.

(2000-04-25 5.) 5. Vizsgálja meg, hogy hányadik legmagasabb normál formában van az R(ISTQ) relációs séma az F = {I → Q, ST → Q, IS → T, QS → I} függéshalmaz esetén!

(2001-11-16 4. módosítva) Mutassa meg, hogy egy 3NF sémára illeszkedő reláció lehet redundáns funkcionális függőség következtében!

(2001-11-16 6. módosítva) Adott az R(ABCDEF) relációs séma és az F = {A → B, AC → DB, C → AD, AF → ECB}, csak funkcionális függőségeket tartalmazó függéshalmaz. A mutatók valamennyi attribútumra mutathatnak. Adja meg a séma egy felbontását 2NF sémákba, törekedve minél kevesebb relációs séma definiálására!

(2002-11-15/A 6.) Bizonyítsa be, hogy az alábbi három szabályból következnek az Armstrong-axiómák! (Azaz pusztán ezen három szabályt használva a levezetés során, az Armstrong axiómák megkaphatók.) Ha X, Y, Z, C egy relációséma attribútumhalmazai, akkor:

B1. X → X mindig igaz.
B2. X → YZ és Z → C-ből következik X → YZC
B3. X → YZ-ből következik X → Y

Megoldás

A reflexivitás: X → Y(X \ Y) igaz B1 miatt, ha Y ⊆ X, innen pedig B3-mal jön, hogy ekkor X → Y is fennáll.
A kiegészítés: Legyen A → B igaz és legyen F egy tetszőleges attribútumhalmaz. B1 miatt AF → AF is igaz. Erre a függésre és az A → B-re alkalmazva B2-t (X = AF, Z = A, Y = F, illetve C = B szereposztással) kapjuk, hogy AF → AFB igaz. Innen B3-mal jön, hogy AF → BF.
A tranzitivitás: Tegyük fel, hogy A → B és B → D igazak. B2-t használva (X = A, Z = B, Y = ∅ és C = D szereposztással), kapjuk A → BD-t, ahonnan B3-mal jön A → D.

(2004-11-19 3.) Igazak-e az alábbi szabályok? Ha igen, miért?

a) X → Y, X → W, YW → Z ⊨ X → Z

b) XY → Z, Y → W ⊨ XW → Z

Megoldás

a) Igaz:

X → Y adott.
X → W adott.
X → YW egyesítési szabály alapján.
YW → Z adott.
X → Z tranzitivitás szabály alapján.

A kezdeti függésekből levezethető X → Z az axiómák ismételt alkalmazásával. És ami levezethető, az igaz is.

b) Nem igaz. Ellenpélda: Vegyünk egy R(X, Y, Z, W) sémát, és egy r(R) relációt, aminek két sora van:

(1, 1, 1, 1)
(1, 2, 2, 1)

XY → Z teljesül, mert nincsenek olyan sorok, ahol X és Y értéke egyezne, a funkcionális függés definíciója nincs megsértve. Y → W is teljesül hasonló okokból. XW → Z viszont nem teljesül, a két sorban X és W értéke egyező, de Z értékei különböznek. Mivel a funkcionális függésnek bármely r(R) reláción igaznak kell lennie, az ellenpélda bizonyítja, hogy nem lehet igaz az állítás.

(2005-04-19 3.) Igazak-e az alábbi szabályok? (A, B, C, D tetszőleges attribútumhalmazok egy R sémán.) Ha igen, miért?

a) A → B, C → D ⊨ (A ∪ (C \ B)) → BD

a) A → B, C → D ⊨ (C ∪ (D \ A)) → BD

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

(2005-04-19 6.a) Adott egy (R, F) séma, ahol R = ABCDE és F = {AB → C, D → A, AE → B, CD → E, BE → D}. BCNF-ben van-e ez a séma?

(2005-05-03 3.) Igaz-e, hogy a következő axiómarendszer teljes. azaz levezethető-e felhasználásukkal minden logikai következmény?

Ha X ⊆ R, akkor X → X.
Ha X, Y ⊆ R és X → Y, akkor XW → YW igaz tetszőleges W ⊆ R-re.
Ha X, Y, Z ⊆ R, X → Y és Y → Z, akkor X → Z.

Megoldás

Nem vezethető le pl. F = ∅-ból X → Y ahol Y ⊆ X. Ugyanis minden felírható lépésben a jobboldal legalább annyi attribútumot tartalmaz, mint a baloldal.

(2005-05-03 4.) Adj egy R(A, B, C) séraára illeszkedő r relációt, melynek 4 sora van és nem teljesül rá semmilyen nemtriviális funkcionális függés!

Megoldás

Legyen r(R) egy olyan reláció, aminek 4 sora van, de mindegyik különböző:

(a, a, a)
(a, a, b)
(a, b, b)
(b, b, b)

ahol a ≠ b. Ekkor AB → C nem áll fenn az 1. és 2. sor miatt, AC → B nem teljesül a 2. és 3. sor miatt, BC → A pedig a 3. és 4. sor miatt. Az X → Y típusú függőségek nem teljesülnek, pl. A → C-nek logikai következménye AB → C, ami viszont már úgysem teljesül.

(2005-05-03 6.) Adott egy (R, F) séma, ahol R ABCGWXYZ és F = {XZ → BGYZ, AY → CG, C → W, B → G}. Igaz-e, hogy (AXZ → BY) ∈ F⁺?

Megoldás

Az XZ → BGYZ-t bővítve A-val kapjuk AXZ → ABGYZ függőséget. Ebből a reflexivitás alapján AXZ → BY is igaz. Mivel a kezdeti függőséghalmazból le tudtuk vezetni a kívánt függőséget is az axiómák ismételt alkalmazásával, az állítás igaz. A függőséghalmaz lezártja pedig mindazon függőségeket tartalmazza, amik levezethetők, így tehát AXZ → BY-t is.

(2006-11-20 5.) Tekintsük az R(A, B, C, D, E, F, G, H) sémát az alábbi funkcionális függőségekkel: F = {A → BCD, AD → E, EFG → H, F → GH}.

a) Mi az egyetlen kulcs a sémában? Hány szuperkulcs van?

b) 3NF-ben van-e a séma?

Megoldás

a) Minden kulcsban benne kell lennie A-nak és F-nek, mert ezek nincsenek sehol sem jobb oldalon, azaz nem jönnek ki semmi másból. AF pedig már kulcs, mert az első függés miatt bejön BCD, a második miatt E, a negyedik miatt pedig GH.

Szuperkulcs az, ami tartalmaz kulcsot, vagyis most AF-et, mert ez az egyetlen kulcs. Annyi szuperkulcs van, ahány részhalmaza a BCDEGH halmaznak van (minden részhalmaz kibővítve AF-fel szuperkulcs lesz). Ebből pedig 26 van (hat elemű halmaznak ennyi részhalmaza van).

b) Minden felsorolt függés sérti a 3NF tulajdonságot, mert egyik baloldal se szuperkulcs és egyik jobboldal se szerepel kulcsban.

(2004-11-30 2.) Legyen r egy R sémára illeszkedő reláció, X pedig R attribútumainak egy részhalmaza. Bizonyítsd be, hogy ha π_X(r) és r sorainak száma megegyezik, akkor bármely Y ⊆ R-re fennáll az X → Y funkcionális függés!

(2004-11-30 6.) Adott a következő séma: R(Név, TBszám, Gyereknév, GyerekTBszám, AutóGySzám, AutóTípus). Jelentése: A gyerek az adott személy gyereke, de a relációban mindkét szülő benne lehet. Az autó az adott személy autója, de lehet egy autónak több tulajdonosa is. A többi összefüggést életszerűen kell értelmezni.

a) Milyen funkcionális függőségek állnak fenn ebben a sémában?

b) Melyik normálformában van a séma?

Tranzakciókezelés

(2004-06-02 6.) A következő tranzakció szigorú 2PL? Ha nem, módosítsa! Mit biztosít ez a protokoll?

Lock A
Read A
A := A * 2
Write A
Commit
Unlock A

(2006-11-20 6.) Tekintsük a t₁, t₂, t₃ tranzakciók írási és olvasási kéréseiből álló r₂(A), r₃(C), r₁(B), w₁(B), w₃(A), w₂(C) sorozaton. Időbélyeges tranzakciókezeléssel akarjuk a sorosítható ütemezést kikényszeríteni, a tranzakciók időbélyegei: TS(t₁) = 1, TS(t₂) = 2, TS(t₃) = 3.

a) Melyik tranzakciót (tranzakciókat) fogja ABORT-ra utasítani az ütemező a fenti sorozat esetén?

b) Változtassuk meg egyetlen kérésben az adatelemet úgy, hogy az így kapott kéréssorozat esetén ne kelljen ABORT-ot elrendelnie az ütemezőnek. Itt több megoldás is van, adjon meg legalább kettőt.

Megoldás

a) Nézzük meg, mi történik az egyes kéréseknél és mi lesz az adatok írási és olvasási ideje.

r₂(A): mehet, r(A) 2 lesz, minden más marad 0
r₃(C) : mehet, r(C) 3 lesz
r₁(B): mehet, r(B) 1 lesz
w₁(B): mehet, mert B-t csak T₁ olvasta eddig, w(B) 1 lesz
w₃(A): mehet, mert A-t csak T₂ olvasta eddig, w(A) 3 lesz
w₂(C): nem mehet, mert C-t T₃ már olvasta (amint ezt r(C) = 3 mu-tatja).

Vagyis csak T₂-t fogja ABORT-ra utasítani az ütemező.

b) Ha w₂(C) helyett w₂(B) lenne, akkor az utolsó előtti utasításig semmi se változik, vagyis addig nem lesz ABORT, de az utolsónál se lesz, mert ekkor r(B) = w(B) = 1, ami nem ütközik a w₂(B) kéréssel. Ha r₃(C) helyett r₃(A) lenne, akkor sem lesz ABORT, mert az A-t érintő kérések r₂(A), r₃(A), w₃(A) sorrendben jönnek, ami pont időbélyeg szerinti sorrend, a C adategységen meg nem is lesz egyáltalán ütközés.