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