Tietokannan hallinta, välikoe 18.5.2001 - ratkaisuista ja arvostelusta

1. Tietorakennekohtaisesti, ensin kasa, sitten järjestetty
peräkkäistiedosto ja viimeksi hajautettu rakenne. 

Kasa:

a) Lisäys on nopea: Jos lisättävä mahtuu kasan (ketjun) viimeiseen
jaksoon (ja jos tämän osoite on tiedostokuvaajassa), tarvitaan 2
levyhakua (luku ja kirjoitus). Jos viimeinen jakso on täynnä, tarvitaan
kaksi kirjoitusta.

b) Lisäys on hidas: on selvitettävä, että samalla avaimella varustettua
tietuetta ei ole jo tiedostossa eli luettava kaikki jaksot läpi.

c) Poisto on hidas: poistettava tietue voi olla missä jaksossa tahansa
(tai ei missään). Pahimmassa tapauksessa tämä selviää vasta viimeisen
jakson lukemisen yhteydessä. (Jos poistetaan muuhun kuin avainarvoon
perustuen, poistettavia voi olla useita ja joudutaan aina lukemaan
kaikki jaksot läpi.)

Järjestetty peräkkäistiedosto:

a) Lisäys on hidas (ainakin suhteessa kasa-lisäykseen). On etsittävä
tietueen paikka ja siirrettävä lisäyskohdan jälkeisiä tietueita
eteenpäin (paitsi jos järjestys on toteutettu ketjuttamalla eikä pidetä
jaksoja täynnä). Binäärihaulla tietueen paikka löytyy log N levyhaulla,
lisäksi kirjoitus ja siirtojen levyoperaatiot.

b) Operaatio on käytännössä sama kuin a-kohdassa.

c) Poistettavan tietueen paikka haetaan binäärihaulla kuten a:ssa. Jos
käytetään poistomerkintää, ei tietueiden siirtoja tarvita eli riittää
log2(N) + 1 levyhakua (yksi kirjoitus).

Hajautettu tiedosto: 

a) Lisäys on nopea: Lasketaan hajauttimella kotisolun osoite ja lisätään
tietue siitä alkavaan kasaan kuten a:ssa. Operaatioita 2 tai 3 (vrt. a),
mikäli kotisolu on keskusmuistissa.

b) Lisäys on nopea, paitsi jos hajautus on huono eli kotisolusta alkava
ketju on pitkä. Tässä tapauksessa on käytävä koko ketju läpi.

c) Poisto on nopea samalla ehdolla kuin b:ssä.

Arvostelu (Janne Rinta-Mänty): lähtökohtana 9 x 1 p; pisteitä
vähennettiin kohdittain, jos vastaus osoittaa, ettei ao.  kohtaa ole
ymmärretty oikein.  Samoin on tarkistettu, että vaaditut 3 täsmällistä
levyhakujen määrää sisältyvät vastaukseeen (vähennys 1 p / puute). 

Binäärihaun ohella on tietysti hyväksytty läpilukemiseen perustuvat
ratkaisut, kunhan perustelut ovat selkeät. 


2. a) jakso 303: (70, Mercedes, 2000, punainen)
		 (50, Fiat,     1996, vihreä)
		 (30, Volvo,    1996, vihreä)

      Kun jaksossa on kolme tietuetta, voidaan ajatella, että tietue on 
      kiinteänmittainen eli myös kentille on varattu kiinteät tilat
      kuten esimerkissä. (Huom. Tehtäväpaperin virhe 'tietueessa kolme
      tietuetta' -> 'jaksossa 3 tietuetta' on varmaan ymmärretty yhteydestä
      oikein.

b) Lisäyksillä muodostuu B+-puu, jossa on juuri ja neljä lehtisolmua.
Kyselyssä tarvitaan vain juuri ja se jakso, jossa reknro:lla 50
varustettu tietue sijaitsee:

      juuri jaksossa 403: (401, 40, 404, 60, 402, 90, 405, xx, xx)

      lehtisolmu 404: (303, 50, 301, 60, xx, xx, xx, xx, 405)

	xx = tyhjää; lehtisolmun 405 osoittaa viereiseen lehtisolmuun
	lehtisolmussa voisi olla myös tietueosoitteita: (303,2) jne

c) Lisäyksiä voidaan tehdä 0-5 kappaletta riippuen lisättävän tietueen
avainarvosta X: jos X < 40, joudutaan ensimmäinen lehtisolmu heti
jakamaan; jos lisätään esimerkiksi avaimet 55, 65, 95, 120, 130, kaikki
mahtuvat vajaisiin lehtisolmuihin ja vasta seuraava lisäys tuottaa
jaon.

d) Vuosimalli ei ole yksikäsitteinen, joten tarvitaan jokin luennoilla
(s. 2/10-11) mainituista ratkaisuista. Jos halutaan säilyttää
lehtisolmujen rakenne, tehdään välitaso siten, että lehtitasolta
osoitetaan välitason jaksoon, josta vasta osoitetaan perusjaksoon.

Esim. lehtisolmu (701, 1992, 705, 1996, ....)

      jakso 705: ((303,2), (303,3), (301,3), ...)  (vuoden 1996 autoja ...)
	(myös jakso-osoite riittää)   

Arvostelu (Jouni Siren): kohdittain 3+5+3+3 pistettä seuraavasti:

a)  Oikeat avaimet
    Oikea järjestys & jakso
    Oheisroina ylläoleville

b)  Oikeat hakemistosolmut
    Oikeat tiedot juuressa
    Juuri esitetty oikein
    Lehtisolmu kunnossa
    Osoitin seuraavaan lehteen

c)  Oikea yläraja
    Ylärajan perustelu
    Alaraja

d)  Duplikaatit
    Toimiva ratkaisu
    Perusteluita ja tarkennuksia


Kommentteja

Kohdassa a pyydettiin esittämään yksityiskohtaisesti jakson sisältö. Tässä ei
siis riittänyt kertoa, mitä avainarvoja jaksosta löytyi, vaikka mainitsisikin
että myös muut attribuutit ovat tiedostossa. Sen sijaan ratkaisu tyyliin
  70 | ...
  50 | Fiat | 1996 | vihreä
  30 | ...
kelpasi. Myös jakson rakenne esitettiin monissa vastauksissa, mutta se oli
ylimääräistä.

Kohdissa b ja c annetaan puolet pisteistä normaalisti pyöristäen, jos
vastaukset ovat oikeita vastaajan konstruoimassa puussa, mutta puun
konstruoinnissa on sattunut jokin virhe. Puun täytyy löytyä tehtäväpaperilta
ja sen täytyy olla oikeellinen. Lähes oikeellisella puulla saa kolmanneksen
pisteistä. Jos solmujen koko poikkesi tehtävänannosta, mutta kysymyksessä oli
hakupuu, jonka solmut olivat vähintään 50% täynnä, puu kelpasi lähes
oikeellisesta. B-puita ei kuitenkaan hyväksytty. Jakoa ei kuitenkaan tehty
silloin, kun pisteitä tuli vain kohdista, jotka eivät liittyneet puun
virheellisiin kohtiin.

Kohdassa b jotkut olettivat, että yhteen jaksoon mahtuu useampi
hakemistosolmu. Tästä ei viety pisteitä, jos vastaus oli muuten ok, sillä
sama oletus johti c-kohdassa nollalinjaan. Monet olivat unohtaneet, että
B+-puun lehdet muodostavat yksisuuntaisesti linkitetyn listan, mistä
verotettiin piste.

Kohdassa c tehtiin usein oletus, että rekisterinumeroiden tulee olla aina
kymmenellä jaollisia. Tämä oletus hyväksyttiin, jos se mainittiin
eksplisiittisesti. Alarajaa 0 ei tarvinnut mainita erikseen, jos mainitsi
esittämänsä ylärajan olevan yläraja ja teki muuten selväksi, etteivät
lisättävät alkiot saaneet olla mitä tahansa. Ylärajasta ei saanut pisteitä,
jos perustelu oli virheellinen.

Kohdassa d sai kolmannen pisteen, jos lähti tarkastelemaan asiaa lähemmin
kuin vain kertoi, että voidaan käyttää ylivuotolistaa tai muuttaa B+-puuta
niin, että samoja avainarvoja voi olla useita.


3. a) Kun ei ole hakemistoja, joudutaan joka tapauksessa lukemaan kaikki
jaksot läpi eli levyhakujen osalta kyselyjen tehokkuudessa ei ole eroa.
Pieni ero tulee puskurisa olevan tiedon käsittelyssä: Q2:n ehto on
hiukan yksinkertaisempi eli nopeammin testattavissa.

b) Q1 voidaan toteuttaa valitsemalla merkkihakemistoa käyttäen
Audi-tietueet ja tutkimalla vain niistä vuosimallit. Jos siis
Audi-tietueita ei ole jokaisessa jaksossa, kaikkia jaksoja ei tarvitse
lukea ollenkaan.

Q2-toteutus vaatii kaikkien jaksojen lukemisen, koska vuosimallia ei
saada muuten selvitetyksi. Merkki-hakemiston käytöstä ei ole hyötyä,
vaan haittaa (jos taulu on iso, hakemistossa voi olla useita
tasoja eli tulee ylimääräisiä levyhakuja). 

Arvostelu (Jaana Heino):

a) Yhteensä 4 pistettä. 2 pistettä ideasta "molemmat käytännössä yhtä
tehokkaita" + 2 pistettä perustelusta (kaikki jaksot joudutaan kuitenkin
lukemaan läpi). 0-2 pistettä vastauksesta, jossa ainoastaan spekuloitu
valintaehtojen välisellä nopeudella eikä tajuttu, ettei sillä ole
juurikaan merkitystä.

b) Yhteensä 5 pistettä. 2 pistettä vastauksesta Q1 nopeampi.
Perusteluissa 1 piste Q1:n toteutuksen selostuksesta (haetaan hakemiston
avulla ja valitaan), 2 pistettä Q2:n toteutuksesta (ei kannata käyttää
hakemistoa). Viimeistä kahta ei ole saanut, jos on yrittänyt käyttää
Q2:ssa hakemistoa, josta ei ole hyötyä.

Tehtävässä esiintyi kahta tyypillistä ajatusvirhettä.

Ensinnäkin monet eivät tajunneet, että perustiedostosta voi testata yhtä
riviä kohden kaikki ehdot samalla läpiluvulla ja väittivät, että esim.
a)-kohdassa kaikki jaksot pitää lukea *useita* kertoja. Tässä kannattaa
ajatella itseään lukemassa läpi rivejä luettelossa: jos pitää etsiä
vuosimallin 1995 Audit, ei kannata ensin käydä luetteloa läpi merkiten
Audit ja sitten lukea sitä uudestaan merkiten niistä 1995 mallit, vaan
tarkistaa molemmat ehdot samantien ko. rivin kohdalla.

Toiseksi tuntui esiintyvän harhaluuloa, että jos hakemisto on olemassa,
sitä pitää tai kannattaa aina käyttää. Kannattaa huomata, että jos
esimerkiksi b)-kohdan Q2:ssa käy läpi ensin hakemiston avulla oikeat
merkit ja sitten läpikäynnillä tietyt vuosimallit, tulee levyhakuja
*enemmän* kuin jos kävisi vain kerran kaikki läpi. Siksi hakemistoa ei
kannata ko.  kohdassa käyttää lainkaan, jos ja kun vuosimallihakemistoa ei
ole.

Lisäksi esiintyi yhtä aivan kummallista ajatusta: että SQL-kyselyn
tarkoitus olisi löytää *joku* ko.  ehtoihin täsmäävä rivi ja kysely
voidaan lopettaa kun on löytynyt yksikin.  Näille vastaajille
suosittelen Tietokantojen perusteiden käymistä uudestaan ennen uutta
yritystä TiKaHassa.  Esitettyjen SQL-kyselyjen tehtävä on löytää
*kaikki* sellaiset rivit, joille ehdot täsmäävät. 


4. a) Tietokannan tietoja päivitetään operaatioissa 101, 103 ja 107.
Aikaisin mahdollinen levylle viennin aika on heti operaation jälkeen
(välitön päivitys), myöhäisin mahdollinen seuraava tarkistuspiste. Jos
transaktio ei sitoudu (abort), tietoja ei viedä levylle välttämättä
ollenkaan (vaan ne vain häviävät puskurista abort-toiminnon jälkeen).

Siis:   101: 101-106
	103: 103-106
	107: 107-108 (ajankohta 108 siis myöhäisin mahdollinen, jos
			levylle vienti yleensä tapahtuu)

b) WAL: ks. luennot, s. 5/22. Lokin tiedot viedään levylle aina ennen
dataa, koska muuten (lokin mahdollisesti tuhoutuessa) elvytys ei olisi
mahdollinen. 

Arvostelu (Jaana Heino):

a) Kustakin oikein "arvatusta" numerosta 1/2 pistettä ja ko. numeron
perustelusta 1/2 pistettä. (Perustelut tyyliin "ks. edellinen kohta"
tietenkin hyväksytty.) Puolikkaiksi jääneet pisteet pyöristetty joko ylös
tai alaspäin perustelujen yleisen tason mukaan.

b) 3 pistettä oikeasta vastauksesta. 2 pistettä, jos oikea vastaus, mutta
sen lisäksi selitetty jotain aivan älytöntä. 0 pistettä, mikäli vastattu
väärin tai selostettu ainoastaan jotain sinänsä oikeata, mutta asiaan
kuulumatonta.

Tehtävässä oli kaksi yleistä virhettä.

Ensimmäinen oli se, että ei tajuttu mitä "operaation tuloksella"
tarkoitetaan. Operaatioilla, jotka eivät kirjoita, ei tietenkään ole
mitään tulosta, joka pitäisi kirjoittaa levylle. Jokunen vaikutti ihan
rehellisesti erehtyneen kysymyksestä ja selitti *lokin* kirjoittamista
levylle.

Jokunen epävarma selitti varmuuden vuoksi sekä lokin että varsinaisen
datan kirjoittamista. Joillekin kuitenkin näytti ero olevan vielä epäselvä
ja puhuttiin "operaation tuloksen kirjoittamisesta tietokantaan" kun
selvästi tarkoitettiin lokin kirjoittamista levylle. Pääsääntöisesti en
ole lukenut muita kuin operaatioita 101, 103 ja 107 koskevat selitykset,
muita ainoastaan silloin kun näistä on viitattu write-operaatioita
koskeviin juttuihin.

Toinen yleinen harhaluulo koski commitin yhteydessä tapahtuvia asioita.
Sekä luuloa, että mitään transaktiota koskevaa ei koskaan kirjoiteta ennen
commitia että luuloa, että commit aina pakottaa tiedot levylle, esiintyi.


5. a) 1 T1:     read-lock(X);
      2		read-item(X);
      3		unlock(X);
      4 	T2:     read-lock(X);
      5			read-item(X);
      6			unlock(X);
      7 T1:     write-lock(X);
      8		write-item(X);
      9		unlock(X);
     10   	T2:     write-lock(X);
     11			write-item(X);
     12			unlock(X);
     13   	T2:     commit;
     14 T1:     commit;

Eristyneisyysongelmat (-anomaliat):
   - rivin 5 read-item(X) on toistokelvoton, koska rivin 8
	write-item(X) kirjoittaa saman tietoalkion ennen T2:n
	sitoutumista
   - rivin 11 write-item(X) kirjoittaa likaista eli rivin 8 kirjoittaman
	tuloksen päälle

b) Ankara kaksivaiheinen lukitus vaatii transaktioita pitämään lukkonsa
sitoutumiseen asti. Tässä T1 ja T2 saavat kumpikin lukulukon, mutta
kumpikaan ei saa kirjoituslukkoa eli transaktioiden välille syntyy
lukkiuma. (Ajoituksesta siis poistetaan esitetyt unlock-operaatiot ja
lisätään unlock-operaatiot kummankin commmit-lauseen jälkeen. Näitä ei
kuitenkaan päästä koskaan toteuttamaan.)

Arvostelu (Mika Karlstedt):

a) 6 p (lukitusoperaatiot 2 p, anomaliat 2 + 2 p

b) 3 p