Øvingseksamen 08 · TDT4145

Øvingseksamen 08

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

Hovedfokus: DBMS-komponenter, theta-join, RA-selvprodukt, GRANT/REVOKE-kjede, svake entiteter, ISA, kandidatnøkkel-telling. Del 2 speiler oppgavebank-stilen tett: heap, statisk og extendible hashing, B+-tre-sizing, hash-clusterscan, range-aksess, Block-NL, hash-join, sortering, snapshot isolation, 2PL, ARIES analyse + UNDO.

Del 1 — Theodoros (~40 %)

Konseptspørsmål og SQL-evaluering — speiler stilen i midtveiseksamen.

Spørsmål 1 3 poeng Kap. 1

Hvilken komponent i en database-motor er ansvarlig for å lese og skrive blokker fra disk og holde dem i et felles cache-område slik at andre komponenter kan jobbe i minne?

A Query processor.
B Lock manager.
C Transaction manager.
D Buffer manager (storage manager).

Vis fasit

Riktig svar: D

Buffer manager (en del av storage manager) holder en pool av blokker i minne. Når en spørring trenger en blokk, leser buffer manager den fra disk hvis den ikke allerede er i bufferet; modifiserte blokker skrives ut iht. caching-strategi (f.eks. LRU, ARIES no-force/steal). Dette er hva som lar query processor jobbe med "in-memory" data uten å vite om disk-detaljer.

A (query processor) parser SQL og bygger eksekverings-planer — bruker buffer manager, men håndterer ikke I/O selv. B (lock manager) håndhever 2PL-låser. C (transaction manager) koordinerer commit/abort/recovery — gir ordrer til logg og buffer, men cacher ikke blokker selv.

Pensum: Kap. 1 — Introduksjon

Spørsmål 2 3 poeng Kap. 2

Hva karakteriserer en theta-join (θ-join) i relasjonsalgebra?

A Theta-join krever at predikatet er på formen <attr> = <konstant>.
B Theta-join eliminerer duplikate kolonner (i likhet med natural join).
C Theta-join bruker et generelt boolean predikat over attributtene.
D Theta-join produserer alltid færre tupler enn et kryssprodukt.

Vis fasit

Riktig svar: C

Theta-join R ⋈_θ S er definert som σ_θ(R × S) — kryssproduktet filtrert med et generelt boolean predikat θ. Predikatet kan være likhet, ulikhet (<, >, ≠), kombinasjoner med AND/OR, og kan referere til attributter med ulike navn på begge sider.

A er en spesialform (equijoin på konstant); en θ-join er mer generell. B beskriver natural join, ikke theta-join; theta-join beholder duplikate kolonner. D er feil — om θ alltid er sant, gir θ-joinen samme antall tupler som kryssproduktet.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 3 4 poeng Kap. 2

Følgende tabell er gitt:

employee
name	salary	dept
Alice	50	1
Bob	30	2
Cathy	40	1
Dave	60	2

La e1 og e2 være to renames av employee. Hvor mange tupler returnerer:

σ_{e1.salary < e2.salary ∧ e1.dept = e2.dept}(e1 × e2)

Vis fasit

Riktig svar: B

Vi parrer hver rad e1 med hver rad e2 hvor de tilhører samme avdeling og e1.salary < e2.salary.

Avdeling 1: Alice (50) og Cathy (40). Par hvor første har lavere salary: (Cathy, Alice). 1 tuppel.

Avdeling 2: Bob (30) og Dave (60). Par: (Bob, Dave). 1 tuppel.

Sum: 2 tupler.

A (4) teller hvert par to ganger. C (6) er totalt antall par på samme avdeling uten salary-filteret. D (8) er totalt antall par hvor salaries er forskjellige (uavhengig av avdeling).

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 4 3 poeng Kap. 3

Følgende tabell er gitt:

employee
name	salary
Alice	40
Bob	35
Cathy	30
Dave	50

Hva er resultatet av spørringen?

SELECT count(*)
FROM employee AS a, employee AS b
WHERE a.salary > b.salary;

A 12
B 4
C 8
D 6

Vis fasit

Riktig svar: D

Kryssproduktet er 4 · 4 = 16 par. WHERE-predikatet a.salary > b.salary ekskluderer alle par hvor salaries er like (4 selv-par, 0 ekte ties siden alle salaries her er distinkte) og halvparten av de gjenværende.

Distinkte par: 4·3 = 12. For hvert distinkte par har én side strengt høyere salary enn den andre — så halvparten (6) tilfredsstiller predikatet.

A (12) teller alle par av distinkte rader uten retningsfilter. B (4) teller kun selv-par eller én rad per. C (8) er nær men feil — uten ties er svaret nøyaktig 6.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 5 3 poeng Kap. 3

Hvor i en SQL-spørring kan kolonnealiaser definert i SELECT (f.eks. SELECT salary*12 AS yearly) refereres?

A I WHERE.
B I FROM.
C I ORDER BY.
D I GROUP BY (alle dialekter).

Vis fasit

Riktig svar: C

Logisk evalueringsrekkefølge: FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY → LIMIT. Aliaser defineres i SELECT, så de er tilgjengelige i klausuler som evalueres etter SELECT — det er bare ORDER BY (og LIMIT). Derfor kan vi skrive ... ORDER BY yearly DESC, mens WHERE yearly > 500000 vil feile (yearly eksisterer ikke ennå).

A (WHERE) er feil — den evalueres før SELECT. B (FROM) er feil — det er der vi henter tabeller, før SELECT i det hele tatt. D (GROUP BY) er forskjellig per dialekt: SQL-standarden tillater det ikke (siden GROUP BY evalueres før SELECT), men noen dialekter (PostgreSQL, MySQL) gjør det som utvidelse. Standard SQL-svaret er ORDER BY.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 6 4 poeng Kap. 3

Skjema:

student(sid, name)
takes(sid, cid)

Hvilken SQL er ekvivalent med:

SELECT name FROM student
WHERE sid IN (SELECT sid FROM takes WHERE cid = 'DB');

SELECT s.name FROM student s
WHERE EXISTS (SELECT * FROM takes t
              WHERE t.sid = s.sid AND t.cid = 'DB');

SELECT DISTINCT name FROM student s, takes t
WHERE s.sid = t.sid
ORDER BY name;

SELECT DISTINCT name FROM student s
WHERE NOT EXISTS (SELECT * FROM takes t
                  WHERE t.cid = 'DB');

SELECT name FROM student s
LEFT JOIN takes t USING (sid)
WHERE t.cid = 'DB'
ORDER BY name;

Vis fasit

Riktig svar: A

EXISTS-formen er den klassiske ekvivalente omskrivingen av IN-subquery. Den korrelerer på t.sid = s.sid og legger til samme cid-filter inne i subqueriet. Hvis subqueriet returnerer minst én rad for en gitt student, er EXISTS sant — som er nøyaktig det IN gjør for samme sid.

B er feil — den returnerer ALLE studentnavn for hver takes-rad uavhengig av cid (ingen 'DB'-filter). C er motsatt — den returnerer studenter når ingen tar 'DB' globalt, og den korrelerer ikke på student. D er nær, men en LEFT JOIN med WHERE-filter på den joinede tabellen kan gi duplikate rader hvis en student tar 'DB' flere ganger; IN-versjonen returnerer nøyaktig én rad per matchende student.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 7 3 poeng Kap. 3

Hva betyr følgende SQL-setning?

GRANT SELECT ON employee TO alice WITH GRANT OPTION;

A Alice får SELECT-rettigheten og kan videredelegere den til andre brukere.
B Alice mister sine eksisterende rettigheter på employee.
C Alice får full kontroll over employee og kan slette tabellen.
D Alice får SELECT, men kun én gang — etter første spørring revokeres rettigheten.

Vis fasit

Riktig svar: A

WITH GRANT OPTION lar mottakeren (Alice) videregi SELECT-rettigheten til andre brukere (f.eks. GRANT SELECT ON employee TO bob;). Uten WITH GRANT OPTION kan Alice selv lese, men ikke gi andre tilgang.

B er feil — GRANT legger til en rettighet, fjerner ikke andre. C er feil — kun SELECT er tildelt; INSERT/UPDATE/DELETE/DROP er ikke inkludert. D er feil — det er ingen "engangsrettighet" i SQL.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 8 4 poeng Kap. 3

Bruker A kjører:

GRANT SELECT ON tab TO B WITH GRANT OPTION;

Bruker B kjører deretter:

GRANT SELECT ON tab TO C;

Til slutt kjører A:

REVOKE SELECT ON tab FROM B CASCADE;

Hva skjer med C sin SELECT-rettighet på tab?

A C beholder rettigheten — REVOKE påvirker bare B direkte.
B C mister rettigheten fordi hjemmelen (B) er fjernet (CASCADE).
C C får automatisk WITH GRANT OPTION i tillegg.
D Hele tabellen tab slettes som følge av CASCADE.

Vis fasit

Riktig svar: B

CASCADE-modifikatoren på REVOKE rekursivt fjerner alle videredelegerte rettigheter som hadde sin opprinnelse hos den brukeren rettigheten fjernes fra. Når B mister SELECT, mister C også sin SELECT (siden C kun fikk den fra B). Hadde C også fått SELECT direkte fra A, ville C beholdt rettigheten.

A er hvordan REVOKE RESTRICT (eller default) virker uten CASCADE — men her er CASCADE eksplisitt. C er feil — REVOKE legger ikke til rettigheter. D er feil — REVOKE påvirker rettigheter, ikke selve tabellen (det ville krevd DROP TABLE).

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 9 3 poeng Kap. 4

Hvordan mappes en svak entitet (med en identifying relationship til en sterk entitet) til relasjonsmodellen?

A Den svake entiteten kollapser inn i den sterke — én tabell totalt.
B Den svake entiteten får sin egen autonome PK uten referanse til den sterke entiteten.
C Identifying relationships kan ikke mappes til relasjonsmodellen.
D Den svake entiteten får en FK til den sterke, og PK består av partial key + FK.

Vis fasit

Riktig svar: D

Standard mapping: opprett en tabell for den svake entiteten med (1) en FK til den sterke entitetens PK, (2) den svake entitetens egne attributter inkludert "partial key" (det attributtet som diskriminerer instanser innenfor samme sterke entitet). Sammensatt PK = (sterk entitet sin PK) + (partial key).

A er feil — om vi kollapset, mister vi multiplisiteten (én sterk entitet kan ha flere svake instanser). B er feil — svake entiteter har per definisjon ikke autonomt unike attributter. C er feil — mapping er fullt mulig.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 10 3 poeng Kap. 4

Tabellen

R(A, B, C)
F = { A → B,  B → C }

Anta 1NF. Hvilken er den høyeste oppfylte normalformen?

A 1NF
B 2NF
C 3NF
D BCNF

Vis fasit

Riktig svar: B

Kandidatnøkkel: {A} (A determinerer B, B determinerer C, så A → ABC). Prim: A. Ikke-prim: B, C.

2NF: krever at ingen ikke-prim er delvis avhengig av PK. Siden PK er enkelt-attributt (A), kan ikke noen avhengighet være "delvis". 2NF oppfylt.

3NF: forbyr transitive avhengigheter PK → ikke-prim → ikke-prim. Vi har A → B → C: A er PK, B er ikke-prim, C er ikke-prim. Dette er en transitiv avhengighet og bryter 3NF.

Høyeste oppfylte: 2NF.

A (1NF) er for konservativt. C (3NF) brytes av A→B→C. D (BCNF) er enda strengere og brytes også (siden B ikke er supernøkkel).

Pensum: Kap. 4 — Normalformer

Spørsmål 11 4 poeng Kap. 4

Skjema R(A, B, C, D, E) med

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

Hvor mange kandidatnøkler har R?

Vis fasit

Riktig svar: D

FDs danner en sykel: A → B → C → D → A, så hver av A, B, C, D determinerer alle de andre. Men ingen av dem determinerer E (E er ikke på høyresiden av noen FD), så E må være med i hver kandidatnøkkel.

Sjekk: {A,E}⁺ = {A,E,B,C,D} = R ✓ (minimal). Tilsvarende for {B,E}, {C,E}, {D,E}. Alle fire er minimale supernøkler.

Kandidatnøkler: {A,E}, {B,E}, {C,E}, {D,E} = 4 stk.

A (1) ignorerer at sykelen gjør alle av A, B, C, D ekvivalente. B (2) undervurderer. C (5) er for høyt — {E} alene er ikke supernøkkel.

Pensum: Kap. 4 — Normalformer

Spørsmål 12 3 poeng Kap. 3

Hvilken trigger kjøres én gang per UPDATE-statement, uavhengig av antall rader som blir oppdatert?

A BEFORE UPDATE FOR EACH ROW.
B AFTER UPDATE FOR EACH STATEMENT.
C AFTER UPDATE FOR EACH ROW.
D BEFORE UPDATE FOR EACH ROW WHEN (...).

Vis fasit

Riktig svar: B

FOR EACH STATEMENT (også kalt "statement-level" trigger) kjører nøyaktig én gang per utløsende SQL-statement, selv om statement-en oppdaterer 1 eller 1 000 000 rader. Den har ikke direkte tilgang til NEW/OLD per rad — kun til transition tables (NEW TABLE, OLD TABLE) hvis dialekten støtter det. Statement-triggere er typisk effektive for revisjonslogger ("noen oppdaterte denne tabellen").

A og C er FOR EACH ROW — kjører én gang per påvirket rad. D er også FOR EACH ROW (med en filter-klausul). Ingen av disse er statement-level.

Pensum: Kap. 3 — Prosedyrer, triggere og rekursjon

Del 2 — Svein Erik (~60 %)

Konkrete regneoppgaver fra oppgavebanken — heap, hashing, B+-tre, access paths, joins, sortering, snapshot isolation, 2PL og ARIES.

Spørsmål 13 4 poeng Kap. 6

Vi har poster som er 600 byte store og en tabell med 8000 poster. Hvor mange blokker har vi i en heapfil når blokkene er 4096 bytes store? Anta det kun lagres hele poster i blokkene.

A 1170
B 1500
C 1333
D 1334

Vis fasit

Riktig svar: D

Poster per blokk: floor(4096 / 600) = 6. Antall blokker: ceil(8000 / 6) = ceil(1333.33) = 1334.

A (1170) er antall blokker hvis post-størrelse var 700 byte (8000/floor(4096/700)=8000/5≈1600) — feil ide. B (1500) er noe runding-feil. C (1333) bruker floor — vi må runde opp for å få plass til de siste 4 postene.

Pensum: Kap. 6 — Heapfiler

Spørsmål 14 4 poeng Kap. 6

Anta vi har følgende nøkler som skal settes inn i en statisk hash-struktur:

3, 6, 1, 4, 9, 12, 7, 10

Strukturen er tom, har 3 blokker, og hver blokk kan inneholde 2 nøkler. Vi bruker separat lenket overløp. Bruk h(K) = K mod 3. Hvor mange blokkaksesser får vi gjennomsnittlig per aksess av en tilfeldig nøkkel? Rund av til to desimaler.

A 1.00
B 1.50
C 1.25
D 1.75

Vis fasit

Riktig svar: B

Plassering etter K mod 3:

Blokk 0 (mod 3 = 0): 3, 6 — full. 9 → ovfl [9]; 12 → ovfl [9, 12].
Blokk 1 (mod 3 = 1): 1, 4 — full. 7 → ovfl [7]; 10 → ovfl [7, 10].
Blokk 2 (mod 3 = 2): tom.

Hovedblokker: 4 nøkler (3, 6, 1, 4). 1 aksess hver.

Overløp: 4 nøkler (9, 12, 7, 10). 2 aksesser hver (hovedblokk + 1. overløpsblokk).

Snitt: (4·1 + 4·2) / 8 = 12 / 8 = 1.50.

A (1.00) ville krevd ingen overløp. C (1.25) ville krevd 2 overløp av 8. D (1.75) ville krevd flere kjeder med 2.+overløp.

Pensum: Kap. 6 — Statisk hashing

Spørsmål 15 5 poeng Kap. 6

Vi har en extendible hashing-datastruktur. Da vi startet hadde den global dybde 2. Akkurat nå har den global dybde 4. Hvilke verdier er mulige for lokal dybde i denne strukturen?

A 1, 2, 3 og 4.
B Bare 2 og 4.
C 2, 3 og 4.
D Bare 4 (alle blokker har samme LD som GD).

Vis fasit

Riktig svar: C

Tre invarianter:

LD ≤ GD alltid. Så LD ≤ 4.
Da vi startet med GD=2, hadde alle blokker LD=2 (eller mindre om strukturen var annerledes; men typisk LD=2 ved start).
Når en blokk splittes, går LD opp med 1 (og GD doblet om nødvendig). En blokk som aldri har blitt splittet siden GD=2 beholder LD=2.

Mulige LD-verdier: 2 (uberørte blokker fra start), 3 (splittet én gang), 4 (splittet to ganger eller blokker fra siste splitt). Så 2, 3 og 4.

A inkluderer LD=1 — det forutsetter at vi startet med GD ≤ 1 (vi startet med GD=2). B utelater LD=3, men en blokk som har blitt splittet én gang etter at GD ble 3 har LD=3. D er motbevist av at noen blokker kan ha LD < GD.

Pensum: Kap. 6 — Extendible hashing

Spørsmål 16 5 poeng Kap. 6

Vi har en tabell med 24 000 poster på 180 byte hver. Postene lagres i et clustered B+-tre med blokker på 4096 byte. Anta blokkene har 2/3 fyllgrad og at vi kun lagrer hele poster. Hvor mange blokker er det på level=0 (løvnivå)?

A 1500
B 132
C 2400
D 1600

Vis fasit

Riktig svar: D

Tilgjengelig plass per løvblokk: 4096 · 2/3 ≈ 2730 byte. Poster per blokk: floor(2730 / 180) = 15. Antall løvblokker: ceil(24 000 / 15) = 1600.

A (1500) bruker 100 % fyllgrad: floor(4096/180)=22, 24000/22≈1091 — ikke konsistent heller. B (132) er 24000/180 — feil enhet. C (2400) overestimerer dramatisk.

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

Spørsmål 17 4 poeng Kap. 7

Tabell Birdwatcher(bwid, navn, adresse, alder, ...) har 10 000 rader. bwid er primærnøkkel og tabellen er lagret i en clustered, statisk hash-struktur med bwid som søkenøkkel. Alle radene får plass i 500 blokker totalt, og gjennomsnittlig aksesseres 1.25 blokker per oppslag på bwid. Hvor mange blokkaksesser kreves av:

SELECT * FROM Birdwatcher;

A 500
B 12500
C 625
D 10000

Vis fasit

Riktig svar: A

For en full table-scan leser vi hver blokk i hash-strukturen nøyaktig én gang — totalt 500 blokker. Tallet 1.25 (gjennomsnittlig blokker per oppslag på en gitt nøkkel) gjelder kun for punkt-spørringer som WHERE bwid = K; ved en full scan har det ingen relevans, fordi vi tar alle blokker uansett.

B (12500) multipliserer 10000·1.25 — feil bruk av "per oppslag"-tallet på alle radene. C (625) ganger 500·1.25 — også feil bruk. D (10000) er antall rader, ikke blokker.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 18 4 poeng Kap. 7

Tabell Bird(bid, ..., alder, ...) er lagret i et clustered B+-tre på bid med 1500 løvblokker og 3 nivåer. I tillegg finnes et unclustered B+-tre på alder med 80 løvblokker og 3 nivåer. Anta 70 % av alle Bird-radene har alder > 30. Hvor mange blokker aksesseres ved optimal utføring av:

SELECT * FROM Bird WHERE alder > 30;

A 1500
B 80
C 56
D 7000

Vis fasit

Riktig svar: A

Med 70 % av radene som matcher predikatet, blir bruken av en unclustered indeks verre enn full scan: indeksen gir oss RID-er, men hver RID-oppslag mot heapen kan i værste fall hente en ny blokk (siden den er unclustered). Det blir lett mer enn én blokk per matchende rad i gjennomsnitt — vi snakker fort om tusenvis av tilfeldige I/O-er.

Optimal plan er full sequential scan av det clustered B+-treets løvnivå = 1500 blokker. Det clustered treet inneholder hele tabellen på løvnivå.

B (80) er kun indeks-løvnivå-scan, men vi får ikke alder + andre attributter; vi trenger heap. C (56) er 70 % av indeksens løvnivå — også uten heap-aksess. D (7000) er nær 70 % · 10000 hvis hver matchende rad gir én blokk-aksess — men det er nettopp problemet med unclustered: vi vil heller scanne sekvensielt.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 19 5 poeng Kap. 7

Vi har:

Department(dnumber, dname, ...)        — 12 blokker
Employee(ssn, dno, ...)                — 4000 blokker

Vi joiner på Employee.dno = Department.dnumber med Block-Nested-Loop Join, og bufferet har 8 plasser. Hvor mange blokker leses?

A 4012
B 12012
C 8012
D 11988

Vis fasit

Riktig svar: C

Plasser den minste tabellen (Department, 12 blokker) ytterst. Med B = 8 brukes 1 til indre + 1 til output, så ytre chunk-størrelse = B − 2 = 6.

Antall ytre chunks: ceil(12 / 6) = 2. For hver chunk leses hele indre tabell: 2 · 4000 = 8000 blokker. Pluss ytre tabell leses én gang totalt: 12. Sum: 12 + 8000 = 8012.

A (4012) er ett pass av begge — krever at hele Dep + 1 indre-blokk + 1 output får plass i bufferet (Dep er 12 blokker, men buffer er kun 8). B (12012) tilsvarer Dep ytre med chunk-størrelse 1 og 1000 chunks — feil aritmetikk. D (11988) er ikke konsistent med standardanalysen.

Pensum: Kap. 7 — Join-algoritmer

Spørsmål 20 5 poeng Kap. 7

Hvilken egenskap er nødvendig for at en partition-hash-join (J4) skal være effektiv (i den enkle ettpasningsvarianten)?

A Begge tabellene må være sortert på joinattributtet.
B Etter hashing må den minste partisjonen få plass i RAM (build-fasen).
C Joinattributtet må være primærnøkkel i den minste tabellen.
D Det må finnes B+-tre-indekser på joinattributtet i begge tabellene.

Vis fasit

Riktig svar: B

I partition-hash-join hash-fordeler vi begge tabellene på joinattributtet til n partisjoner. For å gjøre joinen i én probe-pass må den minste tabells partisjon få plass i minne, slik at vi kan bygge en in-memory hashtabell og probe den større partisjonen mot den. Hvis ikke, må vi rekursivt partisjonere igjen, eller bruke "grace hash join" med flere passes.

A beskriver sort-merge join, ikke hash join. C er feil — joinattributtet trenger ikke være PK; bare må kunne hashes konsistent. D er feil — hash join bruker ikke eksisterende indekser; den bygger sin egen midlertidige hashtabell.

Pensum: Kap. 7 — Hash-join

Spørsmål 21 5 poeng Kap. 7

Vi har en usortert fil bestående av 512 blokker og et buffer med plass til 5 blokker. Hvor mange blokker leses og skrives til sammen ved flettesortering? En lesing og en skriving av en blokk blir til sammen 2.

A 2048
B 2560
C 5120
D 1024

Vis fasit

Riktig svar: C

Sort-fasen lager n_R = ceil(512 / 5) = 103 initielle runs. Merge-grad d_M = min(5 − 1, 103) = 4.

Antall merge-passes:

Pass 1: ceil(103/4) = 26 runs.
Pass 2: ceil(26/4) = 7 runs.
Pass 3: ceil(7/4) = 2 runs.
Pass 4: ceil(2/4) = 1 run.

Totalt: 1 sort-pass + 4 merge-passes = 5 passes. Per pass leses og skrives alle 512 blokker = 2 · 512 = 1024. Sum: 5 · 1024 = 5120.

A (2048) er 2 passes. B (2560) er 2.5 passes — ikke et heltall. D (1024) er kun 1 pass.

Pensum: Kap. 7 — External merge sort

Spørsmål 22 4 poeng Kap. 8

Vi har to transaksjoner T1 og T2 som deler data og bruker SNAPSHOT ISOLATION. A = 20 og B = 30 før T1 og T2 starter.

A = 20
B = 30

T1: r1(A);                                        r1(B); D = A+B; w1(D); c1;
T2:           r2(A); A=A*2; w2(A); r2(B); B=B*2; w2(B); c2;

T1 og T2 starter samtidig; T2 committer før T1. Hvilken verdi vil D ha i databasen når begge er committet?

A 100
B 70
C 80
D 50

Vis fasit

Riktig svar: D

Under snapshot isolation tar T1 sitt snapshot ved start (verdier A=20, B=30). T1's lesinger er konsistente mot dette snapshotet, uavhengig av at T2 commits underveis.

Sekvens: T1 leser A=20 fra snapshot. T2 leser A=20, oppdaterer til 40, skriver A=40. T2 leser B=30, oppdaterer til 60, skriver B=60. T2 commits. T1 leser B fra sitt snapshot = 30 (ikke 60). T1 beregner D = 20 + 30 = 50. T1 commits med D=50.

A (100) ville krevd at T1 så T2's nye verdier (A=40 + B=60). B (70) er rar mellomverdi. C (80) ville krevd 40+40 eller lignende — heller ikke konsistent.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 23 5 poeng Kap. 8

Følgende sekvens kommer inn til databasen, og vi bruker rigorous 2PL. I hvilken rekkefølge committer T1, T2 og T3?

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

A T1; T2; T3
B T3; T2; T1
C T2; T1; T3
D T3; T1; T2

Vis fasit

Riktig svar: B

Trace med rigorous 2PL:

r1(X): T1 tar rl(X).
r2(X): T2 tar rl(X) (kompatibel).
w1(X): T1 vil ha wl(X). T2 har rl(X) → T1 venter.
r3(Y): T3 tar rl(Y).
c1: T1 venter → c1 settes på vent.
w2(Y): T2 vil ha wl(Y). T3 har rl(Y) → T2 venter.
c2: T2 venter → c2 settes på vent.
r3(Z): T3 tar rl(Z).
c3: T3 committer, slipper rl(Y) og rl(Z). T2 vekkes: tar wl(Y), gjør w2(Y), committer, slipper rl(X) og wl(Y). T1 vekkes: tar wl(X), gjør w1(X), committer.

Rekkefølge: T3 → T2 → T1.

A (T1; T2; T3) går imot låse-sekvensen. C plasserer T1 før T3 — feil. D bytter T2 og T1 etter T3 — feil rekkefølge.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 24 5 poeng Kap. 8

Følgende logg ble funnet etter et krasj. Vi bruker ARIES recovery.

LSN	PrevLSN	TID	Operasjon	PageID
201	199	T1	Update	A
202	0	T2	Update	A
203	201	T1	Update	B
204	202	T2	Update	B
205	203	T1	Update	C
206			Ckpt start
207			Ckpt end
208	205	T1	Commit
209	204	T2	Update	D
210	0	T3	Update	E
211	209	T2	Commit

I sjekkpunktloggposten med LSN=207 ble TT funnet: (T1, LastLSN=205, Active), (T2, LastLSN=204, Active). DPT funnet: (A, recLSN=202), (B, recLSN=203). Hvilken DPT er korrekt etter analysen?

A {(A,202), (B,203), (D,209), (E,210)}
B {(A,202), (B,203), (C,205), (D,209), (E,210)}
C {(A,201), (A,202), (B,203), (D,209), (E,210)}
D {(D,209), (E,210)}

Vis fasit

Riktig svar: A

Analyse-fasen starter ved sjekkpunktets DPT/TT og leser loggen forover fra LSN 208. Eldre updates (201–205) er allerede oppsummert i sjekkpunktets DPT — vi legger ikke til sider som ikke står der, fordi det ville bety at de allerede ble flushet før sjekkpunktet.

LSN 208 (T1 commit): TT[T1] → Commit. DPT uendret.
LSN 209 (T2 update D): D ikke i DPT → legg til (D, 209). TT[T2].LastLSN = 209.
LSN 210 (T3 update E): T3 ikke i TT → legg til (T3, 210, Active). DPT: legg til (E, 210).
LSN 211 (T2 commit): TT[T2] → Commit.

Sluttinnhold DPT: (A,202), (B,203), (D,209), (E,210).

B legger feilaktig til C (som ble oppdatert ved LSN 205, men som ikke er i sjekkpunktets DPT — så vi antar C ble flushet før sjekkpunktet). C dobbel-teller A. D mister sjekkpunktets DPT-innslag.

Pensum: Kap. 8 — Recovery

Spørsmål 25 5 poeng Kap. 8

Med samme logg som forrige oppgave: hvilke loggposter genereres under undo-fasen? Format: (LSN, PrevLSN, TID, Operation, PageID).

A (212, 210, T3, CLR av 210, E), (213, 212, T3, Abort, )
B (212, 211, T2, CLR av 211, ), (213, 212, T2, Abort)
C (212, 209, T2, CLR av 209, D), (213, 212, T2, CLR av 204, B), (214, 213, T2, CLR av 202, A), (215, 214, T2, Abort)
D Ingen loggposter genereres siden T1 og T2 har committet.

Vis fasit

Riktig svar: A

Etter analysen: vinnere = T1 (committet via 208), T2 (committet via 211). Taper = T3 (Active, LastLSN=210).

UNDO prosesserer kun tapere baklengs. For T3:

Siste handling: LSN 210 (Update E). Skriv CLR: (212, prevLSN=210, T3, CLR av 210, E).
T3's prevLSN ved 210 er 0 → ingen flere loggposter å undoe.
Skriv abort: (213, prevLSN=212, T3, Abort, ).

B undoer T2 — feil, T2 committet. C undoer T2 hele veien tilbake — også feil. D ignorerer at T3 var aktiv ved krasj.

Pensum: Kap. 8 — Recovery

Slutt på øvingseksamen 08.