Øvingseksamen 01 · TDT4145

Øvingseksamen 01

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

Kun flervalgsspørsmål · Klikk et alternativ for å låse svaret og se forklaring.

Del 1 — Theodoros (~40 %)

Relasjonsmodell, SQL, ER-modellering, normalformer.

Spørsmål 1 3 poeng Kap. 2

Gitt følgende to tabeller:

A
a	b
1	x
2	y
2	z

B
b	c
x	p
y	q
y	r

Hvor mange tupler returnerer det naturlige join A ⋈ B?

Vis fasit

Riktig svar: B

Naturlig join matcher rader hvor felles attributt b er likt. Tupelet (1, x) matcher (x, p) → ett tuppel. (2, y) matcher både (y, q) og (y, r) → to tupler. (2, z) har ingen match i B og forsvinner. Resultat: 3 tupler.

A teller bare matchene fra (2, y), C/D antar at (2, z) også genererer rader (gjelder bare i full outer join eller cross product).

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 2 3 poeng Kap. 2

Hvilket utsagn om supernøkkel og kandidatnøkkel er korrekt?

A En kandidatnøkkel er en minimal supernøkkel — ingen ekte delmengde av den er selv supernøkkel.
B Enhver supernøkkel er også en kandidatnøkkel, men ikke alltid omvendt slik teorien tilsier.
C En tabell kan godt ha flere primærnøkler så lenge alle samtidig er kandidatnøkler.
D En kandidatnøkkel kan inneholde NULL-verdier mens en primærnøkkel aldri kan ha det.

Vis fasit

Riktig svar: A

En supernøkkel er enhver mengde attributter som unikt identifiserer en rad. En kandidatnøkkel er en minimal supernøkkel — ingen ekte delmengde er selv supernøkkel. Primærnøkkelen er én utvalgt kandidatnøkkel.

B snur retningen: enhver kandidatnøkkel er en supernøkkel, men supernøkler trenger ikke være minimale. C er feil — en tabell har høyst én primærnøkkel. D blander begrepene; kandidatnøkler kan i prinsippet ha NULL i SQL, men i klassisk teori behandles de likt med primærnøkler.

Pensum: Kap. 2 — Relasjonsmodellen

Spørsmål 3 3 poeng Kap. 3

Tabellen Score:

student_id	points
1	80
2	NULL
3	60
4	NULL
5	40

Hva returnerer:

SELECT COUNT(*), COUNT(points), AVG(points) FROM Score;

A 5, 5, 36
B 5, 3, 60
C 3, 3, 60
D 5, 3, 36

Vis fasit

Riktig svar: B

COUNT(*) teller alle rader: 5. COUNT(points) teller bare ikke-NULL verdier: 3 (kun 80, 60, 40). AVG(points) ignorerer NULL og regner gjennomsnitt over de 3 tellbare verdiene: (80+60+40)/3 = 60.

A behandler NULL som 0 i COUNT (feil). C behandler COUNT(*) som COUNT(points). D regner gjennomsnitt som (80+60+40)/5 = 36, dvs. inkluderer NULL i nevneren — det gjør AVG aldri.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 4 3 poeng Kap. 3

I hvilken rekkefølge evalueres logisk klausulene i en SELECT-spørring uten subqueries?

A SELECT → FROM → WHERE → GROUP BY → HAVING → ORDER BY
B FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY
C FROM → SELECT → WHERE → GROUP BY → HAVING → ORDER BY
D WHERE → FROM → GROUP BY → SELECT → HAVING → ORDER BY

Vis fasit

Riktig svar: B

Logisk evalueringsrekkefølge: først bygges FROM-resultatet (kryssprodukt + joins), deretter filtrerer WHERE rader, så grupperer GROUP BY, HAVING filtrerer grupper, SELECT projiserer attributter (og evaluerer aggregater), og til sist sorterer ORDER BY.

Dette er grunnen til at man ikke kan referere til en SELECT-alias i WHERE — WHERE evalueres før SELECT. Alternativene A, C og D bryter denne logikken.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 5 3 poeng Kap. 3

Gitt:

Customer
cid	cname
1	Alice
2	Bob
3	Carol

Ordre
oid	cid	total
101	1	50
102	1	30
103	2	90

Hvor mange rader returnerer:

SELECT * FROM Customer LEFT OUTER JOIN Ordre ON Customer.cid = Ordre.cid;

Vis fasit

Riktig svar: B

Alice (cid=1) matcher to ordre → 2 rader. Bob (cid=2) matcher én ordre → 1 rad. Carol (cid=3) matcher ingen, men beholdes i et LEFT OUTER JOIN med NULL i Ordre-kolonnene → 1 rad. Totalt: 4.

A er antall kunder (glemmer at Alice har to ordre). C antar at Carol gir 2 rader. D er størrelsen på kryssproduktet (3 × 3).

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 6 3 poeng Kap. 3

Skjema:

Student(sid, name)
Enrolled(sid, course)

Hvilken av spørringene under finner navnet på alle studenter som er meldt opp i minst ett kurs?

SELECT name FROM Student WHERE sid IN (SELECT sid FROM Enrolled);
SELECT name FROM Student s WHERE EXISTS (SELECT 1 FROM Enrolled e WHERE e.sid = s.sid);
SELECT DISTINCT s.name FROM Student s, Enrolled e WHERE s.sid = e.sid;

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

Vis fasit

Riktig svar: D

Alle tre formuleringene returnerer samme mengde studentnavn. IN-versjonen er ukorrelert subquery, EXISTS-versjonen er korrelert, og join-versjonen bruker DISTINCT for å unngå duplikater når en student har flere kursoppmeldinger. Resultatmengden er identisk.

Hadde det stått SELECT name uten DISTINCT i alternativ 3, ville den fått duplikater og vært ulik 1 og 2 — men DISTINCT retter det opp.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 7 3 poeng Kap. 3

Hva karakteriserer en updatable view i SQL?

A Alle views er updatable så lenge de spør fra én eneste tabell, uavhengig av aggregat-funksjoner i SELECT.
B En view er updatable hvis den unngår DISTINCT, GROUP BY og aggregater, og hver kolonne mapper til én ekte kolonne.
C Views kan aldri oppdateres direkte i SQL-standarden — man må alltid bruke INSTEAD OF-triggere på dem.
D En view blir automatisk updatable så snart man legger til WITH CHECK OPTION i definisjonen.

Vis fasit

Riktig svar: B

For at en view skal være updatable må DBMS-et entydig kunne oversette en INSERT/UPDATE/DELETE på viewet til operasjoner på den underliggende tabellen. Det krever blant annet ingen DISTINCT, ingen aggregater, ingen GROUP BY/HAVING og at hver synlig kolonne mapper til én ekte kolonne.

A er for liberal — en view SELECT AVG(salary) FROM Emp er ikke updatable selv om den spør fra én tabell. C overser at SQL-standarden faktisk definerer updatable views. D forveksler WITH CHECK OPTION (som håndhever at innsatte rader er synlige i viewet) med selve updatability-kravet.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 8 3 poeng Kap. 3

En trigger er definert som BEFORE INSERT FOR EACH ROW på tabell T. Hva er den vanligste, og typiske, bruken av nettopp denne trigger-typen?

A Logge alle innsettinger til en historikk-tabell etter at innsettingen er fullført.
B Validere eller transformere NEW-radens verdier før de skrives til T.
C Oppdatere aggregat-tabeller som er avhengige av den nye raden, etter at den er commit-et.
D Forhindre samtidige innsettinger fra flere transaksjoner mot T.

Vis fasit

Riktig svar: B

BEFORE INSERT-triggere kjøres før raden faktisk skrives, og kan endre eller avvise NEW-raden. Typisk bruk er å normalisere data (f.eks. lower-case e-post), fylle inn standardverdier, eller kaste en feil hvis raden ikke tilfredsstiller en forretningsregel.

A og C beskriver typiske AFTER INSERT-bruksområder — du kan ikke logge en innsetting som ennå ikke har skjedd. D er en oppgave for låsesystemet/transaksjoner, ikke triggere.

Pensum: Kap. 3 — Prosedyrer, triggere, rekursjon

Spørsmål 9 3 poeng Kap. 3

Vurder følgende rekursive spørring som finner alle indirekte ledere over en ansatt:

WITH RECURSIVE Boss(eid, mid) AS (
    SELECT eid, mid FROM Employee WHERE eid = 5
  UNION
    SELECT e.eid, e.mid FROM Employee e
    JOIN Boss b ON e.eid = b.mid
)
SELECT mid FROM Boss;

Hvilken beskrivelse av evalueringen er korrekt?

A Spørringen kjører nøyaktig to iterasjoner og avslutter, uavhengig av lederkjedens lengde.
B Anker-delen (over UNION) kjøres først, og rekursjonsdelen kjøres gjentatte ganger så lenge den produserer nye rader.
C Begge SELECT-blokkene kjøres parallelt og resultatene unioneres til slutt — rekursjon er bare en notasjon.
D Spørringen vil alltid gå i evig løkke fordi den ikke har en eksplisitt LIMIT-klausul.

Vis fasit

Riktig svar: B

Anker-delen produserer den initielle mengden av Boss-rader. Rekursjonsdelen joiner Employee mot den siste mengden Boss-rader og legger til nye rader. Dette gjentas til iterasjonen ikke produserer noen nye rader (fixed point). UNION (i motsetning til UNION ALL) sørger samtidig for at duplikater fjernes — som hindrer evig løkke ved sykler.

A er feil — antall iterasjoner er lik kjedens lengde, ikke konstant. C bryter med definisjonen av rekursjon. D ignorerer at UNION garanterer terminering så lenge grafen er endelig.

Pensum: Kap. 3 — Prosedyrer, triggere, rekursjon

Spørsmål 10 3 poeng Kap. 4

Et ER-diagram inneholder en svak entitet Dependent med diskriminator name, totalt avhengig av en sterk entitet Employee (PK ssn). Hvor mange tabeller får vi etter mapping til relasjonsmodellen, og hva blir primærnøkkelen til Dependent?

A 1 sammenslått tabell der (ssn) er PK og name blir et attributt.
B 1 sammenslått tabell der (ssn, name) tilsammen utgjør PK.
C 2 tabeller; Dependent får (name) som PK uten FK-referanse til Employee.
D 2 tabeller; Dependent får (ssn, name) som PK, og ssn er FK til Employee.

Vis fasit

Riktig svar: D

En svak entitet mappes til sin egen tabell. PK-en blir kombinasjonen av eieren (Employee.ssn) og diskriminatoren (name), og ssn fungerer samtidig som FK til Employee for å håndheve den eksistensielle avhengigheten.

A og B foreslår å slå sammen Employee og Dependent — det fjerner skillet mellom sterk og svak entitet og gir én rad per Dependent, ikke per Employee. C overser at navnet alene ikke er unikt på tvers av Employees (to ansatte kan ha en datter ved navn "Eva").

Pensum: Kap. 4 — ER til relasjon

Spørsmål 11 3 poeng Kap. 4

Et ER-diagram modellerer regelen: «Hver student leverer nøyaktig én masteroppgave; hver masteroppgave leveres av nøyaktig én student.» Hvilken kardinalitet og deltakelse er korrekt?

A M:N med total deltakelse fra Student.
B 1:N (Student → Masteroppgave) med total deltakelse fra Student.
C 1:1 med total deltakelse fra begge sider.
D 1:1 med partial deltakelse fra begge sider.

Vis fasit

Riktig svar: C

«Nøyaktig én» på begge sider gir 1:1. «Hver student leverer» og «hver masteroppgave leveres» indikerer at ingen Student eller Masteroppgave står uten kobling — altså total deltakelse fra begge sider.

A og B bryter 1:1-strukturen. D ville tillatt at en Student ikke leverte en oppgave — i strid med «hver student leverer».

Pensum: Kap. 4 — ER-modellen

Spørsmål 12 4 poeng Kap. 4

Tabellen R(A, B, C, D) har funksjonelle avhengigheter:

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

Hvilket utsagn er korrekt?

A Kandidatnøklene er {A} og {D}.
B Kandidatnøklene er {AC}, {DC} og {BC}.
C R er på BCNF.
D R bryter med 3NF på grunn av D → A.

Vis fasit

Riktig svar: B

Vi beregner attributthyller: A⁺ = {A,B} og D⁺ = {D,A,B} — ingen er supernøkler. Men AC⁺ = {A,B,C,D}, DC⁺ = {D,A,B,C}, BC⁺ = {B,C,D,A} (BC → D, deretter D → A). Alle tre er supernøkler og minimale → kandidatnøkler.

A overser at {A} ikke alene gir oss C eller D. C er feil: A → B bryter BCNF siden A ikke er supernøkkel. D er feil: D → A bryter ikke 3NF — A er prim-attributt (med i {AC} og {DC}), så regelen «høyresiden er prim-attributt» reddes.

Pensum: Kap. 4 — Normalformer

Spørsmål 13 3 poeng Kap. 3

Vi har følgende skjema:

CREATE TABLE Department (
    dept_id INT PRIMARY KEY,
    name    VARCHAR(50)
);
CREATE TABLE Employee (
    emp_id  INT PRIMARY KEY,
    name    VARCHAR(50),
    dept_id INT,
    FOREIGN KEY (dept_id) REFERENCES Department(dept_id)
        ON DELETE SET NULL
);

Hva skjer hvis vi sletter en rad fra Department som har relaterte Employee-rader?

A Slettingen avvises av DBMS-et på grunn av referensiell integritet.
B Tilhørende Employee-rader slettes også, kaskaderende fra Department.
C Tilhørende Employee-rader beholdes, og dept_id settes til NULL i hver av dem.
D En feilmelding kastes, og hele transaksjonen rulles tilbake automatisk.

Vis fasit

Riktig svar: C

ON DELETE SET NULL betyr at FK-kolonnen i de avhengige radene settes til NULL når den refererte raden slettes. Slettingen i Department lykkes, og Employee.dept_id blir NULL der den pekte på den slettede avdelingen.

A beskriver standardoppførselen ON DELETE NO ACTION / RESTRICT. B beskriver ON DELETE CASCADE. D forveksler en applikasjonsfeil med en gyldig DDL-spesifisert handling.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Del 2 — Svein Erik (~60 %)

Lagring, indekser, queries, transaksjoner og recovery.

Spørsmål 14 4 poeng Kap. 6

En tabell skal lagres som en heapfil. Postene er 200 byte hver, og det er 50 000 poster. Blokkstørrelsen er 8 KiB (8192 byte). Hvor mange blokker brukes til å lagre filen? (Anta at blokkene fylles helt.)

A 1000
B 1250
C 1500
D 2500

Vis fasit

Riktig svar: B

Antall poster per blokk: floor(8192 / 200) = 40. Antall blokker: ceil(50000 / 40) = 1250.

A bruker en optimistisk antakelse om 50 poster per blokk. C ignorerer at vi ikke kan dele poster på tvers av blokker. D dobler resultatet — tilsvarer en B+-tre-løvberegning med 2/3 fyllgrad.

Pensum: Kap. 6 — Lagring

Spørsmål 15 4 poeng Kap. 6

Et clustered B+-tre lagrer 30 000 ansattposter. Hver post er 150 byte, blokker er 4096 byte, og fyllgraden er 2/3. Hvor mange blokker er det på løvnivå (level=0)?

A 1099
B 1667
C 2000
D 5000

Vis fasit

Riktig svar: B

Tilgjengelig plass per blokk: 4096 · 2/3 ≈ 2730 byte. Poster per blokk: floor(2730 / 150) = 18. Blokker på løvnivå: ceil(30000 / 18) = 1667.

A regner uten fyllgrad (floor(4096/150) = 27, 30000/27 ≈ 1112 — feil). C bruker 15 poster per blokk. D antar 6 poster per blokk.

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

Spørsmål 16 4 poeng Kap. 6

Fortsetter fra forrige oppgave: 1667 løvblokker, 4 KiB blokker, 2/3 fyllgrad. En index-record på indre nivåer er på formen (key, BlockId) og er 12 byte. Hvor mange blokker er det på level=1?

A 4
B 8
C 12
D 24

Vis fasit

Riktig svar: B

Indeks-records per blokk på indre nivå: floor(4096 · 2/3 / 12) = floor(2730/12) = 227. Level 1 trenger én record per løvblokk: ceil(1667 / 227) = 8 blokker.

A glemmer 2/3 fyllgrad i nevneren. C runder feil. D dobler resultatet.

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

Spørsmål 17 4 poeng Kap. 6

I extendible hashing settes en ny nøkkel inn i en blokk som er full, og hvor lokal dybde er lik global dybde. Hva skjer?

A Bare den fulle blokken splittes i to; directory-en endres ikke i denne situasjonen.
B En overflow-blokk kobles på den fulle blokken og lagrer den nye nøkkelen der.
C Directory-en dobles, blokken splittes, og lokal dybde i begge nye blokker øker med én.
D Alle blokker rehasheres med en ny hash-funksjon for å fordele nøklene jevnt.

Vis fasit

Riktig svar: C

Når lokal dybde = global dybde har vi ikke nok bits i directory-indeksen til å skille de to nye blokkene. Directory-en må dobles (global dybde + 1), den fulle blokken splittes, og begge resulterende blokker får økt lokal dybde med én — slik at de matcher den nye, lengre directory-indeksen.

A er feil — uten directory-dobling kan vi ikke peke til to ulike blokker. B beskriver statisk hashing med overflow-kjeder. D er en (dyr) operasjon som er det extendible hashing er laget for å unngå.

Pensum: Kap. 6 — Lagring

Spørsmål 18 4 poeng Kap. 6

En statisk hashfil har N=10 blokker og hashfunksjon h(K) = K mod 10. Vi setter inn nøklene 23, 47, 13, 33, 5, 25. Hvor mange nøkler ender i blokk 3?

Vis fasit

Riktig svar: C

Hash-verdier: 23 mod 10=3, 47 mod 10=7, 13 mod 10=3, 33 mod 10=3, 5 mod 10=5, 25 mod 10=5. Tre nøkler (23, 13, 33) havner i blokk 3.

A teller bare den første. B glemmer enten 13 eller 33. D legger feilaktig til en av nøklene som faktisk hasher til 5.

Pensum: Kap. 6 — Lagring

Spørsmål 19 4 poeng Kap. 6

Hvilket utsagn beskriver best avveiningen mellom LSM-trær og B+-trær?

A LSM-trær har bedre lesehastighet, mens B+-trær har bedre skrivehastighet pga. sortering.
B LSM-trær har bedre skrivehastighet, mens B+-trær har bedre lesehastighet for direkteoppslag.
C LSM-trær brukes utelukkende for lesetunge analyse-arbeidslaster.
D B+-trær er ikke egnet for store datamengder; LSM er den eneste opsjonen for «big data».

Vis fasit

Riktig svar: B

LSM-trær batcher skriv i memtable og flusher store SSTabeller sekvensielt — dette gir høy skrivedurchsats og lav write amplification. B+-trær må derimot oppdatere riktig blokk på riktig sted og kan trigge mange små I/O-er ved tilfeldige innsettinger. For lesing må LSM-trær slå opp i flere SSTabeller (ofte med Bloom-filter-hjelp), mens B+-trær gir et enkelt sti-traversering.

A snur retningen. C er feil — LSM brukes nettopp i skrivetunge systemer som RocksDB, HBase, Cassandra. D er overdrevet; B+-trær brukes i nesten alle SQL-DBMS-er.

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

Spørsmål 20 4 poeng Kap. 7

Vi har et clustered B+-tre på AnsattId med 4 nivåer (rot på level=3, løv på level=0) og 1200 blokker på løvnivå. I tillegg har vi et unclustered B+-tre på etternavn med 3 nivåer og 600 løvblokker.

Hvor mange blokker leses ved optimal utføring av:

SELECT * FROM Ansatt WHERE AnsattId = 12345;

(Anta at AnsattId er unik.)

A 1
B 4
C 5
D 1200

Vis fasit

Riktig svar: B

Vi traverserer det clustered treet fra rot til løv: 4 nivåer = 4 blokk-aksesser. Selve raden ligger i løvblokken (clustered), så ingen ekstra heap-aksess er nødvendig.

A glemmer at vi må gå gjennom indre nivåer. C legger til én ekstra heap-aksess som ikke trengs i en clustered struktur. D er kostnaden for en full scan.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 21 4 poeng Kap. 7

Samme oppsett som forrige (clustered B+-tre på AnsattId, 4 nivåer, 1200 løvblokker; unclustered B+-tre på etternavn, 3 nivåer, 600 løvblokker). Hvor mange blokker leses optimalt for:

SELECT etternavn FROM Ansatt ORDER BY etternavn DESC;

A 600
B 602
C 1203
D 1800

Vis fasit

Riktig svar: B

Siden vi bare trenger etternavn, og det ligger som søkenøkkel i det unclustered treet, kan vi skanne dette treet sideveis i sortert rekkefølge — uten å gå til den clustered tabellen. Vi traverserer fra rot til ytre løv (3 blokker) og skanner deretter de resterende 599 løvblokkene. Totalt: 3 + 599 = 602.

A glemmer traverseringen ned til løvnivå. C ville ha brukt det clustered treet (mye dyrere). D dobler.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 22 4 poeng Kap. 7

Vi sorterer en fil med 800 blokker og har 6 buffere tilgjengelig. Hvor mange merge-passer (etter initial sort) trengs?

Vis fasit

Riktig svar: C

Initial-fasen produserer nR = ceil(800/6) = 134 sorterte runs. Merge-graden er dM = min(6 − 1, 134) = 5. Antall merge-passer er ceil(log₅(134)) = 4, fordi 5³ = 125 < 134 ≤ 5⁴ = 625.

A og B undervurderer høyden på merge-treet. D er én pass for mye.

Pensum: Kap. 7 — Sortering og query processing

Spørsmål 23 4 poeng Kap. 8

Hvilken av de følgende schedulene er ikke konfliktserialiserbar?

A r1(A); r2(A); w1(B); w2(B);
B r1(A); w2(A); r2(B); w1(B);
C r1(A); w1(A); r2(A); w2(A);
D w1(A); r2(A); w1(B); r2(B);

Vis fasit

Riktig svar: B

Bygg presedensgrafen for hver schedule. I B er det konflikt mellom r1(A) og w2(A) (T1→T2), og mellom r2(B) og w1(B) (T2→T1). Det danner en sykel T1↔T2 → ikke konfliktserialiserbar.

A har bare T1→T2 (via w1(B)/w2(B)), C har bare T1→T2, D har bare T1→T2. Ingen sykler — alle er konfliktserialiserbare.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 24 4 poeng Kap. 8

Vurder schedulen:

w1(X); r2(X); w2(Y); c2; c1;

Hvilket utsagn er korrekt?

A Schedulen er strict.
B Schedulen er ACA, men ikke strict.
C Schedulen er recoverable, men ikke ACA.
D Schedulen er ikke recoverable.

Vis fasit

Riktig svar: D

T2 leser X mens T1 ennå ikke har committet (dirty read). Deretter committer T2 før T1. Dersom T1 hadde abortert etter c2, ville vi ikke kunne rulle tilbake T2 — den er allerede commit-et. Det bryter recoverability-kravet om at en transaksjon må commit-e etter alle den har lest fra.

A og B krever at T2 ikke leser uncommitted data — utelukket. C krever at T2 commit-er etter T1 — også utelukket.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 25 4 poeng Kap. 8

Vi bruker rigorous 2PL. Sekvensen kommer inn til scheduleren:

r1(X); r2(X); w1(Y); r2(Y); c1; c2;

Hva skjer under utføring?

A Sekvensen utføres uten venting; alle låser er kompatible.
B T1 må vente på T2 sin lesetlås; deretter committer begge.
C T2 må vente på T1 sin skrivelås på Y; ingen deadlock.
D Det oppstår deadlock mellom T1 og T2 på Y.

Vis fasit

Riktig svar: C

r1(X) og r2(X) er kompatible (begge leselåser). w1(Y) gir T1 en eksklusiv lås på Y. Når T2 prøver r2(Y) må den vente — leselåser er ikke kompatible med en holdt skrivelås. Etter c1 frigis alle låser i T1 (rigorous), T2 får leselåsen, fullfører og committer. Ingen deadlock fordi T1 ikke trenger noe fra T2.

A overser w1(Y) som blokkerer r2(Y). B snur ventingen. D ville krevd at T1 også ventet på T2, noe som ikke skjer her.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 26 4 poeng Kap. 8

Under snapshot isolation startes T1 først, mens X har verdi 100. Mens T1 er aktiv, oppdaterer T2 X til 200 og committer. T1 leser deretter X. Hvilken verdi ser T1?

A 200 — fordi T2 har committet og endringen er synlig globalt.
B 100 — fordi T1 leser fra snapshotet tatt da T1 startet.
C NULL — fordi snapshot isolation blokkerer kollisjoner.
D Begge verdiene returneres som duplikate rader.

Vis fasit

Riktig svar: B

Hovedidéen i snapshot isolation er at hver transaksjon ser databasen slik den var ved sin egen starttid. T1 ser derfor fortsatt X = 100, selv etter at T2 har committet en ny verdi. Nye transaksjoner som starter etter T2 sin commit, vil derimot se X = 200.

A beskriver hvordan READ COMMITTED kunne oppført seg, ikke snapshot isolation. C og D er ikke realistiske utfall i noen kjent isolasjonsnivå.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 27 4 poeng Kap. 8

Vi bruker ARIES. Etter en krasj fant vi følgende logg:

LSN	PrevLSN	Tx	Op	Page
198	—	T1	Update	P1
199	—	T2	Update	P2
200	—	—	Begin_ckpt	—
201	—	—	End_ckpt	—
202	198	T1	Commit	—
203	199	T2	Update	P3
204	—	T3	Update	P1
205	203	T2	Commit	—
206	204	T3	Update	P4

End_ckpt (LSN=201) inneholder:

Tx-tabell: (T1, last=198, active), (T2, last=199, active)
DPT: (P1, recLSN=198), (P2, recLSN=199)

Hvilken DPT er korrekt etter analyse-fasen?

A (P1, 198), (P2, 199)
B (P1, 198), (P2, 199), (P3, 203), (P4, 206)
C (P1, 204), (P2, 199), (P3, 203), (P4, 206)
D (P3, 203), (P4, 206)

Vis fasit

Riktig svar: B

Vi starter fra DPT i end_ckpt og skanner forover. LSN=202 er commit (ingen DPT-effekt). LSN=203 oppdaterer P3 (ny entry: P3 → 203). LSN=204 oppdaterer P1 — P1 er allerede i DPT, så recLSN beholdes på 198 (vi vil ikke flytte recLSN fremover). LSN=205 er commit. LSN=206 oppdaterer P4 (ny entry: P4 → 206).

A glemmer alle nye dirty pages. C overskriver P1 sin recLSN — det er nettopp det vi ikke skal gjøre. D fjerner pages fra checkpointet.

Pensum: Kap. 8 — Recovery

Spørsmål 28 4 poeng Kap. 8

Etter analyse-fasen er DPT:

(P1, recLSN=198), (P2, recLSN=199), (P3, recLSN=203), (P4, recLSN=206)

Ved start av REDO-fasen leser vi P1 fra disk og finner pageLSN=204 i blokkhodet. Loggposten med LSN=198 oppdaterer P1. Skal denne loggposten redoes?

A Ja, fordi P1 finnes i DPT-tabellen etter analyse-fasen.
B Ja, fordi recLSN i DPT er lik loggpostens LSN her.
C Nei, fordi pageLSN på P1 (204) er større enn loggpostens LSN (198).
D Nei, fordi T1 allerede har committet før crashet skjedde.

Vis fasit

Riktig svar: C

REDO-testen i ARIES sier: hopp over en loggpost dersom (1) PageID ikke er i DPT, (2) DPT.recLSN > LSN, eller (3) blokkens pageLSN ≥ LSN. Her er pageLSN=204 og LSN=198 → effekten av loggpost 198 er allerede skrevet til disk, og vi skal ikke redoe den.

A og B forveksler analyse-kriterier (DPT-medlemskap) med REDO-kriteriet. D er irrelevant: ARIES gjentar historien for både winners og losers under REDO; commit-status spiller først rolle i UNDO.

Pensum: Kap. 8 — Recovery

Slutt på øvingseksamen 01.