Tietokannan hallinta - Kurssikoe 17.5.2002
Ratkaisut ja arvosteluperusteet:
Tehtäviä 1-3 koskeva yhteinen osa:
Relaatio henkilo(hetu, nimi, kotipaikka) on toteutettu järjestettynä
peräkkäistiedostona kotipaikan mukaan. Jaksonpituus on suuri, joten
yhteen jaksoon mahtuu paljon tietueita.Tietueet esitetään
vaihtuvanmittaisina ja niitä on noin 20000.
1. a) Esitä tietuetta <'121212-3456', 'Aho, Marianne', 'Helsinki'> esimerkkinä
käyttäen yksityiskohtaisesti Oraclen käyttämä tietuerakenne.
b) Onko tietueen esitysmuodolla vaikutusta tiedoston läpikäynnissä
tarvittavien levyhakujen määrään? Perustele.
c) Anna kaksi erilaista (lyhyesti perusteltua) esimerkkiä pelkästään
henkilo-relaatioon kohdistetusta kyselystä, jonka toteutuksessa
esitetty järjestys on edullinen. 10 p
Tietokannan hallinta, kevät 2002
Kurssikoe 17.5.2002
Kommentit:
a)
+---+--+-+-+--+----------+-+--+-------------+-+-+--------+
|123|38|0|1|11|12121-3456|2|13|Aho, Marianne|3|8|Helsinki|
+---+--+-+-+--+----------+-+--+-------------+-+-+--------+
A B C D E F D E F D E F
A = tietueen järjestysnumero
B = tietueen pituus(*)
C = hallintatietoa (esim. poistomerkintä)
D = kentän tunniste (järjestysnumero)
E = kentän pituus
F = kentän arvo
(*) Oletus: kentän numero ja pituus yht. 2 tavua,
11 + 13 + 8 + 3 * 2 = 38.
Tässä on hyväksytty myös (luentomateriaalin mukainen)
pelkkä kenttien yhteenlaskettu pituus, eli 32.
(Pienet laskuvirheetkin on annettu anteeksi.)
(4 pistettä)
b)
On. Jos tietue esitetään mahdollisimman tiiviisti, jaksoon mahtuu
mahdollisimman paljon tietueita. Tällöin jaksoja on yhteensä
mahdollisimman vähän, samoin levyhakuja.
Esimerkiksi jos tietueen kentissä on paljon vaihtuvanmittaista tietoa,
mutta tietue esitetään kiinteänmittaisena, jää todennäköisesti paljon
hukkatilaa. Jos taas tiedot ovat kiinteänmittaisia, mutta tietue
esitetään vaihtuvanmittaisena, menee ylimääräistä tilaa kenttien
tunnisteisiin, pituusmerkintöihin tai erotinmerkkeihin.
(2 pistettä)
c)
Esimerkiksi
select * from henkilo where kotipaikka = 'Espoo';
etu: koska tiedosto on järjestyksessä kotipaikan mukaan, haku voidaan
lopettaa keskimäärin aikaisemmin kuin järjestämättömän tiedoston
tapauksessa.
select kotipaikka, count(*)
from henkilo
group by kotipaikka;
etu: ryhmittely valmiina, laskureita ei tarvita kuin yksi kerrallaan.
(2 + 2 pistettä)
2. Henkilo-relaatiolle tehdään B+ -muotoinen hakemisto attribuuteille
(kotipaikka, nimi). Jaksonpituus on 4 KB. Hakemistoattribuuttien
yhteispituus on keskimäärin 30 merkkiä ja maksimissaan 70 merkkiä.
Kuinka monta tietuetta relaatiossa voi olla, että kyselyn
select * from henkilo
where kotipaikka = 'Helsinki' and nimi = 'Aho, Marianne'
toteutus vaatii enintään kolme levyhakua (millä tahansa kotipaikan ja nimen
yhdistelmällä)? Arvioi lukumäärä
a) tietueiden satunnaisen lisäysjärjestyksen,
b) pahimman tapauksen kannalta.
Mikään hakemiston osa ei ole puskurissa. (Lukuja voi pyöristää,
kunhan selittää asian.)
c) Voidaanko ISAM-hakemistossa taata vastaava enintään kolmen
levyhaun raja? Perustele. 10 p
Tehtävän 2 kommentit
3. Oletetaan henkilo-relaation lisäksi relaatio kunta(kunnan_nimi,
asukasmaara) ja kysely
select nimi, kotipaikka from henkilo, kunta
where kotipaikka = kunnan_nimi and asukasmaara < 2000;
Selitä kolme olennaisesti erilaista tapaa toteuttaa liitosoperaatio
tässä kyselyssä. Relaatiolle kunta mahdollisesti tarvittavat
oletukset tulee esittää vastauksessa. 10 p
Kommentit:
Kolme OLENNAISESTI ERILAISTA tapaa toteuttaa LIITOSoperaatio saadaan
valitsemalla ne luennoilla esitetyistä neljästä liitoksen
toteutuksesta.
Yleisiä oletuksia: kunta-relaatio on varmaankin paljon pienempi kuin
henkilo, kunnan_nimi lienee relaation avain.
1. Lomitusliitos.
Henkilo-relaatio on valmiiksi järjestyksessä liitosattribuutin
mukaan. Jotta voitaisiin käyttää lomitusliitosta, pitää
kunta-relaation olla järjestyksessä kunnan_nimi-attribuutin
mukaan. Jos se ei ole jo valmiiksi, järjestetään se (ensin
kannattaa tiputtaa pois kunnat, joissa on vähintään 2000 asukasta).
Käydään henkilo- ja kunta-relaatioita tahdistetusti läpi
(käsittelyssä aina vastaavat kotipaikka- ja kunnan_nimi-rivit) ja
otetaan tulokseen nimi ja kotipaikka.
2. Hakemistoliitos.
Jos kunta-relaatiolle on kunnan_nimi-hakemisto, voidaan käyttää
hakemistoliitosta. Luetaan henkilo-relaatio läpi ja haetaan joka
tietueelle kotipaikkaa vastaava kunta-rivi hakemiston avulla.
Tarkastetaan asukasmaara.
Jos henkilo-relaatiolle on kotipaikka-hakemisto, käydään
kunta-relaatio läpi, ja jokaiselle asukasmaara-ehdon täyttävälle
kunnalle haetaan asukkaat kotipaikka-hakemiston avulla.
3. Sisäkkäiset silmukat.
Koska kunta-relaatio on pienempi kuin henkilo, otetaan se ulompaan
silmukkaan. Käydään kunta-relaation askukasmaara-ehdon täyttävät
rivit läpi puskuriin mahtuvissa erissä ja jokaista erää kohti
käydään läpi koko henkilo-relaatio, tulokseen nimi ja kotipaikka
niiltä riveiltä, joilla kunnan_nimi ja kotipaikka ovat samat.
(oikeastaan henkilo-relaation läpikäynti voidaan lopettaa heti kun
kotipaikka > kunnan_nimi).
4. Hajautusliitos.
Käydään läpi kunta-relaatio, ja hajautetaan ne rivit (tai pelkkä
kunnan_nimi), joissa asukasmaara on pienempi kuin 2000
(hajautusavaimena kunnan_nimi). Käydään sitten henkilo-relaatio
läpi, ja jokaisella rivillä katsotaan, löytyykö edellä
muodostetusta hajautusrakenteesta kotipaikan kotisolusta vastaava
kunnan_nimi. Jos löytyy, otetaan tulokseen nimi ja kotipaikka.
(3 * 3 (eri tavat) + 1 (vastauksen yleinen tarkkuus) pistettä)
4. a) Mikä on aikaisin ja mikä myöhäisin ajankohta seuraavan
lokitiedoston sisältämien operaatioiden tulosten levylle
kirjoittamisessa? Ajankohta ilmoitetaan lokitiedoston rivin
järjestysnumeroon viitaten muodossa '1xx: 1yy-1zz'. Esimerkki
tarkoittaa, että rivin 1xx operaation tulos menee levylle aikaisintaan
rivin 1yy operaation yhteydessä ja viimeistään rivin 1zz operaation
yhteydessä.
100: (start, T1)
101: (write, T1, X, a, b)
102: (commit, T1)
103: (start, T2)
104: (checkpoint)
105: (write, T2, Y, u, v)
106: (start, T3)
107: (write, T3, Y, v, w)
108: (checkpoint)
109: (write, T3, X, b, c)
110: (commit, T2)
111: (abort, T3)
b) Oletetaan, että X ja Y ovat tietokannassa eri sivuilla. Mitkä
ovat näiden kahden sivun PageLSN-arvot? Selitä lyhyesti, mikä
merkitys PageLSN-arvoilla on.
10 p
Kommentit:
Oikea ratkaisu:
101: 101-104
105: 105-108
107: 107-108
109: 109-110 (tai ei ollenkaan)
Oikeasta vastauksesta sai 6p, puutteellisesta 0-5 p virheiden lukumäärästä
riippuen. Perusteluja ei vaadittu.
b)
Oikea ratkaisu:
PageLSN(X) = 101 tai 109 1p (jompi kumpi arvoista)
PageLSN(Y) = 107 1p
PageLSN-arvoa käytetään elvytyksessä. 1p
Sen avulla tiedetään lokia tutkittaessa, täytyykö write-lause perua (undo)
vai onko se suoritettava uudelleen (redo). 1p
5. a) Selitä pientä esimerkkiä käyttäen lyhytaikaisten ja
pitkäaikaisten lukkojen merkityksen ero kolmen eristyneisyysanomalian
kannalta. Oletetaan, että järjestelmässä kaikki transaktiot käyttävät
joko lyhytaikaisia tai (kaikki) pitkäaikaisia lukkoja.
b) Mitä hyviä puolia ja mitä huonoja puolia on ankaran kaksivaiheisen
lukituksen käytöllä?
10 p
Kommentit:
Oikea ratkaisu:
I Likainen kirjoitus
1 T1: write-lock(X);
2 T1: write-item(X);
3 T2: write-lock(X);
4 T2: write-item(X);
5 T1: commit;
Jos rivin 1 lukko on lyhytaikainen, T2 pääsee tekemään likaisen luvun
rivillä 4. Pitkäaikainen lukko estää T2:n etenemisen.
II Likainen luku
1 T1: write-lock(x);
2 T1: write-item (X);
3 T2: read-lock(X);
4 T2: read-item(X);
5 T1: commit;
Kuten I.
III Toistokelvoton luku
1 T1: read-lock(X);
2 T1: read-item(X);
3 T2: write-lock(X);
4 T2: write-item(X);
5 T1: commit;
Kuten I.
Kustakin esimerkistä selityksineen sai 2p eli yhteensä 6 p.
b)
Oikea ratkaisu:
+ 2PL takaa sarjallistuvuuden (estää eristyvyysanomaliat) 2 p
- rajoittaa vahvasti samanaikaisia transaktioita 1p
- voi aiheuttaa lukkiutumisen 1p