Øvingseksamen 10 · TDT4145

Øvingseksamen 10

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

Bredt sett (44 oppgaver). Hovedfokus: theta-join, division, EXISTS-semantikk, GRANT-cascade, M:N-aggregering, BCNF-dekomponering, minimum cover, sort-merge join, fuzzy checkpoint, deadlock-prevention og ARIES winners/losers.

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

Konseptspørsmål, RA-utregninger, SQL-resultater, ER og normalformer. Vinklingen er forskjellig fra tidligere sett.

Spørsmål 1 2 poeng Kap. 1

Hva er den primære fordelen et DBMS gir over et flatt filsystem for applikasjoner som lagrer strukturert data?

A Filsystemet garanterer ACID-egenskaper på tvers av prosesser; DBMS er en optimaliseringslag oppå.
B DBMS leverer samtidighetskontroll, recovery, integritetsbetingelser og deklarative spørringer som applikasjonen ellers måtte implementere selv.
C DBMS er alltid raskere enn filsystem for store filer fordi det bruker B+-trær internt.
D DBMS bruker mindre minne enn fil-baserte applikasjoner siden den deduplisererer rader automatisk.

Vis fasit

Riktig svar: B

DBMS adresserer fundamentale problemer i fildatahandtering: tap av oppdateringer ved samtidighet, redundans, integritetsbrudd, fravær av recovery, og lavnivå-tilgang. Det tilbyr ACID-transaksjoner, deklarative spørringer (SQL) og en datamodell som lar applikasjoner uttrykke hva de vil ha, ikke hvordan det skal lagres.

A er motsatt: filsystemet gir ikke ACID på tvers av prosesser. C er for enkel — DBMS kan være raskere ved høyt-konkurrerende workload pga. sin caching og indeksering, men ikke alltid. D er en oppspinning.

Pensum: Kap. 1 — Introduksjon

Spørsmål 2 2 poeng Kap. 2

Uttrykket R ⋈_{R.x < S.y} S betegner:

A En natural join som finner par der x og y har samme verdi.
B En equi-join der join-attributtet er x = y.
C En theta-join med predikat R.x < S.y.
D En semi-join som returnerer kun R-rader med en match i S.

Vis fasit

Riktig svar: C

Theta-join er en generalisering av equi-join der join-predikatet kan være hvilken som helst boolsk uttrykk over attributtene fra R og S — ikke bare likhet. Subskripten på ⋈ angir akkurat hvilket predikat som brukes. ⋈_{R.x < S.y} = σ_{R.x < S.y}(R × S).

A — natural join krever felles attributter, ikke et eksplisitt predikat. B — equi-join bruker likhet, ikke ulikhet (<). D — semi-join uttrykkes ikke med ⋈-symbolet alene; den projiserer til kun R sin attributter.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 3 3 poeng Kap. 2

Gitt:

R
a
1
3
5
7

S
b
2
4

Hvor mange tupler returnerer R ⋈_{R.a > S.b} S?

Vis fasit

Riktig svar: B

Sjekk hvert par (a, b):
(1,2): 1>2? Nei.
(1,4): 1>4? Nei.
(3,2): 3>2? Ja. ✓
(3,4): 3>4? Nei.
(5,2): 5>2? Ja. ✓
(5,4): 5>4? Ja. ✓
(7,2): 7>2? Ja. ✓
(7,4): 7>4? Ja. ✓
Totalt 5 par tilfredsstiller predikatet.

A glemmer ett par. C dobler-teller eller inkluderer en feil. D er hele kartesisk produktet (4×2=8) uten predikatfilter.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 4 2 poeng Kap. 3

Hvilket utsagn om GROUP BY i standard SQL er korrekt?

A SELECT-listen kan inneholde ikke-aggregerte kolonner som ikke er nevnt i GROUP BY.
B Hver ikke-aggregert kolonne i SELECT må også være med i GROUP BY-klausulen.
C HAVING må syntaktisk komme før GROUP BY i klausulrekkefølgen.
D ORDER BY er obligatorisk når man bruker GROUP BY for å sikre deterministisk resultat.

Vis fasit

Riktig svar: B

I standard SQL må hver kolonne som vises i SELECT enten være (a) et aggregat eller (b) nevnt i GROUP BY. Hvis ikke, er resultatverdien udefinert (hvilken rad i gruppen skal man velge?). Noen DBMS-er (eldre MySQL) er mer permisjive, men det er en avvik fra standard.

A er feil iht. standard. C — GROUP BY kommer før HAVING (FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY). D — ORDER BY er aldri obligatorisk.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 5 3 poeng Kap. 3

Skjema:

artist(aid, navn)
sang(sid, aid, avspillinger)

Tabellinnhold (avspillinger per artist):

artist	antall sanger
Anna	8
Bob	3
Cara	10
Dan	5

Hvor mange rader returnerer:

SELECT a.navn, COUNT(*) FROM artist a
JOIN sang s ON a.aid = s.aid
GROUP BY a.navn
HAVING COUNT(*) > 5;

A 0 rader
B 1 rad
C 2 rader
D 4 rader

Vis fasit

Riktig svar: C

JOIN gir én rad per (artist, sang)-kombinasjon. GROUP BY navn samler radene per artist; COUNT(*) teller sanger. HAVING COUNT(*) > 5 holder igjen Anna (8) og Cara (10). Bob (3) og Dan (5) faller bort. Resultat: 2 rader.

A er for streng. B glemmer enten Anna eller Cara. D bruker ingen HAVING-filter (alle 4 ville passert).

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 6 2 poeng Kap. 3

Tabell t1.x = {1, 2, 2, 3} og t2.x = {2, 4}. Hvor mange rader returnerer SELECT x FROM t1 UNION SELECT x FROM t2;?

Vis fasit

Riktig svar: B

UNION (uten ALL) fjerner duplikater. Slått sammen og deduplisert: {1, 2, 3, 4} = 4 rader.

A glemmer at vi har 4 distinkte verdier (1, 2, 3, 4). C overser deduplisering av "2"-en som finnes både i t1 og t2. D er UNION ALL-resultatet (4 + 2 = 6) som beholder duplikater.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 7 2 poeng Kap. 3

Skjema og data:

artist(aid, navn): {(1,'Anna'), (2,'Bob'), (3,'Cara'), (4,'Dan')}
sang(sid, aid, avspill):
  Annas sanger: avspill = {500, 1500}
  Bobs sanger: avspill = {200, 300}
  Caras sanger: avspill = {1500, 2000}
  Dan har ingen sanger

Hvilke artister returneres av:

SELECT a.navn FROM artist a
WHERE EXISTS (SELECT 1 FROM sang s
              WHERE s.aid = a.aid AND s.avspill > 1000);

A Alle fire artister.
B Anna og Cara (har minst én sang > 1000).
C Kun Cara (alle hennes sanger er > 1000).
D Ingen artister (Dan mangler sanger og bryter EXISTS).

Vis fasit

Riktig svar: B

EXISTS returnerer TRUE hvis subspørringen produserer minst én rad. For hver artist sjekker vi om det finnes minst én sang med avspill > 1000:
Anna: har 1500 → ja.
Bob: max 300 → nei.
Cara: har 1500, 2000 → ja.
Dan: ingen sanger → ingen treff.

A overser EXISTS-filtreringen. C krever at alle sanger > 1000 (det krever NOT EXISTS-mønster eller ALL-kvantor). D blander EXISTS med en sterkere betingelse.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 8 2 poeng Kap. 3

Bruker A har gitt GRANT SELECT ON tabell TO B WITH GRANT OPTION. B har deretter gitt GRANT SELECT ON tabell TO C. Nå utfører A: REVOKE SELECT ON tabell FROM B CASCADE. Hvilke privilegier blir igjen?

A Kun B mister tilgang; C beholder sin SELECT.
B Både B og C mister SELECT-tilgangen.
C Kun C mister tilgang; B beholder sin egen SELECT.
D Ingen mister tilgang — REVOKE forplanter seg ikke uten direkte relasjon.

Vis fasit

Riktig svar: B

CASCADE-formen av REVOKE fjerner ikke bare det privilegiet som direkte gis tilbake (B), men også alle privilegier B har gitt videre på basis av sin egen tildeling (C). Dette sikrer integriteten i autorisasjonshierarkiet — uten det kunne C beholde tilgang via en kjede med slettet rot.

A og C ser bare halvparten. D ignorerer CASCADE-keywordet helt; det er nettopp denne forplantingen som er hele poenget.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 9 2 poeng Kap. 3

Vi setter inn en rad i en tabell som har: (i) en BEFORE INSERT-trigger som modifiserer NEW-raden, (ii) en CHECK-betingelse på en kolonne, og (iii) en AFTER INSERT-trigger som logger til revisjonstabell. I hvilken rekkefølge utføres disse?

A CHECK → BEFORE → AFTER.
B BEFORE → CHECK → AFTER.
C BEFORE → AFTER → CHECK.
D AFTER → CHECK → BEFORE.

Vis fasit

Riktig svar: B

BEFORE-triggeren kjører først og kan modifisere NEW-raden (f.eks. sette default eller normalisere). Deretter validerer DBMS-et constraint-betingelser (CHECK, NOT NULL, FK, UNIQUE) på de endelige verdiene. Hvis alt godkjent, settes raden inn fysisk og AFTER-triggeren kjøres til slutt.

A — CHECK må komme etter BEFORE (ellers kan trigger-modifikasjoner brekke constraints). C — AFTER kjøres aldri før constraint-sjekk. D er full omvendt rekkefølge.

Pensum: Kap. 3 — Prosedyrer, triggere, rekursjon

Spørsmål 10 2 poeng Kap. 3

Vi har CREATE INDEX idx ON tabell(x, y). Hvilken spørring drar mest nytte av denne indeksen?

A WHERE y = 5 alene.
B WHERE x = 5 AND y > 10.
C WHERE x > 5 AND y = 10.
D WHERE y = 5 OR x = 10.

Vis fasit

Riktig svar: B

I en composite indeks (x, y) er rader sortert leksikografisk: først på x, så på y for samme x. x = 5 AND y > 10 kan navigere direkte til x=5-segmentet og deretter scanne y > 10 sekvensielt.

A — uten å vite x kan ikke indeksen brukes effektivt; man må fullskanne. C — x > 5 dekker mange x-verdier, så y = 10 er ikke sammenhengende; indeks gir noe nytte men ikke som B. D — OR med kolonne som ikke er prefiks gir generelt fullskan.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 11 2 poeng Kap. 3

parent.id er PK referert av child.parent_id via FK med ON UPDATE CASCADE. Vi utfører UPDATE parent SET id = 9 WHERE id = 5; Hva skjer med child-rader som peker på 5?

A UPDATE avvises — primærnøkler kan ikke endres når de refereres.
B Berørte child-radenes parent_id oppdateres automatisk fra 5 til 9.
C Child-radene slettes (CASCADE betyr alltid sletting).
D Databasen ignorerer endringen og lar child-rader peke på den gamle verdien.

Vis fasit

Riktig svar: B

ON UPDATE CASCADE betyr at endringer i den refererte kolonnen (her parent.id) automatisk forplanter seg til alle FK-kolonner som peker på den (child.parent_id). Dette holder referensiell integritet uten manuell intervensjon.

A er feil — CASCADE er nettopp tillatelsen til å endre. C blander sammen ON UPDATE med ON DELETE. D ville bryte FK-betingelsen og er ikke noen DBMS' atferd.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 12 3 poeng Kap. 4

Vi modellerer Bruker M:N Spilleliste, med relasjons-attributtet lagtTil (tidspunkt brukeren la til spillelisten). Hvor mange tabeller trenges i relasjonsskjemaet, og hvor lagres lagtTil?

A 2 tabeller; lagtTil lagres i Spilleliste-tabellen.
B 2 tabeller; lagtTil lagres i Bruker-tabellen.
C 3 tabeller (Bruker, Spilleliste, og Bruker_Spilleliste-koblingstabell); lagtTil lagres i koblingstabellen.
D 4 tabeller — én ekstra "metadata"-tabell utelukkende for lagtTil.

Vis fasit

Riktig svar: C

En M:N-relasjon kan ikke representeres ved fremmednøkkel i en av de to entitetstabellene (det ville krevd flere verdier per rad). Standardteknikken er en koblingstabell Bruker_Spilleliste(brukerId, spilleId, lagtTil) med PK = (brukerId, spilleId) og FK-er til Bruker og Spilleliste. Relasjonsattributter lagres her — naturlig sted siden de hører til kombinasjonen, ikke til entitetene alene.

A og B antar at attributtet kan ligge i én av de to entitetene; men én bruker kan ha flere lister med ulike lagtTil, og motsatt. D er overdreven; én tabell holder.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 13 2 poeng Kap. 4

I en database modelleres at "et lag spiller i en serie", og at denne (lag, serie)-relasjonen i sin tur kan motta sponsing fra en bedrift. Hvilken ER-konstruksjon brukes typisk for å modellere dette?

A Svak entitet — relasjonen mangler egen nøkkel.
B ISA-hierarki — relasjonen er en spesialisering av en entitet.
C Aggregering — relasjonen "spiller i" pakkes som en høyere-nivå entitet som kan delta i ny relasjon (sponsing).
D Sammensatt attributt — sponsing modelleres som et attributt med flere komponenter.

Vis fasit

Riktig svar: C

Aggregering i ER-modellen lar deg behandle en hel relasjon (med deltakende entiteter) som om den var en entitet, slik at den kan delta i en ny relasjon. Dette modellerer "relasjon-på-relasjon" uten å oppfinne en kunstig entitet.

A — svak entitet er en entitet uten egen primærnøkkel, ikke det samme. B — ISA er et generaliserings/spesialiserings-hierarki mellom entiteter. D — sammensatt attributt er en strukturert verdi i én entitet, ikke en mekanisme for relasjons-deltakelse.

Pensum: Kap. 4 — ER-modellen

Spørsmål 14 2 poeng Kap. 4

"Hvert kurs har nøyaktig én underviser; en underviser kan undervise ett eller flere kurs." I (min, max)-notasjon mot relasjonen Underviser-Kurs:

A Underviser (1, N), Kurs (1, 1).
B Underviser (0, N), Kurs (1, 1).
C Underviser (1, 1), Kurs (1, N).
D Underviser (0, 1), Kurs (1, N).

Vis fasit

Riktig svar: A

Sett fra Kurs-siden: hvert kurs deltar i nøyaktig 1 relasjons-instans → (1, 1). Sett fra Underviser-siden: en underviser deltar i 1 til N → (1, N). "ett eller flere" innebærer minst 1 (total deltakelse).

B antar at underviser kan ha 0 kurs (men teksten sier "ett eller flere"). C bytter rollene. D antar partial deltakelse fra underviser.

Pensum: Kap. 4 — ER-modellen

Spørsmål 15 3 poeng Kap. 4

R(A, B, C, D) med F = {A → B, B → C, C → D}. Hvilken dekomponering er både lossless og dependency-preserving og i tillegg har alle delrelasjoner på BCNF?

A {(A,B,C), (C,D)}: lossless og dependency-preserving, men (A,B,C) er ikke BCNF.
B {(A,B), (B,C), (C,D)}: lossless, dependency-preserving, alle delrelasjoner BCNF.
C {(A,B,C,D)}: vi beholder R, men R selv er ikke BCNF.
D {(A,B), (C,D)}: ikke lossless siden B og C ikke er felles.

Vis fasit

Riktig svar: B

Først: Kandidatnøkkelen til R er {A} (siden A⁺ = ABCD). Brudd på BCNF: B → C (B ikke superkey) og C → D (C ikke superkey).
Dekomponering {(A,B), (B,C), (C,D)}:
• (A,B) med FD A→B: A er nøkkel → BCNF.
• (B,C) med FD B→C: B er nøkkel → BCNF.
• (C,D) med FD C→D: C er nøkkel → BCNF.
Alle tre FD-er er bevart, og lossless-join holder (felles attributt B mellom (A,B)/(B,C), C mellom (B,C)/(C,D)).

A bevarer dependencies men (A,B,C) inneholder fortsatt B → C med B ikke-superkey → ikke BCNF. C er ingen reell dekomponering; R er fortsatt ikke BCNF. D mister C → D fra dekomponeringen og er ikke lossless.

Pensum: Kap. 4 — Normalformer

Spørsmål 16 2 poeng Kap. 4

Hvilket av følgende skjemaer bryter med 2NF (men er på 1NF)?

A R(empId, navn, deptId), PK = empId, FD: deptId → navn (transitiv).
B R(ordreId, prodId, antall, prodNavn), PK = (ordreId, prodId), FD: prodId → prodNavn.
C R(navn, alder), PK = navn, ingen andre FD-er.
D R(empId, deptId), PK = empId, FD: empId → deptId.

Vis fasit

Riktig svar: B

2NF krever at ingen ikke-prim attributt er delvis avhengig av en kandidatnøkkel (dvs. avhenger av en del av nøkkelen). I (B) er PK = (ordreId, prodId) og prodNavn avhenger kun av prodId — en delvis avhengighet av en sammensatt PK. Dette bryter 2NF.

A bryter 3NF (transitiv via deptId), ikke 2NF — siden PK er enkel (empId), kan det ikke være partielle avhengigheter. C er på BCNF (eneste FD er triviell). D er også BCNF (FD-en har PK på venstre side).

Pensum: Kap. 4 — Normalformer

Spørsmål 17 2 poeng Kap. 4

Gitt F = {A → B, B → C, A → C, AB → D}. Hvilket sett er en minimum cover av F?

A {A → B, B → C, A → C, AB → D} (F er allerede minimal).
B {A → B, B → C, A → D}.
C {A → B, A → C, A → D, AB → D}.
D {A → B, B → C, AB → D}.

Vis fasit

Riktig svar: B

Steg 1 (RHS som enkelt-attributter): allerede oppfylt. Steg 2 (eliminer redundante FD-er): A → C er implisert av A → B sammen med B → C — fjern den. Steg 3 (reduser venstresider): AB → D — er A alene tilstrekkelig? A⁺ i den reduserte mengden = {A, B, C}, så B er fjernbart fra venstresiden. AB → D blir A → D. Resultat: {A → B, B → C, A → D}.

A glemmer både redundansen (A→C) og forenklingen av AB→D. C beholder den redundante A → C og originale AB → D. D forenkler ikke AB → D til A → D.

Pensum: Kap. 4 — Normalformer

Spørsmål 18 2 poeng Kap. 4

R(A,B,C,D) med F = {A→B, B→C, C→D} dekomponeres til R1(A,B) og R2(B,C,D). Hvilken egenskap har dekomponeringen?

A Lossless og dependency-preserving.
B Lossless, men ikke dependency-preserving.
C Dependency-preserving, men ikke lossless.
D Verken lossless eller dependency-preserving.

Vis fasit

Riktig svar: A

Lossless test: R1 ∩ R2 = {B}. Trenger vi at B → R1\R2 = {A} eller B → R2\R1 = {C, D}? B → C (gitt), og B → C → D, så B → CD. Dekomponeringen er lossless.
Dependency-preservation: A → B er i R1, B → C i R2, C → D i R2. Alle FD-er kan håndheves lokalt → bevart.

B og C glemmer ett av kriteriene. D er feil på begge.

Pensum: Kap. 4 — Normalformer

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

Lagring, indeksering, queries, transaksjoner og recovery. Vinklingene varierer fra tidligere sett.

Spørsmål 19 2 poeng Kap. 8

Hva er kostnaden for å hente en post når man har dens RID (Record ID, dvs. (sideId, slotNr))?

A O(log n) — krever indeks-oppslag før sidehenting.
B O(1) — direkte sidetilgang via sideId, deretter slot-oppslag innen siden.
C O(n) — full skan av filen er nødvendig.
D O(n log n) — avhenger av sortering på siden.

Vis fasit

Riktig svar: B

RID inneholder direkte adresse til siden, og slotNr peker på offset-arrayen i sidens header. Henting er én blokklesing pluss et O(1) slot-array-oppslag. Dette er hvorfor unclustered indeksers løv lagrer (key, RID) — etter indeks-traversering kan posten hentes med én ekstra blokklesing.

A blander seg med fremgangsmåten uten RID. C ville være tilfelle uten både indeks og RID. D er oppspinning.

Pensum: Kap. 6 — Lagring

Spørsmål 20 3 poeng Kap. 8

En heap-fil har 800 blokker og 100 000 poster. Vi kjører WHERE x = c, og det finnes ingen indeks på x. Hvor mange blokker leses ved optimal utføring?

A 100 (én per matchende rad, ved 0,1% selektivitet).
B 800 (full skan av heap-filen).
C 8 (best case-prefetch).
D 800 000 (random rad-leseoperasjoner).

Vis fasit

Riktig svar: B

Uten en indeks på x må DBMS-et lese hver blokk for å sjekke alle rader. Det er ingen måte å hoppe direkte til "rader med x = c" uten å betale for full skan = 800 blokker. Selektivitet på matching påvirker antall returnerte rader, men ikke antall leste blokker.

A regner I/O som om vi visste eksakt hvor radene var. C er en imaginær optimalisering. D er feil enhet — vi teller blokker, ikke rader, og antallet av leste blokker er begrenset av filstørrelsen.

Pensum: Kap. 6 — Lagring

Spørsmål 21 2 poeng Kap. 8

Hvilken egenskap er viktigst for en hash-funksjon brukt i statisk hashing?

A Returnerer samme bucket for nøkler med liknende verdier.
B Distribuerer nøkler uniformt over bucketene.
C Returnerer alltid laveste bucket-indeks ved kollisjon.
D Er invertibel (man kan rekonstruere nøkkelen fra hash-verdien).

Vis fasit

Riktig svar: B

Uniform fordeling minimerer overflyt-kjeder og holder forventet aksess-kost lav (~1 blokk per oppslag). Klumpede hash-verdier gir lange overflyt-kjeder og degraderer ytelsen til lineær.

A er motsatt av riktig — vi vil spre, ikke samle. C ville gjøre alle kollisjoner gå til samme bucket. D er ikke et krav for hashing — invertibilitet er kryptografi-relevant, ikke ytelsesrelevant.

Pensum: Kap. 6 — Lagring

Spørsmål 22 2 poeng Kap. 8

I et extendible hashing-skjema med GD = 2 og 3 distinkte buckets med LD-er 2, 2, 1: hvor mange directory-entries peker på bucketen med LD = 1?

Vis fasit

Riktig svar: B

GD = 2 gir 2² = 4 directory-entries totalt. Hver LD = 2-bucket får 1 entry hver (2 totalt). LD = 1-bucketen får 2^(GD−LD) = 2^(2−1) = 2 entries. Sjekk sum: 1 + 1 + 2 = 4 ✓.

A undervurderer LD = 1-andelen. C og D bommer på sumstilkravet (totalt antall entries skal være 2^GD).

Pensum: Kap. 6 — Lagring

Spørsmål 23 2 poeng Kap. 8

En heap-fil holder en separat lenkliste over delvis fulle blokker (med ledig plass). Hvorfor er denne separasjonen nyttig?

A Den reduserer I/O når DBMS-et skal finne en blokk med plass for en ny INSERT.
B Den tillater flere samtidige lesere uten låsekonflikter.
C Den reduserer minneforbruket i buffer-poolen.
D Den kreves av primærindeksen for å fungere med RID-pekere.

Vis fasit

Riktig svar: A

Uten en fri-liste måtte DBMS-et skanne filen for å finne en blokk med plass. Fri-listen lar oss umiddelbart hoppe til en kandidat-blokk. Etter INSERT, hvis blokken nå er full, fjernes den fra fri-listen og legges (implisitt) i "full"-listen.

B handler om låsing, ikke fri-liste. C — listen tar plass i blokkens header, ikke i bufferpool. D — RID-pekere fungerer uavhengig av fri-liste.

Pensum: Kap. 6 — Lagring

Spørsmål 24 3 poeng Kap. 11

35 000 poster, 120 byte per post, blokkstørrelse 8192 byte, fyllgrad 2/3. Hvor mange blokker er det på løvnivået?

A 600
B 769
C 778
D 875

Vis fasit

Riktig svar: C

Poster per løvblokk = floor(8192 × 2/3 / 120) = floor(5461 / 120) = floor(45.5) = 45. Antall løvblokker = ceil(35 000 / 45) = ceil(777.78) = 778. (Sjekk: 777 × 45 = 34 965, som er < 35 000, så vi trenger 778.)

A antar 100% fyllgrad og runder ned (35000/45 ≈ 778, men 35000/(8192/120) ≈ 35000/68 ≈ 515 — så 600 er heller ikke riktig der; A er bare en distractor uten klart utgangspunkt). B = 769 ville krevd ~46 poster per blokk, dvs. en høyere fyllgrad enn 2/3. D er en grov overestimat.

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

Spørsmål 25 3 poeng Kap. 11

En B+-tre-indeks er på composite-keyen (by, postnr). Hvilken WHERE-klausul kan effektivt utnytte indeksen for et range-treff?

A WHERE postnr BETWEEN 5000 AND 7000 — bruker postnr alene.
B WHERE by = 'Trondheim' AND postnr BETWEEN 7000 AND 7500.
C WHERE by LIKE 'Tr%' OR postnr = 7034.
D WHERE postnr = 7034 AND by = 'Trondheim' — postnr må komme før by i WHERE.

Vis fasit

Riktig svar: B

Composite-key (by, postnr) er sortert leksikografisk: først på by, deretter på postnr innen samme by. (B) bruker både prefiks-attributtet (by) til å finne alle postnr-radene for "Trondheim", og deretter en range over postnr — perfekt match.

A — uten å vite "by" er postnr ikke kontigert i løvene. Indeksen kan ikke brukes effektivt; vi må fullskanne. C — OR krever full skan over alle "by"-verdier. D — likhet AND likhet utnytter indeksen bra, men er punktoppslag, ikke range. WHERE-rekkefølgen i SQL har ikke betydning; optimizeren gjør om uansett.

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

Spørsmål 26 2 poeng Kap. 11

En splitt på løvnivået i et B+-tre kan i verste fall propagere oppover. Hvor stopper propageringen senest?

A Ved første interne node som har plass.
B Ved roten — hvis roten splittes lager vi en ny rot og treet vokser med ett nivå.
C Ved nivå 2 — over det er det aldri splitt.
D Aldri — interne noder splittes ikke i B+-trær.

Vis fasit

Riktig svar: B

Splitt-propageringen følger forelder-pekere oppover. Hver intern node som blir full når vi setter inn ny separator, splittes selv. Kjeden stopper enten ved første ikke-full intern node (A er en delvis sannhet, men ikke senest) eller ved roten. Når roten splittes, lages en ny rot med to barn — dette er den eneste måten et B+-tre vokser i høyde.

A er korrekt for typiske tilfeller, men spørsmålet spør om verste tilfelle/seneste stopp. C — ingen slik "magisk grense"; et tre kan være vilkårlig høyt. D er feil; interne noder splittes ofte.

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

Spørsmål 27 3 poeng Kap. 11

LSM-trær bruker ofte bloom filters per SST-fil. Hvilken funksjon har de?

A Komprimerer dataene i SST-filen for å redusere diskforbruk.
B Lar lese-pathen raskt utelukke SST-er som ikke kan inneholde nøkkelen, og redusere unødige diskoppslag.
C Erstatter B+-treet i memtable, slik at insert blir O(1).
D Trigger automatisk compaction når filteret når en gitt fyllgrad.

Vis fasit

Riktig svar: B

Bloom filter er en sannsynlighetsbasert "kan denne nøkkelen være i settet?"-test. Per SST holder vi et bloom-filter; ved point-lookup sjekker vi filteret først, og kan med null falske negativer slippe å lese filen hvis den definitivt ikke har nøkkelen. Dette adresserer LSM-treets "read amplification"-problem.

A — bloom filters lagrer ikke data. C — memtable bruker oftere skip-list eller B+-tre; bloom-filter er ikke et lagringsformat. D — compaction triggers fra størrelses-baserte tærskler eller tidsplaner, ikke fra bloom-filteret.

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

Spørsmål 28 2 poeng Kap. 13

Index-nested-loop join er typisk billigere enn block-nested-loop når:

A Det finnes en indeks på indre relasjons join-attributt og den ytre er liten.
B Begge relasjoner er sortert på join-attributtet.
C Den minste relasjonen passer i RAM hele veien.
D Hash-funksjonen distribuerer godt over partisjonsnøkkelen.

Vis fasit

Riktig svar: A

Index-NL gjør for hver rad i ytre relasjon ett indeks-oppslag i den indre. Det vinner når (a) det fins en indeks på indre relasjons join-attributt, og (b) ytre relasjon er liten nok til at totale antall oppslag = |R_ytre| × kost(oppslag) er mindre enn full scan av indre relasjon × |R_ytre| / blokk.

B beskriver sort-merge join. C er en hash join-forutsetning. D er hash join-teknikk.

Pensum: Kap. 7 — Queries

Spørsmål 29 3 poeng Kap. 13

Sort-merge join på R (300 blokker) og S (700 blokker), med 11 buffer-rammer. Begge relasjoner må sorteres først (de er ikke pre-sorterte). Hva er total I/O-kost?

A 1 000 (kun merge-fasen).
B 3 000 (sort R + sort S + merge).
C 5 000 (2× sortering, 2-pass for S, plus merge).
D 8 000 (skyldes ekstra hashing-pass).

Vis fasit

Riktig svar: B

Med 11 buffere kan vi lage initial runs av 11 blokker hver. R = 300 blokker → 28 runs, mergebar i én pass (10-veis fan-in: 28 → ceil(28/10) = 3 runs etter første merge → ferdig i én ekstra pass). Likeledes S = 700 → 64 runs, merger i to passes? Nei: 64 → 7 runs (i én merge-pass), så ferdig (vi merger 7 til output sammen med R i merge-fasen).
Forenklet kost: sortere hver relasjon = 2 × |R| × passes. For dette eksemplet med passes ≈ 1 hver: I/O ≈ 2 × 300 + 2 × 700 + (300 + 700) merge = 600 + 1 400 + 1 000 = 3 000.

A glemmer sortering. C overteller passes. D er hash join, ikke sort-merge.

Pensum: Kap. 7 — Queries

Spørsmål 30 2 poeng Kap. 13

Hvilken statistikk er typisk lagret i DBMS-katalogen og brukt av query-optimizeren for å estimere selektivitet?

A Antall rader, distinkte verdier per kolonne, og histogrammer over verdifordelinger.
B Hash-verdiene til hver verdi i hver kolonne.
C Komplett innhold i alle indekser (duplikat med selve indeksstrukturen).
D Brukerens spørringshistorikk for å lære hvilke planer som har vært raskest.

Vis fasit

Riktig svar: A

Optimizer-statistikk inkluderer: tabellstørrelser, kolonne-kardinalitet (distinkte verdier), eventuelle min/max, og — for nøyaktigere estimater — histogrammer som beskriver verdifordeling. Disse oppdateres periodisk via ANALYZE-kommandoen og brukes til å estimere kostnaden for hver kandidatplan.

B — hash-verdier hjelper ikke optimizeren. C ville være ekstrem redundans. D er adaptive learning-tilnærminger som finnes i noen moderne systemer, men er ikke standard katalog-statistikk.

Pensum: Kap. 7 — Queries

Spørsmål 31 2 poeng Kap. 13

Hva er hovedfordelen med pipelining mellom operatorer i en query-plan?

A Den unngår å lagre mellomresultater på disk og kan starte å produsere output før input er ferdig lest.
B Den eliminerer alle joins ved å inline dem som subqueries.
C Den krever at alle operatorer er hash-baserte for at det skal fungere.
D Den brukes kun i materialiserte views for å holde dem oppdatert.

Vis fasit

Riktig svar: A

Pipelining (a.k.a. iterator-basert eller volcano-modellen) lar én operatør sende rader rett til neste operatør gjennom en tuple-for-tuple-pipeline (next()-kall), uten mellomlagring. Dette sparer I/O og latens. Visse operatører (sort, hash join build) er "blokkerende" — de må materialisere før de kan gi ut output — men mellom blokkerende operatører kan vi pipeline.

B — inline joins er noe optimizeren gjør, ikke pipelining. C — pipelining er uavhengig av algoritme. D — pipelining brukes overalt, ikke kun for views.

Pensum: Kap. 7 — Queries

Spørsmål 32 3 poeng Kap. 16

Schedule:

S: r1(X); r2(Y); w3(X); r4(Y); w2(X); w4(Z); c1; c2; c3; c4

Er S konfliktserialiserbar?

A Ja, ekvivalent med T1 → T3 → T2 → T4.
B Ja, ekvivalent med T1 → T4 → T3 → T2.
C Nei, syklus T1 ↔ T3.
D Nei, syklus T2 ↔ T3.

Vis fasit

Riktig svar: A

Konflikter:
• r1(X) før w3(X): T1 → T3
• r2(Y) ↔ r4(Y): begge er reads — ingen konflikt
• r1(X) før w2(X): T1 → T2
• w3(X) før w2(X): T3 → T2
• w4(Z): ingen relevant konflikt med andre.
Edges: T1 → T3, T1 → T2, T3 → T2. Ingen kant til/fra T4 utenom T4 sine egne reads/writes som ikke kolliderer.
Ingen syklus. Topologisk sortering: T1 → T3 → T2 (T4 kan plasseres hvor som helst, men r4(Y) leser før w-fra-T2 hvis Y blir oppdatert; her ingen W-Y, så T4 fri). Et gyldig serielt orden er T1 → T3 → T2 → T4.

B er ikke topologisk konsistent (T3 → T2 må holde). C overser at T1 → T3 ikke har returkant. D — det er ingen konflikt mellom T2 og T3 i motsatt retning.

Pensum: Kap. 8 — Intro og teori

Spørsmål 33 2 poeng Kap. 16

Hvilken anomali beskriver phantom read?

A En transaksjon leser samme rad to ganger og får forskjellige verdier.
B En transaksjon kjører samme range-spørring to ganger og får forskjellig antall rader fordi en annen transaksjon har satt inn en rad i mellomtiden.
C En transaksjon leser uncommitted skrive-data som senere rulles tilbake.
D To transaksjoner overskriver hverandres oppdateringer pga. lost update.

Vis fasit

Riktig svar: B

Phantom read oppstår når en INSERT (eller DELETE) i en samtidig transaksjon endrer settet av rader som matcher en predikat-betingelse, slik at samme spørring returnerer ulike rader-sett innen samme transaksjon. REPEATABLE READ kan forhindre unrepeatable read (samme rad ikke endret) men ikke phantoms uten predikat-låsing eller sterkere isolation.

A er unrepeatable read. C er dirty read. D er lost update.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 34 2 poeng Kap. 17

Multi-granularity locking bruker intent locks (IS, IX, SIX). Hvorfor?

A For å la subnodene i en hierarkisk struktur arve låsene fra rotnoden automatisk.
B For å markere på høyt nivå (f.eks. tabell) at et lavere objekt (f.eks. rad) er låst, slik at en tabell-lås kan oppdage konflikten uten å sjekke alle rader.
C For å effektivisere deadlock-deteksjon ved å redusere størrelsen på vente-grafen.
D For å erstatte S- og X-låser i transaksjoner som leser hele tabeller.

Vis fasit

Riktig svar: B

Intent-låser propagerer info oppover i lås-hierarkiet. Når T1 ønsker å låse rad r i tabell T, må T1 først få IX-lås på T (intent-exclusive). Dersom T2 senere vil ha S-lås på hele T, vil T2 oppdage T1s IX-lås og blokkere — uten å sjekke hver eneste rad.

A — låser arves ikke automatisk; intent-låser tas eksplisitt. C — lås-granularitet er ikke direkte deadlock-detection. D — intent-låser supplerer S/X-låser, erstatter dem ikke.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 35 2 poeng Kap. 17

I wait-die-protokollen (en deadlock-prevention-teknikk basert på timestamps): hva skjer når en eldre transaksjon T_i trenger en lås holdt av en yngre transaksjon T_j?

A T_i aborter (dør).
B T_i venter på T_j.
C T_j aborter, T_i får låsen.
D Begge aborter samtidig.

Vis fasit

Riktig svar: B

Wait-die: eldre transaksjon venter, yngre dør. Dvs. hvis ts(T_i) < ts(T_j) (T_i er eldre), så venter T_i; hvis omvendt, så aborter T_i. Wound-wait er motsatt: eldre "sårer" (aborter) yngre.

A er wound-wait med rollene byttet. C er wound-wait. D er ingen reell protokoll.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 36 2 poeng Kap. 17

2PL (basic) garanterer:

A Konfliktserialiserbarhet, men ikke fravær av deadlock.
B Konfliktserialiserbarhet og fravær av deadlock.
C Fravær av deadlock, men ikke konfliktserialiserbarhet.
D Verken serialiserbarhet eller fravær av deadlock — det er kun en intern protokoll.

Vis fasit

Riktig svar: A

2PL (to-fase-låsing) garanterer at den resulterende schedule er konfliktserialiserbar. Men 2PL kan resultere i deadlock — to transaksjoner kan vente på hverandres låser. Conservative 2PL (alle låser ved start) unngår deadlock, men er upraktisk.

B — feil; deadlock kan oppstå. C — 2PL er nettopp for serialiserbarhet. D er en oppspinning.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 37 3 poeng Kap. 17

Schedule i et strict 2PL-system:

T1: SLock(A); read(A); XLock(B); write(B); ...
T2:                    SLock(A); read(A); XLock(B); ...

T1 har akkurat tatt SLock(A) og deretter XLock(B). T2 ber så om SLock(A) (innvilges, siden flere S-låser er kompatible). T2 ber så om XLock(B). Hva skjer?

A XLock(B) innvilges siden T1 holder kun SLock(B).
B T2 venter — T1 holder XLock(B), og X er inkompatibel med X.
C T1 må slippe XLock(B) for å unngå deadlock.
D T2 oppgraderes umiddelbart til XLock(A) i stedet.

Vis fasit

Riktig svar: B

X-X er inkompatible. T1 holder XLock(B) → T2s XLock(B) blokkeres. T2 settes i ventekø på B. Hvis T1 senere prøver å oppgradere SLock(A) til XLock(A) (mens T2 holder SLock(A)), oppstår deadlock.

A — T1 har X-lås, ikke S, på B. C er ikke en regel i 2PL; T1 holder låsen til commit (strict). D er ikke standard atferd; oppgradering må forespørres eksplisitt.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 38 2 poeng Kap. 18

ARIES bruker hvilken kombinasjon av force/no-force og steal/no-steal?

A Force, no-steal — enklest, krever ikke UNDO.
B No-force, steal — krever både UNDO og REDO, men gir maksimal fleksibilitet.
C Force, steal — krever UNDO men ikke REDO.
D No-force, no-steal — krever REDO men ikke UNDO.

Vis fasit

Riktig svar: B

ARIES bruker no-force (committede sider trenger ikke flushes umiddelbart — krever REDO ved recovery for å re-anvende endringer som ikke nådde disk) og steal (uncommittede sider kan flushes for å frigjøre buffer — krever UNDO for å rygge tilbake hvis transaksjonen aborter). Dette er det mest fleksible valget og hvorfor ARIES er kompleks.

A er den enkleste, men gir dårligst ytelse. C er sjelden brukt. D er aldri brukt — den kombinasjonen gir dårlig fleksibilitet.

Pensum: Kap. 8 — Recovery

Spørsmål 39 3 poeng Kap. 18

ARIES-logg:

LSN  Type
80   BEGIN T1
85   T1 update P1
90   BEGIN T2
95   T1 update P2
100  T2 update P3
105  COMMIT T1
110  BEGIN T3
115  T3 update P1
120  CHECKPOINT (ATT={T2,T3}, DPT={P1:115, P2:95, P3:100})
125  T2 update P4
130  T3 update P5
[CRASH]

Etter analyse-fasen, hvilke transaksjoner er winners (committed) og hvilke er losers (må undoes)?

A Winners: T1, T2; Losers: T3.
B Winners: T1; Losers: T2, T3.
C Winners: T1, T3; Losers: T2.
D Winners: ingen; Losers: T1, T2, T3.

Vis fasit

Riktig svar: B

T1 commit ved LSN 105 → winner. T2 har ikke commit-record før crash → loser, må undoes. T3 har heller ingen commit → loser. Analyse-fasen oppdaterer ATT: starter med {T2, T3} fra checkpoint, sjekker poster etter checkpoint (LSN 125, 130) — ingen ny BEGIN eller COMMIT → ATT forblir {T2, T3} ved krasj. UNDO-fasen ruller derfor T2 og T3 tilbake.

A — T2 har ikke committet. C — T3 har heller ikke. D — T1 committet før checkpoint og er ferdig.

Pensum: Kap. 8 — Recovery

Spørsmål 40 2 poeng Kap. 18

Hva er hovedforskjellen på en fuzzy checkpoint og en sharp (consistent) checkpoint?

A Fuzzy checkpoint krever at alle transaksjoner stopper midlertidig; sharp tillater fortsatt aktivitet.
B Fuzzy checkpoint skriver kun en checkpoint-record + DPT/ATT-snapshot uten å vente på flushing; sharp checkpoint stopper aktivitet og fluser alle dirty pages.
C Fuzzy checkpoint er kun for read-only databaser; sharp brukes i transaksjonelle systemer.
D Det er ingen reell forskjell — det er to navn på samme teknikk.

Vis fasit

Riktig svar: B

Sharp checkpoint stopper transaksjoner, fluser alle dirty pages og logger en checkpoint-record. Veldig dyrt for lange systemer. Fuzzy checkpoint (brukt i ARIES) lar transaksjoner kjøre videre; det skriver bare et CHECKPOINT-BEGIN, snapshot av DPT og ATT (active transactions table), og en CHECKPOINT-END. Pages flushes asynkront i bakgrunnen.

A er motsatt. C er oppspinning. D er feil — det er en reell og betydningsfull forskjell.

Pensum: Kap. 8 — Recovery

Spørsmål 41 2 poeng Kap. 18

Hvorfor er det viktig at REDO-operasjoner er idempotente i ARIES?

A For å garantere at samme rad ikke kan modifiseres to ganger.
B For at recovery-prosessen kan gjenta REDO trygt om recovery selv krasjer underveis.
C For å unngå at flere transaksjoner samtidig REDO-er samme operasjon.
D For å redusere antallet log-poster som må skrives.

Vis fasit

Riktig svar: B

Hvis recovery krasjer mens den utfører REDO, må neste recovery-runde kunne starte fra begynnelsen og gjenta REDO uten å forårsake feil. Idempotens (samme operasjon flere ganger gir samme resultat) sikres ved å sjekke pageLSN ≥ recordLSN før REDO anvendes — hvis siden allerede har LSN større eller lik record-LSN-en, hopper vi over.

A er for spesifikt og ikke poenget. C — recovery er en enkelt-tråds prosess i ARIES. D — idempotens påvirker ikke log-volumet.

Pensum: Kap. 8 — Recovery

Spørsmål 42 2 poeng Kap. 18

Group commit er en optimalisering der:

A Mange transaksjoner committer i samme database-instans for å dele cachen.
B DBMS-et samler flere transaksjoners commit-records og fluser logg-bufferen i én I/O-operasjon, slik at fsync-kostnad amortiseres.
C Flere brukere må committe samtidig for å oppfylle kvoter.
D Det er en bakgrunnsprosess som rydder commit-records hver natt.

Vis fasit

Riktig svar: B

Force-log-at-commit krever at log-bufferen flushes til disk før commit returnerer til klient. fsync er dyrt (hundre-talls mikrosek). Group commit lar flere transaksjoners commit-records vente kort tid og deretter flushes sammen, så hver fsync amortiseres over mange transaksjoner. Throughput øker dramatisk på bekostning av en liten forhøyet latency for individuelle transaksjoner.

A er ikke et reelt konsept. C er forvirring. D er ikke hvordan det fungerer.

Pensum: Kap. 8 — Recovery

Spørsmål 43 2 poeng Kap. 18

Hvor i loggen begynner REDO-fasen i ARIES?

A Ved siste log-post (vi går baklengs som UNDO).
B Ved siste checkpoint-record.
C Ved minimum recLSN i DPT etter analyse-fasen.
D Ved første log-post i loggen (full skan fra start).

Vis fasit

Riktig svar: C

recLSN i DPT er det tidligste log-LSN som potensielt kan ha endringer som ikke er flushet til disk. REDO må starte fra MIN(recLSN) for å være sikker på at ingen oppdatering går tapt.

A er UNDO-startpunkt. B er for sent — endringer dirtied før checkpoint kan også mangle på disk. D er for tidlig — sløser ressurser på poster som garantert er på disk.

Pensum: Kap. 8 — Recovery

Spørsmål 44 2 poeng Kap. 18

Hva slår WAL-protokollen (Write-Ahead Logging) fast?

A En log-post må skrives til stabil lagring før den korresponderende side-modifikasjonen flushes til disk.
B Sider må alltid skrives til disk i samme rekkefølge som de ble modifisert.
C Loggen må holdes på samme fysiske disk som dataene.
D Hver transaksjon må vente på alle tidligere transaksjoner før den committer.

Vis fasit

Riktig svar: A

WAL er fundamentet for ARIES og lignende protokoller: før en uncommitted side flushes til disk (steal-policy), må tilhørende UNDO-log-post være på stabil lagring først. Dette gir oss garanti om at recovery alltid kan rygge tilbake. WAL er også grunnlaget for force-log-at-commit: alle commit-relevante log-poster må flushes før commit-svar gis.

B er ikke et WAL-krav (sider kan flushes i hvilken rekkefølge så lenge log-rekkefølgen holdes). C er motsatt — log skal helst være på separat disk for ytelse og feiltoleranse. D er ikke WAL.

Pensum: Kap. 8 — Recovery