DONE: 1, 4, 5c, 6a, 6c TODO: 2, 3, 5a, 5b, 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. se .pdf ************************************************** ****************************** 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å 4/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, eller de samme to på hver side. **************************************** ************************* 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 , og oversettes med henholdsvis navnet på attributtet, navnet på relasjonen og en streng i enkle anførselstegn. ::= ::= SELECT FROM WHERE ::= ::= , ::= ::= ::= AND ::= = ::= = ::= LIKE --------------------- 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 Totalt antall entries: 50.000 + 50.000 + 200.000 + 250.000 = 550.000 Størrelse på headerne til entriesene: 550.000 * 10 bytes = 5.500.000 bytes Totalplass: 1 blokk + 550.000 entries + Størrelse på alle entries 10 bytes + 5.500.000 bytes + (3.250.000 + 750.000 + 6.800.000 + 6.000.000) bytes 10 + 5.500.000 + 16.800.000 = 22.300.010 bytes. 22.300.010 bytes -> 22.300,01kbyte -> 22,3 megabyte Siden den skal være unspanned, så forstår vi det slik at det bare skal være 1 blokk. ---------------------------------------------------------------------------- (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. ------------------------- T1: l1(A);r1(A);l1(B);r1(B);w1(A);l1(Z);u1(A);u1(B);w1(Z);u1(Z); T2: l2(A);r2(A);l2(B);r2(B);w2(B);l2(Z);u2(A);u2(B);w2(Z);u2(Z); T3: l3(C);r3(C);w3(C);l3(Z);u3(C);w3(Z);u3(Z); ------------------------------------------------------------------------------- (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 . ----------------------------------------------------- T2 må vente på T1 mens T3 kan låse lese og skrive til C men når den kommer til Z variablen må T3 vente på at T1 og T2 blir ferdige med Z og unlocker variablen. Eksekveringsplanen blir seende ut som spesifisert i oppgaven : S:r1(A);r1(B);r2(A);w1(A);r2(B);r3(C);w2(B); w2(Z);w1(Z);w3(C);w3(Z) Og ut fra dette ser vi at C variablen og Z variablen blir tatt hånd om helt til slutt, altså T3-transaksjonen --------------------------------------------------------------------------------- (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. ----------- T1| ls1(A);r1(A);ls1(B);r1(B);lx1(A);w1(A);lx1(Z);u1(A);u1(B);w1(Z);u1(Z); T2| ls2(A);r2(A);ls2(B);r2(B);lx2(B);w2(B);lx2(Z);u2(A);u2(B);w2(Z);u2(Z); T3| ls3(C);r3(C);lx3(C);w3(C);lx3(Z);u3(C);w3(Z);u3(Z); ------------------------------------------------------------------------------- (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. ----------------------------- Om man prøver å utføre aksjonene i s på dette vil vi havne i en deadlock hvor T1 venter på at T2 unlocker og T2 venter på at T1 unlocker, sånn at vi kan gå videre. ls1(A),r1(A),ls1(B),r1(B),ls2(A),r2(A),write her kan ikke brukes siden vi har en sharedlock på A, står å venter. w2(B) vil nå også bli sittende å vente, så w2 venter på at B blir unlocked og w1 venter på at A blir unlocked. ----------------------------------------------- 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. ----------------------------------- ----------------------------------------------------------------- (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. Loggen må alltid skrives før commit. Da kan vi rulle tilbake aksjoner som evt. går galt. ******************************************************************