Adatbázisok - Relációs lekérdezések optimalizálása gyakorlat

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

Feladatok

1. feladat: (bemelegítés, jelölések, katalógusinformációk és alap algoritmusok)

Egy bank nyilvántartásából ${\text{ACCOUNT(BRANCH-NAME, BALANCE,}}\dots {\text{)}}$ szeretnénk megtudni a budapesti számlák adatait. Ezeket tudjuk a relációról:

• $f_{\text{ACCOUNT}}=20$ (Az ACCOUNT reláció 20 rekordja fér bele egy lemezblokkba)
• $V({\text{BRANCH-NAME}},{\text{ACCOUNT}})=50$ (50 különböző fiók-név létezik az ACCOUNT relációban)
• $V({\text{BALANCE}},{\text{ACCOUNT}})=500$ (500 különboző értékű számla van az ACCOUNT relációban)
• $n_{\text{ACCOUNT}}=10000$ (Az ACCOUNT relációnak 10 000 eleme van)
• $P$

Kérdések:

• 1. Adjuk meg a feladatot megoldó relációalgebrai lekérdezést.
• 2. Mennyi minimális/maximális/átlagos költség, ha lineáris keresést alkalmazunk? Mitől függ, hogy mennyi?
• 3. Tfh. a rekordok a fiók szerint rendezetten tárolódnak. Mennyi a bináris keresés költsége várható értékben?

2. feladat: a join nagyságának becslése

Adott két relációs sémánk, A BETETES és az UGYFEL. Illesszük a két (sémára illeszkedő) relációt a mindkettőben szereplő ÜGYFÉL_NÉV attribútúm szerint. Tegyük fel, hogy a két relációról a következő katalógusinformációk állnak rendelkezésre:

• $n_{\text{UGYFEL}}=10000$
• $f_{\text{UGYFEL}}=24;b_{\text{UGYFEL}}=?$

• $n_{\text{BETETES}}=5000$
• $f_{\text{BETETES}}=50;b_{\text{BETETES}}=?$

• Értelmezés sikertelen (formai hiba): {\displaystyle V(\text{UGYFEL\_NEV}, \text{BETETES}) = 2500 } , azaz átlagban minden felhasználónak két számlája van.

Mekkora a BETÉTES és az ÜGYFÉL természetes illesztésének mérete, ha egyetlen közös attribútumunk az ÜGYÉL_NÉV? Általánosítsuk a feladatot az alábbi esetekre (R és S az illesztendő relációk sémái, természetes illesztéssel)!

• 1. $R\cap S=\emptyset$.
• 2. $R\cap S$ az R reláció kulcsa.
• 3. $R\cap S\neq \emptyset$ egyik relációs sémának sem kulcsa.

3. feladat: Hash-join költsége

Számítsd ki a "hash join" algoritmussal végrehajtott join költségét, ha vödrös hashelést alkalmazunk! A hash függvény egyenletes eloszlással képezi le a kulcsokat az értékkészletére. Hogyan érdemes a join-t végrehajtani? A blokkméret nettó 2000 byte, a hash tábla szokás szerint elfér a memóriában.

• 1. reláció: 120 000 rekord, rekordhossz 150 byte, kulcs 12 byte, mutató 5 byte, a hash tábla mérete 10 000 byte.
• 2. reláció: 10 000 rekord, rekordhossz 250 byte, kulcs 15 byte, mutató 8 byte, a hash tábla mérete 1000 byte.

4. feladat: index-alapú illesztés

Számítsd ki az illesztés költségét, ha elsődleges, B*-fa struktúrájú indexeket használhatunk a join attribútumok sziernti rekordelérésre! A blokkméret nettó 4000 byte. Melyik reláció legyen a külcső hurokban? Hányszoros válszidőt kapunk, ha az optimalizáló rosszul dönt?

• 1. reláció: 140 000 rekord, rekordhossz 140 byte, kulcs 10 byte, mutató 4 byte.
• 2. reláció: 15 000 rekord, rekordhossz 300 byte, kulcs 6 byte, mutató 4 byte.

Gondolkodtató kérdések

1. Relacióanalízis feladat: A relációs lekérdezések költség alapú optimalizációjakor az ekvivalens alakokat előállító szabályoknak nincs jelentősége, mert csak a heurisztikus (vagy szbály alapú) optimalizálás alapszik átalakítási szabályokon.

2. Vizsgáld meg a blokkalapú egymásba ágyazott ciklikus illesztés és az egymásba ágyazott ciklikus illesztés algoritmusokban: a legbelső ciklusmag hányszor fut le worst-case esetben. Vesd össze az eredményt a két algorimtuss worst-case költségével, és magyarázd meg a tapasztaltakat.

3. A természetes illesztésnél előbb "érdemes" végrehajtani az egy relációt érintő szelekció műveleteket, és ezt meg is tehetjük: ekvivalens algebrai alakot kapunk, ha lentebb (az alaprelációk irányába) süllyesztjük a szelekciókat. Megtehető-e ugyanez külső illesztés esetén? Mitől függ, hogy megtehető-e?

4. Lehet-e értelme olyan alapos költségbecslést és optimalizációt végezni, amelynek a kölstsége eléri/meghaladja a lekérdezés legköltségesebb szóba jövő végrehajtási módja költségét?

5. Melyek azoka műveletek, ahol elsődleges index használata olcsóbb végrehajtást eredményez, mint egy egyszerű index használata?

6. Mutass példát arra, amikor az elsődleges index használata ront a teljesítményen!

7. Mutass példát, amikor a lineáris keresés olcsóbb, mint az indexelt keresés! Próbáld általánosan megfogalmazi az eredményt!

8. Mi a biztos jele annak, hogy adatbázisunkból a szekvenciálisan generált ID nevű, elsődleges kulcsmezőt törölni kell? Mit vesztünk azzal, ha nem töröljük?

9. A relációs lekérdezések végrehajtási folyamatában szereplő optimalizálás bemenete miért relációalgebrajellegű kifejezés, ahelyett hogy valamilyen kalkulus-kifejezés lenne?

10. Az "index alapú illesztés" feladatban a relációs sémák kulcsait különböző hosszon tároltuk, azonban a természetes illesztés miatt rajtuk egyenlőségvizsgálatot kellett végezni. Lhetséges ilyen eset? Mutass példát rá, ha lehetséges, és indokold, ha nem!

11. Az "index alapú illeszteés" feladatban erre vonatkozó információ hiányában feltételeztük, hogy az indexelt kulcsok egyedi értékűek a sémára illeszkedő relációban. Hogyan változik a join költsége/memóriaigénye, ha az egyes relációkban:

• 1. SC(Kulcs, R) < $f_{R}$?
• 2. SC(Kulcs, R) tetszőleges?

-- soyer - 2008.11.18.