Øvingseksamen 03 · TDT4145

Øvingseksamen 03

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

Hovedfokus: subqueries, BCNF-dekomponering, hashing, J2, isolation levels, WAL/CLR.

Del 1 — Theodoros (~40 %)

Introduksjon, relasjonsalgebra, SQL, ER-modellering, normalformer.

Spørsmål 1 3 poeng Kap. 1

Hva er hovedgrunnen til at applikasjoner bruker et DBMS i stedet for å lagre data i flate filer direkte?

A DBMS-er er alltid raskere enn filsystemer fordi de bruker B+-trær internt til all dataaksess.
B DBMS-er gir samtidighetskontroll, recovery, integritet og deklarative spørringer som applikasjonen ellers måtte implementert selv.
C Filer på disk kan ikke lagre tabulære data — bare DBMS-er kan representere ekte relasjonsstruktur.
D Operativsystemer hindrer applikasjoner fra å skrive direkte til disk, og DBMS-er omgår denne restriksjonen.

Vis fasit

Riktig svar: B

Et DBMS løser fire hovedklasser av problemer som applikasjonen ellers måtte løse selv: (1) samtidighet (lost update, dirty read, ...), (2) recovery (atomær commit, durability), (3) integritet (typer, FKs, CHECK, triggere), og (4) deklarative spørringer (relasjonsalgebra/SQL i stedet for manuell traversering). I tillegg får man datauavhengighet og eksponering via views.

A er en overforenkling — DBMS-er er ofte tregere på enkel lesing av et helt filinnhold; gevinsten ligger i avansert spørringsutføring og pålitelighet. C er feil: filer lagrer fint tabulære data (CSV, parquet, ...). D er en sammenblanding med OS-tilgangskontroll.

Pensum: Kap. 1 — Introduksjon

Spørsmål 2 3 poeng Kap. 2

Tabellene:

L
k	v
1	a
2	b
3	c

R
k	w
2	x
4	y

Hvor mange rader returnerer L FULL OUTER JOIN R ON L.k = R.k?

Vis fasit

Riktig svar: C

Match: k=2 (én rad). Ikke-match fra L: k=1, k=3 (to rader, R-side er NULL). Ikke-match fra R: k=4 (én rad, L-side er NULL). Totalt: 1 + 2 + 1 = 4.

A teller bare match. B er størrelsen til L (left join). D er kryssproduktet (3 × 2 = 6).

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 3 3 poeng Kap. 2

Tabellen P(a) har 5 distinkte rader, og Q(b) har 8 distinkte rader. Hva er det maksimale antallet tupler i σ_(a < b)(P × Q)?

A 13
B 40
C 5
D 8

Vis fasit

Riktig svar: B

Kryssproduktet har 5 · 8 = 40 tupler. I verste/maksimale tilfelle (alle a-er er mindre enn alle b-er) tilfredsstiller hver kombinasjon predikatet a < b, så hele kryssproduktet beholdes. Maks: 40.

A forveksler predikatet med en union-størrelse (5 + 8). C antar a får én match. D antar b får én match. Generelt: |σ_θ(P × Q)| ≤ |P| · |Q|.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 4 3 poeng Kap. 3

Spørringene S1 og S2 returnerer henholdsvis 100 og 60 rader. Det er kjent at 25 rader er identiske (samme verdier i alle kolonner). Hvor mange rader returnerer:

SELECT * FROM S1
UNION
SELECT * FROM S2;

og hvor mange returnerer UNION ALL-versjonen?

A UNION: 160; UNION ALL: 135.
B UNION: 160; UNION ALL: 160.
C UNION: 25; UNION ALL: 160.
D UNION: 135; UNION ALL: 160.

Vis fasit

Riktig svar: D

UNION fjerner duplikater på tvers av S1 og S2: 100 + 60 − 25 = 135 rader. UNION ALL beholder alle rader, inkludert duplikater: 100 + 60 = 160.

A bytter om de to. B forutsetter at UNION ikke fjerner duplikater. C teller bare felles rader.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 5 3 poeng Kap. 3

Skjema:

Forfatter(fid, navn)
Bok(bid, fid, tittel)

En forfatter kan ha skrevet flere bøker. Hvilken spørring returnerer uten duplikater alle forfattere som har skrevet minst én bok?

SELECT navn FROM Forfatter f JOIN Bok b ON f.fid = b.fid;
SELECT DISTINCT navn FROM Forfatter f JOIN Bok b ON f.fid = b.fid;
SELECT navn FROM Forfatter f WHERE EXISTS (SELECT 1 FROM Bok b WHERE b.fid = f.fid);

A Bare 2 og 3.
B Bare 2.
C Bare 3.
D Alle tre er ekvivalente.

Vis fasit

Riktig svar: A

Spørring 1 produserer én rad per (forfatter, bok)-par — en forfatter med 5 bøker fremstår 5 ganger. Den oppfyller derfor ikke "uten duplikater". Spørring 2 fjerner duplikater eksplisitt med DISTINCT. Spørring 3 bruker EXISTS som per definisjon returnerer én rad per forfatter — implisitt uten duplikater. Begge 2 og 3 tilfredsstiller kravet; 1 gjør det ikke.

B og C overser at den andre formuleringen også er korrekt. D feilaktig anser spørring 1 som ekvivalent.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 6 3 poeng Kap. 3

Hva er den vesentlige forskjellen mellom en korrelert og en ukorrelert subquery, sett fra utførelsessynspunkt?

A En korrelert subquery returnerer alltid bare én enkelt rad, mens en ukorrelert subquery kan returnere mange rader.
B En korrelert subquery må alltid bruke EXISTS som operator, mens en ukorrelert kan bruke IN.
C En korrelert subquery refererer kolonner fra ytre spørring og må re-evalueres per ytre rad; en ukorrelert beregnes én gang.
D En ukorrelert subquery kan ikke skrive til den ytre spørringens datasett, mens en korrelert subquery kan gjøre det.

Vis fasit

Riktig svar: C

Korrelasjonen handler om hvorvidt subqueryen refererer en variabel definert i den ytre spørringen. Hvis ja, er subqueryen "låst" til den enkelte ytre raden og må logisk evalueres på nytt for hver ytre rad. Hvis nei kan optimizer evaluere den én gang og bruke resultatet som en konstant. Optimizers gjenkjenner ofte mønsteret og rewriter til en join.

A er feil — korrelert kan returnere mange rader (tenk på EXISTS som er TRUE hvis > 0). B forveksler form med funksjon; IN kan også brukes korrelert. D er fri fantasi.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 7 3 poeng Kap. 3

Hvilken spørring returnerer alle ansatte med lønn høyere enn maksimum lønn i Oslo-avdelingen?

A SELECT navn FROM Ansatt WHERE lonn > ANY (SELECT lonn FROM Ansatt WHERE avd = 'Oslo');
B SELECT navn FROM Ansatt WHERE lonn > ALL (SELECT lonn FROM Ansatt WHERE avd = 'Oslo');
C SELECT navn FROM Ansatt WHERE lonn = SOME (SELECT lonn FROM Ansatt WHERE avd = 'Oslo');
D SELECT navn FROM Ansatt WHERE lonn IN (SELECT MAX(lonn) FROM Ansatt WHERE avd = 'Oslo');

Vis fasit

Riktig svar: B

> ALL er TRUE når verdien er strengt større enn alle verdiene i mengden — altså høyere enn maksimum. Det er nøyaktig det vi vil.

A: > ANY betyr "større enn minst én" — det blir høyere enn minimum, ikke maksimum. C: = SOME finner ansatte som har samme lønn som noen Oslo-ansatt. D finner ansatte som har akkurat samme lønn som maks i Oslo (likhet, ikke strengt større).

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 8 3 poeng Kap. 3

Vi oppretter en updatable view:

CREATE VIEW HoyLonn AS
  SELECT * FROM Ansatt WHERE lonn > 700000
  WITH CHECK OPTION;

En bruker forsøker:

INSERT INTO HoyLonn VALUES (101, 'Per', 600000);

Hva skjer?

A Innsettingen lykkes; raden vises i den underliggende tabellen men ikke gjennom selve viewet.
B Innsettingen lykkes; viewet er kun et lesefilter og ikke en innsettingsgaranti for DBMS-et.
C En kjøretidsfeil kastes som forklarer at INSERT-operasjoner på views aldri er tillatt i SQL.
D Innsettingen avvises fordi raden ville blitt usynlig i viewet (600 000 oppfyller ikke lonn > 700000).

Vis fasit

Riktig svar: D

WITH CHECK OPTION håndhever at enhver INSERT eller UPDATE gjennom viewet må produsere rader som fortsatt vil være synlige i viewet. Her ville lønn 600 000 falle utenfor predikatet, så DBMS-et avviser innsettingen.

A beskriver oppførselen uten WITH CHECK OPTION. B ignorerer hele poenget med klausulen. C er for absolutt — innsettinger på updatable views uten WITH CHECK OPTION lykkes faktisk.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 9 3 poeng Kap. 3

Hva karakteriserer en statement-level trigger sammenlignet med en row-level trigger?

A Statement-level kjøres en gang per affektert rad i tabellen, mens row-level kjøres én gang totalt for setningen.
B Statement-level kjøres én gang per utløsende SQL-setning uansett antall rader, mens row-level kjøres én gang per rad.
C Statement-level kan ikke se på de affekterte radene, og row-level kan ikke se den utløsende setningens kontekst.
D Statement-level fungerer kun mot views, mens row-level fungerer kun mot vanlige tabeller i databasen.

Vis fasit

Riktig svar: B

En statement-level trigger fyrer av nøyaktig én gang for hele SQL-setningen — uavhengig av om setningen rammer 0, 1 eller 1 000 rader. Row-level trigger fyrer av per rad. Statement-level er nyttig for audit-logging på setningsnivå, valideringer mot aggregat osv.; row-level for å manipulere/validere de individuelle radene.

A er motsatt av riktig. C er overforenklet — moderne DBMS-er gir tilgang til transition tables (NEW/OLD rader) også på statement-nivå. D er fabrikert.

Pensum: Kap. 3 — Prosedyrer, triggere, rekursjon

Spørsmål 10 4 poeng Kap. 3

Du skal optimalisere spørringen:

SELECT navn, lonn FROM Ansatt
WHERE avd = 'IT' AND startdato >= '2024-01-01'
ORDER BY lonn DESC;

Tabellen er stor (10 millioner rader). Hvilken enkelt indeks vil generelt gi best ytelse?

A CREATE INDEX idx ON Ansatt(navn);
B CREATE INDEX idx ON Ansatt(lonn);
C CREATE INDEX idx ON Ansatt(avd, startdato);
D CREATE INDEX idx ON Ansatt(startdato, avd);

Vis fasit

Riktig svar: C

(avd, startdato) matcher WHERE-betingelsen som prefiks: indeksen kan seek-e til avd = 'IT' og deretter range-skanne fremover på startdato >= '2024-01-01'. Likheter først, så range — det optimale prefikset for komposittindeks.

A indekserer en kolonne som ikke filtreres på. B er nyttig for ORDER BY men hjelper ikke filtrere — vi må fortsatt skanne hele indeksen og filtrere. D snur leksikografisk rekkefølge — startdato range gir oss et bredt intervall, og likhetstesten på avd kan ikke utnyttes som prefiks-seek.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 11 3 poeng Kap. 4

En M:N-relasjon "deltar_i" mellom Student (PK sid) og Kurs (PK kid) har et attributt karakter. Hvordan mappes denne typisk?

A En relasjonstabell DeltarI(sid, kid, karakter) med PK = (sid, kid), og FKs sid til Student og kid til Kurs.
B En kolonne karakter legges til i Student; relasjonen modelleres bare via FK fra Kurs.
C En egen tabell per (student, kurs)-par; karakter dupliseres i begge.
D En relasjonstabell DeltarI(sid, kid, karakter), men PK er en surrogat-id; (sid, kid) er bare UNIQUE.

Vis fasit

Riktig svar: A

M:N-relasjoner krever en egen relasjonstabell. Den naturlige PK er paret (sid, kid), fordi en student kan delta i ett kurs maksimalt én gang (i en gitt periode). Eventuelle relasjonsattributter (her karakter) ligger som ekstra kolonner i denne tabellen.

B er umulig — en kolonne i Student kan ikke representere mange kurs per student. C dupliserer karakter unødvendig og bryter modellen. D er teknisk mulig, men en separat surrogat-id på en M:N-relasjonstabell er anti-mønster i pensum — det skjuler den naturlige PK-en.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 12 3 poeng Kap. 4

En entitet Person (PK pid) har et flerverdig attributt telefon. Hvordan håndteres dette i mappingen til relasjonsmodellen?

A Telefonene konkateneres til en kommaseparert streng i en kolonne i Person.
B Vi legger til en ekstra kolonne per telefon (telefon1, telefon2, telefon3).
C Vi flytter telefon-attributtet ut til en helt ny entitet i ER-modellen og remapper.
D Vi oppretter en ny tabell PersonTelefon(pid, telefon) med PK = (pid, telefon) og FK fra pid til Person.

Vis fasit

Riktig svar: D

Et flerverdig attributt mappes til en separat tabell med en sammensatt PK = (eier-PK + det flerverdige attributtet) og FK tilbake til entiteten. Dette holder skjemaet på 1NF og lar antall verdier være ubegrenset uten skjemaendringer.

A bryter 1NF (kolonneverdien er ikke atomær). B har et fast tak på antall telefoner og lager NULL-er. C er overengineering — attributtet er flerverdig, ikke en egen entitet med egen identitet.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 13 3 poeng Kap. 4

Tabellen Foredrag(rom, tid, foreleser, emne) har FDs:

F = { (rom, tid) → foreleser,
      foreleser → emne,
      (rom, tid) → emne }

Kandidatnøkkelen er (rom, tid). Hvilken dekomponering er på BCNF, lossless-join og dependency-preserving?

A R1(rom, tid, foreleser, emne) — uendret.
B R1(rom, tid, foreleser), R2(foreleser, emne).
C R1(rom, tid), R2(rom, foreleser), R3(foreleser, emne).
D R1(rom, foreleser), R2(tid, emne).

Vis fasit

Riktig svar: B

R1 har FD (rom, tid) → foreleser — venstresiden er supernøkkel i R1 → BCNF. R2 har FD foreleser → emne — venstresiden er supernøkkel i R2 → BCNF. Lossless-join: skjæringen R1 ∩ R2 = {foreleser} bestemmer R2 (via foreleser→emne) — ja. Dependency preservation: (rom, tid) → foreleser er bevart i R1, og foreleser → emne er bevart i R2; (rom, tid) → emne følger transitivt → bevart. ✓

A bryter BCNF fordi foreleser → emne har foreleser som ikke-supernøkkel. C splitter for mye og mister evnen til å rekonstruere relasjonen lossless. D mister referanseintegritet — verken R1 eller R2 kan re-skape originalen.

Pensum: Kap. 4 — Normalformer

Del 2 — Svein Erik (~60 %)

Lagring, indekser, queries, transaksjoner og recovery.

Spørsmål 14 4 poeng Kap. 6

En heapfil organiseres som en lenket liste der blokk-headeren peker både forover og bakover, og det finnes en separat pekerkjede gjennom blokker som har ledig plass. Hva er hovedfordelen ved den separate ledig-listen?

A Den lar oss slette blokker uten å oppdatere noen pekere.
B Den gjør det mulig å sortere blokker etter nøkkel uten ekstra strukturer.
C Den lar buffer-manageren prefetche flere blokker parallelt.
D Vi finner raskt en blokk med plass for en ny innsetting uten å skanne hele filen.

Vis fasit

Riktig svar: D

Uten en ledig-liste måtte INSERT skanne fra første blokk og lete etter en med plass — O(N). Med ledig-listen følger DBMS-et bare pekeren til den første tilgjengelige blokken. Når blokken blir full fjernes den fra ledig-listen; når en sletting frigjør plass legges blokken til igjen.

A — sletting krever fortsatt å oppdatere både full-listen og ledig-listen. B — heap er per definisjon usortert. C — prefetching avhenger av OS/DBMS-buffer, ikke av ledig-listen.

Pensum: Kap. 6 — Lagring

Spørsmål 15 4 poeng Kap. 6

En statisk hashfil har 8 blokker (N=8) med kapasitet 2 poster per blokk. Hash-funksjonen er h(K) = K mod 8. Vi setter inn nøklene 17, 9, 25, 33, 41, 1 i denne rekkefølgen. Hvor mange overflow-blokker brukes etter alle innsettingene?

Vis fasit

Riktig svar: A

Alle nøkler hasher til samme blokk: 17 mod 8 = 1, 9 mod 8 = 1, 25 mod 8 = 1, 33 mod 8 = 1, 41 mod 8 = 1, 1 mod 8 = 1. Blokk 1 fyller seg etter 2 poster (17, 9). Overflow-blokk #1 trengs for (25, 33). Overflow-blokk #2 trengs for (41, 1). Totalt: 2 overflow-blokker.

B antar at alle blokker fyller seg jevnt. C glemmer den tredje paret. D inkluderer en ekstra blokk feilaktig.

Pensum: Kap. 6 — Lagring

Spørsmål 16 4 poeng Kap. 6

En RID (Record ID) i et typisk DBMS består av to deler. Hvilken kombinasjon er korrekt?

A (filnavn, byteoffset i filen) — slik at RID alltid er stabil ved blokk-flytting.
B (tabellnavn, primærnøkkelen til raden) — RID er en logisk peker.
C (BlockId, slot-nummer i blokken) — fysisk adressering med en indirection-pekertabell i blokken.
D (transaksjons-id, sekvensnummer) — sporer når raden ble lagt inn.

Vis fasit

Riktig svar: C

En RID består av (BlockId, SlotNr). Slot-nummeret peker inn i en pekertabell i blokk-headeren, slik at posten kan flyttes innenfor blokken (f.eks. ved kompaktering) uten at RID-en endres — kun slot-pekeren oppdateres internt.

A er upraktisk — direkte byteoffset endres ved enhver intern flytting. B er en logisk peker, ikke RID; den krever indeks-oppslag for å finne raden. D blander RID med transaksjonslogger.

Pensum: Kap. 6 — Lagring

Spørsmål 17 4 poeng Kap. 6

Hva ligger på løvnivå (level=0) i et clustered versus et unclustered B+-tre?

A Begge har (key, RID)-poster, og forskjellen er kun at clustered-trær har færre nivåer i strukturen.
B Clustered har hele dataradene sortert etter søkenøkkelen; unclustered har (key, RID)-poster som peker til separat struktur.
C Clustered løvnivå inneholder kun nøkkelverdiene, mens unclustered løvnivå inneholder hele dataradene direkte.
D Clustered krever at hver rad ligger i sin egen blokk, mens unclustered tillater flere rader per blokk.

Vis fasit

Riktig svar: B

Et clustered B+-tre er selve filen — på løvnivået ligger hele radene i sortert rekkefølge etter søkenøkkelen. Et unclustered B+-tre er en sekundær struktur: løvnivået inneholder (key, RID)-poster, og selve raden hentes fra en separat heap- eller clustered-fil.

A overser det grunnleggende skillet. C er motsatt av riktig. D er fri fantasi — clustered B+-trær pakker mange rader per blokk.

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

Spørsmål 18 4 poeng Kap. 6

På de indre nivåene av et B+-tre lagres (key, BlockId)-poster. Key er 8 byte og BlockId er 4 byte. Blokker er 4096 byte og fyllgraden er 2/3. Hva er fan-out?

A 227
B 341
C 100
D 512

Vis fasit

Riktig svar: A

Tilgjengelig plass per blokk med 2/3 fyllgrad: 4096 · 2/3 ≈ 2730 byte. Hver indeks-record er 8 + 4 = 12 byte. Fan-out: floor(2730 / 12) = 227.

B regner uten 2/3-fyllgrad: 4096/12 ≈ 341. C velger en for liten verdi vilkårlig. D bruker bare 8 byte per record (glemmer BlockId).

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

Spørsmål 19 4 poeng Kap. 6

Hva er hovedformålet med compaction i et LSM-tre?

A Å konvertere hele LSM-treet til et B+-tre når antall SST-filer overskrider en gitt terskel.
B Å sjekke alle FK-constraints batch-vis i bakgrunnen for å unngå brudd på integritet i databasen.
C Å slå sammen flere SST-filer til større, fjerne overskrevne/slettede nøkler, og holde lese-aksesser nede.
D Å fryse memtable-en og hindre videre skriv mens en pågående recovery-prosess kjører ferdig.

Vis fasit

Riktig svar: C

Hver gang memtable flushes til disk dannes en ny SST. Uten compaction ville antallet SST-er vokse ubegrenset, og hver lesing måtte sjekke alle (med Bloom-filter-hjelp). Compaction slår sammen SST-er nivåvis, fjerner gamle versjoner av samme nøkkel og tombstones, og holder lese-amplifikasjonen lav. Dette er det grunnleggende write-vs-read tradeoff'et som karakteriserer LSM.

A — LSM forblir LSM, det konverteres ikke til B+-tre. B — compaction har ingenting med FK å gjøre. D — compaction kjører kontinuerlig i bakgrunnen, ikke under recovery.

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

Spørsmål 20 4 poeng Kap. 7

Tabellen Sak har 80 000 rader, lagret som heap (1500 blokker). På opprettet_dato finnes et clustered B+-tre med 4 nivåer og 2000 løvblokker (det er denne indeksen som bestemmer fysisk rekkefølge). Hvor mange blokker leses optimalt for:

SELECT * FROM Sak ORDER BY opprettet_dato ASC;

A 4
B 1500
C 2003
D 2000

Vis fasit

Riktig svar: D

Et clustered B+-tre på opprettet_dato betyr at radene allerede er fysisk sortert i denne rekkefølgen. Vi kan derfor bare skanne løvnivået i sin naturlige rekkefølge — 2000 blokker — og returnere radene direkte. Ingen sortering trengs, og indre nivåer trengs ikke (vi starter fra første løvblokk og følger neste-pekeren).

A er antall nivåer i indekstreet — ikke nyttig for full skann. B er heap-størrelsen, men i et clustered tre er løvnivået selve filen. C antar at vi traverserer fra rot ned (4 + 1999) — overflødig.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 21 4 poeng Kap. 7

Vi joiner R (1000 rader, 50 blokker) med S (10 000 rader, 500 blokker) på betingelsen R.fk = S.pk. Det finnes et clustered B+-tre på S.pk med 3 nivåer. Hvilken kostnad har index nested loop join (J2) med R som ytre?

A 50 + 1000 · 500 = 500 050.
B 50 + 1000 · 3 = 3050.
C 500 + 50 · 3 = 650.
D 50 + 500 = 550.

Vis fasit

Riktig svar: B

J2 leser den ytre tabellen R én gang (50 blokker), og for hver av de 1000 R-rader gjøres et index-oppslag i S. Hver oppslag traverserer indekstreet (3 nivåer = 3 blokk-aksesser); siden indeksen er clustered ligger raden i selve løvblokken — ingen ekstra heap-aksess. Totalt: 50 + 1000 · 3 = 3050.

A regner med en full skann av S per ytre rad — det er J1 (block nested) uten buffer-optimalisering. C bytter R og S som ytre. D glemmer index-oppslagene.

Pensum: Kap. 7 — Join-algoritmer

Spørsmål 22 4 poeng Kap. 7

En fil på 400 blokker sorteres med 6 buffer-rammer. Hvor mange totale blokk-I/O-er (lese + skrive) trengs for å produsere den ferdig sorterte filen?

A 800
B 1600
C 2400
D 3200

Vis fasit

Riktig svar: D

Initial sort-pass: nR = ceil(400/6) = 67 sorterte runs. Merge-grad: dM = min(6−1, 67) = 5. Antall merge-passer: ceil(log_5(67)) = 3 (5² = 25 < 67 ≤ 5³ = 125). Hvert pass leser og skriver hele filen én gang. Totalt I/O: 2 · B · (1 + passes) = 2 · 400 · (1 + 3) = 3200.

A teller bare initial pass. B teller ett pass for lite. C bommer på antall merge-passer (regner med 2). Husk: 2B er per pass (lese alle, skrive alle), gangs antall passes (initial + merge).

Pensum: Kap. 7 — Sortering

Spørsmål 23 4 poeng Kap. 8

Vurder schedulen:

r1(A); r2(B); w1(B); r3(A); w2(A); w3(B);

Er den konfliktserialiserbar?

A Ja, med ekvivalent rekkefølge T1, T2, T3.
B Ja, med ekvivalent rekkefølge T3, T1, T2.
C Nei — presedensgrafen har sykel.
D Ja, med ekvivalent rekkefølge T2, T1, T3.

Vis fasit

Riktig svar: C

Vi bygger presedensgrafen. r1(A) ↔ w2(A): T1 → T2 (les før skriv). r2(B) ↔ w1(B): T2 → T1 (les før skriv). Allerede her har vi sykel T1 ↔ T2, og videre kanter (T3 → T2 fra r3(A)/w2(A); T1 → T3 fra w1(B)/w3(B)) gjør grafen enda mer sammenkoblet. Sykel = ikke konfliktserialiserbar.

A, B og D foreslår serielle rekkefølger som ikke kan reproduseres når presedensgrafen har sykel.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 24 4 poeng Kap. 8

Hvilken kombinasjon av SQL-isolation level og tillatt anomali er feil?

A READ COMMITTED tillater dirty read.
B READ COMMITTED tillater unrepeatable read.
C REPEATABLE READ tillater phantom.
D SERIALIZABLE tillater ingen av anomaliene.

Vis fasit

Riktig svar: A

READ COMMITTED hindrer dirty read — det er hele poenget med nivået. Dirty read er kun tillatt på READ UNCOMMITTED. B er korrekt: READ COMMITTED låser ikke leselåser etter at lesingen er ferdig, så en repeat-lesing kan se en ny verdi. C er korrekt: REPEATABLE READ låser eksisterende rader, men nye rader kan dukke opp i et range — det er phantom. D er per definisjon korrekt for SERIALIZABLE.

B/C/D er alle gyldige utsagn; bare A bryter den klassiske isolation-level-tabellen.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 25 4 poeng Kap. 8

Hva er hovedegenskapen ved conservative (statisk) 2PL?

A Alle låser frigis umiddelbart etter hver enkelt operasjon, noe som gir høy gjennomstrømning og samtidighet i schedulen.
B Det skiller seg fra strict 2PL kun ved at exclusive-låser frigis tidligere, mens shared-låser holdes helt til commit-tidspunktet.
C Det bruker tidsstempler i stedet for låser for å serialisere — det er nettopp derfor det kalles "konservativt".
D Hver transaksjon ber om alle låsene den trenger på forhånd og starter ikke før alle er innvilget. Ingen deadlocks oppstår.

Vis fasit

Riktig svar: D

Conservative 2PL forhåndsallokerer alle låser før transaksjonen starter sin første operasjon. Hvis ikke alle kan innvilges, venter transaksjonen i atom-bestilling. Siden ingen transaksjon noensinne er "halvferdig" når den ber om en lås, er sykler i wait-for-grafen umulige → ingen deadlocks. Prisen er at samtidigheten reduseres (transaksjoner blokkerer hverandre lenger ute), og det krever forhåndskunnskap om hvilke objekter som vil bli aksessert.

A beskriver "ikke-2PL" — det ville brutt serialiseringsregelen. B beskriver en variant av basic 2PL men ikke conservative. C blander 2PL med timestamping.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 26 4 poeng Kap. 8

Vi bruker rigorous 2PL. Følgende sekvens kommer inn til scheduleren (operasjonene utføres når de er låsekompatible — venter ellers):

r1(X); r2(Y); w3(X); r1(Y); w2(Y); w3(Y); w1(X); c1; c2; c3;

I hvilken rekkefølge committer transaksjonene?

A T2, T3, T1.
B T1, T2, T3.
C Vi får deadlock mellom T1 og T2.
D T3, T2, T1.

Vis fasit

Riktig svar: B

Spor utviklingen:

r1(X): T1 får S(X).
r2(Y): T2 får S(Y).
w3(X): T3 vil ha X(X), men T1 har S(X) → T3 venter på T1.
r1(Y): T1 vil ha S(Y) — kompatibel med T2 sin S(Y) → T1 får S(Y).
w2(Y): T2 vil ha X(Y), men T1 har S(Y) → T2 venter på T1.
w3(Y): T3 venter allerede på T1; også på T2 nå.
w1(X): T1 vil ha X(X) — kun T1 har S(X) (kompatibel oppgradering, ingen andre lesere) → T1 får X(X).
c1: T1 committer, frigir alle låser. T2 kan nå få X(Y), gjør w2(Y), committer (c2). T3 får X(X) og X(Y), gjør w3(X) og w3(Y), committer (c3).

Wait-for-grafen er asyklisk (T2 → T1, T3 → T1, T3 → T2) — ingen deadlock. Commit-rekkefølge: T1, T2, T3.

A antar at T2 og T3 blir ferdige før T1, men begge venter på T1. C ville krevd sykel i wait-for-grafen — finnes ikke. D snur rekkefølgen helt.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 27 4 poeng Kap. 8

Hva sier Write-Ahead Logging (WAL) protokollen, og hvilken konsekvens har "force-log-at-commit"?

A WAL: enhver ikke-committet endring må logges før data-blokken skrives til disk. Force-log-at-commit: commit-loggposten må være på disk før commit returneres til klienten.
B WAL: data-blokken må skrives til disk samtidig som den tilhørende loggposten. Force-log-at-commit: tx-loggen flushes asynkront av en bakgrunnstråd med jevne mellomrom.
C WAL: alle loggposter buffres helt til neste checkpoint, og skrives først da til disk. Force-log-at-commit: alle data-blokker flushes ved hver eneste commit.
D WAL: i ARIES skrives REDO-logg til en separat disk og UNDO-logg til hovedminnet. Force-log-at-commit: garanterer at REDO-loggen er skrevet først av alt.

Vis fasit

Riktig svar: A

WAL-regelen: loggposten som beskriver en endring må persistre før selve dataendringen flushes — slik kan vi alltid undoe en endring (loggen har den nødvendige before-image). Force-log-at-commit: før vi sier ja til klienten ved en commit, må alle loggposter for den transaksjonen — særlig commit-posten — være på disk. Det garanterer Durability uten å kreve at data-blokkene er flushet (de kan flushes senere, derav "no-force"-policy).

B og C inverterer prinsippet. D blander ARIES inn — ARIES bruker én logg, ikke to atskilte.

Pensum: Kap. 8 — Recovery

Spørsmål 28 4 poeng Kap. 8

Hva er hensikten med en Compensation Log Record (CLR) i ARIES, og hvorfor undoes den aldri?

A CLR-en logger commit-tidspunktet for en winner-transaksjon, og den undoes ikke fordi commits per definisjon er irreversible operasjoner.
B CLR-en lagrer LSN-en til siste checkpoint, og den undoes ikke fordi den representerer recovery-state og ikke en vanlig datatransaksjon.
C CLR-en logger en UNDO-handling utført under recovery eller rollback. Den undoes aldri — det ville startet en uendelig løkke. undoNextLSN peker forbi den.
D CLR-en er en redundant kopi av en vanlig loggpost, og brukes hovedsakelig for ekstra sikkerhet i forbindelse med replikering av databasen.

Vis fasit

Riktig svar: C

Når ARIES gjør UNDO (enten ved recovery eller en rollback), skriver den en CLR for hver reverserings-handling. CLR-en inneholder undoNextLSN — pekeren til den neste loggposten som skal undoes (typisk forrige PrevLSN i transaksjonens kjede, eller null hvis ferdig). Hvis et nytt krasj inntreffer midt i UNDO-en kan recovery resume fra CLR-ens undoNextLSN uten å gjenta arbeid. Hvis CLR-er kunne undoes ville recovery komme inn i en evig løkke (undo-undoer en undo).

A og B beskriver andre logg-typer. D er en grov misforståelse — CLR-er er strengt nødvendige, ikke redundante.

Pensum: Kap. 8 — Recovery

Slutt på øvingseksamen 03.