Ratkaisut ja arvostelu:

1. Tietokantataulun hakemisto voi olla harva tai tiheä.  Selitä
lyhyesti, miksi harva hakemisto vie vähemmän tilaa kuin tiheä, ja
milloin harvaa hakemistoa ei voi käyttää.  6 p

Ratkaisu: Vähemmän tilaa, koska hakemistotietueita ei ole kaikille
perustietueille, vaan esimerkiksi jokaisen jakson pienimmälle
(avaimelle). Hakemistotietue voi olla myös hieman lyhyempi, koska
voidaan käyttää jakso-osoitteita (tiheäkin tietysti toimii
jakso-osoitteilla, mutta silloin tietueosoitteet ovat luonnollisemmat).
Harvaa hakemistoa ei voi käyttää, ellei perustiedosto ole hakemiston
avaimen mukaan järjestyksessä (tai periaatteessa jokin muu tapa,
jolla yksi avain voidaan liittää joukkoon perustietueita).

Arvostelu: harvan periaate 3 p, osoittimien pituusero 1p,
järjestysvaatimus 2p (osattiin yleisesti hyvin, 5p yleisin)

2.  Tietokantataulussa on 60000 riviä.  Selitä taulun hakemistona
käytetyn B+ -puun solmurakenne ja puun tilantarve.  Hakemiston sivunkoko
olkoon 4 KB, taulun avainkentän pituus 20B ja hakemiston osoittimien
pituus 2B.  8 p

Ratkaisu: Ks. luennot, s. 3-30..31. Lehtisolmuun mahtuu maksimissaan p
avainta, missä  20p + 2p + 2 <= 4096 eli p <= 186. Jättämällä hieman tilaa
hallinnollisille tiedoille voidaan käyttää esim. astelukua p = 185,
jolloin 60000 tietueen osoitteet (ja avaimet) vaativat 60000/185 = 325
lehtisolmua. Näiden osoittaminen vaatii seuraavaksi ylemmällä tasolla 2
sisäsolmua ja näiden osoittaminen juuren. Tarvitaan siis yhteensä 325 +
2 + 1 = 328 jaksoa eli 1.3MB. Käytännössä B+ -puu asettuu
tasapainotilaan, jossa solmujen täyttöaste on 69 %. Ottamalla tämä
huomioon tarvitaan lehtisolmuja 60000/127 = 473 ja sisäsolmuja 4 + 1 eli
kaikkiaan 478 jaksoa eli noin 1.9 MB.

Arvostelu: Laskennallinen lopputulos ei ole tärkeä, kunhan periaatteet
näkyvät oikein. Solmurakenne 5 p. tilantarve 3 p. Solmurakenteen
yhteydessä pitää kertoa avainten looginen järjestys. Täyttöasteen 69%
puuttumisesta -1 p. 


3.  Oletetaan, että relaatio employee(ssn, lname, fname, salary, dno) on
toteutettu kasana ja sille on olemassa kaksi ISAM-rakenteista
hakemistoa, toinen attribuuttiparin (LNAME, FNAME) ja toinen attribuutin
SSN perusteella.  Lisäksi on hajautusrakenteinen hakemisto attribuuttiin
DNO perustuen.  (Relaatio on luennoilta, harjoituksista ja E&N-kirjasta
tuttu: siis henkilötunnus, sukunimi, etunimi, palkka, osastonumero.)
Anna 3 esimerkkiä kyselystä, joka on tehokkaasti toteutettavissa
mainituilla hakemistolla ja 3 kyselyä, joita nämä hakemistot eivät
tehosta.  Vastaukseksi annetaan loppuosat muotoa

        select * from employee where ...

olevaan kyselyyn.  Esimerkkikyselyjen tulee olla keskenään
periaatteeltaan erilaisia ja käytännön kannalta luontevia.  12 p

- tehokkaita: SSN = '100235-1234'

	      LNAME like 'Elo%'

	      LNAME < 'Kaaaaa' and DNO = 5

- tehottomia: SALARY = 2500

	      DNO < 7

	      FNAME = 'Kalle' 

Arvostelu: 2 p / esimerkki.  Vähennyksiä tuli siitä, että muutamat
antoivat kaksi loogisesti samanlaista esimerkkiä (yhtäläisyysehtoa). 
Tehottomien puolella oli vastauksissa kyselyitä, joita kuitenkin
hakemistot tehostavat ainakin osittain.  (osattiin yleisesti hyvin)


4.  Selitä pienen esimerkin avulla, mitä tarkoitetaan a) heuristisella,
b) kustannuslaskentaan perustuvalla kyselyn optimoinnilla.  12 p

Ratkaisu: Ks. luennot, luku4.

Arvostelu: a) 5 p, b) 7 p. Varsin harvat antoivat esimerkkejä (esim.
pieni kyselypuun muunnos tai jonkin liitosoperaation levyoperaation
arviointi; kustannuslaskennastahan ei juuri muita esimerkkejä ollut).
Esimerkittömästä vastauksesta sai enintään 2+2 = 4 p.

5.  Tietokannan sisällön kirjoittaminen levymuistiin voi tapahtua kahden
pääperiaatteen mukaan: välittömillä päivityksillä (immediate updates)
tai viivästetyillä päivityksillä (deferred updates).  Vertaile näiden
periaatteiden merkitystä yleisesti ja erityisesti häiriötilanteista
elvyttämisen kannalta.  10 p

Ratkaisu: Ks. luennot, s. 5-18..19 (pääasiat). 

Arvostelu: välittömien ja viivästettyjen päivitysten määrittely (idea)
3p, merkitys (päivitysten vaatima 'työmäärä', puskurissa olevan tiedon
käyttömahdollisuus) 3p, yhteys elvytykseen 4 p. (Elvytyksessä tuli
näkyä, että viivästetyt johtavat redo- ja välittömät undo-tarpeeseen.)


6.  Tietokannan eheysrajoitteen mukaan tietoalkioilla X, Y ja Z pitää
olla sama arvo.  Tarkastellaan seuraavaa transaktiojoukon T1, T2, T3
ajoitusta:

T1: read-item(X, v);
T1: v:=v+1;
T1: write-item(X, v);
T2: read-item(X, w);
T2: write-item(Y, w);
T2: commit;
T3: read-item(Y, p);
T1: abort;
T3: write-item(Z, p);
T3: commit;

a) Ovatko transaktiot oikeellisia?
b) Mikä on kunkin transaktion eristyneisyystaso?
c) Mitä lokitietueita syntyy, kun tietokannassa on aluksi X = Y = Z = 0?
d) Millä toimenpiteillä tietokannan eheys voidaan säilyttää?           
12 p


Ratkaisu (likimain harjoitustehtävä 6.1):

a) Kaikki ovat (yksinään) oikeellisia, myös T1, kun sattuu
abortoitumaan. (Muutenhan se muuttaisi X:n arvoa, mikä rikkoisi eheyttä
vastaan.) 

b) T1 ja T3 ovat sarjallistuvia (taso 3), T2 sisältää likaisen luvun
(mutta ei likaista kirjoitusta) eli taso on 1 ('lue sitoutumatonta').

c) lokitietueet:
	start, T1
	write. T1, X, 0, 1
	start, T2
	write, T2, Y, 0, 1
	commit, T2
	start, T3
	abort, T1
	write, T3, Z, 0, 1
	commit, T3

d) Olennaista on estää T2:n lukukäsky pitkäaikaisella kirjoituslukolla.
Ankara kaksivaiheinen lukitus yleisenä ratkaisuna.

Arvostelu: 3p / kohta. Kohdassa a oikeellisuuden käsite oli monelle
'tuntematon' eli sekoitettu kokonaistilanteen virheeseen jollain
tavalla. Kohdassa c yllättävän monet kertoivat vain muuttjien arvoja,
mutta eivät lokitietueita. joita kysyttiin. Kohdassa d oli ylimalkaisia
vastauksia (joista ei paljon hyvitetty).