DONE:1, 4, 5c, 6c
TODO:1c, 2, 3, 5a, 5b, 6a, 6b
***********************************
Oppgave 1 Relasjonsdatabaser (55%)
-----------------------------------
I Uqbar, Ruritania, foregår søkningen til videregående skoler ved at hver elev
oppgir inntil fem skoler og inntil fem linjer som de ønsker seg til (egentlig i
prioritert rekkefølge, men det skal vi ikke bry oss om her). Elevene søker
altså ikke konkrete linjer på de ulike skolene, blant annet fordi det på
søknadstidspunktet ikke nødvendigvis er klart hvilke skoler som kommer til
å tilby de ulike linjene.
Alle søknadene lagres i en relasjonsdatabase som blant annet inneholder
relasjonene
Skolesøknad(søknadsNr, skole)
Linjesøknad(søknadsNr, linje)
Søknad(fødselsNr, søknadsNr)
Elev(fødselsNr, navn, karaktersnitt)
Skolesøknad har primærnøkkel (søknadsNr, skole).
Linjesøknad har primærnøkkel (søknadsNr, linje).
Søknad har primærnøkkel fødselsNr. Dessuten er søknadsNr kandidatnøkkel
i Søknad.
Elev har primærnøkkel fødselsNr.
En oversikt over hvilke skoler som tilbyr hvilke linjer, vil etterhvert lagres i
følgende relasjon:
Tilbud(skole, linje, antallPlasser)
Her er (skole, linje) primærnøkkel.
(Fortsettes på side 2.)
Eksamen i INF3100, 8. juni 2009 Side 2
------------------------
1a FDer og MVDer (20%)
------------------------
Et alternativt design for søknadene er
Elev(fødselsNr, søknadsNr, navn, karaktersnitt)
Søknad(søknadsNr, skole, linje)
-----------------------------------------------------------------------
(i) Hvis disse relasjonene skal ha samme instanser som de opprinnelige,
hvilke FDer og MVDer må da gjelde?
------------------------------------
Vi får Fd'en:
fødselsNr->søknadsNr,navn,karaktersnitt
og mvd'en:
søknadsNr->>skole
søknadsNr->>linje
---------------------------------------------------------------
(ii) Hvilken normalform er relasjonen Elev på? Begrunn svaret.
---------------------------------------------------------------
Elev(fødselsNr, søknadsNr, navn, karaktersnitt)
Normalform: 1NF fordi vi har en relasjon alle relasjoner er 1NF fra starten av.
2NF fordi vi har en supernøkkel i fødselsnr siden vi da har X->Y så er X en supernøkkel i Elev
dermed havner vi helt på BNCF.
------------------------------------------------------------------
(iii) Hvilken normalform er relasjonen Søknad på? Begrunn svaret.
------------------------------------------------------------------
Søknad(søknadsNr, skole, linje)
Normalform: 1NF fordi vi har en relasjon og alle relasjoner er automatisk 1NF fra starten av.
2NF fordi vi har en supernøkkel i søknadsNr.
Nå siden vi har mvd'er som ser ut som dette her X-->Y og når X da er en
supernøkkel så havner vi på 4NF.
-------------
1b SQL (25%)
-------------
Ta utgangspunkt i de opprinnelige relasjonene fra innledningsteksten.
---------------------------------------------------------------------------
(i) Bruk SQL til å lage en liste over hvor populære de ulike (skole,linje)-
kombinasjonene er, basert på antall søknader. De med størst søkning
skal komme først.
---------------------
svar:
select distinct ss.skole,ls.linje, (select count(*) from Skolesøknad ss2,Linjesøknad ls2,Søknad s
where ss.søknadsNr =ls.søknadsNr and ss.søknadsNr=s.søknadsNr) from Skolesøknad ss,Linjesøkna ls
where ss.søknadsNr=ls.søknadsNr;
søknads tabellen er antageligvis irrelevant tror jeg.. fix ?
----------------------------------------------------------------------
(ii) Bruk SQL til å finne (skole,linje)-kombinasjoner som tilbys, men
som ikke er søkt av en eneste elev.
-------------------------------------
svar:
create view linjer(select(*) tb.linje from Tilbud tb);
create view søkt(select(*) lo.linje from Linjesøknad lo);
select li.linje from linjer li
MINUS
select so.linje from søkt.so;
------------------------------------------------------------------------
(iii) Bruk SQL til å finne fødselsnummer og navn på de elevene som bare
har søkt linjer som ikke tilbys på noen av skolene de har søkt (og som
derfor ikke kan tilbys plass på noen av sine skolealternativer).
-------------------------
svar:
create view info(select e.fødselsNr,sø.søknadsNr,e.navn from Søknad sø,Elev e
where e.fødselsNr=sø.fødselsNr);
select i.navn,i.fødselsNr from info i,Tilbud t,Linjesøknad li,Skolesøknad sø where
i.søknadsNr=li.søknadsNr and li.linje!=t.linje and sø.skole=t.skole and sø.søknadsNr=i.søknadsNr;
-------------------------
1c Relasjonsalgebra (10%)
-------------------------
Besvar oppgave 1b punkt (i) med relasjonsalgebra.
**************************************************
******************************
Oppgave 2 Dekomposisjon (15%)
(i) Hva er en tapsfri dekomposisjon?
La R være en relasjon med de åtte attributtene A, B, C, D, E, F, G og H.
La mengden av FDer som gjelder, være
F = {AC!H,BE!F,DH!FG, EF!D, FG!AE}
og sett dekomposisjonen til D = {ABCE,ACFGH,BCDFG,BDEG}.
(ii) Gi et begrunnet svar på om D er en tapsfri dekomposisjon av R med
hensyn på F.
(Fortsettes på side 3.)
Eksamen i INF3100, 8. juni 2009 Side 3
Oppgave 3 Transaksjonshåndtering (30%)
Gitt tre transaksjoner T1, T2 og T3 samt en eksekveringsplan S:
S: r1(a); r1(b); r2(c);w1(b); r2(b); r3(d);w2(c); r1(c);
w1(c); r3(c);w2(b);w3(c);w1(a);w3(d)
3a Serialiserbarhet og låser (15%)
(i) Avgjør om S er konfliktserialiserbar. Begrunn svaret ditt.
(ii) Vi skal så benytte eksklusive låser i transaksjonshåndteringen. La li(x)
betegne at Ti tar en lås på elementet x og ui(x) at Ti frigir låsen på x.
Sett inn låser i transaksjonene i henhold til tofaselås-protokollen (2PL)
og beskriv hva som skjer hvis lese- og skriveoperasjonene så langt som
mulig utføres i rekkefølgen angitt i S.
3b Distribuerte transaksjoner (15%)
(i) Beskriv prinsippene bak protokollen tofasecommit (2PC).
Anta at vi har et distribuert system med tre noder K, M og N, hvor M har
en kopi (replikat) av elementet a og N en kopi av hvert av elementene b, c
og d. K har ingen kopier. K initierer transaksjonen T1 og N transaksjonene
T2 og T3. Transaksjonene T2 og T3 kan kjøres lokalt på node N. Transaksjon
T1 må imidlertid utføres distribuert på de tre nodene.
(ii) Anta at node K gjennomfører 2PC-protokollen på vegne av transaksjon
T1 og at node M fullfører sin deltransaksjon av T1, mens node N må
abortere sin del av T1 fordi den kommer i konflikt med T2 og T3. Beskriv
hvordan den resulterende meldingsutvekslingen mellom K, M og N
forløper.
(iii) Anta at nettverket mellom nodene K og M går ned under fase 2 i 2PCprotokollen
slik at M aldri får noen fase 2-melding fra koordinatoren
K. Senere kommer nettverket opp igjen. Hvordan kan M få avsluttet
sin del av protokollen?
***************************************
Oppgave 4 Moderne RAID-teknologi (10%)
---------------------------------------
Stadig billigere disker gjør det mulig med nye metoder for å redusere risikoen
for at diskkrasj medfører at hele systemet går ned. En slik metode er å
kombinere RAID 5 med RAID 1, dvs. at vi organiserer en gruppe disker som
RAID 5 (paritetsblokker fordelt på alle diskene i gruppen), og så speiler vi
hele gruppen. Denne metoden kalles RAID 51.
Hva er det minste antall disker som må krasje samtidig for at systemet skal
gå ned når vi bruker RAID 51? Begrunn svaret.
---------------------------------------------
For at systemet skal kræsje når vi bruker RAID51, så må 5/6 disker gå ned.
Dette er fordi at når du setter opp RAID 5, så vil du kunne bygge opp enhver
datablokk med de andre datablokkene. Når du da i tillegg bestemmer deg for å
speile alt sammen, så vil du til enhver tid ha nok å bygge på, med mindre da
alt går ned.
****************************************
*************************
Oppgave 5 Implementasjon
Ta utgangspunkt i relasjonsdatabasen i oppgave 1. Betrakt følgende SQLspørring
som finner navn og fødselsnummer til alle som har søkt om opptak
til Uqbar katedralskole og dessuten opptak på musikk, dans og drama:
select Elev.navn, Elev.fødselsNr
from Elev, Søknad, Skolesøknad, Linjesøknad
where Elev.fødselsNr = Søknad.fødselsNr and
Søknad.søknadsNr = Skolesøknad.søknadsNr and
Søknad.søknadsNr = Linjesøknad.søknadsNr and
Skolesøknad.skole = ’Uqbar katedralskole’ and
Linjesøknad.linje = ’musikk, dans og drama’;
-------------
5a Parsering
---------------------------------------------------------------------------------
(i) Bruk den enkle grammatikken under til å lage et parseringstre for spørringen
ovenfor.
---------
---------------------------------------------------------------------------
Elementære syntaktiske kategorier som <attribute>, <relation> og <pattern>
oversettes med henholdsvis navnet på attributtet, navnet på relasjonen
og en streng i enkle anførselstegn.
<query> ::= <SFW>
<SFW> ::= SELECT <selList> FROM <fromList> WHERE <condition>
<selList> ::= <attribute>
<selList> ::= <attribute>, <selList>
<fromList> ::= <relation>
<fromList> ::= <relation, <fromList>
<condition> ::= <condition> AND <condition>
<condition> ::= <attribute> = <attribute>
<condition> ::= <attribute> = <pattern>
<condition> ::= <attribute> LIKE <pattern>
---------------------
5b Logisk spørreplan
---------------------------------------------------------------------------------------
(i) Konverter parseringstreet i oppgave 5a til en logisk spørreplan i relasjonsalgebra
(tegn uttrykkstreet).
---------------------
--------------------------------------------------------------------------
(ii) Optimer den logiske spørreplanen i punkt (i) hvis den ikke alt er på
optimal form (tegn det nye uttrykkstreet).
--------------
5c Datalagring
-----------------------------------------------------------------------------
Anta at vi har en disk med følgende spesifikasjoner for lagring av våre data:
Diskplater: 10 (med 2 overflater hver)
Spor: 10.000 pr. overflate
Antall sektorer pr. spor: 1000 (en ikke-sonet disk)
Byte pr. sektor: 512
Byte pr. “gap”: 64
Gjennomsnittlig søketid: 5 ms
Spor-spor søk: 0,5 ms
Rotasjonshastighet: 15.000 RPM
Databasen inneholder følgende antall tupler:
Antall Elev-tupler: 50.000
Antall Søknad-tupler: 50.000
Antall Skolesøknad-tupler: 200.000
Antall Linjesøknad-tupler: 250.000
I tillegg gjelder følgende informasjon om diverse størrelser:
• Hver blokk har en “header” (hode) på 20 byte.
• Hver “record” (post) har et hode på 10 byte.
• Hvert attributt har følgende størrelse i antall bytes:
Elevsøknad Skolesøknad Linjesøknad
fødselsNr: 11 fødselsNr: 11 søknadsNr: 4 søknadsNr: 4
navn: 50 søknadsNr: 4 linje: 20
karaktersnitt: 4 skole: 30
-----------------------------------------
(i) Hva er diskens utnyttbare kapasitet?
-----------------------------------------
Overflate * spor * sektor * bytes
20 * 10.000 * 1.000 * 512
Dette tilsvarer 102.400.000.000 bytes.
Dette kan forkortes: -> 102.400.000kbyte -> 102.400Mbyte -> 102,4Gbyte
---------------------------------------------------------------------------------------
(ii) Hvilke faktorer inngår i å aksessere en blokk på disken, og hva er gjennomsnittlig
aksesstid for en vilkårlig 4 Kbyte blokk?
-----------------------------------------
Faktorer som spiller inn er:
- avstand til lesehodet
- tid hodet bruker på å flytte seg.
4000byte / 512byte = 8sektorer
Det er 1000 sektorer i et spor.
Vi trenger 1 spor for å dekke en 4Kbyte blokk.
Gjennomsnittlig søketid er 5ms, pluss 0,5ms per sporlesing. Derfor trenger vi:
5ms + 0,5ms = 5,5ms
Sett at hodet står på feil sted, så har vi 15.000 rpm. Det vil si at det tar
1/15.000 = 6.666e^-5 sekunder for 1 rotasjon.
Dette blir 0,066ms
Står hodet helt feil, så må vi i legge på 0,066ms. Da får vi:
5,5ms + 0,066ms = 5,566ms.
---------------------------------------------------------------------------------
(iii) Hvor stor plass trenger disse relasjonene på disken i tilfellet “unspanned”
lagring (dvs. hvis ingen enkelt post er delt over flere blokker)?
-----------------------------------------------------------------
Elevtupler: 50.000
Søknadstupler: 50.000
Skolesøknadstupler: 200.000
Linjesøknadstupler: 250.000
Bytesize på de forskjellige tuplene:
Elev: 11 + 50 + 4 = 65 bytes
Søknad: 11 + 4 = 15 bytes
Skolesøknad: 4 + 30 = 34 bytes
Linjesøknad: 4 + 20 = 24 bytes
Plass for de forskjellige tuplene
Elev: 50.000 * 65 bytes = 3.250.000 bytes
Søknad: 50.000 * 15 bytes = 750.000 bytes
Skolesøknad: 200.000 * 34 bytes = 6.800.000 bytes
Linjesøknad: 250.000 * 24 bytes = 6.000.000 bytes
Headerstørrelser:
Block: 20 bytes
Record: 10 bytes
----------------------------------------------------------------------------
(iv) Hvor lang tid tar det å lese hele relasjonen Skolesøknad uavbrutt hvis
vi antar vilkårlig plassering av data i diskblokker på disken?
--------------------------------------------------------------
---------------------------------------------------------------------
(v) Hvis pekere er på 8 byte, hvor mange blokker må aksesseres og hva
er gjennomsnittlig aksesstid totalt for å finne et tuppel (en post) i
Skolesøknad for en gitt verdi av attributtet søknadsNr hvis Skolesøknad
har tynn indeks på søknadsNr og indeksen er realisert ved et B+-tre?
--------------------------------------------------------------------
********************************************************************************
Oppgave 6 Transaksjoner
Gitt tre transaksjoner T1, T2 og T3:
T1 : r1(A); r1(B);w1(A);w1(Z);
T2 : r2(A); r2(B);w2(B);w2(Z);
T3 : r3(C);w3(C);w3(Z)
4
Betrakt følgende eksekveringsplan S av T1, T2 og T3:
S : r1(A); r1(B); r2(A);w1(A); r2(B); r3(C);w2(B);
w2(Z);w1(Z);w3(C);w3(Z)
------------------------------------------------
6a Samtidighetskontroll, pessimistisk protokoll
Anta at vi har eksklusive låser. Låsene skal brukes på vanlig måte, ved at
hver lese- og skriveaksjon skal ha en forutgående låseaksjon og en etterfølgende
opplåsningsaksjon. Dessuten skal hver transaksjon benytte tofaselåsing
(2PL).
La aksjonen li(Y ) bety at Ti tar låsen på Y og ui(Y ) at Ti frigir låsen på Y .
--------------------------------------------------------------------------------
(i) Legg inn aksjoner av formen li(Y ) og ui(Y ) i hver av T1, T2 og T3 slik
at de oppfyller reglene for bruk av låsene under 2PL, og samtidig frigir
låser så snart som mulig.
-------------------------
-------------------------------------------------------------------------------
(ii) Beskriv hva som skjer hvis vi prøver å utføre aksjonene i de resulterende
transaksjonene slik at lese/skriveaksjonene utføres mest mulig i samsvar
med rekkefølgen angitt av S.
Anta så at vi har to typer låser – en delt (S-lås, shared lock) og en eksklusiv
(X-lås), der en S-lås kan oppgraderes til (byttes ut med) en X-lås ved behov.
Låsene skal forøvrig brukes som vanlig for S/X-låser og i henhold til 2PL.
La aksjonene lsi(Y ) og lxi(Y ) bety at Ti tar henholdsvis S-låsen og X-låsen
på Y , og ui(Y ) at Ti frigir alle sine låser på Y .
-----------------------------------------------------
---------------------------------------------------------------------------------
(iii) Legg inn aksjoner av formen lsi(Y ), lxi(Y ) og ui(Y ) i hver av T1, T2 og
T3 slik at de oppfyller reglene for bruk av låsene under 2PL, og slik at
transaksjonene ikke benytter X-låser mer enn strengt nødvendig (dvs.
de benytter oppgradering der dette er mulig). Låser skal frigis så snart
som mulig.
-----------
-------------------------------------------------------------------------------
(iv) Beskriv hva som skjer hvis vi prøver å utføre aksjonene i de resulterende
transaksjonene slik at lese/skriveaksjonene utføres mest mulig i samsvar
med rekkefølgen angitt av S.
-----------------------------
-----------------------------------------------
6b Samtidighetskontroll, optimistisk protokoll
Vi skal så se på hva som skjer hvis vi bruker en tidsstemplingsprotokoll. Anta
at T1, T2 og T3 får tidsstemplene t1, t2 og t3 hvor t1 < t2 < t3.
------------------------------------------------------------------
(i) Beskriv hva som skjer med T1, T2 og T3 hvis vi prøver å utføre aksjonene
i rekkefølgen angitt av S.
Anta så at T2 aborterer (må rulles tilbake) etter at alle aksjonene dens er
utført.
-------
------------------------------------------------------------------------------
(ii) Beskriv hva som skjer med T1, T2 og T3 hvis vi prøver å utføre aksjonene
i rekkefølgen angitt av S.
---------------------------
-----------
6c Logging
Det semantiske innholdet av transaksjonen T1 består av følgende operasjoner
der x og y er lokale arbeidsvariable for T1 og derfor ikke skal logges:
T1 : x := A; y := B;A := x - 5; Z := 200;
--------------------------------------------------------------------------
(i) Beskriv postene i undo-loggen for transaksjonen T1 når vi initielt har
verdiene A = 10, B = 4 og Z = 100.
-----------------------------------
<T1,start>
<T1,A,10>
<T1,Z,100>
-----------------------------------------------------------------
(ii) Når skal de forskjellige typene loggposter skrives til disk?
-----------------------------------------------------------------
I undo logging skrives loggen først i primærminnet før man skriver opperasjonene på disken.
For hver write må man ha en linje i loggen som har den gamle verdien, altså før operasjonen.
Før man endrer noe må alle logglinjer som gjelder den aktuelle operasjonen være skrevet til disk.
Før commit i logg må alle write opperasjoner være overført til disken, å skrive commit i logge blir dermed det siste
som skjer i en transaksjon.
******************************************************************
Comments