Øvingseksamen 09 · TDT4145

Øvingseksamen 09

Tidsramme: 4 timer · Hjelpemidler: Ingen · Total: 100 poeng · 44 oppgaver

Bredt sett (44 oppgaver) som dekker hele pensum. Hovedfokus: NULL-feller i SQL, hard FD-analyse (3NF vs BCNF, kandidatnøkler i sykel), B+-tre splittmekanikk, CLR/UNDO i ARIES, og scenario-basert resonnement i alle blokker.

Del 1 — Theodoros (~40 %, 18 oppgaver)

Konseptspørsmål, RA-utregninger, SQL-resultater, ER og normalformer. Mange oppgaver tester edge-cases og NULL-semantikk.

Spørsmål 1 2 poeng Kap. 1

Hva betyr det at en database har logisk datauavhengighet?

A Den fysiske lagringen kan endres uten at logisk skjema endres.
B Det logiske skjemaet kan endres (f.eks. ny kolonne) uten at applikasjoner som bruker views må endres.
C Logikk-laget i applikasjonen kan flyttes til klienten uten å endre databasen.
D Spørringer kan optimaliseres uavhengig av indekseringsvalg.

Vis fasit

Riktig svar: B

Logisk datauavhengighet betyr at applikasjoner som er bygget mot eksterne views ikke skal trenge å endres når det logiske (konseptuelle) skjemaet endres. Eksempel: legg til en ny kolonne i en tabell — eksisterende views fortsetter å produsere samme resultat, så apper merker ingenting.

A beskriver fysisk datauavhengighet (endre indekser, lagringsformat) — også viktig, men ikke logisk. C handler om applikasjonsarkitektur (2-tier vs 3-tier). D handler om query-optimalisering, som er et annet tema.

Pensum: Kap. 1 — Introduksjon

Spørsmål 2 2 poeng Kap. 2

Hvilken av følgende operatorer i relasjonsalgebra er ikke fundamental (dvs. den kan defineres ut fra andre)?

A Selection (σ) — filtrerer rader basert på predikat.
B Set difference (−) — fjerner tupler som finnes i andre relasjon.
C Natural join (⋈) — kombinerer relasjoner på felles attributter.
D Cross product (×) — kartesisk produkt av to relasjoner.

Vis fasit

Riktig svar: C

De seks fundamentale operatorene er σ, π, ∪, −, ×, og ρ (rename). Natural join kan uttrykkes som π_attrs(σ_predikat(R × S)) der predikatet matcher fellesattributtene og projeksjonen fjerner duplikatkolonner. Den er derfor derivert, ikke fundamental.

A, B, D er fundamentale. Andre derverte operatorer er intersection (∩ = R − (R − S)), theta join, division, og diverse outer joins.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 3 3 poeng Kap. 2

Følgende tabeller er gitt:

Pasient
pid	navn
1	Anne
2	Bjørn
3	Cara
4	Dag

Innlagt
pid	avd
1	Hjerte
2	Hjerte
2	Lunge
3	Ortopedi

Hvor mange tupler returnerer:

π_pid(Pasient) − π_pid(σ_avd='Hjerte'(Innlagt))

Vis fasit

Riktig svar: B

π_pid(Pasient) = {1, 2, 3, 4}. σ_avd='Hjerte'(Innlagt) = {(1,Hjerte), (2,Hjerte)}. π_pid på dette = {1, 2}. Differansen {1,2,3,4} − {1,2} = {3, 4} → 2 tupler.

A glemmer at både Cara (pid=3) og Dag (pid=4) mangler hjerteinnleggelse. C tar ikke set difference riktig (kan ha telt antall avdelinger). D er hele Pasient-relasjonen uten differanse.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 4 2 poeng Kap. 2

Tabell R har 100 rader, tabell S har 50 rader. INNER JOIN R ⋈ S produserer 80 rader, hvor 30 distinkte R-rader matcher minst én S-rad (noen R-rader matcher flere S-rader). Hvor mange rader produserer R LEFT JOIN S på samme join-betingelse?

A 80 rader — kun matchende rader, samme som INNER JOIN.
B 100 rader — én rad per R-rad, NULL-utvidet ved manglende match.
C 130 rader — alle matchede pluss alle umatchede S-rader.
D 150 rader — alle 80 matchende, pluss 70 umatchede R-rader med NULL.

Vis fasit

Riktig svar: D

LEFT JOIN inkluderer alle rader fra inner join (80) pluss én NULL-utvidet rad for hver R-rad uten match (100 − 30 = 70 umatchede R-rader). Total: 80 + 70 = 150.

A glemmer NULL-padding av umatchede R-rader. B antar at antall LEFT JOIN-rader = |R|, men det stemmer kun hvis hver R-rad matcher maksimalt én S-rad. C blander LEFT med FULL OUTER. Vanlig feiltagelse er å glemme at INNER JOIN kan ha flere rader enn |R| pga. multiple matches.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 5 2 poeng Kap. 3

Vurder spørringen:

SELECT salary * 12 AS aarslonn
FROM ansatt
WHERE aarslonn > 600000;

Hva er problemet?

A Ingen — spørringen fungerer korrekt i alle SQL-dialekter.
B WHERE evalueres før SELECT, så aliaset aarslonn er ikke synlig der.
C Aliaser kan ikke brukes i sammenligning med tall-literal som 600000.
D Spørringen mangler en GROUP BY-klausul for å bruke alias.

Vis fasit

Riktig svar: B

SQL evalueres logisk i rekkefølgen FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY. Aliaser defineres i SELECT, og er derfor først synlige i ORDER BY (og noen ganger HAVING, dialekt-avhengig). I WHERE må man skrive uttrykket på nytt: WHERE salary * 12 > 600000.

A er feil — i standard SQL feiler dette. C er en oppspinning — aliaser kan godt sammenlignes med konstanter der de er gyldige (i ORDER BY, f.eks.). D — GROUP BY er irrelevant; problemet er evalueringsrekkefølge, ikke aggregering.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 6 3 poeng Kap. 3

Tabellen salg:

region	belop
Nord	50
Nord	80
Sør	30
Sør	50
Øst	NULL
Øst	NULL

Hvor mange rader returneres av:

SELECT region, SUM(belop)
FROM salg
GROUP BY region
HAVING SUM(belop) > 100;

A 0 rader — alle gruppene har ufullstendige data.
B 1 rad — kun Nord (sum 130).
C 2 rader — Nord (130) og Øst (NULL behandles som stor).
D 3 rader — alle gruppene returneres.

Vis fasit

Riktig svar: B

Gruppe-summer: Nord = 50+80 = 130, Sør = 30+50 = 80, Øst = NULL (SUM av kun NULL-er gir NULL). HAVING-betingelsen SUM(belop) > 100 evalueres som UNKNOWN for Øst (NULL > 100 = UNKNOWN), som filtreres bort. Sør (80) er ikke > 100. Kun Nord overlever.

A overser at Nord faktisk har komplette data og en sum > 100. C bommer på NULL-semantikken — UNKNOWN er ikke "stor", det filtreres bort. D ignorerer HAVING-filteret helt.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 7 2 poeng Kap. 3

Tabellkolonnen pris inneholder verdiene: 10, 10, NULL, 20, NULL, 30. Hva returnerer SELECT COUNT(DISTINCT pris) FROM ...?

Vis fasit

Riktig svar: D

COUNT(DISTINCT col) ekskluderer NULL-verdier (som alle COUNT(col)-varianter), og fjerner duplikater blant ikke-NULL. Distinkte ikke-NULL verdier: {10, 20, 30} → 3.

A teller alle radene rått. B inkluderer NULL som én "verdi" (men COUNT teller ikke NULL). C dobbelt-teller 10 (men DISTINCT fjerner duplikater).

Note: For SELECT DISTINCT pris derimot ville resultatsettet inneholde 4 rader: {10, 20, 30, NULL} — der NULL telles som én distinkt verdi. Men COUNT(DISTINCT pris) ekskluderer NULL.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 8 3 poeng Kap. 3

Vi har:

SELECT navn FROM ansatt
WHERE avd_id NOT IN (SELECT manager_avd_id FROM avdeling);

Hvis subspørringen returnerer minst én NULL-verdi (f.eks. en avdeling uten manager), hva returnerer ytre spørringen?

A Alle ansatte hvis avd_id ikke matcher noen ikke-NULL manager_avd_id.
B Tom resultatmengde — uavhengig av faktiske data i ansatt.
C Alle ansatte i avdelinger som mangler manager (NULL betyr "matcher alt").
D Syntaksfeil — NOT IN tillater ikke NULL i subspørringen.

Vis fasit

Riktig svar: B

Den klassiske NOT IN + NULL-fellen. x NOT IN (a, b, NULL) ekspanderes til x ≠ a AND x ≠ b AND x ≠ NULL. Men x ≠ NULL evalueres alltid til UNKNOWN, og noe AND UNKNOWN blir UNKNOWN (eller FALSE) — aldri TRUE. Resultatet: ingen rader passerer WHERE-filteret. Bruk i stedet NOT EXISTS (...) eller filtrer NULL i subspørringen.

A er hva folk forventer, men SQLs trivaluerte logikk fungerer ikke slik. C er motsatt av hva som skjer — NULL forårsaker en tom resultatmengde, ikke en utvidet. D — det er ingen syntaksfeil; det er en semantisk felle.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 9 2 poeng Kap. 3

Vurder de to spørringene:

-- (1)
SELECT a.id FROM A LEFT JOIN B ON A.id = B.id WHERE B.x > 5;

-- (2)
SELECT a.id FROM A LEFT JOIN B ON A.id = B.id AND B.x > 5;

Hva er forholdet mellom resultatene?

A Begge gir samme resultat — ON og WHERE er ekvivalente i LEFT JOIN.
B (1) tilsvarer en INNER JOIN; (2) er en ekte LEFT JOIN som beholder umatchede A-rader.
C (2) tilsvarer en INNER JOIN; (1) returnerer alle A-rader med B-felter null-utvidet.
D (1) er ulovlig — WHERE kan ikke filtrere på et NULL-utvidet B.x.

Vis fasit

Riktig svar: B

I (1) gjøres LEFT JOIN først (umatchede A-rader får B-feltene NULL), så filtrerer WHERE bort rader med B.x > 5 usant — men NULL > 5 er UNKNOWN, så NULL-utvidede rader filtreres bort. Resultatet er ekvivalent med en INNER JOIN. I (2) er B.x > 5 en del av selve join-betingelsen; rader i A som ikke matcher noen B med x > 5 beholdes med NULL i B-feltene.

A er en svært vanlig misforståelse. C er motsatt av riktig svar. D er feil — WHERE kan godt referere kolonner som er NULL, det er bare semantikken man må forstå.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 10 2 poeng Kap. 3

Hvilken av spørringene er korrelert?

A SELECT * FROM A WHERE x IN (SELECT y FROM B WHERE B.z = 5);
B SELECT * FROM A WHERE x IN (SELECT y FROM B WHERE B.z = A.z);
C SELECT * FROM A WHERE x IN (SELECT y FROM B);
D SELECT * FROM A, B WHERE A.x = B.y AND B.z = 5;

Vis fasit

Riktig svar: B

En subspørring er korrelert hvis den refererer en kolonne fra en ytre spørring. I (B) refererer den indre spørringen A.z, som tilhører den ytre. Subspørringen må derfor evalueres på nytt for hver rad i A.

A og C er ukorrelerte — den indre spørringen er uavhengig av A og kan evalueres én gang. D er ikke en subspørring i det hele tatt; det er en flat join. Den siste kan dessuten ikke være "korrelert" siden begrepet kun gir mening for nestede spørringer.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 11 2 poeng Kap. 3

Tabellen ansatt(id, navn, sjef_id) har følgende struktur (id → sjef_id):

5 har ingen sjef (rotnode)
7, 8 rapporterer til 5
9 rapporterer til 7
10, 11 rapporterer til 8
12 rapporterer til 9

Hva returnerer:

WITH RECURSIVE kjede AS (
    SELECT id, sjef_id, 0 AS niva FROM ansatt WHERE id = 5
  UNION ALL
    SELECT a.id, a.sjef_id, k.niva + 1
    FROM ansatt a JOIN kjede k ON a.sjef_id = k.id
)
SELECT COUNT(*) FROM kjede;

A 5
B 6
C 7
D Uendelig (CTE-en terminerer ikke).

Vis fasit

Riktig svar: C

CTE-en starter med rotnoden {5} og legger på rader for hver underordnet i hver iterasjon. Iterasjon 0: {5}. Iterasjon 1 (rapporterer til 5): {7, 8}. Iterasjon 2 (rapporterer til 7 eller 8): {9, 10, 11}. Iterasjon 3 (rapporterer til 9, 10, 11): {12}. Iterasjon 4: ingen nye → terminerer. Total: {5, 7, 8, 9, 10, 11, 12} = 7 rader.

A teller bare 5 nivåer eller én sti. B mangler én av nodene, typisk 12. D — CTE-en terminerer fordi treet er endelig og hver rad legges til kun én gang.

Pensum: Kap. 3 — Prosedyrer, triggere, rekursjon

Spørsmål 12 2 poeng Kap. 3

Skjemaet:

CREATE TABLE child (
  id INT PRIMARY KEY,
  parent_id INT NOT NULL,
  FOREIGN KEY (parent_id) REFERENCES parent(id)
    ON DELETE SET NULL
);

Hva skjer når vi prøver å slette en parent-rad som har minst én tilknyttet child-rad?

A Child-rader får parent_id = NULL og parent slettes uten feil.
B DELETE feiler — SET NULL kommer i konflikt med NOT NULL-betingelsen på parent_id.
C Child-radene slettes også (DBMS-et faller tilbake til CASCADE).
D Parent slettes, og child-rader peker fortsatt på den slettede id-en (hengende referanse).

Vis fasit

Riktig svar: B

SET NULL forsøker å sette parent_id = NULL i child, men kolonnen er definert som NOT NULL. Resultatet er en constraint-feil, og DELETE rulles tilbake. Skjemaet er internt inkonsistent og bør avvises ved CREATE TABLE i strenge DBMS, eller feile ved første DELETE i mer permissive systemer.

A ignorerer NOT NULL-konflikten. C er feil — DBMS faller ikke tilbake til CASCADE; det er to forskjellige policy-er. D bryter referensiell integritet og er ikke noe DBMS gjør automatisk.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 13 2 poeng Kap. 3

Hva er hovedforskjellen mellom et materialisert view og et vanlig (virtuelt) view?

A Materialisert view reflekterer alltid nyeste data; vanlig view kan være utdatert.
B Materialisert view lagrer resultatet på disk; vanlig view beregnes på nytt ved hver spørring.
C Vanlig view kan oppdateres (INSERT/UPDATE), materialisert view kan ikke.
D Materialisert view brukes kun i DDL; vanlig view brukes kun i DML.

Vis fasit

Riktig svar: B

Et materialisert view er en lagret kopi av resultatsettet (som regel oppdatert manuelt eller på timer/triggere). Et vanlig view er bare en lagret SQL-spørring som kjøres på nytt hver gang viewet brukes.

A er motsatt riktig retning — vanlig view er alltid "ferskt", materialisert kan være utdatert mellom oppdateringer. C er feil — begge kan teknisk være oppdaterbare under visse forutsetninger, og materialiserte views har egne oppdateringsmekanismer. D er oppspinning.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 14 2 poeng Kap. 4

Et ER-diagram inneholder entiteten Bygning (PK: byggId) og den svake entiteten Rom, som identifiseres med romNr innen sin Bygning (en svak entitet med identifiserende relasjon til Bygning). Hvor mange tabeller trengs i relasjonsskjemaet, og hva blir Roms primærnøkkel?

A 1 tabell (Bygning utvidet med rom-felter); PK = (byggId, romNr).
B 2 tabeller (Bygning, Rom); Roms PK = romNr.
C 2 tabeller (Bygning, Rom); Roms PK = (byggId, romNr).
D 3 tabeller (Bygning, Rom, en koblingstabell for relasjonen).

Vis fasit

Riktig svar: C

En svak entitet mappes til sin egen tabell, og dens primærnøkkel er kombinasjonen av (a) eierens PK som fremmednøkkel + (b) sitt eget partielle nøkkelattributt. Her: Rom(byggId, romNr, ...) med PK (byggId, romNr) og FK byggId → Bygning(byggId).

A samler alt i én tabell, noe som bryter med relasjonsmodellens prinsipp om at hver entitet er sin egen tabell (og krever én rad per (bygning, rom)-par i samme tabell — ikke standard mapping). B mister byggId i nøkkelen, så to ulike bygninger kan ikke ha samme romNr. D legger til en unødvendig koblingstabell (svak entitet trenger ikke det — den identifiserende relasjonen er implisitt i FK-en).

Pensum: Kap. 4 — ER til relasjon

Spørsmål 15 2 poeng Kap. 4

Et ISA-hierarki har Kjøretøy som superklasse, og {Bil, Lastebil, Motorsykkel} som disjunkte og totale subklasser. Hver subklasse har egne attributter pluss superklassens. Hvilken mapping bruker færrest tabeller og unngår NULL-felter?

A Én tabell per subklasse, med superklasse-attributtene kopiert ned i hver. Totalt 3 tabeller, ingen NULL.
B Én Kjøretøy-tabell med type-diskriminator og alle subklasse-kolonner med NULL der ikke aktuelt. Totalt 1 tabell, mange NULL.
C Én tabell for superklassen og én per subklasse, koblet via felles PK. Totalt 4 tabeller, ingen NULL.
D Én Kjøretøy-tabell + én koblingstabell per subklasse. Totalt 4 tabeller, krever JOIN.

Vis fasit

Riktig svar: A

"Én tabell per subklasse uten supertype-tabell" fungerer kun når mapping er disjunkt og total (hver kjøretøy er nøyaktig én subtype). Da kan hver subklasse-tabell inneholde alle attributter (egne + nedarvede), uten NULL-felter, og uten å trenge en separat Kjøretøy-tabell.

B bruker færre tabeller (1) men introduserer NULL-felter — mislykket på begge kriterier. C bruker fler tabeller (4) selv om vi ikke trenger Kjøretøy-tabellen pga. disjunkt+total. D er en uvanlig variant som typisk ikke brukes for ISA.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 16 3 poeng Kap. 4

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

F = { AB → C,  BC → D,  CD → E,  DE → A }

Hva er alle kandidatnøklene?

A Kun {AB}.
B {AB} og {BC}.
C {AB}, {BC}, {BD}, {BE}.
D {AB}, {BC}, {BD} og {ABE}.

Vis fasit

Riktig svar: B

Først må vi finne attributter som må være med i hver kandidatnøkkel. B forekommer aldri på høyresiden — så B må være med. Ingen andre attributter har den egenskapen alene. Test så minimale supersett som inneholder B:

{AB}⁺: AB→C gir {ABC}; BC→D gir {ABCD}; CD→E gir {ABCDE}. Hele R. ✓ {AB} er en superkey, og minimal (siden {A}⁺={A} og {B}⁺={B}). Kandidatnøkkel.

{BC}⁺: BC→D gir {BCD}; CD→E gir {BCDE}; DE→A gir {BCDEA}. ✓ Kandidatnøkkel.

{BD}⁺: ingen FD har venstreside ⊆ {B,D} (alle FD-er trenger A, BC, CD eller DE). Så {BD}⁺={BD}. Ikke superkey.

{BE}⁺: tilsvarende, ingen FD utløses. {BE}⁺={BE}. Ikke superkey.

Eneste kandidatnøkler: {AB, BC}.

A glemmer {BC}. C og D antar feilaktig at {BD} og {BE} blir kandidater — men attributtlukningen stagnerer på dem. Dette er den klassiske fellen: kun fordi B må være med, betyr ikke at alle par med B er kandidater — du må verifisere med lukningstesten.

Pensum: Kap. 4 — Normalformer

Spørsmål 17 2 poeng Kap. 4

Tabellen R(ansattId, navn, avdId, avdNavn) har ansattId som primærnøkkel. I tillegg gjelder FD-en avdId → avdNavn (hver avdeling har ett unikt navn). Hva er den høyeste normalformen R er på?

A 1NF — fordi tabellen har transitive avhengigheter.
B 2NF — fordi det finnes en transitiv avhengighet (ansattId → avdId → avdNavn).
C 3NF — fordi ingen FD-er bryter med 3NF-betingelsene.
D BCNF — fordi alle ikke-trivielle FD-er har superkey som venstreside.

Vis fasit

Riktig svar: B

R er på 1NF (atomære verdier). På 2NF: PK er en enkelt attributt (ansattId), så det kan ikke finnes partielle avhengigheter — derfor automatisk 2NF. På 3NF: FD-en avdId → avdNavn har venstresiden ikke-superkey, og høyresiden ikke-prim — dette er en transitiv avhengighet (ansattId → avdId → avdNavn), som bryter 3NF. Høyeste NF er derfor 2NF.

A — 1NF er bare en starttilstand; tabellen er minst på 2NF. C feiler på den transitive avhengigheten. D — bryter 3NF, så definitivt ikke BCNF.

Pensum: Kap. 4 — Normalformer

Spørsmål 18 2 poeng Kap. 4

Tabell Time(kurs, rom, tidspunkt) med FD-er:

FD1: kurs → rom              (hvert kurs har ett fast rom)
FD2: rom, tidspunkt → kurs    (rom + tidspunkt identifiserer kurset)

Kandidatnøklene er {kurs, tidspunkt} og {rom, tidspunkt}. Hva er høyeste NF?

A 1NF
B 2NF
C 3NF
D BCNF

Vis fasit

Riktig svar: C

FD1 (kurs → rom) bryter BCNF: kurs er ikke en superkey (alene). Men rom er prim-attributt (del av kandidatnøkkelen {rom, tidspunkt}), så FD1 oppfyller 3NF-vilkåret "RHS er prim". FD2 har en superkey som venstreside (faktisk er {rom, tidspunkt} en kandidatnøkkel) → uproblematisk for både 3NF og BCNF. 2NF er oppfylt fordi alle ikke-prim attributter (ingen i denne relasjonen — alle tre er prim) avhenger fullt av hver kandidatnøkkel.

A og B er for lave. D er feil pga. FD1: BCNF krever at alle ikke-trivielle FD-er har en superkey som venstreside, uten prim/non-prim-unntak. Dette er det klassiske scenariet hvor 3NF og BCNF skiller seg: overlappende kandidatnøkler.

Pensum: Kap. 4 — Normalformer

Del 2 — Svein Erik (~60 %, 26 oppgaver)

Lagring, indeksering, queries, transaksjoner og recovery. Tunge regneoppgaver med konkrete tall.

Spørsmål 19 2 poeng Kap. 8

En heapfil lagrer 12 000 poster med fast lengde 80 bytes per post. Blokkstørrelsen er 2048 bytes (ingen header-overhead). Hvor mange blokker bruker filen ved 100 % fyllgrad?

A 469 blokker
B 480 blokker
C 500 blokker
D 600 blokker

Vis fasit

Riktig svar: B

Poster per blokk = floor(2048 / 80) = floor(25.6) = 25. Antall blokker = ceil(12 000 / 25) = 480.

A bruker ceil(12 000 × 80 / 2048) = ceil(468.75) = 469, men dette overser at man ikke kan splitte poster over blokkgrenser med fast lengde. C runder oppover for sikkerhets skyld. D er en grov overestimat.

Pensum: Kap. 6 — Lagring

Spørsmål 20 2 poeng Kap. 8

Hvilket av følgende formater for variable-length records gir direkte (O(1)) tilgang til attributt nummer i?

A Komma-separerte verdier i en streng.
B Tag-length-value sekvens (hver verdi prefikset med sin lengde).
C Record vector: array med offsets til hvert attributt i starten av posten.
D Sluttdelimiter etter hvert attributt (f.eks. NULL-byte).

Vis fasit

Riktig svar: C

Med en record vector (også kalt offset array eller slot directory innen posten) kan man slå opp offset[i] og hoppe direkte til attributt i — O(1). Dette er hvordan moderne DBMS-er typisk lagrer variable-length records.

A, B og D krever sekvensiell parsing fra starten av posten for å nå attributt i — O(i), ikke O(1). Tag-length-value er kompakt men ikke direkteindekserbart.

Pensum: Kap. 6 — Lagring

Spørsmål 21 3 poeng Kap. 8

Statisk hashing med 5 buckets (h(K) = K mod 5) og kapasitet 2 poster per primær-bucket. Vi setter inn nøklene 8, 13, 17, 22, 27, 33, 38 i denne rekkefølgen. Hver overflyt-blokk holder 2 poster. Hvor mange overflyt-blokker trenges totalt?

Vis fasit

Riktig svar: B

Plassering: 8→bucket 3, 13→bucket 3 (full nå), 17→bucket 2, 22→bucket 2 (full), 27→bucket 2 (overflyt), 33→bucket 3 (overflyt), 38→bucket 3 (overflyt).
Bucket 2 har 1 overflyt-post (27): 1 overflyt-blokk holder den.
Bucket 3 har 2 overflyt-poster (33, 38): 1 overflyt-blokk (passer 2 poster).
Totalt 2 overflyt-blokker.

A glemmer den ene av de to bucketene. C overteller (kanskje regnet 1 per overflyt-post). D er antall buckets totalt, ikke overflyt.

Pensum: Kap. 6 — Lagring

Spørsmål 22 2 poeng Kap. 8

En extendible hash-directory har global depth (GD) = 3 og 4 distinkte buckets. Local depths (LD) for de fire bucketene er 3, 3, 2, 1. Hvor mange directory-entries peker til bucketen med LD = 1?

Vis fasit

Riktig svar: C

Med GD=3 har directoryen 2³ = 8 entries totalt. Hver bucket med LD=k får 2^(GD−LD) = 2^(3−k) entries pekende til seg.
LD=3: 2⁰ = 1 entry × 2 = 2 entries
LD=2: 2¹ = 2 entries × 1 = 2 entries
LD=1: 2² = 4 entries × 1 = 4 entries
Sjekk: 2 + 2 + 4 = 8 ✓.

A antar feilaktig at hver bucket har 1 entry. B mistenker LD=2-bucketens andel. D antar at LD=1 dekker hele directoryen — men den deler med de tre andre.

Pensum: Kap. 6 — Lagring

Spørsmål 23 2 poeng Kap. 8

Hva er hovedformålet med å "pinne" (pin) en side i buffer-poolen?

A Markere siden som nylig brukt slik at LRU ikke kaster den.
B Hindre at siden kastes ut mens noen aktivt leser/skriver den.
C Tvinge siden til å bli skrevet til disk umiddelbart.
D Reservere et bufferslot eksklusivt for denne siden permanent.

Vis fasit

Riktig svar: B

Pin-tellern øker når en operasjon trenger å garantere at siden forblir i bufferen. Når tellern er > 0, er siden låst mot evictering. Når operasjonen er ferdig, "unpinner" den (tellern minker). Nødvendig for f.eks. WAL: log må være på disk før relevant data, og data-siden må holdes pinnet til loggen er flushet.

A er forskjellen på pin og LRU-bookkeeping: pin er hardt, LRU er soft prioritering. C er FORCE-policy, ikke pinning. D er feil — pinning er midlertidig, ikke permanent.

Pensum: Kap. 6 — Lagring

Spørsmål 24 2 poeng Kap. 11

En B+-tre indeks lagrer 20 000 poster på løvnivå. Hver post er 100 bytes, blokkstørrelse 4096 bytes, fyllgrad 2/3. Hvor mange blokker er det på løvnivået?

A 666
B 740
C 741
D 800

Vis fasit

Riktig svar: C

Poster per løvblokk = floor(4096 × 2/3 / 100) = floor(27.31) = 27. Antall løvblokker = ceil(20 000 / 27) = ceil(740.74) = 741.

A er feil fyllgrad-formel (kanskje 30 poster per blokk uten fyllgrad). B glemmer å avrunde oppover. D bruker en altfor lav per-blokk-tellevariant.

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

Spørsmål 25 2 poeng Kap. 11

Med 741 løvblokker fra forrige oppgave: hver intern node lagrer (key, BlockId)-par der key=8 bytes, BlockId=4 bytes, fyllgrad 2/3. Hvor mange nivåer har treet (løvnivå pluss interne)?

A 2 nivåer (løv + rot).
B 3 nivåer.
C 4 nivåer.
D 5 nivåer.

Vis fasit

Riktig svar: B

Entries per intern blokk = floor(4096 × 2/3 / 12) = floor(227.6) = 227 (key,BlockId)-par. Fan-out er da 228 barn per intern node.
Nivå 1 (over løv): ceil(741 / 228) = 4 blokker.
Nivå 2: ceil(4 / 228) = 1 blokk (rot).
Totalt: løv (1 nivå) + nivå 1 + rot = 3 nivåer.

A er for grunt (741 løv passer ikke i 1 rot med fan-out 228). C og D overteller — fan-out 228 reduserer raskt.

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

Spørsmål 26 2 poeng Kap. 11

Hva er forskjellen på clustered og unclustered B+-tre på primærnøkkelen?

A Clustered lagrer hele radene på løvnivå; unclustered lagrer (key, RID).
B Clustered lagrer (key, RID); unclustered lagrer hele radene.
C Begge lagrer (key, RID); forskjellen er kun i sorteringsrekkefølgen til heap-filen.
D Begge lagrer hele radene; forskjellen ligger i hvor ofte indeksen oppdateres.

Vis fasit

Riktig svar: A

Clustered (også kalt index-organized eller primary index i noen bøker): løvnivået er selve dataen — hele radene lagret i sortert rekkefølge. Unclustered (sekundærindeks): løvnivået lagrer (nøkkelverdi, RID) som peker til en separat heap-fil. Konsekvens: range-spørringer på clustered er veldig billige (sekvensiell scan av løv), mens unclustered krever én heap-aksess per rad.

B er motsatt. C og D blander begrepene helt.

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

Spørsmål 27 3 poeng Kap. 11

En B+-tre løvblokk har plass til 6 nøkler og er full med [10, 20, 30, 40, 50, 60]. Vi setter inn 35. Bratsberg-konvensjonen (kompendium-kap. 10): først splittes blokken — halvparten av nøklene flyttes til en ny høyre-blokk → [10, 20, 30] og [40, 50, 60]. Deretter settes 35 inn i blokken som har plass: [10, 20, 30, 35] og [40, 50, 60]. Hva propageres opp til foreldre-noden?

A Verdien 35 (største i venstre løv etter innsetting), flyttet opp.
B Verdien 40 (minste i høyre løv), kopiert opp (forblir i løvet).
C Verdien 40 (minste i høyre løv), flyttet opp (fjernet fra løvet).
D Median 35 av de 7 nøklene (de 6 originale + den nye), kopiert opp.

Vis fasit

Riktig svar: B

Per splitt-prosedyren i Bratsberg-kompendiet (kap. 10) flyttes halvparten av nøklene til ny høyre-blokk før den nye nøkkelen settes inn. Etter at 35 er plassert i venstre-blokken, er den minste nøkkelen i høyre-blokken 40 — og det er denne separator-nøkkelen som propageres opp til foreldre-noden. På løvnivå kopieres separatoren opp (alle nøkler må fortsatt finnes på løvnivå for at sekvensiell skanning skal fungere); det skiller B+-tre fra B-tre, hvor separatoren ved indre splitt blir flyttet.

A bryter med konvensjonen — venstre-løvets største (35) blir ikke separator i denne prosedyren; det er minste i høyre-løv som blir det. Et vanlig fallgrop er å «sette inn først, deretter splitte midt på de 7 nøklene», som ville gjort 35 til separator — men det er ikke algoritmen kompendiet beskriver. C ville bryte invariansen: 40 må fortsatt være på løvnivå. D blander sammen Bratsberg-konvensjonen med standard B-tre-splitt der medianen propageres.

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

Spørsmål 28 2 poeng Kap. 11

Hvilket scenario favoriserer en LSM-tre fremfor et B+-tre?

A Workload med tilfeldige punktlesninger på et lite datasett som passer i RAM.
B Skrive-tung workload med høy throughput, der periodisk compaction er akseptabelt.
C Range-spørringer som må gi konsistente svar under samtidige lesninger.
D Workload som domineres av oppdateringer av eksisterende nøkler (in-place writes).

Vis fasit

Riktig svar: B

LSM-treet samler skriverier i en in-memory memtable og flusher dem som immutable SST-er. Skriving er sekvensiell og raskt; ulempen er at lesninger kan måtte sjekke flere SST-er, og bakgrunns-compaction kreves for å holde antallet i sjakk. Dette er en god match for write-tunge logger, tidsserie og NoSQL-stores.

A — for RAM-resident data er forskjellen liten, og B+-tre er ofte raskere på reads. C — LSM kan ha høyere read-amplification under range, så den er ikke et naturlig valg her. D — oppdateringer i LSM er "tombstones" + nye verdier, ikke in-place; dette kan tvert imot bli kostbart over tid.

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

Spørsmål 29 3 poeng Kap. 13

Heap-fil H har 800 blokker og 200 000 poster. Det finnes en unclustered B+-tre indeks på attributt X med 3 nivåer (rot + intermediate + 600 løvblokker). Spørringen er SELECT * FROM H ORDER BY X; Med 10 buffer-blokker tilgjengelig for sortering — hvilken plan har lavest I/O?

A Bruk indeksen og scan løvnivået: ~603 blokker (3 nivåer + 600 løv).
B Bruk indeksen og følg RID-er per post: ~200 600 blokker totalt.
C Ekstern merge-sort på heapen: ~4 800 blokker (3 passes × 2 × 800).
D Begge er like raske: ~5 000 blokker.

Vis fasit

Riktig svar: C

Spørringen krever alle kolonnene fra hver rad i sortert X-rekkefølge. Indeksens løvnivå inneholder kun (X, RID) — ikke selve raden. For å hente raden må vi følge RID til heap-blokk. Med unclustered indeks kan tilgrensende X-verdier ligge i vidt forskjellige heap-blokker → opptil 200 000 random heap-aksesser. Sammenlikn det med ekstern merge-sort: pass 0 lager 80 sorterte runs (800/10), så merger vi med fan-in 9. Antall passes (incl. initial): 3, totalt I/O = 2 × 800 × 3 = 4 800. Sortering vinner soleklart.

A overser at SELECT * trenger full rad — bare å scanne løvene gir ikke radene. B er korrekt på cost-tallet, men presenteres som om det "fungerer", når det faktisk er den dårligste planen. D er feil; dette er ikke et tilfelle der valgene er like.

Pensum: Kap. 7 — Queries

Spørsmål 30 3 poeng Kap. 13

Heap-fil med 1 000 blokker og 100 000 poster. Unclustered B+-tre på attributt Y, 3 nivåer (omtrent 10 løvblokker per spørring i et range-treff). Vi kjører WHERE Y > c med varierende selektivitet. Omtrent ved hvilken selektivitet begynner full scan å slå unclustered-indeksen?

A Rundt 0,1 % — full scan vinner allerede ved svært lave treffrater.
B Rundt 1 % — break-even.
C Rundt 10 % — under 10 % vinner indeksen.
D Rundt 50 % — break-even.

Vis fasit

Riktig svar: B

Indeks-kost ved selektivitet s: 3 (tre-traversering) + (s × #løvblokker) + (s × 100 000) heap-aksesser. Den dominerende termen er heap-aksesser. Full scan koster 1 000.
0,1 %: indeks ≈ 3 + 1 + 100 = 104. Indeks vinner.
1 %: indeks ≈ 3 + 10 + 1 000 = 1 013. Full scan (1 000) vinner såvidt.
10 %: indeks ≈ 10 003. Full scan vinner soleklart.

A: Indeksen vinner ved 0,1 % — for tidlig. C: Ved 10 % er full scan langt foran allerede. D: Ved 50 % er forskjellen astronomisk.

Pensum: Kap. 7 — Queries

Spørsmål 31 3 poeng Kap. 13

Vi sorterer 1 500 blokker med 12 buffer-rammer tilgjengelig. Antallet av initielle sorterte runs er nR = ceil(1500/12) = 125. Merge-graden er dM = 11 (12 − 1 utgangsbuffer). Hvor mange totale I/O-er bruker sorteringen?

A 6 000
B 9 000
C 12 000
D 15 000

Vis fasit

Riktig svar: C

Antall merge-passes = ceil(log₁₁(125)). 11² = 121 < 125, 11³ = 1331 > 125, så 3 merge-passes. Total antall passes (inkl. initial sorting pass): 1 + 3 = 4. I/O = 2 × B × passes = 2 × 1 500 × 4 = 12 000.

A og B er for lave (færre passes). D antar 5 passes, men 3 merge-passes er nok siden 11³ = 1331 >> 125.

Pensum: Kap. 7 — Queries

Spørsmål 32 3 poeng Kap. 13

Block nested loop join mellom R (200 blokker) og S (1 000 blokker), med buffer-størrelse 10 blokker. R brukes som ytre relasjon. Hvor mange blokk-leseoperasjoner i alt?

A 1 200 leseoperasjoner
B 12 000 leseoperasjoner
C 25 200 leseoperasjoner
D 200 000 leseoperasjoner

Vis fasit

Riktig svar: C

Block-NL bruker (B − 2) blokker av buffer for ytre relasjon, 1 for indre, 1 for output. Per ytre "batch" leses hele indre relasjon. Antall batches = ceil(200 / (10 − 2)) = ceil(200/8) = 25. Total I/O = |R| + 25 × |S| = 200 + 25 × 1 000 = 25 200.

A glemmer multiplisering. B antar feilaktig at vi leser S én gang per blokk i R. D er nested-loop "rad-for-rad" feil.

Pensum: Kap. 7 — Queries

Spørsmål 33 2 poeng Kap. 13

Hva er hovedforutsetningen for at en partition-hash join skal kunne fullføres uten ytterligere passes?

A Den minste relasjonen (eller hver av dens partisjoner) må passe i minne.
B Begge relasjoner må være sortert på join-attributtet.
C Join-attributtet må være primærnøkkel i én av relasjonene.
D Buffer-poolen må være større enn summen av begge relasjonene.

Vis fasit

Riktig svar: A

Hash join partisjonerer begge relasjoner med samme hash-funksjon, så bygger en hashtabell på den minste sidens partisjon (build-fase) og prober med den større (probe-fase). For at build-tabellen skal kunne bo i minne uten å spilles til disk, må hver partisjon av den minste relasjonen være ≤ buffer-størrelsen.

B beskriver sort-merge join. C er en optimalisering, ikke en forutsetning. D er sterkere enn nødvendig — vi trenger bare at den minste relasjonen passer (eller at vi rekursivt re-partisjonerer).

Pensum: Kap. 7 — Queries

Spørsmål 34 2 poeng Kap. 15

Hvilken mekanisme i et DBMS sikrer primært Durability i ACID?

A Lockingprotokoller (f.eks. 2PL).
B Constraint-sjekk (CHECK, NOT NULL, FK).
C Write-ahead logging og force-log-at-commit.
D Transaksjonsisolation (READ COMMITTED, etc.).

Vis fasit

Riktig svar: C

Durability betyr at en committed transaksjon overlever krasj. WAL sikrer dette: før commit-svar gis til klient, må alle log-poster opp til commit være på disk. Ved krasj bruker recovery (ARIES eller tilsvarende) loggen for å re-anvende endringer. Locking gir Isolation, constraints gir Consistency, og isolation levels gir Isolation.

A gir Isolation (også Atomicity sammen med abort-protokoll). B gir Consistency. D gir Isolation.

Pensum: Kap. 8 — Intro og teori

Spørsmål 35 2 poeng Kap. 16

Vurder schedule:

S: r1(X); r2(Y); w1(Y); r3(X); w2(X); c1; c2; c3

Er S konfliktserialiserbar?

A Ja, ekvivalent med serielt orden T1 → T2 → T3.
B Ja, ekvivalent med serielt orden T2 → T3 → T1.
C Nei, presedensgrafen har syklus T1 ↔ T2.
D Nei, presedensgrafen har syklus T1 → T2 → T3 → T1.

Vis fasit

Riktig svar: C

Konflikter i S:
• r1(X) før w2(X) → kant T1 → T2.
• r2(Y) før w1(Y) → kant T2 → T1.
• r3(X) før w2(X) → kant T3 → T2.
Presedensgraf har T1 → T2 og T2 → T1 — en 2-syklus mellom T1 og T2. Schedule er IKKE konfliktserialiserbar.

A og B feiler å oppdage konflikten r2(Y)/w1(Y). D legger til en falsk kant T1 → T3 (det er ingen konflikt mellom T1 og T3; begge bare leser X).

Pensum: Kap. 8 — Intro og teori

Spørsmål 36 2 poeng Kap. 16

Hvilken anomali blokkeres av READ COMMITTED men ikke av READ UNCOMMITTED?

A Lost update.
B Phantom read.
C Dirty read.
D Unrepeatable read.

Vis fasit

Riktig svar: C

Standardmatrisen for SQL isolation levels:
READ UNCOMMITTED: tillater alle anomalier, inkludert dirty reads.
READ COMMITTED: blokkerer dirty reads, men tillater unrepeatable og phantom.
REPEATABLE READ: blokkerer også unrepeatable, men kan tillate phantom.
SERIALIZABLE: blokkerer alle.

A — lost update er ikke i SQL-spec som anomali, og blokkeres typisk først ved REPEATABLE READ eller SERIALIZABLE. B — phantom blokkeres først ved SERIALIZABLE. D — unrepeatable read blokkeres først ved REPEATABLE READ.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 37 2 poeng Kap. 16

Klassifiser schedule:

S: w1(A); r2(A); w2(B); c2; c1

A Strict (og dermed også ACA og recoverable).
B ACA, men ikke strict.
C Recoverable, men ikke ACA.
D Ikke recoverable.

Vis fasit

Riktig svar: D

T2 leser A som T1 har skrevet uten å committe (dirty read). For at S skal være recoverable må T2 ikke committe før T1. Men her committer T2 før T1 → ikke recoverable. Hvis T1 nå aborterer, må T2 også rulles tilbake — men T2 har allerede committed. Inkonsistens.

A — strict ville krevd ingen dirty reads i det hele tatt. B — ACA forbyr dirty reads, men her leste T2 fra ucommitted T1. C — recoverable krever c1 før c2.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 38 3 poeng Kap. 17

Tre transaksjoner i et 2PL-system:

T1: SLock(A);  så senere XLock(B)
T2: SLock(B);  så senere XLock(C)
T3: SLock(C);  så senere XLock(A)

Etter at alle tre har tatt sin S-lås (i parallell, ingen blokkerer), forespør de samtidig sin X-lås. Hvilke transaksjoner havner i deadlock?

A Ingen deadlock — S-låser hindrer ikke X-låser.
B Kun T1 og T2.
C Kun T2 og T3.
D Alle tre — T1, T2 og T3.

Vis fasit

Riktig svar: D

X-lås er inkompatibel med S-lås (og med X). T1 vil ha XLock(B), men T2 holder SLock(B) → T1 venter på T2. T2 vil ha XLock(C), men T3 holder SLock(C) → T2 venter på T3. T3 vil ha XLock(A), men T1 holder SLock(A) → T3 venter på T1. Vente-grafen er sykel T1→T2→T3→T1: deadlock.

A bygger på en feil intuisjon: S/X-låser er inkompatible. B og C ser bare deler av sykelen.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 39 2 poeng Kap. 17

Hva er den vesentlige forskjellen på basic 2PL og strict 2PL?

A Basic 2PL bruker kun X-låser; strict 2PL bruker både S og X-låser.
B Basic 2PL har en growing- og shrinking-fase; strict 2PL holder alle X-låser til commit.
C Basic 2PL gjelder kun innen én transaksjon; strict 2PL gjelder på tvers.
D De er identiske; "strict" er bare et alternativt navn.

Vis fasit

Riktig svar: B

Basic 2PL: en transaksjon må først ta alle låser (growing), deretter slippe alle (shrinking) — etter første unlock kan ingen nye låser tas. Strict 2PL: i tillegg må alle X-låser beholdes til transaksjonen committer/aborter (S-låser kan slippes tidligere). Dette gir cascadeless schedules. Rigorous 2PL er enda strengere: alle låser holdes til commit.

A er feil — begge varianter bruker både S og X. C er meningsløs (2PL er en per-transaksjon protokoll, brukt av flere). D er feil — det er en reell forskjell.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 40 2 poeng Kap. 17

I et MVCC-basert system: T1 starter ved tidspunkt t=10 og tar et snapshot. T2 oppdaterer rad R (verdi 100 → 200) og committer ved t=15. T1 leser R ved t=20. Hva ser T1?

A 200 (nyeste committed verdi).
B 100 (snapshot tatt ved t=10).
C NULL (T2s commit ugyldiggjør T1s view).
D Feil — samtidig modifikasjon detektert.

Vis fasit

Riktig svar: B

Snapshot isolation: hver transaksjon ser databasen som den var ved sin start. T1 holder seg til snapshotet ved t=10 (verdi 100), uavhengig av at T2 committet senere. Dette er hovedpoenget med MVCC: read-only transaksjoner blokkerer aldri og blir aldri blokkert.

A ville være tilfellet ved READ COMMITTED. C og D er ikke MVCC-semantikk — det er kun ved write-write konflikter (mellom to oppdaterende transaksjoner) at man får abort, ikke ved en lese-transaksjon.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 41 2 poeng Kap. 17

Hvilket utsagn om sammenhengen mellom strict 2PL og ACA-schedules er sant?

A Schedule produsert av strict 2PL er garantert ACA.
B Hvis en schedule er ACA, må den være produsert av strict 2PL.
C Strict 2PL og ACA er ekvivalente — de definerer nøyaktig samme klasse.
D Strict 2PL er disjunkt fra ACA.

Vis fasit

Riktig svar: A

Strict 2PL holder alle X-låser til commit/abort. Det betyr at ingen annen transaksjon kan lese/skrive en uncommitted verdi → ingen dirty reads → cascadeless (ACA). Strict 2PL produserer faktisk strict schedules, som er en delmengde av ACA, som er en delmengde av recoverable. Hierarki: strict ⊂ ACA ⊂ recoverable ⊂ alle.

B er motsatt retning: en ACA-schedule kan være produsert av andre protokoller. C — implikasjonen går bare én vei. D er det motsatte av sannheten.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 42 3 poeng Kap. 18

ARIES-logg:

LSN  Type        Detaljer
100  BEGIN T1
105  UPDATE T1   P1, pageLSN sett til 105
110  BEGIN T2
115  UPDATE T2   P2, pageLSN sett til 115
120  CHECKPOINT  ATT={T1,T2}, DPT={P1:105, P2:115}
125  UPDATE T1   P3, pageLSN sett til 125
130  COMMIT T2
135  BEGIN T3
140  UPDATE T3   P1, pageLSN sett til 140
[CRASH her]

Hva er Dirty Page Table (DPT) etter analyse-fasen?

A {P1:105, P2:115, P3:125}
B {P1:140, P2:115, P3:125} — bruk siste LSN per side.
C {P1:105, P3:125} — P2 fjernet fordi T2 committet.
D {P3:125, P1:140} — bare nye dirty pages siden checkpoint.

Vis fasit

Riktig svar: A

DPT skal inneholde recLSN: tidligste log-LSN som potensielt påvirker en uflushet versjon av siden. Vi starter med checkpointets DPT {P1:105, P2:115}.
LSN 125 dirties P3 (ny side i DPT med recLSN=125).
LSN 130 (T2 commit) endrer ikke DPT — sider blir ikke automatisk flushet ved commit (under no-force).
LSN 140 dirties P1 igjen, men P1 har allerede recLSN=105 som er tidligere — vi beholder den.
DPT etter analyse: {P1:105, P2:115, P3:125}.

B bruker feil LSN — recLSN er tidligste, ikke seneste. C antar incorrekt at commit fluser sider (det gjør det ikke under no-force). D ignorerer at checkpointet allerede satte P1 og P2 i DPT.

Pensum: Kap. 8 — Recovery

Spørsmål 43 2 poeng Kap. 18

Samme scenario som Spørsmål 42. Etter analyse-fasen er ATT (Active Transaction Table) = {T1, T3} (T2 committet, så fjernet). Hvilke loggposter UNDO-fasen anvender invers operasjon på (i hvilken rekkefølge)?

A 105 og 125 (kun T1s).
B 140 (kun T3s).
C 140, 125, 105 (alle taperes operasjoner i omvendt rekkefølge).
D 105, 125, 140 (alle taperes operasjoner i original rekkefølge).

Vis fasit

Riktig svar: C

UNDO-fasen rygger alle losers (uncommittede transaksjoner ved krasj) tilbake. Losers her: T1, T3. UNDO går baklengs gjennom loggen for å sikre at avhengigheter respekteres: starter ved siste loser-update (140) og jobber bakover (140 → 125 → 105). Hver UNDO skriver en CLR for å være idempotent ved senere krasj under recovery.

A glemmer T3. B glemmer T1. D undør i feil rekkefølge — fremover kan bryte avhengigheter (selv om for disse uavhengige sidene ville sluttresultatet vært det samme, gjør protokollen alltid bakover).

Pensum: Kap. 8 — Recovery

Spørsmål 44 2 poeng Kap. 18

Hva er sant om Compensation Log Records (CLR) i ARIES?

A CLR registrerer en vellykket commit og forbereder å glemme transaksjonen.
B CLR skrives under UNDO og kan selv aldri rulles tilbake (de inneholder en "UndoNextLSN").
C CLR skrives under REDO når tapt arbeid re-anvendes.
D CLR brukes for å spore lesninger til snapshot isolation.

Vis fasit

Riktig svar: B

CLR (Compensation Log Record) skrives når UNDO ruller tilbake en operasjon. Hver CLR inneholder en "UndoNextLSN" som peker på neste LSN som skal undoes for denne transaksjonen. Hvis recovery krasjer midt i UNDO og må starte på nytt, hopper systemet over allerede undone operasjoner ved å følge UndoNextLSN-kjeden — derfor er CLR redo-only og kan aldri selv undoes (det ville være å "undo en undo", som ikke gir mening).

A beskriver COMMIT- eller END-record. C er feil — REDO re-anvender originale UPDATE-poster, ikke CLR. D er fra MVCC-verden, ikke ARIES-recovery.

Pensum: Kap. 8 — Recovery