„Adatbázisok/Vizsga feladatok” változatai közötti eltérés

A VIK Wikiből
Ugrás a navigációhoz Ugrás a kereséshez
 
1. sor: 1. sor:
 
<!--
 
<!--
−
{{Rejtett|mutatott='''Megoldás'''|szöveg=
+
 
−
TODO.
+
 
−
}}
+
 
 +
 
 +
A listát ne bővítsd új évek feladatsoraival. Lásd az Adatbázisok lapra írtakat. Ha hibát vagy hiányosságot találsz, azt javíthatod.
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 
-->Ezen az oldalon néhány feladatot találsz témakörönként az új (VITMAB04) [[Adatbázisok|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 [[Adatbázisok_(régi)#Zh|régi tárgy]] oldalán.
 
-->Ezen az oldalon néhány feladatot találsz témakörönként az új (VITMAB04) [[Adatbázisok|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 [[Adatbázisok_(régi)#Zh|régi tárgy]] oldalán.
  
 
== Normalizálás==  
 
== 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!
+
(1996-04-16 4.) Bizonyítsa be, hogy ha az R relációs séma nem BCNF, akkor <code>∃ A, B (A, B ∈ R)</code>, hogy <code>(R \ AB) → A</code>!
 +
 
 +
{{Rejtett|mutatott='''Megoldás'''|szöveg=
 +
Mit jelent az, hogy R nem BCNF? Azt, hogy van egy olyan nemtriviális <code>X → A</code> 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 <code>X ⊆ R \ AB</code>, hiszen sem A, sem B nem lehet X része.
 +
 
 +
Most vegyük sorra bele <code>R \ AB</code>-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 <code>R \ AB</code>-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.
 +
}}
  
  
12. sor: 28. sor:
  
  
−
(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!
+
(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 <code>F = {I → Q, ST → Q, IS → T, QS → I}</code> függéshalmaz esetén!
  
  
24. sor: 40. sor:
  
  
−
(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!
+
(2001-11-16 6. módosítva) Adott az R(ABCDEF) relációs séma és az <code>F = {A → B, AC → DB, C → AD, AF → ECB}</code>, 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!
  
  
31. sor: 47. sor:
  
 
(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:
 
(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.
+
* B1. <code>X → X</code> mindig igaz.
−
* B2. X → YZ és Z → C-ből következik X → YZC
+
* B2. <code>X → YZ</code> és <code>Z → C</code>-ből következik <code>X → YZC</code>
−
* B3. X → YZ-ből következik X → Y
+
* B3. <code>X → YZ</code>-ből következik <code>X → Y</code>
  
 
{{Rejtett|mutatott='''Megoldás'''|szöveg=
 
{{Rejtett|mutatott='''Megoldás'''|szöveg=
−
* 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 reflexivitás: <code>X → Y(X \ Y)</code> igaz B1 miatt, ha <code>Y ⊆ X</code>, innen pedig B3-mal jön, hogy ekkor <code>X → Y</code> 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 kiegészítés: Legyen <code>A → B</code> igaz és legyen F egy tetszőleges attribútumhalmaz. B1 miatt <code>AF → AF</code> is igaz. Erre a függésre és az <code>A → B</code>-re alkalmazva B2-t (X = AF, Z = A, Y = F, illetve C = B szereposztással) kapjuk, hogy <code>AF → AFB</code> igaz. Innen B3-mal jön, hogy <code>AF → BF</code>.
−
* 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.
+
* A tranzitivitás: Tegyük fel, hogy <code>A → B</code> és <code>B → D</code> igazak. B2-t használva (X = A, Z = B, Y = ∅ és C = D szereposztással), kapjuk <code>A → BD</code>-t, ahonnan B3-mal jön <code>A → D</code>.
 
}}
 
}}
  
47. sor: 63. sor:
 
(2004-11-19 3.) Igazak-e az alábbi szabályok? Ha igen, miért?
 
(2004-11-19 3.) Igazak-e az alábbi szabályok? Ha igen, miért?
  
−
a) X → Y, X → W, YW → Z ⊨ X → Z
+
a) <code>X → Y, X → W, YW → Z ⊨ X → Z</code>
 +
 
 +
b) <code>XY → Z, Y → W ⊨ XW → Z</code>
 +
 
 +
{{Rejtett|mutatott='''Megoldás'''|szöveg=
 +
a) Igaz:
 +
* <code>X → Y</code> adott.
 +
* <code>X → W</code> adott.
 +
* <code>X → YW</code> egyesítési szabály alapján.
 +
* <code>YW → Z</code> adott.
 +
* <code>X → Z</code> tranzitivitás szabály alapján.
 +
 
 +
A kezdeti függésekből levezethető <code>X → Z</code> az axiómák ismételt alkalmazásával. És ami levezethető, az igaz is.
  
−
b) XY → Z, Y → W ⊨ XW → Z
+
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)
 +
<code>XY → Z</code> 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. <code>Y → W</code> is teljesül hasonló okokból. <code>XW → Z</code> 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.
 +
}}
  
  
57. sor: 89. sor:
 
(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?
 
(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) <code>A → B, C → D ⊨ (A ∪ (C \ B)) → BD</code>
  
−
a) A → B, C → D ⊨ (C ∪ (D \ A)) → BD
+
a) <code>A → B, C → D ⊨ (C ∪ (D \ A)) → BD</code>
  
  
71. sor: 103. sor:
  
  
−
(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-04-19 6.a) Adott egy (R, F) séma, ahol R = ABCDE és <code>F = {AB → C, D → A, AE → B, CD → E, BE → D}</code>. BCNF-ben van-e ez a séma?
  
  
78. sor: 110. sor:
  
 
(2005-05-03 3.) Igaz-e, hogy a következő axiómarendszer teljes. azaz levezethető-e felhasználásukkal minden logikai következmény?
 
(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 <code>X ⊆ R</code>, akkor <code>X → X</code>.
−
* Ha X, Y ⊆ R és X → Y, akkor XW → YW igaz tetszőleges W ⊆ R-re.
+
* Ha <code>X, Y ⊆ R</code> és <code>X → Y</code>, akkor <code>XW → YW</code> igaz tetszőleges <code>W ⊆ R</code>-re.
−
* Ha X, Y, Z ⊆ R, X → Y és Y → Z, akkor X → Z.
+
* Ha <code>X, Y, Z ⊆ R</code>, <code>X → Y</code> és Y → Z, akkor <code>X → Z</code>.
 +
 
 +
{{Rejtett|mutatott='''Megoldás'''|szöveg=
 +
Nem vezethető le pl. <code>F = ∅</code>-ból <code>X → Y</code> ahol <code>Y ⊆ X</code>. Ugyanis minden felírható lépésben a jobboldal legalább annyi attribútumot tartalmaz, mint a baloldal.
 +
}}
  
  
87. sor: 123. sor:
  
 
(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!
 
(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!
 +
 +
{{Rejtett|mutatott='''Megoldás'''|szöveg=
 +
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 <code>AB → C</code> nem áll fenn az 1. és 2. sor miatt, <code>AC → B</code> nem teljesül a 2. és 3. sor miatt, <code>BC → A</code> pedig a 3. és 4. sor miatt. Az <code>X → Y</code> típusú függőségek nem teljesülnek, pl. <code>A → C</code>-nek logikai következménye <code>AB → C</code>, ami viszont már úgysem teljesül.
 +
}}
  
  
92. sor: 137. sor:
  
  
−
(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<sup>+</sup>?
+
(2005-05-03 6.) Adott egy (R, F) séma, ahol R ABCGWXYZ és <code>F = {XZ → BGYZ, AY → CG, C → W, B → G}</code>. Igaz-e, hogy <code>(AXZ → BY) ∈ F<sup>+</sup></code>?
 +
 
 +
{{Rejtett|mutatott='''Megoldás'''|szöveg=
 +
Az <code>XZ → BGYZ</code>-t bővítve A-val kapjuk <code>AXZ → ABGYZ</code> függőséget. Ebből a reflexivitás alapján <code>AXZ → BY</code> 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 <code>AXZ → BY</code>-t is.
 +
}}
  
  
98. sor: 147. sor:
  
  
−
(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: A → BCD, AD → E, EFG → H, F → GH.
+
(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: <code>F = {A → BCD, AD → E, EFG → H, F → GH}</code>.
  
 
a) Mi az egyetlen kulcs a sémában? Hány szuperkulcs van?
 
a) Mi az egyetlen kulcs a sémában? Hány szuperkulcs van?
  
 
b) 3NF-ben van-e a séma?
 
b) 3NF-ben van-e a séma?
 +
 +
{{Rejtett|mutatott='''Megoldás'''|szöveg=
 +
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.
 +
}}
  
  
108. sor: 165. sor:
  
  
−
(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 π<sub>X</sub>(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 2.) Legyen r egy R sémára illeszkedő reláció, X pedig R attribútumainak egy részhalmaza. Bizonyítsd be, hogy ha <code>π<sub>X</sub>(r)</code> és <code>r</code> sorainak száma megegyezik, akkor bármely <code>Y ⊆ R</code>-re fennáll az <code>X → Y</code> funkcionális függés!
  
  
149. sor: 206. sor:
  
 
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.
 
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.
 +
 +
{{Rejtett|mutatott='''Megoldás'''|szöveg=
 +
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<sub>2</sub>(A): mehet, r(A) 2 lesz, minden más marad 0
 +
* r<sub>3</sub>(C) : mehet, r(C) 3 lesz
 +
* r<sub>1</sub>(B): mehet, r(B) 1 lesz
 +
* w<sub>1</sub>(B): mehet, mert B-t csak T<sub>1</sub> olvasta eddig, w(B) 1 lesz
 +
* w<sub>3</sub>(A): mehet, mert A-t csak T<sub>2</sub> olvasta eddig, w(A) 3 lesz
 +
* w<sub>2</sub>(C): nem mehet, mert C-t T<sub>3</sub> már olvasta (amint ezt r(C) = 3 mu-tatja).
 +
 +
Vagyis csak T<sub>2</sub>-t fogja ABORT-ra utasítani az ütemező.
 +
 +
b) Ha w<sub>2</sub>(C) helyett w<sub>2</sub>(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<sub>2</sub>(B) kéréssel. Ha r<sub>3</sub>(C) helyett r<sub>3</sub>(A) lenne, akkor sem lesz ABORT, mert az A-t érintő kérések r<sub>2</sub>(A), r<sub>3</sub>(A), w<sub>3</sub>(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.
 +
}}

A lap jelenlegi, 2018. december 27., 13:07-kori változata

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ő:

  1. (a, a, a)
  2. (a, a, b)
  3. (a, b, b)
  4. (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 t1, t2, t3 tranzakciók írási és olvasási kéréseiből álló r2(A), r3(C), r1(B), w1(B), w3(A), w2(C) sorozaton. Időbélyeges tranzakciókezeléssel akarjuk a sorosítható ütemezést kikényszeríteni, a tranzakciók időbélyegei: TS(t1) = 1, TS(t2) = 2, TS(t3) = 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.

  • r2(A): mehet, r(A) 2 lesz, minden más marad 0
  • r3(C) : mehet, r(C) 3 lesz
  • r1(B): mehet, r(B) 1 lesz
  • w1(B): mehet, mert B-t csak T1 olvasta eddig, w(B) 1 lesz
  • w3(A): mehet, mert A-t csak T2 olvasta eddig, w(A) 3 lesz
  • w2(C): nem mehet, mert C-t T3 már olvasta (amint ezt r(C) = 3 mu-tatja).

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

b) Ha w2(C) helyett w2(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 w2(B) kéréssel. Ha r3(C) helyett r3(A) lenne, akkor sem lesz ABORT, mert az A-t érintő kérések r2(A), r3(A), w3(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.
A lap eredeti címe: „https://wiki.sch.bme.hu/index.php?title=Adatbázisok/Vizsga_feladatok&oldid=195388”