Gagnasafnsfræði, haust 2011

Verkefni 8 - Venslaalgebra og bestun fyrirspurna

Lausnum skal skilað í hólf viðkomandi dæmakennara (sjá lista yfir dæmatíma).

Skiladagur: þriðjudaginn 25. október fyrir kl 16:00

Skiladæmi:

Sýnið fram á að tengivirkinn (e. join operator) er tenginn (e. associative), þ.e. (R1 join R2) join R3 gefur sömu niðurstöðu og R1 join (R2 join R3).
Er vinstri ytri tenging (e. left outer join) tengin? Ef aðgerðin er tengin gefið þá stuttan rökstuðning, en gefið mótdæmi ef hún er það ekki.
Gefin eru eftirfarandi vensl, þar sem aðallyklar eru undirstrikaðir.
- actor(actorid, name)
- movie(movieid, title, year, votes, score)
- casting(actorid, movieid, ord)
Teiknið venslaalgebru tré fyrir eftirfarandi segðir:
1. Sýnið nöfn allra kvikmynda sem hafa einkunn > 8.5
2. Sýnið nöfn allra leikara sem hafa leikið í Schindler's List.
3. Sýnið nöfn allra kvikmynda sem Al Pacino hefur leikið í.
Höfum eftirfarandi B+ tré fyrir dálk X:
1. Hvaða síður þarf að lesa til að sækja gildi þar sem X = 35?
2. Hvaða síður þarf að lesa til að sækja öll gildi þar sem X < 17?
3. Hvaða síður þarf að lesa til að sækja öll gildi þar sem 17 < X < 35?
Gefin eru eftirfarandi vensl: R(a) með 150 síðum, og S(a) með 1000 síðum. Hver síða inniheldur L = 200 gildi.
Gerum ráð fyrir að við megum nota M = 50 síður af vinnsluminni.
1. Gerum ráð fyrir engum flýtivísum.
  Hvað kostar að tengja R og S með hreiðraðri tengilykkju (e. nested loop join) ?
2. Gerum ráð fyrir hakkavísi á R(a).
  Hvað kostar að tengja R og S með hreiðraðri tengilykkju sem notar vísi (e. index nested loop join) ?
3. Gerum ráð fyrir hakkavísi á S(a).
  Hvað kostar að tengja R og S með hreiðraðri tengilykkju sem notar vísi (e. index nested loop join) ?
4. Gerum ráð fyrir engum flýtivísum.
  Hvað kostar að tengja R og S með hreiðraðri tengilykkju sem notar blokkir (e. block nested loop) ?
5. Gerum ráð fyrir engum flýtivísum.
  Hvað kostar að tengja R og S með samröðunartengingu (e. sort-merge join) ?