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).
Lausn:
Teiknum segðirnar sem tré.
(R1 join R2) join R3:

R1 join (R2 join R3):

Það er hægt að skilgreina tengingu (join) sem val eftir krossmargfeldi, þ.e. SELECT(c, A cross B) = JOIN(A, B, c). Við skulum nýta okkur þetta og teikna ný tré.

Röð dálka skiptir ekki máli þ.a. við fáum sömu raðir úr (R1 cross R2) cross R3 og við fáum úr R1 cross (R2 cross R3). Við veljum síðan út raðir samkvæmt sama skilyrði í báðum tilfellum. Við fáum því sömu gögn úr báðum segðum.
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.
Lausn:
Nei, hún er ekki tengin. Gerum ráð fyrir að við höfum eftirfarandi töflur.

A
x a

1 A

B
x b

2 B

C
x c

1 C

Þá gefur A NATURAL LEFT JOIN B okkur eftirfarandi töflu:

x a b

1 A NULL

og þá gefur (A NATURAL LEFT JOIN B) NATURAL LEFT JOIN C eftirfarandi töflu:

x a b c

1 A NULL C

En ef við reiknum hinsvegar fyrst B NATURAL LEFT JOIN C:

x b c

2 B NULL

Ef við reiknum síðan A NATURAL LEFT JOIN (B NATURAL LEFT JOIN C) þá fæst.

x a b c

1 A NULL NULL

Það fæst ekki sama niðurstaða þegar við reiknum (A NATURAL LEFT JOIN B) NATURAL LEFT JOIN C og þegar við reiknum A NATURAL LEFT JOIN (B NATURAL LEFT JOIN C). Vinstri ytri tenging er því ekki tengin.
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
  Lausn:
2. Sýnið nöfn allra leikara sem hafa leikið í Schindler's List.
  Lausn:
3. Sýnið nöfn allra kvikmynda sem Al Pacino hefur leikið í.
  Lausn:
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?
  Lausn:
  Síður nr. 1, 2 og 5.
2. Hvaða síður þarf að lesa til að sækja öll gildi þar sem X < 17?
  Lausn:
  Síður nr. 1, 2, 3 og 4.
3. Hvaða síður þarf að lesa til að sækja öll gildi þar sem 17 < X < 35?
  Lausn:
  Síður nr. 1, 2, 4 og 5.
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.
Rp = 150
Rn = 150*200 = 30.000
Sp = 1000
Sn = 1000*200 = 200.000
1. Gerum ráð fyrir engum flýtivísum.
  Hvað kostar að tengja R og S með hreiðraðri tengilykkju (e. nested loop join) ?
  Lausn:
  Rp + Rn*Sp = 150 + 30000*100 = 30.001.000
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) ?
  Lausn:
  Notum S sem ytri töfluna og R sem innri töfluna.
  Sp + Sn*C(R) = 1000 + 200.000*1.2 = 241.000
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) ?
  Lausn:
  Notum R sem ytri töfluna og S sem innri töfluna.
  Rp + Rn*C(S) = 150 + 30000*1.2 = 36.150
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) ?
  Lausn:
  Ef við notum R sem ytri töfluna og S sem innri töfluna:
  Rp + Rp/M * Sp = 150 + 150/50 * 1000 = 3150
  Ef við notum S sem ytri töfluna og R sem innri töfluna:
  Sp + Sp/M * Rp = 1000 + 1000/50 * 150 = 4000
5. Gerum ráð fyrir engum flýtivísum.
  Hvað kostar að tengja R og S með samröðunartengingu (e. sort-merge join) ?
  Lausn:
  Þarf að raða R og S. Getum ekki raðað þeim í vinnsluminni (höfum bara 50 síður af vinnsluminni). Notum ytri röðun.
  Röðum R.
  Fjöldi umferða er:
  >>> 1 + math.ceil(math.log(math.ceil(150.0/50.0), 50-1)) 2.0
  Röðunin kostar því 2N * passes = 2*150*2.0 = 600
  Röðum S.
  Fjöldi umferða er:
  >>> 1 + math.ceil(math.log(math.ceil(1000/50.0), 50-1)) 2.0
  Röðunin kostar því 2N * passes = 2*1000*2.0 = 4000
  Heildarkostnaður við að raða R og S er því 600+4000 = 4600 síður
  Heildarkostnaður við röðun R og S ásamt tengingu með sameiningu (merge) er því 4600 + 150 + 1000 = 5750.