Avsluttende eksamen 2025

Problem 1 — B+-trær 5 % Kap. 6

Vi har et clustered B+-tre hvor vi setter inn 20 200 studentposter à 120 byte. Nøkkelen studNr er 4 byte, RecordID er 12 byte, BlockId er 8 byte, blokken er 4096 byte. Hvor mange blokker finnes på løvnivå (level=0) etter at alle postene er satt inn? Anta 2/3 fyllgrad.

A 571
B 919
C Ingen av de andre alternativene er riktige
D 5000
E 22
F 595

Vis fasit

Riktig svar: B

Tilgjengelig plass per blokk: 4096 · 2/3 ≈ 2730 byte. Poster per blokk: floor(2730 / 120) = 22. Løvblokker: ceil(20200 / 22) = 919.

I et clustered tre lagres hele postene på løvnivå.

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

Problem 2 — B+-tre level 1 5 % Kap. 6

Samme oppsett som Problem 1. Hvor mange blokker finnes på level=1 i B+-treet?

A 3
B 2
C 5
D 4
E 1
F Ingen av de andre alternativene er riktige

Vis fasit

Riktig svar: C

Index-records (key + BlockId) er 4 + 8 = 12 byte. Med 2/3 fyllgrad: floor(2730 / 12) = 227 entries per blokk på indre nivå. Level 1 trenger én entry per løvblokk: ceil(919 / 227) = 5.

Du kan også regne det med full kapasitet: floor(4096/12) = 341, deretter 341 · 2/3 ≈ 227 — samme resultat.

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

Problem 3 — Access paths 5 % Kap. 7

Clustered B+-tre på AnsattId: 1000 løvblokker, 3 nivåer. Unclustered B+-tre på EtterNavn: 500 løvblokker, 3 nivåer. Spørring:

SELECT EtterNavn FROM Ansatt WHERE AnsattId = 12001;

Hvor mange blokker aksesseres ved optimal utføring?

A 1002
B Ingen av de andre alternativene er riktige
C 5
D 4
E 3
F 502
G 2

Vis fasit

Riktig svar: E

Equality-oppslag på AnsattId bruker det clustered treet. 3 nivåer = 3 blokk-aksesser fra rot ned til løv. Posten ligger ferdig i løvblokken (clustered) — ingen ekstra heap-aksess.

Pensum: Kap. 7 — Spørringsutføring

Problem 4 — Access paths 5 % Kap. 7

Samme oppsett som Problem 3. Spørring:

SELECT ForNavn FROM Ansatt WHERE EtterNavn = 'Johannessen';

Anta at det finnes nøyaktig én med dette etternavnet. Hvor mange blokker aksesseres optimalt?

A Ingen av de andre alternativene er riktige.
B 502
C 1002
D 3
E 4
F 6

Vis fasit

Riktig svar: F

Bruk det unclustered treet på EtterNavn (3 nivåer = 3 blokker) for å finne AnsattId. ForNavn ligger ikke i indeksen, så vi må slå opp posten via det clustered treet på AnsattId (3 nivåer = 3 blokker). Totalt: 3 + 3 = 6.

Vi kan ikke gå direkte til en heap-blokk: i en clustered struktur er løvene B+-treets egne, så «heap-aksessen» er en traversering fra rot til løv på det clustered treet.

Pensum: Kap. 7 — Spørringsutføring

Problem 5 — Access paths 5 % Kap. 7

Samme oppsett som Problem 3. Spørring:

SELECT EtterNavn FROM Ansatt ORDER BY EtterNavn DESC;

Hvor mange blokker aksesseres optimalt?

A 6
B Ingen av de andre alternativene er riktige
C 1503
D 502
E 3
F 1002

Vis fasit

Riktig svar: D

Vi trenger bare EtterNavn, og det ligger sortert i det unclustered treet — perfekt index-only scan. Traverser fra rot til ytre løv (2 indre + 1 første løv = 3 blokker), deretter skann de resterende 499 løvblokkene baklengs via søsken-pekerne. Totalt: 3 + 499 = 502.

Vi går aldri til selve heap-tabellen, og vi bruker ikke det clustered treet (det er sortert på AnsattId, ikke EtterNavn).

Pensum: Kap. 7 — Spørringsutføring

Problem 6 — Konfliktserialiserbarhet 6 % Kap. 8

Hvilke av disse historiene er konfliktserialiserbare? (multi-select)

1 r1(B); w3(A); r3(B); w2(A); r1(A);
2 w2(A); r2(B); w1(A); w1(B); r2(B); w2(B); r3(C);
3 r1(A); r2(A); w1(A); w2(A); r3(B); w3(B);
4 r2(A); r1(B); w2(A); r3(A); w1(B); w3(A); r2(B); w2(B);
5 r2(A); w1(B); w2(A); r3(A); w2(B); w3(A); r1(B); w2(B);

Vis fasit

Riktig svar: 1 og 4

Schedule 1: Konflikter: w3(A)→w2(A) (T3→T2), w3(A)→r1(A) (T3→T1), w2(A)→r1(A) (T2→T1). Presedens: T3→T2→T1, T3→T1. Ingen sykel ⇒ konfliktserialiserbar.

Schedule 2: w2(A)→w1(A) gir T2→T1. r2(B)→w1(B) gir T2→T1, men w1(B)→r2(B) (andre opptreden) gir T1→T2. Sykel ⇒ ikke konfliktserialiserbar.

Schedule 3: r1(A)→w2(A) (T1→T2), r2(A)→w1(A) (T2→T1). Sykel ⇒ ikke konfliktserialiserbar.

Schedule 4: Edges: T2→T3 (r2(A) før w3(A); w2(A) før r3(A)/w3(A)) og T1→T2 (r1(B) før w2(B); w1(B) før r2(B)/w2(B)). Ingen sykel ⇒ konfliktserialiserbar.

Schedule 5: w1(B)→w2(B) (T1→T2) og w2(B)→r1(B) (T2→T1). Sykel ⇒ ikke konfliktserialiserbar.

Pensum: Kap. 8 — Transaksjoner: teori

Problem 7 — ARIES analyse-fase 8 % Kap. 8

Etter et krasj (ARIES). Sjekkpunkt LSN=107 hadde tx-tabell (T1, lastLSN=105, Active), (T2, lastLSN=104, Active), og DPT (A, recLSN=102), (B, recLSN=103). Hvilke elementer er med i DPT etter analysen? (multi-select)

Selve loggen er en figur i papireksamen og vises ikke her. Fasiten under følger den offisielle løsningen.

A (A, recLSN=102)
B (B, recLSN=104)
C (B, recLSN=103)
D (C, recLSN=105)
E (E, recLSN=110)
F (A, recLSN=101)
G (D, recLSN=109)
H (Commit, recLSN=111)
I Ingen av de andre alternativene er korrekte

Vis fasit

Typisk riktig svar (basert på offisiell løsning): A, C, D, E, G

Analyse-fasen: start fra DPT i sjekkpunktet, skann forover. Regler:

Update på en page som allerede er i DPT: behold opprinnelig recLSN.
Update på en ny page: legg til (page, recLSN = LSN av den loggposten).
Commit/abort/end: oppdater tx-tabell, ikke DPT.

Med tilhørende logg blir A og C fra sjekkpunktet uendret. Nye updates på C, E, D legges til med sin første LSN. B forblir på 103 (ikke 104). H er ikke en page — Commit oppdaterer tx-tabellen, ikke DPT. F endres ikke fordi A allerede har recLSN=102.

Pensum: Kap. 8 — Recovery

Problem 8 — ARIES sikkert flushed 8 % Kap. 8

Sjekkpunkt LSN=107: tx-tabell (T1, lastLSN=105, Active), (T2, lastLSN=104, Active), DPT (A, recLSN=102), (C, recLSN=105). Ved kjøring av loggpost LSN=105 ble plassen til Page B «stjålet» fra bufferet (skitten side som kastes ut skrives først til disk ved steal-policy + WAL). Hvilken page ble, som direkte følge av denne hendelsen, skrevet ut til disk? (multi-select — kun ett riktig blant sidene)

Loggen er en figur i papireksamen. Fasiten følger standard ARIES-resonnement.

A A
B Ingen av de andre alternativene er riktige
C D
D E
E B
F C

Vis fasit

Riktig svar: E (B)

Oppgaven spør hvilken blokk som måtte skrives ut i akkurat den buffer-hendelsen der plassen til B ble stjålet. Da er svaret entydig B: det er siden som evikteres, og steal krever flush før RAM-plassen kan gjenbrukes.

At en side står i DPT betyr at den fortsatt regnes som skitten ved sjekkpunktet — ikke «aldri skrevet til disk»: eldre endringer kan allerede være på disk (f.eks. kan (A, recLSN=102) oppstå ved flush mellom oppdatering LSN 101 og 102 på A). DPT alene binder ikke ett entydig svar om «som følge av steal». For C, D og E finnes ingen tilsvarende tvangsmulighet beskrevet. Derfor matcher alternativ E på lista.

Pensum: Kap. 8 — Recovery

Problem 9 — Lock setting 7 % Kap. 8

Vi har en bestemt låsetilstand (figur i papireksamen) som er resultatet av rigorous 2PL. Hvilken sekvens kunne ha produsert tilstanden?

Figuren med låsekjedene vises ikke her. Bruk fasiten til å se hvordan løsningen typisk argumenteres — den oppgitte fasiten markerer det offisielle svaret.

A r1(X); r2(X); w1(Y); r2(Y); w3(Y);
B Ingen av de andre alternativene er korrekte
C r1(X); r3(X); w1(Y); r3(Y); r2(Y);
D w3(X); r2(Y); r3(Y); r2(X); r1(X);
E w1(X); r2(X); w1(Y); r3(Y); r2(Y);

Vis fasit

Riktig svar (offisielt): C

Tankegangen: i rigorous 2PL holder hver transaksjon alle sine låser til commit. Tilstandsfiguren viser hvilke transaksjoner som holder en lås på hvert element, og hvilke som venter. Sekvensen må gi nøyaktig samme bilde av holdte/ventende låser.

Uten figuren kan du ikke avgjøre svaret eksakt — men typisk for denne typen oppgave er svaret den sekvensen der ingen tx må aborteres pga. inkompatible operasjoner, og der rekkefølgen av låser stemmer med has locks-rekkefølgen i figuren.

Pensum: Kap. 8 — Samtidighet og låser

Problem 10 — Commit-rekkefølge med rigorous 2PL 7 % Kap. 8

Sekvens som kommer inn til scheduleren:

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

I hvilken rekkefølge committer T1, T2 og T3?

A T3; T1; T2;
B T3; T2; T1;
C T2; T1; T3;
D Vi får vranglås mellom T1 og T2.
E T1; T3; T2;
F T1; T2; T3;
G Ingen av de andre alternativene stemmer
H T2; T3; T1;

Vis fasit

Riktig svar: B (T3; T2; T1)

Trace:

r1(X): T1 får S(X). r2(X): T2 får S(X) (kompatibel).
w1(X): T1 vil ha X(X), men T2 holder S(X). T1 blokkeres.
r3(Y): T3 får S(Y).
c1: T1 venter ennå — kan ikke commite.
w2(Y): T2 vil ha X(Y), men T3 holder S(Y). T2 blokkeres.
c2: T2 venter — kan ikke commite.
r3(Z): T3 får S(Z). c3: T3 commiter, frigir S(Y), S(Z). T3 først.
Nå kan T2 få X(Y), gjøre w2(Y), commite, og frigi S(X), X(Y). T2 deretter.
Til slutt får T1 X(X), gjør w1(X), commiter. T1 sist.

Ingen vranglås (ventekjeden er asyklisk: T1→T2→T3, og T3 har ingenting den venter på).

Pensum: Kap. 8 — Samtidighet og låser

Problem 11 — Normalisering 4 % Kap. 4

Tabellen Geography(CountryCode, CountryName, Population, Continent) med

F = { CountryCode → CountryName;
      CountryName → CountryCode, Population, Continent }

Antar 1NF. Finn den høyeste normalformen som tabellen oppfyller.

A 3NF
B BCNF
C 1NF
D 2NF

Vis fasit

Riktig svar: B (BCNF)

Attributthyller: {CountryCode}+ = {CountryCode, CountryName, Population, Continent} (alle), {CountryName}+ = {CountryName, CountryCode, Population, Continent} (alle). Begge er kandidatnøkler (minimale superkeys).

BCNF-test: hver venstre side i F må være supernøkkel.

CountryCode → CountryName ✓ (CountryCode er supernøkkel)
CountryName → ... ✓ (CountryName er supernøkkel)

Begge oppfyller BCNF — som er strengeste normalform i pensum. Tabellen er på BCNF.

Pensum: Kap. 4 — Normalformer

Problem 12 — BCNF-dekomponering 8 % Kap. 4

Tabell:

Exam(StudentNo, StudentName, CourseNo, CourseName,
     ExamNo, ExamDay, ExamMonth, ExamYear, Grade)

F = { StudentNo → StudentName;
      CourseNo  → CourseName;
      ExamNo    → CourseNo;
      ExamNo    → ExamDay, ExamMonth, ExamYear;
      StudentNo, ExamNo → Grade }

Splitt opp tabellen slik at alle deltabeller er på BCNF, med attributtbevaring, FD-bevaring og tapsløst-join. Begrunn.

Vis fasit

Eksempel-svar:

Kandidatnøkkel for Exam: {StudentNo, ExamNo} — beregn closure for å verifisere.

Foreslått BCNF-dekomponering (4 tabeller):

Student(StudentNo, StudentName)
       FD: StudentNo → StudentName        (PK = StudentNo)

Course(CourseNo, CourseName)
       FD: CourseNo → CourseName          (PK = CourseNo)

Exam(ExamNo, CourseNo, ExamDay, ExamMonth, ExamYear)
       FD: ExamNo → CourseNo, ExamDay, ExamMonth, ExamYear
                                          (PK = ExamNo,
                                           FK CourseNo → Course)

Result(StudentNo, ExamNo, Grade)
       FD: StudentNo, ExamNo → Grade      (PK = (StudentNo, ExamNo),
                                           FK StudentNo → Student,
                                           FK ExamNo    → Exam)

BCNF: i hver tabell er venstresiden av hver FD en supernøkkel (faktisk hele PK-en).

Attributtbevaring: union av kolonnene = de 9 originale.

FD-bevaring: alle 5 originale FD-er gjenfinnes lokalt — ingen krever join på tvers.

Tapsløst-join: hver split foregår på en supernøkkel av den ene komponenten (Chase-test eller BCNF-dekomponeringsalgoritmen garanterer dette).

Pensum: Kap. 4 — Normalformer

Problem 13 — Relasjonsalgebra 8 % Kap. 2

Skjema:

By(ByID, Navn, KommuneNr, Innbyggertall)
        -- KommuneNr FK → Kommune, NOT NULL
Kommune(KommuneNr, Navn, Innbyggertall, FylkesNr)
        -- FylkesNr  FK → Fylke,  NOT NULL
Fylke(FylkesNr, Navn, AdministrasjonsBy, Areal)
        -- AdministrasjonsBy FK → By, kan være NULL

Lag en RA-spørring som finner alle byer i Nordland fylke med ≥ 10 000 innbyggere. Resultat: (Navn, Innbyggertall), sortert synkende på Innbyggertall. Helst som RA-graf.

Vis fasit

Eksempel-svar (lineær form):

τ_{Innbyggertall DESC} (
  π_{B.Navn, B.Innbyggertall} (
    σ_{F.Navn = 'Nordland' ∧ B.Innbyggertall ≥ 10000} (
      ρ_{B}(By) ⋈_{B.KommuneNr = K.KommuneNr}
      ρ_{K}(Kommune) ⋈_{K.FylkesNr = F.FylkesNr}
      ρ_{F}(Fylke)
    )
  )
)

RA-graf (bottom-up):

Bladene: By, Kommune, Fylke (omdøpt B, K, F).
σ tidlig: σ_{Navn='Nordland'}(F) for å redusere størrelse.
σ tidlig: σ_{Innbyggertall ≥ 10000}(B).
⋈ Kommune ⋈ Fylke (filtrert) på FylkesNr → kommuner i Nordland.
⋈ By (filtrert) ⋈ resultatet på KommuneNr.
π_{Navn, Innbyggertall}.
τ_{Innbyggertall DESC} til slutt.

Push-down av selections (σ før ⋈) er en standard optimalisering som halverer eller bedre antall mellomraderr.

Pensum: Kap. 2 — Relasjonsalgebra

Problem 14 — ER-modellering: EiT 19 % Kap. 4

Lag en ER-modell for Eksperter i Team (EiT). Bruk hele pensumet (spesialisering, kategorier). Ta utgangspunkt i beskrivelsen av EiT under (oppsummert):

EiT undervises én gang per år (Årgang).
Hver Årgang har flere Landsbyer (unikt landsbynr per årgang) — svak entitet, totalt avhengig av Årgang.
Landsbytype: Langsgående eller Intensiv (spesialisering).
Lærer (PK PersonID; også AnsattID, Navn, e-post, Tittel) er Landsbyleder (1 per landsby) og kan være det for flere landsbyer/årganger.
Hver landsby har 4–6 studentgrupper (unik gruppenr per landsby) — svak entitet under landsby.
Hver gruppe har 5–7 studenter, et gruppetema som passer landsbytemaet.
Hver landsby har 2 læringsassistenter (en student som jobber på kontrakt, kun i én landsby per årgang).
Hver Årgang har én emneansvarlig (Lærer) og flere undervisningsassistenter (Student på kontrakt).
Restriksjon: en student kan ikke samtidig være student-i-emnet og assistent i samme årgang. Læringsassistent og undervisningsassistent er gjensidig utelukkende per årgang.
Hver gruppe leverer 2 Rapporter (prosjektrapport + prosessrapport) — type-attributt eller spesialisering.
Hver rapport vurderes av landsbyleder + ekstern Sensor (egen entitet, registreres i hver årgang).
Karakter og begrunnelse settes felles av leder + sensor på hver rapport. Sluttkarakter for gruppen = snitt av de to.
Kategori (union type): "Person" kan være Lærer / Student / Sensor (kategori, fordi PK-domenene kan overlappe).

Vis fasit

Eksempel-løsning (skisse — tegnes på papir):

Sterke entiteter: Aargang(aar), Lærer, Student, Sensor.

Svake entiteter: Landsby (diskriminator landsbynr, eier Aargang) og Gruppe (diskriminator gruppenr, eier Landsby).

Spesialisering: Landsby ISA (Langsgående | Intensiv) — total/disjoint.

Kategori (union): Person ∈ Lærer ∪ Student ∪ Sensor — siden samme person kan ha ulike roller i forskjellige årganger.

Relasjoner per Årgang:

EmneAnsvarligFor(Lærer, Aargang) — 1 lærer per årgang.
UndervisningsAssistent(Student, Aargang) — N:M mellom Student og Årgang.
Landsbyleder(Lærer, Landsby) — 1 lærer per landsby.
Læringsassistent(Student, Landsby) — student kun i én landsby per årgang (constraint i tekst).
TarEmnet(Student, Gruppe) — student tilhører én gruppe per årgang.

Rapport-side:

Rapport(rid, tittel, type ∈ {prosjekt, prosess}) — eies av Gruppe.
Vurdering(landsbyleder: Lærer, sensor: Sensor, karakter, begrunnelse) — knyttet til Rapport (en vurdering per rapport).
SensorerForÅrgang(Sensor, Aargang) — pool av tilgjengelige sensorer.

Constraints i tekst (kan ikke uttrykkes i ER):

En student kan ikke være TarEmnet og samtidig (Læringsassistent ∨ Undervisningsassistent) i samme Aargang.
Læringsassistent og Undervisningsassistent er gjensidig utelukkende per årgang.
Gruppestørrelse 5–7; landsbyantall typisk 30 studenter; 2 læringsassistenter per landsby.
Sluttkarakter = snitt av de to rapportkarakterene.

Tegn diagrammet med svake entiteter (dobbel ramme), ISA-trekant for landsbytypene, og halvsirkel-symbol for kategori-union over Person.

Pensum: Kap. 4 — ER-modellen · Kap. 4 — ER til relasjon