581334-4 Tietokannan hallinta Kurssikoe 2.11.2001
Kirjoita jokaisen vastauspaperin yläreunaan nimi, syntymäaika,
nimikirjoitus, kurssin nimi ja päiväys!
Kokeessa ei saa käyttää mitään kirjallista materiaalia.
1.Tietokannan tallennusrakenteissa pyritään yleensä säästämään tilaa
siten, että relaation tallentamiseen tarvitaan niin vähän tilaa kuin
mahdollista. Eräissä tapauksissa tästä pääperiaatteesta tingitään
kuitenkin selvästi: ISAM-rakenne, B+ -puu ja hajautusrakenne sisältävät
tyypillisesti jaksoja, jotka eivät ole täynnä. Selitä jokainen mainittu
rakenne siten, että erityisesti tuo tilan 'tuhlaus' ja sen perustelu
selviää. 10 p
Ratkaisu:
1) ISAM-rakenne: perustiedosto järjestyksessä, hakemisto monitasoinen ja
harva (ks. luennot 3,12-18). Tilankäyttö: Monikon lisäys täyteen
perusjaksoon aiheuttaa ylivuotojakson käyttöönoton. Jättämällä
rakennetta luotaessa jokaiseen perustiedoston jaksoon tyhjää (jopa 50%?)
selvitään ilman ylivuotojaksoja varsin pitkään. Ylivuotojakson vikana
on se, että tietueen haun vaatima levyhakujen määrä kasvaa.
2) B+ -puu: Tavallaan ISAM-rakenteen vaikeuksien takia on kehitetty
rakenne, jossa periaatteessa kaikki solmut ovat ei-täysiä eli niihin
voidaan lisätä tietueita (avain + osoitin). Perustiedostossa ei tarvitse
vaatia järjestystä. Ks. luennot 3,24-31 (yleiset ominaisuudet).
Tilankäytön kannalta olennainen ominaisuus on vaatimus, että solmu on
aina 50-100% täynnä (p/2..p osoitinta); tasapainotilassa täyttöaste on
69 %.
3) Hajautusrakenne: Perustietueet jaetaan jaksoihin hajauttimen avulla:
jaksoissa voi olla 1..max tietuepaikkaa käytössä. Tilan "tuhlaus" on
tarpeen, ellei hajautin tuota täysin tasaisesti eri soluihin viittaavia
arvoja. Ylivuotojaksoja voi tulla. Myös soluhakemistossa voi olla
tyhjää; jos se on keskusmuistissa, tällä ei ole paljon merkitystä.
(Yleiset ominaisuudet: luennot 2,26-32.)
Arvostelu (Anna):
ISAM: max 3p
- Jos rakenne hallussa mutta tilankäytön selittämisessä ongelmia 2p
- Jos rakenteessa pienehkö virhe mutta tilankäytön perustelut kunnossa 2p
- Jos rakenteessa pienehkö virhe ja tilankäytön perustelussa ongelmia 1p
B+-puu: max 4p
- Jos rakenne hyvin selitetty (tilankäyttöineen) mutta perustelu
tuhlauksen edulle puuttuu tai virheellinen 3p
- Jos rakenteen selitys vajavainen mutta tilankäytöstä on mainintaa 2p
- Jos virheitä molemmissa mutta silti yritetty ja jotain oikeaakin löytyy
1p
Hajautusrakenne: max 3p
- Jos rakenne selitetty mutta tilankäytön selittämisessä ongelmia 2p
- Jos rakenteessa virhe mutta tilankäyttö kunnossa 2p
- Jos molemmissa virheitä tai vajavaisuutta mutta tarpeeksi asiaakin
oikein 1p
2. Oletetaan relaatio
employee(fname, lname, ssn, salary, dno)
ja kysely
select lname, fname, salary from employee
where salary > 50000 or dno > 10;
Selitä kyselyn toteutuksen vaiheet ja arvioi tarvittavien levyhakujen
määrää, kun
a) relaatiolle ei ole mitään hakemistoa,
b) toiselle attribuuteista salary, dno on hakemisto,
c) kummallekin attribuuteista salary, dno on oma hakemisto.
Kohdissa b ja c voit valita hakemistojen tyypit itse; niistä on
mainittava kyselyn toteutuksen kannalta olennaiset ominaisuudet. 12 p
Ratkaisu: Oletetaan, että relaatiossa on n jaksoa (N monikkoa), ehdon
(salary > 5000) täyttäviä monikkoja on N1 ja ehdon (dno > 5) täyttäviä
monikkoja N2.
a) Jokainen relaation rivi on käytävä läpi ja testattava salary- ja
dno-ehdot. Kun ehdot ovat voimassa, viedään riviltä tulosrelaatioon
lname, fname ja salary. Levyhakuja tulee siis n kappaletta. (Relaation
rivien järjestyksellä ei ole merkitystä eikä kyselyä voida muutenkaan -
operaatioiden järjestyksen kannalta - optimoida.)
b) Oletetaan, että on hakemisto dno-attribuutille. Kysely toteutetaan
kahdessa vaiheessa:
1) Haetaan hakemiston avulla niiden perustiedoston jaksojen osoitteet,
joissa on (dno>10) -tietueita. Tulos on lista L1, jonka avulla saadaan
vastaavat perustietueet. Hakemisto ei voi >-ehdon takia olla
hajautustyyppiä.
2a) Jos perustiedosto on järjestetty laskevaan palkkajärjestykseen,
käydään sitä läpi niin pitkälle kuin salary > 50000. Voidaan muodostaa
jakso-osoitteiden lista L2 tai (mieluummin, koska on jo haettu
perustietueet) tai suoraan salary-ehdon täyttävien tietueiden lista.
Yhdistetään saadut tietueet ja kohdan 1 perusteella saadut tietueet
tulokseksi. Levyhakujen määrä on N1+N2, mikäli välitulokset voidaan
pitää keskusmuistissa ja mikäli missään jaksossa ei ole enempää kuin
yksi ehdon täyttävä tietue. Käytännössä hakujen määrä on pienempi.
Minimimäärä on 1 (haetaan vain ensimmäinen jakso salary-haussa).
2b) Jos perustiedosto on järjestämätön (tai muu järjestys kuin edellä,
siis sellainen, josta ei ole tässä hyötyä), tulee toisessa vaiheessa
käydä koko relaatio läpi. Tässä tapauksessa kannattaa kysely toteuttaa
kuten kohdassa a eli ei kannata käyttää hakemistoa ollenkaan.
Jos on vain salary-hakemisto, ratkaisu on edellisen kanssa symmetrinen.
(Perustiedoston mahdollisista järjestyksistä todennäköisin on ehkä
nouseva dno-järjestys. Siitä ei ole tässä hyötyä, koska ensimmäinen
(dno>5) -rivi tulee hakea selaamalla rivejä (jaksoja) läpi.)
c) Jos on molemmat hakemistot, muodostetaan jakso-osoitteiden listat L1
ja L2 ja sitten niiden yhdiste. Yhdiste sisältää niiden jaksojen
osoitteet, jotka on haettava tuloksen muodostamiseksi. Levyhakuja 0-n
kappaletta.
Arvostelu (Pietu):
- tulossa
3.Relaatiossa R on 40 000 kpl 100 tavun monikoita ja relaatiossa S 10
000 kpl 800 tavun monikoita. Levymuistin jakso on 4 KB.
a) Mikä on levyoperaatioiden määrä sisäkkäisiin silmukoihin perustuvassa
R:n ja S:n liitoksessa, kun puskuritilaa on käytettävissä 20 KB?
b) Mikä on liitoksen suoritusaika (sekunneissa) tyypillisellä
levymuistilla? Karkea arvio riittää, mutta se on perusteltava
selittämällä, kuinka levyoperaation suoritusaika määräytyy.
10 p
a) Jaksoja R:ssä r = 40000/40 = 1000 ja S:ssä s = 10000/5 = 2000
kappaletta. Puskuritilaa on viidelle jaksolle, joka käytetään
seuraavasti: yksi tuloksen kirjoittamiseen, yksi sisemmän silmukan
jaksojen lukemiseen ja kolme ulomman silmukan jaksojen lukemiseen
(kolmen jakson erissä). Jaksomäärältään pienempi relaatio (R) valitaan
ulompaan silmukkaan, jolloin levyhakuja tarvitaan
(3 + 3 + ... + 1) + (2000 x 334) = 669000.
b) Karkea arvio suoritusajalle (jaksot hajallaan levyllä):
kohdistus esim. 6 ms
pyörähdysviive (latenssi) 3 ms (10000 kierrosta/min)
jakson siirto (alle) 1 ms
eli yhteensä noin 10 ms. Kyselyn suoritusaika on tällöin 6690 s eli
lähes 2 tuntia. Kohdistus- ja latenssiajoissa voidaan säästää
huomattavasti, jos sisemmässä silmukassa voidaan lukea
jaksoja peräkkäin.
Arvostelu (Janne):
a) Pisteitä on saanut 5 - virheet. Pelkkiä laskuvirheitä ei ole pidetty
virheinä.
Yleisiä virheitä:
- unohdettu se, että myös ulomman silmukan relaatio luetaan
- unohdettu jättää puskuriin tilaa kummallekin relaatiolle, ts. luettu
aina puskuri täyteen (miten liitos tehdään, kun muistissa on vain
toisen relaation monikoita?)
(- unohdettu varata tulokselle tilaa puskurista; tämä annettiin
anteeksi)
b) 3 pistettä levyoperaation osista, 2 aika-arvio(i)sta.
Yleisiä virheitä:
- keksitty tähän yhtäkkiä aivan eri levyhakujen määrä kuin a-kohdassa
- arvioitu osa-aikoja kummallisesti, esim. jakson siirtoaika
pidemmäksi kuin levyn yhden kierroksen pyörähdys
4. a)
Eristyneisyysongelmat:
rivit 1 ja 4: likainen luku (T1 kirjoittaa X:n, T2 lukee ennen T1:n
sitoutumista)
rivit 2 ja 3: likainen luku (T2 kirjoittaa Y:n, T1 lukee ennen T2:n
sitoutumista)
rivit 2 ja 5: likainen kirjoitus (T1 kirjoittaa T2:n (ei sit.)
kirjoittaman Y:n päälle)
Muita ongelmia ajoituksessa ei ole.
b) Ankara kaksivaiheinen lukitus: lukot vapautetaan vasta
sitoutumisessa.
Tässä tapauksessa tapahtuu seuraavaa:
T1 T2
write_lock(X)
write_item(X)
write_lock(Y)
write_item(Y)
read_lock(Y)
read_lock(X)
T1 saa siis kirjoituslukon X:ään ja T2 Y:hyn. Lukkoja ei vapauteta
heti kirjoittamisen jälkeen. Seuraavaksi T1 jää odottamaan lukulukkoa
Y:hyn (T1 ei saa lukulukkoa, koska T2:lla on kirjoituslukko samaan
alkioon) ja T2 X:ään. Kumpikaan ei pääse etenemään, eli kyseessä on
lukkiuma.
Arvostelu (Janne):
a) 2p/oikea eristyneisyysongelma, väärät ja ylimääräiset -2p/kpl,
yhteensä kuitenkin min 0, max 5 pistettä.
Yleisiä virheitä:
- ylimääräisiä eristyneisyysongelmia
b) max 5 pistett - virheet
Yleisiä virheitä:
- transaktiot pyytävät ja saavat lukkoja, mutta lukoilla ei ole mitään
vaikutusta
- kerrottu (ankarasta) 2PL:stä yleensä, ei mitä tässä tapauksessa
tapahtuu
- transaktiot vapauttelevat lukkoja kesken kaiken
- vaihdettu operaatioiden ajoitusta
5. Selitä lyhyesti seuraavat käsitteet ja niiden merkitys elvytyksessä:
a) tarkistuspiste (checkpoint),
b) sitoutumiskäytäntö (commit protocol). 8 p
Ratkaisu:
a) tarkistuspiste (ks. luennot, s. 5,23-26): tehdään transaktioista
riippumaton "varmistus" viemällä päivitetyt puskurisivut levylle. Lokiin
viedään vastaava checkpoint-tietue ja kirjoitetaan myös loki levylle.
Suorituksen ajaksi estetään transaktioiden suoritus, minkä takia
tarkistuspistettä ei pidä tehdä liian usein. Toisaalta liian pitkä
tarkistuspisteiden väli aiheuttaa sen, että elvytyksessä redo- ja
undo-operaatioita voi tulla paljon.
b) sitoutumiskäytäntö (ks. luennot, s. 5,22..) = onnistuneen transaktion
päättävä toiminto. Ohjelmassa commit-pyyntö aiheuttaa transaktioiden
samanaikaiseen toimintaan liittyviä tarkistuksia. Jos tarkistukset eivät
estä, transaktio sitoutuu ja sen merkiksi lokiin kirjoitetaan
commit-tietue (commit, T) ja loki kirjoitetaan sitten levylle.
Transaktion hallussa olevat lukot vapautetaan.
Merkitys elvytyksessä: Jos T:lle ei löydy häiriön sattuessa lokista
commit-tietuetta (eikä abort-tietuetta), T on aktiivinen ja sen
toimenpiteet on peruttava (undo). Jos (commit,T) löytyy, mutta sen
jälkeen ei ole tehty tarkistuspistettä, T:n toimenpiteet on uusittava
(redo).
Arvostelu (Anna):
a) Checkpoint: max 4p (joko menettelyn kuvaus tai maininta operaation
hitaudesta on vaadittu täysiin pisteisiin)
- Tiedetään tilan tallettaminen ja merkitys elvyttämisessä mutta sekä
menettelyn kuvaus että menetelmän hitaus puuttuvat 3p
- Virheitä joko tilan tallettamisessa tai elvyttämisessä 2p
- Tilan tallettamisessa virheitä ja lisäksi elvytyskin puuttuu 1p
b) Sitoutumiskäytäntö: max 4p
- Muuten kunnossa mutta elvytysmaininta puuttuu 3p
- Mainittu operaatiot jotka tehdään sitoutumisen yhteydessä ilman
tarkempaa selitystä tai virheellisen selityksen kanssa 2p
- Commit lokiin, muuten selitys metsässä 1p