Tietokannan hallinta, loppukoe 12.6.2001 1. Olkoon relaatio jatko-opiskelija(onumero, pääaine), joka on toteutettu kasarakenteisena perustiedostona. Tiedostoon on viety järjestyksessä seuraavat tietueet (onumero = kokonaisluku, pääaineet tässä A, B, C, ...): (20, A), (40, B), (60, C), (80, D), (100, E), (90, A), (70, F), (50, G), (30, A), (10, A), (110, E), (130, B), (150, C). Jaksossa on kolme tietuetta. a) Tiedostolle tehdään ensin ISAM-rakenteinen perushakemisto. Esitä hakemiston rakenne yksityiskohtaisesti, kun hakemistojaksoon mahtuu kolme tietuetta. b) Tiedostolle tehdään sitten ISAM-rakenteinen oheishakemisto pääaineen mukaan. Esitä hakemiston rakenne yksityiskohtaisesti. Hakemistojaksoihin mahtuu tässäkin kolme tietuetta. c) Relaatioon lisätään monikot (120, E) ja (140, E). Montako levyoperaatiota tarvitaan lisäyksissä? Perustele lukumäärät. 15 p a) Perushakemistossa perustiedoston tulee olla avainjärjestyksessä. Kasassa olevat 13 tietuetta järjestetään ensin onumero-järjestykseen ja sitten perustetaan hakemisto tasoittain. Kun tehtävässä mainittiin, että jaksossa on kolme tietuetta, tässä ei ole jätetty perusjaksoihin yhtään kasvuvaraa. (Edellä olevan kanssa samanarvoisena hyväksyttiin ratkaisu, jossa perustiedostoa ei järjestetty, vaan sen 'päälle' luotiin tiheä ISAM-rakenne eli järjestys toteutettiin alimmalla hakemistotasolla.) - ylimän tason hakemistotietueessa on avaimet 0 (pienin mahdollinen) ja 100 sekä viitteet seuraavalle tasolle jaksoihin: ph1: ((0,p1), (40,p2), (70,p3)) ja ph2: ((100,p4), (150,p5), ) - perustiedostossa jaksot p1, ... , p5: ((10,A), (20,A), (30,A)) ((40,B), (50,G), (60,C)) ((70,F), (80,D), (90,A)) ((100,E), (110,E), (130,B)) ((150,C), ) b) Oheishakemistossa on alimmalla tasolla viitteet perustiedoston tietueisiin (myös jakso-osoitteet riittävät, mutta aiheuttavat hieman selaamista). Kun samalla oheishakemiston hakemistoavaimella varustettuja tietueita voi olla enemmän kuin jaksollinen (tässä alkutilanteessa A), voidaan esim. linkittää alimman tason jaksot peräkkäin. Silloin ei tarvita hakemistossa useita alkioita samalle hakemistoavaimelle. Oheishakemiston rakenne: - ylin taso: ((A,b1), (B,b2), (C,b3)) - seuraavalla tasolla jaksot b1, b2 ja b3: ((A,1), (B,2), (C,3)) ((D,3), (E,4), (F,4)) ((G,5), ) (1,2,3,4,5 alimman tason jaksojen osoitteita) - alin hakemistotaso: 1: ((A,(1,1)), (A,(1,2)), (A,(1,3)) + linkki -> 2 2: ((A,(3,3)), (B,(2,1)), (B,(4,3)) 3: ((C,(2,3)), (C,(5,1)), (D,(3,2)) 4: ((E,(4,1)), (E,(4,2)), (F,(3,1)) 5: ((G,(2,2)), ) (1,2) = linkki perusjakosn 1 tietueeseen 2 jne) c) Oletetaan, että kummankin hakemiston ylin taso on keskusmuistissa. Tällöin lisättäessä (120,E) levyoperaatiot: lue ph2 lue p4 kirjoita uusi (ylivuoto)jakso Y kirjoita p4 (linkki ylivuotojaksoon Y) lue b2 lue 4 kirjoita uusi (ylivuoto)jakso Z kirjoita 4 (linkki jaksoon Z) Lisättäessä (140,E) tarvitaan levyoperaatiot: lue ph2 lue p4 lue Y kirjoita Y lue b2 lue 4 lue Z kirjoita Z Yhteensä siis 16 levyoperaatiota. Arvostelu: a) 6 p, b) 6 p, c) 3 p 2. Selosta hajautukseen (hashing) perustuvien menetelmien käyttö kyselyn optimoinnissa. 12 p Hajautukseen perustuvia menetelmiä voidaan käyttää - valintaoperaation toteutuksessa: kun on täsmällinen valintaehto A = v, monikot löydetään hajautusrakenteisen hakemiston avulla - liitosoperaation toteutuksessa: hajautusliitos, ks. luennot, s. 4/25 - duplikaattien poistossa projektion ja yhdisteen toteutuksessa. - koosteoperaation toteutuksessa: tarvittava ryhmä voi olla samassa kotisolussa. Arvostelu suunnilleen jaon liitos (5p), valinta (4p) ja duplikaatit (3p) mukaan. Yleisestä maininnasta hajautushakemiston merkityksestä sai 2 p. Hajautuksen määrittelystä ja yleisestä luonnehdinnasta ei saanut pisteitä. (Yllättäen tehtävään oli vastattu kaikkein vähiten ja huonoimmin.) 3. 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. 9 p Ks. luennot, ss. 5/18-19. - kummankin käsitteen määrittely, vaikutus erityisesti elvytysmenetelmiin, puskurissa olevan tiedon käyttö muiden transaktioiden kannalta Arvostelu karkeasti: elvytys 5p, muut 4p (Kovin monet selittivät vain yleisluontoisesti menetelmien tehokkuutta määrittelemättä edes niitä tai käsittelemättä elvytystä.) 4. Selitä, mitä tarkoitetaan transaktioiden eristyvyysanomalioilla, ja anna yksityiskohtainen esimerkki yhdestä sellaisesta. 12 p Ks. luennot, s. 5/34. Arvostelu: Täsmällinen esimerkki 6p, yleisselvitys samoin 6 p Pelkkä kolmen anomalian nimen mainita antoi 2 pistettä; eristyneisyystasojen käsittelyä ei vaadittu. 5. Selitä lyhyesti seuraavat käsitteet ja niiden merkitys: a) kyselylohko (QUERY BLOCK), b) valitsevuus (selectivity), c) kaksivaiheinen lukitus (two-phase locking, 2PL). 12 p a) Ks. luennot, s. 4/5 b) Ks. luennot, ss. 4/11-12. c) Ks. luennot, s. 5/49. Arvostelu: 4 p / kohta (a ja/tai b puuttuivat aika monelta).