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