Tietokannan hallinta
Välikokeen 01.11.2000 ratkaisut ja arvostelu
Korjaajat: 1&2: Janne Rinta-Mänty, 3: Janne Kraft, 4&5: Anna Pienimäki
1. Olkoon levytiedostossa 200 000 tietuetta, tietueen pituus 200 tavua
ja jakson pituus 4096 tavua. Levyn kohdistusaika (seek time) on 1-12 ms
ja jakson siirtoaika (block transfer time) 0.5 ms. Levykössä on 10
levypintaa, pinnalla 2000 uraa ja uralla 40 jaksoa. Mikä on lyhin ja
pisin aika, minkä tiedoston kaikkien jaksojen lukeminen voi viedä?
(Esitä oletukset, joilla päästään minimiaikaan ja maksimiaikaan, ja
arvioi lukemiseen tarvittava aika.) 6 p
Ratkaisu:
Tietueet vievät tilaa 200 000 x 200 tavua eli 40 MB. Jaksoon
mahtuu 20 tietuetta (jää 96 tavua kontrollitiedoille) eli jaksojen määrä
on 10 000.
Minimiaika: Jaksot ovat peräkkäin sylintereittäin ja urat täynnä.
Hakuvarren siirtoja tarvitaan tällöin vain koko sylinterin jaksojen
lukemisen jälkeen ja siirto on mahdollisimamn lyhyt (seuraavalle
sylinterille).
Maksimiaika: Jaksot ovat "yksitellen" hajallaan, jolloin jokaisen jakson
lukeminen vaatii hakuvarren siirron, pyörähdysviipeen ja jakson
siirtoajan.
Sylinterille mahtuu 10 x 40 = 400 jaksoa; sylintereitä tarvitaan siis
25.
Lasketaan keskimääräinen pyörähdysviive: Yhden pyörähdyksen aikana siirretään
40 jaksoa eli se kestää 40 x 0.5 = 20 ms. Keskimääräinen pyörähdysviive
on siis 10 ms. Käytetään tätä laskuissa. (Maksimaalinen lähes täysi
pyörähdys veisi 39/40 x 20 = 19.5 ms, minimaalinen viive on 0, mutta sen
toteutuminen muuten kuin samaa uraa luettaessa on sattumanvaraista.)
Minimiaika: 1. sylinterin siirto: 1 + 10 + 400 x 0.5 = 211 ms
muut sylinterit: 24 x (1 + 0 + 400 x 0.5) = 4824 ms
eli yhteensä 5.04 ms
Maksimiaika: 10000 x (12 + 10 + 0.5) = 225 000 ms = 225 s
(Kohdistusaika on käytännössä hieman pienempi, koska peräkkäin luettavat
jaksot eivät voi olla aivan reunimmaisilla urilla. Mutta 25 sylinterin
'pahin mahdollinen sijoitus' voisi olla esim. 13 sisimmällä ja 12
uloimmalla uralla, jolloin kohdistukset ovat hyvin lähellä maksimia.)
Arvostelu: Minimiaika oletuksineen 3 pistettä, maksimiaika oletuksineen
3 pistettä. Laskuvirheistä ei sakotettu (jako- ja kertolasku näytti
olleen yllättävän vaikeaa!). Maksimiajassa hyväksyttiin sekä
maksimi- että keskimääräisen kohdistusajan tai pyörähdysviipeen
käyttö.
-----
2. Olkoon relaatiossa 500 000 tietuetta (monikkoa), tietueen pituus 400
tavua ja jakson pituus 4096 tavua. Jakson osoite ja tietueen avain
vievät kumpikin 10 tavua. Jakson saantiaika on 0.2 s.
Keskusmuistitilaa on käytettävissä vain 20 kilotavua.
Relaatiota käyttävässä sovelluksessa halutaan saada monikon haku
suoritetuksi 1 sekunnissa. Relaatio on toteutettu a) hajautukseen
perustuvana tiedostorakenteena tai b) harvana ISAM-rakenteena. Relaatio
on luotu yleisten periaatteiden mukaan 200 000 tietueen kokoisena ja
kasvanut lisäysoperaatioilla vähitellen esitettyyn kokoon.
Selitä kummankin tiedostorakenteen pääpiirteet tehtävässä mainittuihin
kokotietoihin perustuen (kaavio ja riittävästi selitystä). Hajautuksen
tapauksessa ei ole tarkoitus käsitellä dynaamisia hajautusmenetelmiä,
vaan perusmenetelmää.
Millä edellytyksillä monikon haku toteutuu halutussa ajassa? 12 p
Ratkaisu - hieman pitkät selitykset ilman kaaviota (ks. luennot: s.
2-28); näin pitkää ei tietysti vaadittu, kunhan rakenteiden mittasuhteet
oli itselle selvitetty):
a) Hajautusalue = B kpl kotisolujen osoitteita (0..B-1). Kotisolussa on
yksi tai useampia jaksoja ketjussa. Jaksoon mahtuu 10 tietuetta, joten
500 000 tietuetta vaatii 50000 täyttä jaksoa. Käytännössä hajautus ei
ole tasainen, joten jaksoja tarvitaan enemmän.
Yhden sekunnin vaatimus sallii enintään 5 jakson ketjut. Tällöin
kotisolujen jakso-osoitteiden tulisi mahtua keskusmuistiin.
Jakso-osoitteita on vähintään 50000 / 5 = 10000 kpl eli niiden vaatima
tila on vähintään 10 x 10000 tavua eli 100 KB. Keksumuistirajoituksen
takia kotisolujen jakso-osoitteet tulee pitää levymuistissa, ja ketjut
on lyhennettävä enintään 4 jakson pituisiksi, jolloin niitä olisi 12500
kpl. Tällöin jakso-osoitteet (125 000 tavua) olisivat 32 jaksossa;
näiden osoitteet keskusmuistissa.
Käytännössä hajautus ei ole läheskään optimaalisen tasainen eli
tarvitaan enemmän ketjuja eli suurempi hajautusalue. Voidaan kuitenkin
olettaa, että edellä kuvatut periaatteet riittävät.
Esim. B = 40000: keskusmuistissa 100 osoitetta jaksoihin, joissa
kussakin on 400 jakso-osoitetta; tasaisella hajautuksella ketjussa on
keskimäärin 12.5 tietuetta eli 1.25 jaksoa. Alussa (200 000 tietuetta)
ketjut voivat olla yhden jakson pituisia (2 levyhakua).
Ts. edellytyksenä yhden sekunnin riittämiselle on
- riittävän suuri hajautusalueen koko (takaa keskimäärin nopean
toiminnan), ja
- riittävän tasainen hajautus: mikään ketju ei saisi olla pitempi kuin 4
jaksoa.
b) ISAM: levyhakujen määrä muodostuu hakemistotasoista ja perusjaksoista
(ylivuotoketjuineen). Luontivaiheen rakenne: 2 hakemistotasoa, vrt.
'kaavio' luentojen sivulla 3-10).
Perustaso: 200 000 tietuetta, jaksojen 50 %:n täyttöasteella 40000 jaksoa.
1. hakemistotaso: 40000 hakemistotietuetta, jokainen 10 + 10 tavua eli
200 jaksoa.
2. hakemistotaso: 200 hakemistotietuetta eli mahtuvat yhteen jaksoon
(keskusmuistiin).
Luontivaiheen jälkeen kaikki monikon haut toteutuvat kahdella
levyhaulla.
Relaation laajentuminen 500 000 tietueeseen: 200 000 uutta tietuetta
mahtuisi ilman ylivuotojaksoja, jos jakauma olisi hyvin tasainen
(teoriaa!). Lisättäessä vielä 100 000 tietuetta keskimääräinen
ylivuotoketjun pituus jää edelleen pieneksi (jos tietueet jakautuvat
tasaisesti).
Ts. tässä tapauksessa yhden sekunnin rajan edellytyksenä on, että mikään
ylivuotoketju ei tule pitemmäksi kuin 4 jaksoa (perusjakso mukaanluettuna).
Arvostelu: Hajautuksen ja harvan ISAMin perusteiden selittäminen 3
pistettä/kpl, niiden soveltaminen tehtävän tapaukseen 3 pistettä/kpl.
Tässäkään ei sakotettu laskuvirheistä.
----
3. Olkoon tietokannassa relaatiot
henkilö(hetu, snimi, enimi, palkka, osnro),
osasto(onro, onimi, opaikka, johtaja).
a) Selitä valintaoperaation toteutusvaihtoehdot esimerkkikyselyn
select snimi, enimi from henkilö
where palkka < 10000 and osnro = 5;
kannalta. Esitä sopivat oletukset henkilö-relaation vaihtoehtoisille
toteutuksille ja selitä kyselyn toteutus oletuksiin perustuen.
b) Esitä optimoitu kyselypuu (kaavapuu) kyselylle
select snimi, enimi, onimi from henkilö, osasto
where osnro = onro and palkka > 20000 and opaikka = Helsinki;
c) Selitä lyhyesti, mitä vaihtoehtoisia tapoja on b-kohdan kyselyn
liitosoperaation toteuttamiselle? Vastauksesta tulee käydä ilmi, mitä
vaatimuksia eri tavat asettavat relaatioiden toteutukselle. 12 p
Ratkaisu:
a) Ks. luennot, s. 4-11..4-12
Jos relaatiolle ei ole hakemistoja, luetaan kaikki sivut läpi ja
testataan ehdot jokaiselle tietueelle (lineaarinen haku).
Jos relaatio on järjestetty osnro:n mukaan, voidaan hakea binäärihaulla
(osnro=5)- monikot ja testata jokaiselle palkka-ehto. (Vastaavasti
toisinpäin, jos on palkkajärjestys; epätodennäköinen).
Jos relaatiolle on osnro- tai salary-hakemisto tai molemmat, käytetään
ainoaa tai valitsevampaa hakemistoa eli varmaankin osnro-hakemistoa ja
testataan palkkaehto valituille tietueille. Palkka-hakemiston käyttö on
mahdollista vain, jos hakemisto on järjestävä.
Jos on kaksi hakemistoa, voidaan muodostaa niiden antamien
tietueosoitinlistojen leikkaus ja hakea vain leikkaukseen kuuluvat
tietueet.
b) P
snimi, enimi, onimi
|
|
|><|
/\ osnro = onro
/ \
/ \
/ \
S S
palkka > 20000 opaikka = 'Helsinki'
| |
| |
| |
henkilö osasto
(P = projektio, S = valinta)
c) - sisäkkäiset silmukat
käytetään, kun ei ole hakemistoja; pienempi relaatio ulompaan
silmukkaan (tässä riippuu ainakin palkkatasosta)
- lomitus
käytetään, kun relaatiot järjestyksessä
tässä osasto voisi ehkä olla järjestyksessä, mahdollisesti
henkilötkin
- hakemistoliitos
tarvitaan osastonumero-hakemisto ainakin toiselle relaatiolle
- hajautusliitos
hajautetaan pienemmän relaation rivit ensin ja käydään
läpi toinen relaatio (hajauttaen)
tässä kokojen suhde riippuu palkkatasosta ja osastojen määrästä
Helsingissä
Arvostelu: a) 4 p, b) 4 p, c) 4 p (a&c: relaatioiden tai hakemistojen
valintaan liittyvää pohdiskelua ei laajasti vaadittu;
perustelemattomalla asialuettelolla ei toisaalta saanut kuin yhden pisteen)
---
4. a) Selitä elvytykseen käytettävän lokin tietuetyypit ja niiden
käyttö elvytyksessä.
b) Tietosivulla (esim. tunnustietueessa) ylläpidetään erästä
lokitietueen järjestysnumeroa (log sequence number, LSN). Mikä on sen
merkitys elvytyksessä?
c) Mitä tarkoitetaan WAL (write ahead logging) - käytännöllä? 10 p
Ratkaisu:
a) Ks. luennot, s. 5-19 (tietuetyypit), 5-23 (käyttö).
b) Ks. luennot, s. 5-25.
c) Ks. luennot, s. 5-21.
Arvostelu:
a) Tietuetyypit, käyttö (4p)
Tietuetyypit:
Start, Write, Abort, Commit, Checkpoint - 2p
Start puuttuu - ei miinuksia
Muista puutteista -1/2p per puuttuva
Kaikkien käyttö selitetty 2p
-1/2p per puuttuva selitys elytystilanteesta
b) LSN (3p)
Kerrottu lokin rivinumerointi, levyllä olevien tietoalkioiden PageLSN:t
ja elvytystilanteen toiminta - 3p
Elvytys puuttui max. 1 1/2 p
Mainittu vain järjestysnumerointi, elvytyksessä puhuttu järjestyksestä
max. 1 1/2 p
c) WAL (3p)
Lokin kirjoitus levylle aina ennen datasivujen kirjoitusta - 3p
Jos puhuttu pelkästä lokiin kirjoittamisesta (muttei lokin
levylleviennistä) max. 1 1/2 pistettä.
---
5. Oletetaan, että transaktiot T1 ja T2 noudattavat seuraavaa ajoitusta:
1 T1: read_item(X);
2 T2: read_item(X);
3 T1: write_item(X);
4 T1: read_item(Y);
5 T2: read_item(X);
6 T2: write_item(X);
7 T1: write-item(Y);
8 T1: commit;
9 T2: commit;
a) Mitkä operaatioparit tässä ajoituksessa konfliktoivat? Vastaa
numeropareilla: esim. 1-2, jos rivien 1 ja 2 operaatiot konfliktoivat.
Anna kolme esimerkkiä ei-konfliktoivasta operaatioparista ja perustele,
miksi kukin niistä ei konfliktoi. Esimerkkien tulee olla erilaisia
(kussakin eri peruste).
b) Mitä eristyvyysanomalioita konflikteihin liittyy? 10 p
Ratkaisu & arvostelu:
a) Konfliktoivat (2p), Ei-konfliktoivat (2p)
Konfliktoivat: 1-6, 2-3, 3-5, 3-6: 2p
- 1/2 p per puuttuva
Ei-konfliktoivat (esim.):
1-3 saman transaktion operaatioita
6-7 eri tietoalkioon kohdistuvia
1-2 molemmat lukuoperaatioita
Kolme eri perustein ei-konfliktoivaa paria perusteltuna 2p
Tässä hyväksytty myös lokimuotoiset esittelyt ei-konfliktoivista
pareista.
- Ei perusteltu - max 1p
b) Anomaliat:
1-6 toistokelvoton luku (samoin 2-3)
3-5 likainen luku
3-6 likainen kirjoitus
Kaikki kolme anomaliaa esitelty 6p
-2p per puuttuva