Øvingseksamen 06 · TDT4145

Øvingseksamen 06

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

Hovedfokus: Del 1 i midtveiseksamen-stil; Del 2 speiler tidligere eksamener (heap, hashing, B+-tre, access paths, Block-NL, sortering, snapshot isolation, 2PL, ARIES REDO/flush).

Del 1 — Theodoros (~40 %)

Korte konseptspørsmål, RA og SQL-evaluering — speiler midtveiseksamen.

Spørsmål 1 3 poeng Kap. 2/3

Hvilken av følgende påstander om join-operasjoner er sann?

A Resultatet av en INNER JOIN er alltid mindre enn eller lik størrelsen til den minste inputtabellen.
B En FULL OUTER JOIN inneholder aldri NULL-verdier i resultatet.
C En NATURAL JOIN matcher på attributter som har samme navn i de to tabellene.
D Rekkefølgen vi skriver inner joins i, endrer det endelige resultatet.

Vis fasit

Riktig svar: C

NATURAL JOIN bestemmer join-kolonnene implisitt ved å se på alle attributter som har samme navn i begge tabellene. Det er en bekvemmelighet — man slipper å skrive ON-predikatet — men kan også være en fallgruve hvis tabellene tilfeldigvis har en felles kolonne man ikke mente å joine på.

A er feil — INNER JOIN kan godt være større enn begge inputs (f.eks. en M:N-relasjon kan gi mange match per rad). B er feil per definisjon — FULL OUTER fyller på NULL der det ikke er match. D er feil — INNER JOIN er kommutativ og assosiativ i resultatmengde (rekkefølgen kan påvirke ytelsen i optimalisatoren, men ikke det logiske resultatet).

Pensum: Kap. 2 — Joins og outer joins

Spørsmål 2 3 poeng Kap. 3

Hvilken term matcher best følgende beskrivelse?

"En relasjon som ikke er en del av den konseptuelle modellen, men som vises til en bruker som en 'virtuell relasjon'."

A Domain.
B Decomposition.
C Assertion.
D View.

Vis fasit

Riktig svar: D

En view er en navngitt SELECT-spørring som brukeren kan referere til som om den var en tabell. Den lagres ikke som data (vanlige views), men beregnes på nytt ved hver bruk. Materialiserte views er et unntak — de lagres fysisk for ytelse, men oppdateres ved underliggende endringer.

A (domain) er settet av lovlige verdier en attributt kan ha. B (decomposition) er prosessen med å splitte en tabell i delfunksjoner under normalisering. C (assertion) er et SQL-uttrykk som må holde over hele databasen — sjelden implementert i praksis.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 3 4 poeng Kap. 2

Følgende tabeller er gitt:

P (Person)
pid	name
1	Alice
2	Bob
3	Cathy

L (Location)
pid	city
1	Oslo
1	Bergen
2	Trondheim
4	Stavanger

Hvor mange tupler returnerer P ⋈ L (naturlig join på pid)?

A 3
B 4
C 12
D 2

Vis fasit

Riktig svar: A

Match per pid: pid=1 (Alice) → 2 byer (Oslo, Bergen) = 2 tupler. pid=2 (Bob) → Trondheim = 1 tuppel. pid=3 (Cathy) → ingen match. pid=4 (Stavanger) → ingen match i P. Sum: 2 + 1 = 3.

B (4) inkluderer feilaktig en NULL-rad som om det var en LEFT/FULL OUTER JOIN. C (12) er kryssproduktet 3×4 uten match-predikat. D (2) glemmer at Alice har to byer.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 4 3 poeng Kap. 3

Den følgende tabellen er gitt:

employee
name	salary	manager
John	50	NULL
Alice	40	John
Trevor	38	John
Bob	35	Trevor
Jim	35	Trevor

Hva er resultatet av spørringen?

SELECT b.salary
FROM employee AS a JOIN employee AS b ON (a.manager = b.name)
WHERE a.salary < 36
ORDER BY b.salary
LIMIT 1;

A 35
B 38
C 40
D 50

Vis fasit

Riktig svar: B

WHERE filtrerer a.salary < 36: bare Bob (35) og Jim (35). Begge har manager = Trevor. JOIN på a.manager = b.name matcher dem til b = Trevor, som har salary 38. Etter ORDER BY og LIMIT 1: 38.

A (35) er a.salary, ikke b.salary. C (40) er Alice sin salary — men Alice er ikke filtrert inn (40 ≥ 36). D (50) er John sin salary — han kunne kun nås om Alice eller Trevor var i resultatsettet, men de er det ikke.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 5 4 poeng Kap. 3

Følgende skjema er gitt:

bar(bid, name)
serves(bid, did, price)
drink(did, name)

Hvilket RA-uttrykk er ekvivalent med:

SELECT bar.name, drink.name
FROM bar, serves, drink
WHERE bar.bid = serves.bid
  AND drink.did = serves.did
  AND price > 20;

A π_{bar.name, drink.name}(σ_{price > 20}(bar ⋈ serves ⋈ drink))
B σ_{price > 20}(π_{bar.name, drink.name}(bar ⋈ serves ⋈ drink))
C π_{bar.name}(σ_{price > 20}(bar ⋈ serves ⋈ drink))
D π_{bar.name, drink.name, price}(σ_{price > 20}(bar ⋈ serves ⋈ drink))

Vis fasit

Riktig svar: A

SQL-spørringen joiner alle tre tabellene, filtrerer på price > 20, og returnerer to navnkolonner. Riktig RA-form: gjør joinene først, deretter σ (mens price fortsatt finnes), så π.

B utfører π før σ — men da har π allerede fjernet price, så σ kan ikke filtrere på den. C dropper drink-tabellen og returnerer kun bar.name. D inkluderer price i resultatet, men SQL-en velger kun de to navnkolonnene.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 6 3 poeng Kap. 3

Hvilken av følgende klausuler evalueres logisk sist i en SQL-spørring (uten nøstede subqueries)?

A WHERE
B HAVING
C SELECT
D ORDER BY

Vis fasit

Riktig svar: D

Logisk evalueringsrekkefølge: FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY → LIMIT. ORDER BY (og LIMIT) kjøres aller sist; den kan referere til SELECT-aliaser nettopp fordi den evalueres etter SELECT.

A (WHERE) evalueres tidlig, like etter FROM. B (HAVING) er etter GROUP BY men før SELECT. C (SELECT) er nesten sist, men ORDER BY kjører etter SELECT.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 7 4 poeng Kap. 8

Hvilken egenskap ved ACID sier at en transaksjon enten utføres helt eller ikke i det hele tatt — den er en udelelig enhet?

A Atomicity
B Consistency
C Isolation
D Durability

Vis fasit

Riktig svar: A

Atomicity garanterer at en transaksjon er en udelelig enhet — alle endringer commit-es sammen eller rulles tilbake sammen. Hvis et krasj eller feil inntreffer midt i transaksjonen, blir alle dens delvise endringer reversert (via UNDO-loggen).

B (Consistency) sier at en transaksjon tar databasen fra en konsistent tilstand til en annen — integritetsregler holder. C (Isolation) sier at samtidige transaksjoner ikke skal interferere — utad ser hver ut til å kjøre alene. D (Durability) sier at committede endringer overlever krasj — håndteres via WAL og force-log-at-commit.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 8 3 poeng Kap. 3

Følgende skjema er definert:

CREATE TABLE Course (
    cid   INT PRIMARY KEY,
    title VARCHAR(50)
);
CREATE TABLE Enrollment (
    sid   INT,
    cid   INT,
    PRIMARY KEY (sid, cid),
    FOREIGN KEY (cid) REFERENCES Course(cid)
        ON DELETE CASCADE
);

Hva skjer hvis vi sletter et kurs som har 5 påmeldte studenter?

A Slettingen avvises pga. de eksisterende påmeldingene.
B Kurset slettes; de 5 påmeldingene blir foreldreløse (orphan).
C Kurset og alle 5 påmeldingene slettes — kaskaderingen følger FK-handlingen.
D De 5 påmeldingene får cid satt til NULL; kurset slettes.

Vis fasit

Riktig svar: C

ON DELETE CASCADE betyr at sletting av en rad i foreldretabellen automatisk sletter alle tilhørende rader i barntabellen. Sletting av et kurs trigger sletting av alle 5 enrollment-rader som refererer til dette kurset.

A beskriver ON DELETE RESTRICT (eller default i noen RDBMS). B er ikke en lovlig tilstand — DBMS-et tillater ikke at FK-er blir foreldreløse. D beskriver ON DELETE SET NULL, som ville krevd NULL-tillatelse på cid (men cid er del av PK her — ikke tillatt).

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 9 3 poeng Kap. 4

Vurder følgende ER-fragment: Entiteten Movie har en M:N-relasjon "Reviews" til entiteten Person, med relasjonsattributtet rating. Hvilken av påstandene under er sann?

A En person kan ikke gi mer enn én review per film de har sett.
B En film kan ha reviews av flere personer; en person kan reviewe flere filmer.
C En film må ha minst én review for å kunne eksistere i databasen.
D To reviews kan ikke ha samme rating-verdi for samme film i databasen.

Vis fasit

Riktig svar: B

M:N-kardinalitet betyr at hver Movie kan ha mange Person-reviews, og hver Person kan reviews mange Movies. Det er hele poenget med M:N — multiplisitet på begge sider.

A ville krevd en uniqueness-constraint på (Movie, Person)-paret i Reviews — det er en separat designvalgsbeslutning som ikke følger automatisk av M:N. C ville krevd total deltakelse fra Movie — ikke spesifisert. D er en absurd constraint på et numerisk attributt — det er ingenting som hindrer to reviews i å gi samme rating.

Pensum: Kap. 4 — ER-modellen

Spørsmål 10 3 poeng Kap. 4

Et ER-diagram inneholder:

Entiteten Employee (eid PK, name).
Entiteten Project (pid PK, title).
Entiteten Department (did PK, dname).
Relasjonen BelongsTo: 1:N mellom Employee og Department, med total deltakelse fra Employee.
Relasjonen AssignedTo: M:N mellom Employee og Project, med relasjonsattributtet hours.

Hva er minimum antall relasjoner (tabeller) som trengs for å mappe diagrammet?

Vis fasit

Riktig svar: B

Tre entiteter gir tre tabeller: Employee, Project, Department. BelongsTo er 1:N med total deltakelse fra Employee → kan slås sammen ved å legge til en NOT NULL-FK did i Employee-tabellen (ingen ekstra tabell). AssignedTo er M:N → må bli en egen koblingstabell (eid, pid, hours). Totalt: 3 + 1 = 4 tabeller.

A (3) glemmer at M:N-relasjoner krever egen koblingstabell. C (5) ville lagt til ekstra tabell for BelongsTo, men det er unødvendig når 1:N kan inlines som FK. D (2) undervurderer dramatisk.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 11 3 poeng Kap. 4

Vi har tabellen

Sale(saleId, productId, productName, custName, custCity)
F = { saleId → productId, productName, custName, custCity;
      productId → productName;
      custName → custCity }

Anta at tabellen er på 1NF. Finn den høyeste av disse normalformene som oppfylles.

A 1NF
B 2NF
C 3NF
D BCNF

Vis fasit

Riktig svar: B

Kandidatnøkkel = {saleId} (saleId determinerer alt). Ingen prim-attributter utenom saleId.

2NF: krever at ikke-prim-attributter ikke er delvis avhengige av PK. Siden PK er en enkelt attributt, er det ingen mulighet for delvis avhengighet → 2NF oppfylt.

3NF: forbyr transitive avhengigheter PK → ikke-prim → ikke-prim der mottakeren ikke er prim. Vi har saleId → productId → productName (productId og productName er begge ikke-prim) — klar transitiv avhengighet. 3NF brutt.

Høyeste oppfylte: 2NF.

A (1NF) er for konservativt — 2NF holder. C (3NF) brytes av transitiv avhengighet. D (BCNF) er enda strengere og brytes også (productId er ikke supernøkkel).

Pensum: Kap. 4 — Normalformer

Spørsmål 12 4 poeng Kap. 3

Skriv ut en tabell review som tilfredsstiller:

review_id INT er primærnøkkel.
movie_id og user_id er INT, NOT NULL, og er fremmednøkler til movie(movie_id) og user(user_id).
rating INT, NOT NULL, må være mellom 1 og 5.
review_text VARCHAR(200), NOT NULL.
Hver bruker kan kun gi én review per film — paret (movie_id, user_id) er unikt.

Hvilken DDL oppfyller alle kravene?

CREATE TABLE review (
    review_id   INT PRIMARY KEY,
    movie_id    INT NOT NULL,
    user_id     INT NOT NULL,
    rating      INT NOT NULL CHECK (rating BETWEEN 1 AND 5),
    review_text VARCHAR(200) NOT NULL,
    FOREIGN KEY (movie_id) REFERENCES movie(movie_id),
    FOREIGN KEY (user_id)  REFERENCES user(user_id),
    UNIQUE (movie_id, user_id)
);

CREATE TABLE review (
    review_id   INT PRIMARY KEY,
    movie_id    INT NOT NULL,
    user_id     INT NOT NULL,
    rating      INT NOT NULL,
    review_text VARCHAR(200) NOT NULL,
    FOREIGN KEY (movie_id) REFERENCES movie,
    FOREIGN KEY (user_id)  REFERENCES user
);

CREATE TABLE review (
    review_id   INT PRIMARY KEY,
    movie_id    INT NOT NULL UNIQUE,
    user_id     INT NOT NULL UNIQUE,
    rating      INT NOT NULL CHECK (rating BETWEEN 1 AND 5),
    review_text VARCHAR(200) NOT NULL,
    FOREIGN KEY (movie_id) REFERENCES movie(movie_id),
    FOREIGN KEY (user_id)  REFERENCES user(user_id)
);

CREATE TABLE review (
    review_id   INT PRIMARY KEY,
    movie_id    INT PRIMARY KEY,
    user_id     INT PRIMARY KEY,
    rating      INT CHECK (rating BETWEEN 1 AND 5),
    review_text VARCHAR(200),
    UNIQUE (movie_id, user_id)
);

Vis fasit

Riktig svar: A

A oppfyller alle krav: PK på review_id, NOT NULL og CHECK på rating, NOT NULL på review_text, FK-er til movie/user, og en composite UNIQUE på (movie_id, user_id) som forhindrer duplikate reviews per (film, bruker)-par.

B mangler både CHECK på rating og UNIQUE-constraint — to spesifikasjoner brytes. C bruker UNIQUE på hver kolonne hver for seg (i stedet for composite) — det betyr at en film bare kan reviews én gang totalt og en bruker bare én gang totalt; semantisk feil. D har tre PRIMARY KEY-deklarasjoner, som er syntaktisk ulovlig (en tabell kan kun ha én PK).

Pensum: Kap. 3 — DDL og spørringer

Del 2 — Svein Erik (~60 %)

Konkrete regneoppgaver i samme stil som tidligere eksamener — heap, hashing, B+-tre, access paths, join, sortering, snapshot isolation, 2PL og ARIES.

Spørsmål 13 4 poeng Kap. 6

Vi har poster som er 80 byte store. Vi har en tabell med 12 500 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 156
B 246
C 245
D 250
E Ingen av de andre alternativene stemmer

Vis fasit

Riktig svar: B

Antall poster per blokk: floor(4096 / 80) = 51. Antall blokker: ceil(12 500 / 51) = ceil(245.10) = 246.

A (156) er nær 12500/80 = 156.25 — feil enhet (deler poster på post-størrelse i stedet for å regne ut blokker). C (245) bruker floor i stedet for ceil — vi må runde opp for å få plass til de siste 5 postene. D (250) overestimerer.

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:

4, 8, 12, 5, 9, 13, 6, 10, 14

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

A 1.00
B 1.11
C 1.22
D 1.33

Vis fasit

Riktig svar: D

Plassering etter K mod 4:

Blokk 0: [4, 8] full → overløp [12].
Blokk 1: [5, 9] full → overløp [13].
Blokk 2: [6, 10] full → overløp [14].
Blokk 3: tom.

6 nøkler i hovedblokker (1 aksess hver) + 3 nøkler i overløpsblokker (2 aksesser hver). Sum: 6·1 + 3·2 = 12. Snitt: 12 / 9 ≈ 1.33.

A (1.00) ville krevd ingen overløp. B (1.11) ville krevd 1 overløp av 9. C (1.22) ville krevd 2 overløp.

Pensum: Kap. 6 — Statisk hashing

Spørsmål 15 5 poeng Kap. 6

Vi har en extendible hashingstruktur hvor vi starter med 4 blokker (binært: 00, 01, 10, 11), hvor hver blokk har plass til to nøkler. Når vi hasher inn følgende nøkler i den gitte rekkefølgen:

7, 2, 14, 13, 11, 6, 1, 27

Bruk h(K) = K mod 8. Hvilken blokk er den første som må splittes, og hva er lokal dybde for de to resulterende blokkene (gammel og ny)?

A Block 11 splittes; lokal dybde for begge = 3.
B Block 00 splittes; lokal dybde for begge = 3.
C Block 10 splittes; lokal dybde for begge = 3.
D Block 10 splittes; lokal dybde for begge = 2.

Vis fasit

Riktig svar: C

Trace (siste 2 bit indekserer mens GD=2):

7 (111 → 11): blokk 11 = [7]
2 (010 → 10): blokk 10 = [2]
14 (110 → 10): blokk 10 = [2, 14] full
13 (101 → 01): blokk 01 = [13]
11 (1011 → 11): blokk 11 = [7, 11] full
6 (110 → 10): blokk 10 full → FØRSTE SPLITT. LD=2=GD → directory dobles til GD=3.

Rehash av blokk 10 sine nøkler med 3 bit: 2 (010) → bucket 010, 14 (110) → bucket 110. Begge nye blokker har LD=3.

A er feil — blokk 11 er full men 6 hasher til 10. B er feil — blokk 00 er ikke involvert. D er feil — etter split har de nye blokkene LD=3, ikke 2.

Pensum: Kap. 6 — Extendible hashing

Spørsmål 16 5 poeng Kap. 6

Vi har poster som er 150 byte store. Vi har en tabell med 9000 poster. Hvor mange blokker har vi på level=0 i et clustered B+-tre når blokkene er 4096 bytes store, og vi antar det ikke lagres noe annet i blokkene enn poster? Anta fyllingsgrad er 2/3, dvs. blokkene blir ikke mer enn 2/3 fulle, og vi lagrer kun hele poster.

A 60
B 500
C 750
D 600
E Ingen av de andre alternativene stemmer

Vis fasit

Riktig svar: B

Tilgjengelig plass per løvblokk: 4096 · 2/3 ≈ 2730 byte. Poster per løvblokk: floor(2730 / 150) = 18. Antall løvblokker: ceil(9000 / 18) = 500.

A (60) er 9000/150 — feil enhet. C (750) bruker 100 % fyllgrad eller annen feil. D (600) er nær men bruker floor(4096/150·2/3) feil sted. E er ikke aktuelt.

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

Spørsmål 17 4 poeng Kap. 7

Anta vi har en tabell Bird(bid, navn, art, alder, ...) med 8000 rader. Attributtet bid er primærnøkkel. Tabellen er lagret i et clustered B+-tre med bid som søkenøkkel, der løvnodene har 550 blokker. Det er tre nivåer i B+-treet. Hvor mange blokkaksesser får vi med følgende SQL-setning?

SELECT navn, alder FROM Bird WHERE bid = 2001;

A 550
B 1
C 3
D 8000

Vis fasit

Riktig svar: C

Vi traverserer ned det clustered B+-treet: rot → level 1 → løvblokk = 3 blokkaksesser. Fordi treet er clustered, ligger hele raden på løvnivå — ingen ekstra heap-aksess kreves.

A (550) ville vært en full scan av løvnivået — meningsløst når vi har søkenøkkel-match. B (1) glemmer alle nivåene. D (8000) er en full row scan.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 18 4 poeng Kap. 7

Vi har en database som lagrer bomringpasseringer:

Passering(passId, passTime, regNo, turnpikeNo, cost)

Tabellen er lagret i et clustered B+-tre med passId som søkenøkkel — 1500 løvblokker, 3 nivåer. I tillegg finnes et unclustered B+-tre på regNo med 800 løvblokker og 3 nivåer. Løvnodene i det unclustered treet inneholder søkenøkkelen (regNo) og tabellens primærnøkkel (passId). Anta at det er nøyaktig 100 passeringer per regNo.

Hvor mange blokker aksesseres ved optimal utføring av:

SELECT passTime FROM Passering WHERE regNo = 'XY12345';

A 1500
B 303
C 100
D 4
E 103

Vis fasit

Riktig svar: B

Optimal plan: bruk det unclustered B+-treet på regNo for å finne alle primærnøklene for regNo = 'XY12345'. Traversering rot → løv = 3 blokker. For hver av 100 passId-verdier må raden slås opp i det clustered B+-treet på passId; hvert oppslag er 3 blokker (3 nivåer). Sum: 3 + 100 · 3 = 303.

A (1500) er full scan av clustered treets løvnivå. C (100) glemmer indekstraversering og clustered oppslag. D (4) ville tilsvart ett treff (3 + 1·3). E (103) hadde passet dersom løvnodene i regNo-indeksen hadde hatt RID-er og hvert treff bare krevde én ekstra løvblokk i clustered treet.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 19 5 poeng Kap. 7

To tabeller Klasse og Student skal joines ved en nested loop join. Bufferet har 7 plasser til blokker. Klasse har 18 blokker, Student har 600 blokker. Hvor mange lesinger av blokker skjer ved joinen?

A 2418
B 1218
C 600
D 10818
E Ingen av de andre alternativene stemmer

Vis fasit

Riktig svar: A

Plasser den minste tabellen ytterst (Klasse, 18 blokker). Med B = 7 brukes 1 blokk til indre + 1 til output, så ytre chunk = B − 2 = 5 blokker.

Antall ytre chunks: ceil(18 / 5) = 4. For hver chunk leses hele indre tabell: 4 · 600 = 2400. Pluss ytre tabell leses én gang totalt: 18. Sum: 18 + 2400 = 2418.

B (1218) feilteller chunks (2 i stedet for 4). C (600) er kun én pass. D (10818) bruker Student som ytre — verre fordi den er større. E er ikke aktuelt.

Pensum: Kap. 7 — Join-algoritmer

Spørsmål 20 5 poeng Kap. 7

Vi har en usortert fil bestående av 1000 blokker med poster og et buffer med plass til 5 blokker. Hvor mange blokker leses og skrives til sammen når postene skal sorteres ved hjelp av flettesortering? En lesing og en skriving av en blokk blir til sammen 2.

A 2000
B 10000
C 8000
D 4000
E Ingen av de andre alternativene stemmer

Vis fasit

Riktig svar: B

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

Antall merge-passes:

Pass 1: ceil(200/4) = 50 runs.
Pass 2: ceil(50/4) = 13 runs.
Pass 3: ceil(13/4) = 4 runs.
Pass 4: ceil(4/4) = 1 run.

Totalt: 1 sort-pass + 4 merge-passes = 5 passes. Per pass: 2 · 1000 = 2000. Sum: 5 · 2000 = 10000.

A (2000) er kun én pass. C (8000) er 4 passes (glemmer sort-fasen). D (4000) er 2 passes. E er ikke aktuelt.

Pensum: Kap. 7 — External merge sort

Spørsmål 21 5 poeng Kap. 8

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

A = 10
B = 20

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

Transaksjonene utføres fra venstre mot høyre. Hvilken verdi vil D ha i databasen når begge er committet?

A 35
B 40
C 30
D 25

Vis fasit

Riktig svar: C

Under snapshot isolation tar T1 sitt snapshot ved start (før T2 commiter). Snapshot ser A=10, B=20. T1's begge reads henter fra dette snapshotet, uavhengig av at T2 oppdaterer A og B i mellomtiden.

Sekvens: T1 leser A=10. T2 leser A=10, oppdaterer til 15, skriver A=15. T2 leser B=20, oppdaterer til 25, skriver B=25. T2 commiter. T1 leser B fra sitt snapshot = 20. T1 beregner D = 10 + 20 = 30. T1 commiter med D=30.

A (35) ville krevd at T1 så T2's nye A. B (40) ville krevd at T1 så begge oppdaterte verdier. D (25) er bare den nye B uten A.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 22 5 poeng Kap. 8

Vi har følgende låser etter en sekvens av operasjoner mot databasen (rigorous 2PL). rl(X) = leselås på X, wl(X) = skrivelås på X.

T1 har: rl(X), wl(Y).
T2 har: rl(X). T2 venter på: rl(Y).
T3 venter på: wl(X).

Hvilken sekvens av operasjoner gir denne tilstanden?

A w1(X); r2(X); w1(Y); r2(Y); w3(X);
B r1(X); w2(X); w1(Y); r3(X); r2(Y);
C r1(X); r2(X); r1(Y); w2(Y); w3(X);
D r1(X); r2(X); w1(Y); r2(Y); w3(X);

Vis fasit

Riktig svar: D

Trace D:

r1(X) → T1 tar rl(X).
r2(X) → T2 tar rl(X) (kompatibel med rl).
w1(Y) → T1 tar wl(Y).
r2(Y) → T2 ønsker rl(Y), men T1 har wl(Y) → T2 venter.
w3(X) → T3 ønsker wl(X), men T1 og T2 har rl(X) → T3 venter.

Sluttilstand: T1 har rl(X), wl(Y); T2 har rl(X), venter på rl(Y); T3 venter på wl(X). ✓

A starter med w1(X) → T1 har wl(X), ikke rl(X). B har w2(X) som blokkeres umiddelbart — T2 ville ikke holde rl(X). C har T1 med rl(Y) (ikke wl(Y)) og T2 venter på wl(Y) (ikke rl(Y)).

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 23 4 poeng Kap. 8

Hva er recovery-egenskapen til følgende historie? Velg den mest spesifikke egenskapen som er oppfylt.

r1(A); w2(A); w1(A); r3(A); c1; c2; c3;

A Strict
B ACA (unngå galopperende abort)
C Recoverable (gjenopprettbar)
D Unrecoverable (ikke gjenopprettbar)

Vis fasit

Riktig svar: C

Analyser:

Strict? Nei — w1(A) skriver A mens T2's w2(A) ikke er committet. Strict forbyr enhver lese eller skriv på et element med uncommitted skriv.
ACA? Nei — r3(A) leser A, og A er på dette tidspunktet skrevet av uncommitted T1 (siste skriv før c1). ACA forbyr lesing fra uncommitted skrivere.
Recoverable? Ja — T3 leser fra T1 og c3 kommer etter c1. Hvis T1 hadde abortet, kunne også T3 ha blitt rullet tilbake.

Mest spesifikk: Recoverable.

A er feil pga. w-w-konflikt med uncommitted T2. B er feil pga. dirty read av r3. D er feil — recovery er mulig her.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 24 5 poeng Kap. 8

Anta ARIES-recovery. Loggpostene har formatet [LSN, Operation, Transaction, DataItem]:

[101, end_ckpt]
[102, update, T3, B]
[103, update, T3, C]
[104, update, T2, B]
[105, update, T1, D]
[106, commit, T3]
[107, update, T2, D]
[108, commit, T1]

Anta A, B, C, D er datasider det skal gjøres recovery på. DPT som finnes i loggposten med LSN=101 er tom. Blokkene har følgende PageLSN på disken:

(B, pageLSN=104), (C, pageLSN=103), (D, pageLSN=105)

For hvilke loggposter blir det gjort REDO under recovery?

A Ingen loggposter — alt er allerede flushet.
B 102, 103, 104, 105, 107 — alle update-records.
C 107
D 105 og 107
E Ingen av de andre alternativene stemmer

Vis fasit

Riktig svar: C

Analysefasen gir DPT = (B,102), (C,103), (D,105). REDO-testen for hver update: gjør REDO hvis (i) page er i DPT, (ii) recLSN ≤ LSN, og (iii) pageLSN < LSN på disken.

102 (B): recLSN(B)=102 ≤ 102 ✓; pageLSN(B)=104 < 102? Nei. Hopp.
103 (C): recLSN(C)=103 ≤ 103 ✓; pageLSN(C)=103 < 103? Nei. Hopp.
104 (B): recLSN(B)=102 ≤ 104 ✓; pageLSN(B)=104 < 104? Nei. Hopp.
105 (D): recLSN(D)=105 ≤ 105 ✓; pageLSN(D)=105 < 105? Nei. Hopp.
107 (D): recLSN(D)=105 ≤ 107 ✓; pageLSN(D)=105 < 107? Ja. REDO.

Bare LSN 107 redoes. A er feil — minst én må redoes. B redoer alle, ignorerer pageLSN-testen. D inkluderer 105, men pageLSN(D) = 105 viser at endringen ved LSN 105 er allerede på disk. E er ikke aktuelt.

Pensum: Kap. 8 — Recovery

Spørsmål 25 5 poeng Kap. 8

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

LSN	PrevLSN	TID	Operasjon	PageID
101	99	T1	Update	A
102	0	T2	Update	A
103	101	T1	Update	B
104	102	T2	Update	B
105	103	T1	Update	C
106			Ckpt start
107			Ckpt end
108	105	T1	Commit
109	104	T2	Update	D
110	0	T3	Update	E
111	109	T2	Commit

I sjekkpunktloggposten med LSN=107 ble TT funnet: (T1, LastLSN=105, Active), (T2, LastLSN=104, Active). DPT funnet: (A, recLSN=102), (C, recLSN=105). I tillegg vet vi at ved kjøring av loggpost LSN=105 ble plassen til PageID=B «stjålet» fra bufferet — en skitten side som kastes ut må skrives til disk først (steal-policy + WAL). Hvilken datablokk ble, som direkte følge av denne hendelsen, skrevet ut til disken?

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

Vis fasit

Riktig svar: B

Oppgaven spør om hvilken blokk som måtte skrives ut i den konkrete buffer-hendelsen der plassen til B ble stjålet. Da er svaret entydig B: det er nettopp den skitne siden som ble kastet ut av bufferet, og med steal må den skrives til disk før RAM-plassen gjenbrukes.

TT/DPT forteller hva som var skittent ved sjekkpunktet, men sier ikke hvilke andre sider som tilfeldigvis ble flushet tidligere. En side kan stå i DPT og likevel ha eldre endringer på disk (f.eks. gir (A, recLSN=102) sammen med oppdatering LSN 101 på A at endringen ved 101 sannsynligvis allerede er på disk — men det følger ikke av steal-hendelsen). C er per DPT fortsatt i en «skitten periode» fra 105; D og E oppdateres først etter sjekkpunktet. F er feil fordi B er riktig.

Pensum: Kap. 8 — Recovery

Slutt på øvingseksamen 06.