INF3100 - Vår 2005

Andre sett obligatoriske oppgaver i INF3100/INF4100 V2005

Formalia

Studentene skal levere individuell besvarelse. Hvis to studenter �nsker � levere felles besvarelse, m� dette avtales p� forh�nd med gruppel�rer.
Besvarelsen skal sendes med e-post til den gruppen man er formelt opptatt til. (Gruppenes e-postadresser finner dere p� semestersiden til INF3100.)

E-posten til gruppen skal ha f�lgende subjektfelt:
Subject: Oblig 2 inf3100 (<brukernavn student>)

Studenter som har f�tt godkjent de obligatoriske oppgavene (eventuelt en av dem) og likevel vil trekke seg fra eksamen, er selv ansvarlig for � ta vare p� papirkopier av besvarelsene hvor gruppel�reren har kvittert for at oppgaven(e) er godkjent. Dette gjelder bare studenter som trekker seg f�r 14-dagersfristen.

Innleveringfrist: Fredag 13. mai kl. 10.00

Det er lurt � begynne tidlig.

Oppgave 1

Gitt f�lgende datastruktur for en relasjonsdatabase Prim�rn�kler er markert med fete typer, kandidatn�kler er i kursiv, fremmedn�kler fremg�r av attributtnavnene):

PERSON (Fnr, Etternavn, Fornavn, Adresse)
EKTESKAP (Fnr-k Fnr-m, Dato, Etternvn-k, Etternavn-m)
NAVNESKIFTE (Fnr, Dato, Etternavn, Fornavn)

N�v�rende navn lagres i tabellen PERSON. F�lgelig lagres det navnet en person hadde umiddelbart f�r han/hun skiftet navn, i NAVNESKIFTE. Navnene i EKTESKAP er etternavnene etter vielsen.

L�s f�lgende to oppgaver b�de med relasjonsalgebra og SQL:

Finn navn og adresse til alle kvinner som i �rene 1968-72 p� sin bryllupsdag skiftet etternavn til et navn forskjellig fra sin brudgoms etternavn.
Finn navn og adresse til alle kvinner som ved en vielse har byttet navn med sin brudgom. (Ektefeller med samme etternavn skal ikke v�re med.)

Oppgave 2

Med utgangspunkt i Oppgave 1 skal det lages en OO-datastruktur. Det er opplagt at tabellen PERSON skal erstattes av en klasse Person. Det er ogs� noks� opplagt at tabellen NAVNESKIFTE skal erstattes av en lokal liste i hvert personobjekt. (Vi kunne selvf�lgelig ha valgt en mengde eller bag i stedet for en liste, men navneskiftene for en person er jo ordnet.)

For tabellen EKTESKAP er saken ikke s� opplagt. Vi kan velge � erstatte den med en egen klasse Ekteskap eller � erstatte den med lokale data i hvert enkelt personobjekt.

Oppgave 2 a

Skriv en fullstendig ODL-definisjon for hvert av alternativene ovenfor (med hhv. to og en klasse). Ikke glem metodene, og husk at det bare er metodenes signatur som er en del av ODL!

Oppgave 2 b

Bruk OQL til � besvare begge sp�rsm�lene i Oppgave 1 mot hver av ODL-definisjonene i 2 a.

Oppgave 3

Anta at vi har et lagringssystem som bruker (modifiserte) Seagate Cheetah X15 disker Noen av spesifikasjonene er som f�lger:

Diskplater:������������������� ����8

Spor:����������������������������� 20000

Antall sektorer per spor:����� �� 700 (en ikke-sonet disk)

Bytes per sektor:����������������� 512

Bytes per "gap"/sjekksum/...:����� 64

Gjennomsnittlig s�ketid:���������� 3.6 ms

Spor-spor s�k:�������������������� 0.3 ms

Rotasjonshastighet:��������������� 15.000 RPM

Anta videre at lagringssystemet bruker 4 KB blokker, og at vi kan se bort i fra forsinkelser som � prosessere foresp�rsler, overf�ring over busser, vente p� tur, etc.

Oppgave 3 a

Hva er total kapasitet p� disken hvis platene brukes p� begge sider?

Hva er gjennomsnittlig rotasjonsforsinkelse?

Hva er gjennomsnittlig aksesstid for en vilk�rlig blokk?

P� lagringssystemet over lager vi en kundedatabase. Hver blokk har en �header� p� 12 B, og hver post (�record�) har en �header� p� 20 B. Vi har 1.000.000 kunder, hvor hver post har f�lgende felter (antall byte):

navn��� (30)

fnr���� (9)

adresse (30)

tlf���� (8)

email�� (30)

Oppgave 3 b

Hva er blokkfaktoren?

Hvor lang tid tar det � lese hele tabellen (uavbrutt) hvis vi antar �unspanned� lagring og vilk�rlig plassering av blokkene p� disken?

I steden for vilk�rlig plassering pr�ver vi med kontinuerlig plassering p� disken - vi fyller opp et spor f�rst, hvis fullt, s� tar vi neste spor i samme sylinder, hvis igjen fullt, neste sylinder. Anta at tabellen begynner i f�rste sektor i f�rste spor i en sylinder. Hvor lang tid tar det n� � lese hele tabellen (uavbrutt) hvis vi fortsatt antar �unspanned� lagring og at det � bytte lesehode ikke tar noe tid (vi kan begynne � lese direkte)?

Anta igjen at blokkene er vilk�rlig plassert p� disken, og at tiden det tar � prosessere en blokk i minnet er tiln�rmet null.

Oppgave 3 c

Hva er gjennomsnittlig tid for � aksessere en vilk�rlig post uten indekser?

Vi legger p� en tett (�dense�) indeks med bin�rt s�k. Unik s�ken�kkel er fnr, og pekeren tar 8 B. Hvor mye plass tar indeksen hvis hver blokk er 80 % full i gjennomsnitt?

Hva er gjennomsnittlig tid (forutsett et maksimalt antall oppslag i indeksen) for � aksessere en vilk�rlig post med en slik indeks?

Vi bytter s� ut indeksen v�r med et B⁺-tre. Hvor mye plass tar B⁺-treet hvis hver node bruker en egen diskblokk som er 80 % full i gjennomsnitt?

Hva er tiden det n� tar � aksessere en vilk�rlig post?

Oppgave 4

Betrakt f�lgende eksekveringsplan (schedule) der vi bruker bin�re l�ser:

	Trans T1	Trans T2	Trans T3
1	Lock(X)
2	Read(X)
3		Lock(Y)
4		Read(Y)
5	X=f(X)
6			Lock(Z)
7			Read(Z)
8		Y=g(Y)
9		Write(Y)
10		Unlock(Y)
11			Z=h(Z)
12	Write(X)
13	Unlock(X)
14			Write(Z)
15			Unlock(Z)
16			Lock(Y)
17			Read(Y)
18		Lock(X)
19		Read(X)
20	Lock(Z)
21	Read(Z)
22		X=g(X)
23			Y=h(Y)
24	Z=f(Z)
25		Write(X)
26		Unlock(X)
27			Write(Y)
28			Unlock(Y)
29	Write(Z)
30	Unlock(Z)

Oppgave 4 a

Tegn presedensgrafen (serialiserbarhetsgrafen) for denne planen, og avgj�r om planen er konfliktserialiserbar.

Oppgave 4 b

Begrunn at planen ikke tilfredsstiller 2-fasel�singsprotokollen (2PL).

Oppgave 4 c

Lag en plan for de tre transaksjonene som tilfredsstiller 2PL, tegn presedensgrafen for denne nye planen, og vis at den er konfliktserialiserbar.