Øvingseksamen 07 · TDT4145

Øvingseksamen 07

Tidsramme: 3 timer · Hjelpemidler: Ingen · Total: 100 poeng

Hovedfokus: Bredt sett som dekker arkitektur, RA-divisjon, SQL-aggregater, FD-analyse, lossless dekomponering, hashing-statistikk, sort-merge, deadlock og REDO-scan-start.

Del 1 — Theodoros (~40 %)

Konseptspørsmål, RA-utregninger, SQL-resultater, ER og normalformer.

Spørsmål 1 3 poeng Kap. 1

Hvilken databaseapplikasjons-arkitektur har en separat applikasjons- /forretningslogikk-server som mellomledd mellom klient og databaseserver?

A 2-tier arkitektur — klient og DB-server kommuniserer direkte.
B 3-tier arkitektur — klient, applikasjonsserver og databaseserver.
C Sentralisert databasemodell — alt på én maskin.
D Distribuert databasemodell — flere DB-noder uten klar lagdeling.

Vis fasit

Riktig svar: B

3-tier-arkitekturen plasserer en applikasjonsserver mellom presentasjonslaget (klienten) og databaseserveren. Hensikten er å sentralisere forretningslogikk slik at klienten kan være "tynn" og databaseserveren kun behandler datalagring og forespørsler.

A er feil — i 2-tier kommuniserer klienten direkte med databasen, og forretningslogikken ligger på klientsiden eller som lagrede prosedyrer i DB. C beskriver fysisk plassering, ikke lagdeling. D handler om hvordan dataene fordeles geografisk, ikke om forretningslogikk-laget.

Pensum: Kap. 1 — Introduksjon

Spørsmål 2 3 poeng Kap. 1

Hvilken påstand om databaseskjema og databaseinstans er sann?

A Skjemaet endres typisk hyppigere enn instansen.
B Skjema og instans endres kontinuerlig av brukerens DML-spørringer.
C Skjemaet er fast etter opprettelsen og kan aldri endres.
D Skjemaet er strukturen som endres sjelden; instansen er innholdet og endres ofte.

Vis fasit

Riktig svar: D

Skjemaet (CREATE TABLE-definisjonen, integritetskrav, etc.) endres sjelden — typisk via DDL-statement når man redesigner. Instansen (det aktuelle innholdet i tabellene) endres kontinuerlig av INSERT/UPDATE/DELETE.

A er motsatt riktig retning. B er feil — DML endrer instansen, ikke skjemaet. C er for absolutt — skjemaet kan endres med ALTER TABLE, men sjelden i praksis.

Pensum: Kap. 1 — Introduksjon

Spørsmål 3 4 poeng Kap. 2

Følgende tabeller er gitt:

course
cid	title
DB	Databases
AI	Artificial Intelligence
OS	Operating Systems

enroll
cid	sid
DB	1
DB	2
DB	3
AI	1
AI	2
OS	1

Hvor mange tupler returnerer det følgende RA-uttrykket?

σ_{cid='DB'}(course ⋈ enroll)

Vis fasit

Riktig svar: B

Først naturlig join på cid: hver enroll-rad parres med tilsvarende course-rad. Resultatet av joinen har 6 tupler (én per enroll-rad). Deretter σ_{cid='DB'}: kun de tre enroll-radene med cid=DB overlever — 3 tupler.

A (6) er hele joinen uten selection. C (1) regner kun antall course-rader med cid=DB. D (4) er nær men feil — det er 3 DB-enrollments, ikke 4.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 4 3 poeng Kap. 3

Den følgende tabellen er gitt:

employee
name	salary
Alice	50
Bob	NULL
Cathy	30
Dave	40
Eve	NULL

Hva returnerer spørringen?

SELECT COUNT(*), COUNT(salary), AVG(salary)
FROM employee;

A (5, 5, 24.0)
B (5, 3, 40.0)
C (3, 3, 40.0)
D (5, 5, 40.0)

Vis fasit

Riktig svar: B

COUNT(*) teller alle rader uavhengig av NULL → 5. COUNT(salary) teller bare rader hvor salary ikke er NULL → 3 (Alice, Cathy, Dave). AVG(salary) ignorerer NULL og regner snittet over de samme 3 verdiene: (50 + 30 + 40) / 3 = 40.0.

A bruker feil snitt (24.0 = 120/5, dvs. dividerer med antall rader inkludert NULL). C teller også COUNT(*) som 3 — feil, COUNT(*) er alltid antall rader. D teller COUNT(salary) som 5 — feil, NULL ekskluderes fra COUNT(kolonne).

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 5 3 poeng Kap. 3

Vi vil filtrere ut grupper basert på et aggregat (f.eks. COUNT(*) > 3) i en GROUP BY-spørring. Hvilken klausul må vi bruke?

A WHERE — filtrerer rader før grupperingen.
B HAVING — filtrerer grupper etter aggregeringen.
C FILTER — en aggregat-modifier i alle SQL-dialekter.
D ORDER BY — sorterer etter aggregatverdien.

Vis fasit

Riktig svar: B

Logisk evalueringsrekkefølge er FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY. WHERE filtrerer rader før gruppering — den kan derfor ikke referere til aggregater. HAVING evalueres etter GROUP BY og kan referere til aggregater som COUNT(*) eller SUM(x).

A er feil — WHERE kommer før GROUP BY og har derfor ikke aggregater. C — FILTER er en standard modifikator (COUNT(*) FILTER (WHERE ...)), men brukes inne i SELECT-klausulen, ikke som filter på grupper. D sorterer kun, filtrerer ikke.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 6 4 poeng Kap. 3

Skjema:

student(sid)
course(cid)
takes(sid, cid)

Hvilken SQL finner studentene som har tatt alle kursene?

SELECT sid FROM takes t
WHERE t.cid IS NOT NULL
GROUP BY t.sid
HAVING COUNT(DISTINCT t.cid) = 1
ORDER BY t.sid;

SELECT DISTINCT s.sid FROM student s
WHERE s.sid IN
  (SELECT t.sid FROM takes t WHERE t.cid = 'DB'
   GROUP BY t.sid HAVING COUNT(*) >= 1)
ORDER BY s.sid;

SELECT DISTINCT t.sid FROM takes t
WHERE t.cid IN
  (SELECT c.cid FROM course c
   WHERE c.cid IS NOT NULL)
ORDER BY t.sid;

SELECT s.sid FROM student s
WHERE NOT EXISTS (
    SELECT cid FROM course c
    WHERE NOT EXISTS (
        SELECT * FROM takes t
        WHERE t.sid = s.sid AND t.cid = c.cid));

Vis fasit

Riktig svar: D

Dette er det klassiske divisjon-mønsteret i SQL: "ingen kurs eksisterer som studenten ikke har tatt". De to nøstede NOT EXISTS skjekker at det er ingen kursrad i course som mangler en match i takes for studenten.

A finner studenter som har tatt nøyaktig 1 kurs (HAVING COUNT = 1). For å treffe "alle kursene" måtte HAVING-klausulen sammenlignet med (SELECT COUNT(*) FROM course). B finner studenter som har tatt et spesifikt kurs ('DB'), ikke alle. C returnerer alle takes-rader (ingen filtreringskraft når cid uansett er i course pga. FK).

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 7 3 poeng Kap. 3

Hva er hovedfordelen med å bruke en BEFORE INSERT-trigger fremfor en AFTER INSERT-trigger?

A BEFORE-triggeren kan modifisere NEW-radens verdier før de skrives til disk.
B BEFORE-triggeren kjøres i en separat transaksjon og blir derfor raskere enn AFTER.
C BEFORE-triggeren kan utløses av flere SQL-statements samtidig på samme tabell.
D BEFORE-triggeren har tilgang til OLD-raden, mens AFTER ikke har det.

Vis fasit

Riktig svar: A

BEFORE-triggere kjører før raden faktisk settes inn (eller endres). De har tilgang til NEW-raden og kan modifisere verdier i den — for eksempel sette en default, normalisere data, eller avvise raden via SIGNAL/RAISE. AFTER-triggere kan ikke endre raden lenger; de brukes til revisjon, side-effekter eller cascading.

B er feil — triggere kjøres i samme transaksjon som DML-en som utløste dem. C er feil — det handler ikke om samtidighet. D er motsatt: ved INSERT er det ingen OLD-rad (raden eksisterer ikke før). OLD finnes kun ved UPDATE/DELETE.

Pensum: Kap. 3 — Prosedyrer, triggere og rekursjon

Spørsmål 8 3 poeng Kap. 3

Hvilket av følgende kriterier må typisk være oppfylt for at en view skal være oppdaterbar (updatable)?

A Viewet inneholder GROUP BY-klausul og aggregeringsfunksjoner i SELECT-listen.
B Viewet er materialisert og lagret separat som ekte rader på disken et annet sted.
C Viewet bruker UNION-operatoren mellom to forskjellige tabeller i kildedataene.
D Viewet er definert over én enkelt tabell uten DISTINCT eller aggregater.

Vis fasit

Riktig svar: D

For at en INSERT/UPDATE/DELETE mot et view skal kunne propagiseres entydig til underliggende tabell(er), kreves typisk: viewet er bygget over én tabell, ingen DISTINCT, GROUP BY, aggregater, eller UNION; alle PK/NOT NULL-kolonner i underliggende tabell må være med (for INSERT). Disse begrensningene sikrer at hver rad i viewet svarer til nøyaktig én rad i basistabellen.

A — GROUP BY og aggregater diskvalifiserer viewet fra å være updatable; en aggregert verdi har ikke en unik rad-tilbakeoversettelse. B er en separat egenskap (materialisert vs. virtuelt); materialiserte views har egne oppdateringsstrategier. C — UNION blander rader fra ulike tabeller, så DBMS-et kan ikke avgjøre hvilken tabell en INSERT skal gå til.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 9 3 poeng Kap. 4

Anta vi har en rekursiv 1:1-relasjon "married_to" på entiteten Person, med partial deltakelse fra begge "rollene". Hva er minimum antall tabeller for å mappe Person + relasjonen til relasjonsmodellen?

A 1 tabell — Person med en self-FK spouse som tillater NULL.
B 2 tabeller — Person + en koblingstabell for relasjonen.
C 3 tabeller — Person, en kopi for "ektefelle"-rollen og koblingstabell.
D 0 tabeller — rekursive 1:1-relasjoner kan ikke modelleres.

Vis fasit

Riktig svar: A

Standardteknikken for 1:1-relasjoner med partial deltakelse er å legge til en fremmednøkkel (kan være NULL) i én av entitetene. For en rekursiv 1:1 blir dette en self-referencing FK: Person(pid PK, name, spouse FK→Person(pid)). NULL tillater partial deltakelse.

B er overflødig: 1:1 trenger ikke en egen koblingstabell (i motsetning til M:N). C er ikke nødvendig — vi har én entitet, ikke to. D er feil — rekursive relasjoner er fullt modellerbare med self-FK eller koblingstabell.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 10 3 poeng Kap. 4

Vi har en M:N-relasjon "enrolls" mellom Student og Course, med total deltakelse fra Student. Hvilken påstand følger logisk av dette?

A Hver Course må ha minst én Student tilknyttet.
B En Student kan kun ta ett kurs.
C Hver Student må være enrollet i minst ett kurs.
D Alle relasjoner er obligatoriske begge veier.

Vis fasit

Riktig svar: C

Total deltakelse fra Student betyr at hver Student-instans må delta i minst én forekomst av relasjonen. Kombinert med M:N betyr det at hver student må være enrollet i minst ett kurs. Total deltakelse på den ene siden påvirker ikke den andre siden.

A ville krevd total deltakelse fra Course (ikke spesifisert). B er feil — M:N tillater flere kurs per student. D er for sterkt; deltakelsen er kun spesifisert for Student, ikke Course.

Pensum: Kap. 4 — ER-modellen

Spørsmål 11 4 poeng Kap. 4

Gitt skjema R(A, B, C, D, E) med FD-mengde:

F = { A → B,
      BC → D,
      D → E }

Hvilken av de følgende er en kandidatnøkkel for R?

A {A, C}
B {A, B}
C {C, D}
D {A, D}

Vis fasit

Riktig svar: A

Beregn closure: {A,C}⁺: starter med {A,C}; A→B gir {A,B,C}; BC→D gir {A,B,C,D}; D→E gir {A,B,C,D,E} = R. Supernøkkel ✓. Verken {A} alene eller {C} alene er supernøkkel (sjekk: A⁺=AB, C⁺=C), så {A,C} er minimal — kandidatnøkkel.

B: {A,B}⁺ = {A,B}; mangler C. Ikke supernøkkel.

C: {C,D}⁺ = {C,D,E}; mangler A og B. Ikke supernøkkel.

D: {A,D}⁺ = {A,B,D,E}; mangler C. Ikke supernøkkel.

Pensum: Kap. 4 — Normalformer

Spørsmål 12 4 poeng Kap. 4

Skjema R(A,B,C,D) med FDs A→B, A→C, C→D. Vi dekomponerer R til R1(A,B,C) og R2(C,D). Er dekomponeringen lossless-join?

A Ja — R1 ∩ R2 = {C}, og C er supernøkkel for R2 fordi C → D.
B Nei — vi mister koblingen mellom A og D.
C Ja, men kun fordi A→C er en triviell avhengighet.
D Nei — fellesattributtet C er ikke en supernøkkel for hele R.

Vis fasit

Riktig svar: A

For binær dekomponering R = R1 ∪ R2 er kriteriet: R1 ∩ R2 må være supernøkkel for minst én av R1 eller R2. Her er R1 ∩ R2 = {C}, og C → D i F. Det betyr at C funksjonelt determinerer alle attributter i R2 = {C, D}, så C er supernøkkel for R2. Dekomponeringen er lossless-join.

B er feil — A→C i R1 og C→D i R2 lar oss rekonstruere koblingen via joinen. C er feil — A→C er ikke triviell, og det er ikke det som gjør joinen lossless. D forveksler kriteriet — fellesattributtet trenger ikke være supernøkkel for hele R, kun for én av R1 eller R2.

Pensum: Kap. 4 — Normalformer

Del 2 — Svein Erik (~60 %)

Konkrete regneoppgaver — heap, hashing, B+-tre, access paths, join, sortering, 2PL og ARIES.

Spørsmål 13 4 poeng Kap. 6

Vi har poster som er 250 byte store. Vi har en tabell med 16 000 poster. Hvor mange blokker har vi i en heapfil når blokkene er 4096 bytes store? Anta det kun lagres hele poster i blokkene.

A 1024
B 999
C 1000
D 64

Vis fasit

Riktig svar: C

Poster per blokk: floor(4096 / 250) = 16 (resten 96 byte er ubrukt). Antall blokker: ceil(16 000 / 16) = 1000 (eksakt 16·1000).

A (1024) er en runde-feil — sannsynligvis floor(4096/256)=16, så 16000/16=1000 — likevel ikke 1024. B (999) bruker floor i stedet for ceil — feil retning. D (64) er 16000/250 i feil enhet (deler antall poster på post-størrelse).

Pensum: Kap. 6 — Heapfiler

Spørsmål 14 4 poeng Kap. 6

Anta vi har følgende nøkler som skal settes inn i en statisk hash-struktur:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

Hash-strukturen er tom fra før og har 3 blokker, der hver blokk kan inneholde tre nøkler. Vi bruker separat lenket overløp hvis en blokk blir full. Bruk hashfunksjonen h(K) = K mod 3. Hvor mange blokkaksesser får vi gjennomsnittlig per aksess av en tilfeldig nøkkel? Rund av svaret til to desimaler.

A 1.00
B 1.25
C 1.33
D 1.50

Vis fasit

Riktig svar: B

Plasser etter K mod 3:

Blokk 0 (K mod 3 = 0): 3, 6, 9 — full. 12 → overløpsblokk [12].
Blokk 1 (K mod 3 = 1): 1, 4, 7 — full. 10 → overløpsblokk [10].
Blokk 2 (K mod 3 = 2): 2, 5, 8 — full. 11 → overløpsblokk [11].

9 nøkler i hovedblokker (1 aksess hver) + 3 nøkler i overløpsblokker (2 aksesser hver). Snitt: (9·1 + 3·2) / 12 = 15/12 = 1.25.

A (1.00) ville krevd null overløp. C (1.33) ville krevd 4 overløp av 12. D (1.50) ville krevd 6 overløp.

Pensum: Kap. 6 — Statisk hashing

Spørsmål 15 5 poeng Kap. 6

Vi starter med en extendible hashing-struktur hvor det er 4 pekere til 4 tomme blokker (lokal og global dybde = 2). Hver blokk har plass til to nøkler. Så settes nøklene inn i denne rekkefølgen:

27, 18, 9, 7, 16, 13, 15

Bruk h(K) = K mod 8. Når alle nøklene er satt inn, hvor mange blokker har lokal dybde = 3?

Vis fasit

Riktig svar: D

Trace (siste 2 bits indekserer mens GD=2):

27 (11011 → 11): bucket 11 = [27].
18 (10010 → 10): bucket 10 = [18].
9 (1001 → 01): bucket 01 = [9].
7 (111 → 11): bucket 11 = [27, 7] full.
16 (10000 → 00): bucket 00 = [16].
13 (1101 → 01): bucket 01 = [9, 13] full.
15 (1111 → 11): bucket 11 full, LD=GD=2 → directory dobles, GD=3. Rehash 27 (011), 7 (111). 27 → 011, 7 → 111. Begge nye buckets har LD=3. Sett inn 15 (111) → bucket 111 = [7, 15].

Sluttilstand: bucket 011 (LD=3) = [27]; bucket 111 (LD=3) = [7, 15]; resterende blokker beholder LD=2. Antall blokker med LD=3 = 2.

A (0) glemmer at directory ble doblet. B (4) er totalt antall blokker, ikke bare LD=3-ene. C (1) regner kun den blokken som ble splittet, men begge etter splitten har LD=3.

Pensum: Kap. 6 — Extendible hashing

Spørsmål 16 4 poeng Kap. 6

Vi har et clustered B+-tre hvor vi setter inn 12 000 ansattposter av størrelse 250 byte. Nøkkelen empNo er 4 byte. En RecordID er 12 byte og en BlockId er 8 byte. En blokk er 4096 (4K) byte. Hvor mange blokker er det på level=1? Anta blokkene har 2/3 fyllgrad.

Vis fasit

Riktig svar: B

Tilgjengelig plass per blokk: 4096 · 2/3 ≈ 2730 byte. Løvnivå (clustered): hele posten lagres → floor(2730 / 250) = 10 poster per blokk. Antall løvblokker: ceil(12 000 / 10) = 1200.

Indre nivåer: (key, BlockId) = 4+8 = 12 byte per par. Par per indre blokk: floor(2730 / 12) = 227. Antall blokker på level 1: ceil(1200 / 227) = ceil(5.29) = 6.

A (5) bruker floor i stedet for ceil. C (7) overestimerer. D (1) er roten, ikke level 1.

Pensum: Kap. 6 — B+-trær

Spørsmål 17 4 poeng Kap. 7

Vi har tabellen

Student(pno, studno, lastname, firstname, email)

Tabellen er lagret som heapfil med 1500 blokker. Vi har en statisk hashindeks på pno (300 hovedblokker + 60 overløpsblokker, gjennomsnittlig 1.2 blokkaksess per oppslag). I tillegg har vi et unclustered B+-tre på lastname med 500 løvblokker og 3 nivåer.

Hvor mange blokker aksesseres ved optimal utføring av:

SELECT * FROM Student WHERE pno = 12121212345;

A 2.2
B 1.2
C 4
D 1500

Vis fasit

Riktig svar: A

Optimal plan: bruk hashindeksen på pno. Gjennomsnittlig kostnad for å finne (pno, RID)-paret er 1.2 blokker. Deretter ett heap-oppslag for å hente raden via RID = 1 blokk. Sum: 1.2 + 1 = 2.2 blokker.

B (1.2) glemmer heap-oppslaget. C (4) ville vært ca. tre B+-tre-nivåer + heap, men vi bruker hash, ikke B+-tre. D (1500) er full scan av heap-filen — meningsløst når vi har punktindeks.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 18 4 poeng Kap. 7

Samme oppsett som forrige oppgave (Student-heap 1500 blokker, hash på pno, unclustered B+-tre på lastname med 500 løvblokker og 3 nivåer). Hvor mange blokker aksesseres ved optimal utføring av:

SELECT DISTINCT lastname FROM Student;

A 1500
B 500
C 502
D 1503

Vis fasit

Riktig svar: C

Det unclustered B+-treet på lastname har løvene sortert på lastname. Vi traverserer fra rot til venstre løvblokk = levels − 1 = 2 blokker, og leser deretter alle 500 løvblokker sekvensielt. Duplikate lastnames blir naboer — DISTINCT kan elimineres on-the-fly uten ekstra sortering. Heap-radene trenger vi ikke besøke (lastname ligger i indeksen). Sum: 2 + 500 = 502.

A (1500) er full scan av heap-filen + sortering — bortkastet når indeksen allerede er sortert. B (500) glemmer traverseringen til første løvblokk. D (1503) inkluderer feilaktig en heap-aksess for hver løv — unødvendig fordi vi har lastname rett i indeksen.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 19 5 poeng Kap. 7

To tabeller Bok og Forfatter skal joines med nested loop join. Bufferet har 5 plasser til blokker. Bok har 22 blokker, Forfatter har 1200 blokker. Hvor mange lesinger av blokker skjer ved joinen?

A 1222
B 8422
C 9622
D 26422

Vis fasit

Riktig svar: C

Plasser den minste tabellen ytterst (Bok, 22 blokker). Med B = 5 brukes 1 blokk til indre + 1 til output, så ytre chunk-størrelse = B − 2 = 3.

Ytre chunks: ceil(22 / 3) = 8. For hver chunk leser vi hele indre tabell (Forfatter): 8 · 1200 = 9600 blokker. Pluss ytre tabell leses én gang totalt: 22. Sum: 22 + 9600 = 9622.

A (1222) er kun ett pass av begge — mulig kun hvis hele Bok får plass i bufferet (uten chunks). B (8422) feilteller chunks (7 i stedet for 8). D (26422) bruker Forfatter som ytre — verre fordi den er mye større.

Pensum: Kap. 7 — Join-algoritmer

Spørsmål 20 5 poeng Kap. 7

Vi joiner to tabeller med sort-merge join. Tabell A har 200 blokker og er allerede sortert på joinattributtet. Tabell B har 800 blokker og er allerede sortert på samme attributt. Bufferet har 6 plasser. Hvor mange blokkaksesser kreves for joinen alene (ekskludert sortering, siden tabellene allerede er sortert)?

A 600
B 1000
C 5000
D 1200

Vis fasit

Riktig svar: B

Når begge inputs allerede er sortert, består sort-merge join kun av merge-fasen. Vi går gjennom begge filene parallelt med to pekere; hver blokk leses én gang. Total: 200 + 800 = 1000 blokker. Dette er det store argumentet for sort-merge — om sorteringen kan gjenbrukes (f.eks. fra et clustered B+-tre på joinattributtet), er joinen lineær i størrelsen til input.

A (600) er for lite — vi må jo lese hele tabell B (800 blokker). C (5000) er nær om vi måtte sortere på nytt fra usortert. D (1200) er ikke konsistent med noen standardanalyse.

Merknad: i tilfeller hvor mange rader i én tabell deler samme join-nøkkelverdi, kan duplikatpartisjoner kreve flere passes — men i en standard merge gir vi 1·(B+A) som basisestimat.

Pensum: Kap. 7 — Sort-merge join

Spørsmål 21 5 poeng Kap. 7

Vi har en usortert fil bestående av 200 blokker med poster og et buffer med plass til 5 blokker. Hvor mange blokker leses og skrives til sammen når postene skal sorteres ved hjelp av flettesortering? En lesing og en skriving av en blokk blir til sammen 2.

A 1600
B 800
C 2000
D 400

Vis fasit

Riktig svar: A

Sort-fasen lager n_R = ceil(200 / 5) = 40 initielle runs. Merge-grad d_M = min(5 − 1, 40) = 4.

Antall merge-passes:

Pass 1: ceil(40/4) = 10 runs.
Pass 2: ceil(10/4) = 3 runs.
Pass 3: ceil(3/4) = 1 run.

Totalt: 1 sort-pass + 3 merge-passes = 4 passes. Per pass leses og skrives alle 200 blokker = 2 · 200 = 400. Sum: 4 · 400 = 1600.

B (800) er 2 passes. C (2000) er 5 passes — for mange. D (400) er kun 1 pass.

Pensum: Kap. 7 — External merge sort

Spørsmål 22 4 poeng Kap. 8

Hva er recovery-egenskapen til følgende historie? Velg den mest spesifikke egenskapen som er oppfylt.

w1(A); w1(B); w2(A); c1; r2(B); r3(B); c2; c3;

A Strict
B Recoverable (gjenopprettbar)
C ACA (unngå galopperende abort)
D Unrecoverable (ikke gjenopprettbar)

Vis fasit

Riktig svar: C

Analyse:

Strict? Nei — w2(A) skriver A mens T1 ennå har w1(A) og ikke har committet. Strict forbyr lese og skrive på et element som er skrevet av en uncommitted skriver.
ACA? Ja — ACA forbyr lesing fra uncommitted skriver. Sjekk lesinger: r2(B) kommer etter c1, så B er allerede committet. r3(B) tilsvarende. Ingen brudd. ✓
Recoverable? Følger av ACA, men ACA er strengere.

Mest spesifikk: ACA.

A (strict) er feil pga. w-w-konflikt med uncommitted T1. B (recoverable) er sann men ikke mest spesifikk. D er feil — recovery er fullt mulig her.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 23 5 poeng Kap. 8

Følgende sekvens av operasjoner kommer inn til databasen, og vi bruker rigorous 2PL med vranglåsoppdagelse:

r1(A); r2(B); w1(B); w2(A); c1; c2;

Hva skjer med utførelsen?

A Begge transaksjonene committer i rekkefølgen T1; T2.
B Begge transaksjonene committer parallelt uten interferens.
C Begge transaksjonene committer i rekkefølgen T2; T1.
D Det oppstår vranglås mellom T1 og T2 — én av dem aborteres.

Vis fasit

Riktig svar: D

Trace:

r1(A): T1 tar rl(A).
r2(B): T2 tar rl(B).
w1(B): T1 vil ha wl(B). T2 har rl(B) → T1 venter på T2.
w2(A): T2 vil ha wl(A). T1 har rl(A) → T2 venter på T1.

Vi har en sykel i wait-for-grafen: T1 → T2 → T1. Det er en klassisk vranglås. Vranglåsoppdagelsen ruller én transaksjon tilbake (typisk den med færrest holdte ressurser, eller den nyeste); den andre kan så fullføre.

A og C foreslår en ren utførelsesrekkefølge — men begge er blokkert mot hverandre, så ingen rekkefølge er mulig uten å bryte deadlocken. B er feil — låsene er inkompatible (rl ↔ wl).

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 24 5 poeng Kap. 8

Følgende logg ble funnet etter et krasj med ARIES-recovery:

LSN	PrevLSN	TID	Type	PageId
99	null	T1	Update	A
100	99	T1	Update	B
101	100	T1	Update	C
102	null	T2	Update	B
103			begin_ckpt
104			end_ckpt
105	101	T1	Commit
106	102	T2	Update	B
107	null	T3	Update	A
108	107	T3	Update	D
109	106	T2	Commit

Forutsett at end_ckpt med LSN 104 har en DPT som inneholder (B, 102), (A, 99), (C, 101). Ved hvilken LSN må REDO-scannet starte?

A 99
B 100
C 101
D 105

Vis fasit

Riktig svar: A

REDO-scannet i ARIES starter ved den minste recLSN i DPT etter analysen. Sjekkpunktets DPT inneholder (B,102), (A,99), (C,101). Etter analysen kan flere sider legges til (her: B oppdateres på nytt med LSN 106 og D oppdateres med LSN 108), men disse får høyere recLSN. Den minste recLSN er 99 (siden A).

Hvorfor 99 og ikke 102? Page A er i DPT med recLSN=99 — det betyr at A's tilstand på disk ikke nødvendigvis reflekterer endringen ved LSN 99 og senere. For å bringe A i konsistent tilstand må vi spille av loggen fra og med LSN 99.

B (100), C (101) ignorerer at A er i DPT med recLSN=99. D (105) hopper helt over alle update-records — feil, vi må REDO sider som ikke er flushet.

Pensum: Kap. 8 — Recovery

Spørsmål 25 6 poeng Kap. 8

Hvilken av følgende historier er konfliktserialiserbar?

A r1(A); w2(A); w1(A); r2(B);
B r1(X); r2(X); w1(X); w2(X);
C r1(X); w1(X); r2(Y); r2(X); w2(Y);
D r1(A); r3(B); w2(A); w1(B); w3(A);

Vis fasit

Riktig svar: C

Bygg presedensgraf for hvert alternativ.

A: r1(A)–w2(A) gir T1→T2; w2(A)–w1(A) gir T2→T1. Sykel T1↔T2. ✗

B: r1(X)–w2(X) gir T1→T2; r2(X)–w1(X) gir T2→T1; w1(X)–w2(X) gir T1→T2. Sykel T1↔T2. ✗

C: w1(X)–r2(X) gir T1→T2 (eneste konflikt). Ingen sykel. Konfliktserialiserbar — ekvivalent med T1; T2. ✓

D: r1(A)–w2(A): T1→T2; r1(A)–w3(A): T1→T3; w2(A)–w3(A): T2→T3; r3(B)–w1(B): T3→T1. Sykel T1→T3→T1. ✗

Pensum: Kap. 8 — Transaksjoner: teori

Slutt på øvingseksamen 07.