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).