Øvingseksamen 05 · TDT4145

Øvingseksamen 05

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

Hovedfokus: Del 1 speiler midtveiseksamen; Del 2 speiler tidligere eksamener (B+-tre-sizing, hashing, access paths, join-kostnad, sortering, 2PL, ARIES).

Del 1 — Theodoros (~40 %)

Korte konseptspørsmål, RA-utregninger og SQL-resultater — som i midtveiseksamen.

Spørsmål 1 3 poeng Kap. 2

Hvilken av de følgende er ikke en basis-/fundamental-operator i relasjonsalgebraen?

  • A Set intersection (∩).
  • B Set difference (−).
  • C Selection (σ).
  • D Cross product (×).
Vis fasit
Riktig svar: A

De seks fundamentale operatorene er σ (selection), π (projection), ∪ (union), − (set difference), × (cross product) og ρ (rename). Set intersection (∩), join (⋈) og divisjon (÷) er avledede — de kan uttrykkes ved hjelp av de fundamentale (f.eks. R ∩ S = R − (R − S)).

B (set difference), C (selection) og D (cross product) er alle blant de seks fundamentale.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 2 3 poeng Kap. 2

En supernøkkel er en mengde attributter som unikt identifiserer hver tuppel. Hva kalles en minimal supernøkkel — altså en der ingen ekte delmengde også er supernøkkel?

  • A Primary key.
  • B Foreign key.
  • C Candidate key.
  • D Discriminator.
Vis fasit
Riktig svar: C

En kandidatnøkkel er en minimal supernøkkel. Det kan finnes flere kandidatnøkler i samme relasjon; én av dem velges som primærnøkkel, men alle kandidatnøkler har samme egenskap (minimal og unik).

A (primary key) er en valgt kandidatnøkkel, men begrepet i seg selv beskriver ikke minimalitet. B (foreign key) refererer til en nøkkel i en annen tabell. D (discriminator) brukes for å skille tupler innen en svak entitet, ikke som en generell minimal supernøkkel.

Pensum: Kap. 2 — Relasjonsmodellen

Spørsmål 3 4 poeng Kap. 2

Følgende tabeller er gitt:

employee
namedept_idsalary
Alice1500
Bob2600
Cathy1700
Dave3550
dept
dept_idlocation
1Trondheim
2Oslo
4Bergen

Hvor mange tupler returnerer det følgende RA-uttrykket?

σ_{salary > 550}(employee ⋈ dept)
  • A 4
  • B 2
  • C 3
  • D 1
Vis fasit
Riktig svar: B

Først naturlig join på dept_id: Alice (1) → Trondheim, Bob (2) → Oslo, Cathy (1) → Trondheim. Dave (3) får ingen match og dropper ut. Resultatet er 3 tupler. Deretter σ_{salary > 550}: bare Bob (600) og Cathy (700) overlever — 2 tupler.

A (4) ville inkludert Dave selv om join'en eliminerer ham. C (3) glemmer selection-filteret. D (1) eliminerer for mange — Bob og Cathy er begge over 550.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 4 3 poeng Kap. 3

Den følgende tabellen er gitt:

employee
namesalarymanager
Alice60NULL
Bob50Alice
Cathy40Bob
Dave35Bob
Eve30Cathy

Hva er resultatet av spørringen?

SELECT count(*)
FROM employee AS a, employee AS b
WHERE a.manager = b.name;
  • A 25
  • B 5
  • C 3
  • D 4
Vis fasit
Riktig svar: D

Vi parrer hver rad a med en rad b hvor a.manager = b.name. Pga. NULL i Alice sin manager-kolonne så matcher hun ingen (NULL = NULL er ikke sant i SQL). De øvrige fire har en eksisterende manager: Bob → Alice, Cathy → Bob, Dave → Bob, Eve → Cathy. Hvert par teller én gang siden hver navngitte manager finnes som b-rad. Sum: 4 par.

A (25) er kryssproduktet 5×5 uten WHERE. B (5) glemmer at NULL-managerraden ikke matcher. C (3) underteller — Bob er manager for to ulike personer (Cathy og Dave), og hver gir et separat par.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 5 4 poeng Kap. 3

Skjema:

student(sid, name)
takes(sid, cid, grade)
course(cid, title)

Hvilket RA-uttrykk er ekvivalent med følgende SQL?

SELECT s.name, c.title
FROM student s, takes t, course c
WHERE s.sid = t.sid
  AND t.cid = c.cid
  AND t.grade > 80;
  • A σ_{grade > 80}(π_{name, title}(student ⋈ takes ⋈ course))
  • B π_{name}(σ_{grade > 80}(student ⋈ takes))
  • C π_{name, title}(σ_{grade > 80}(student ⋈ takes ⋈ course))
  • D π_{name, title, grade}(σ_{grade > 80}(student ⋈ takes ⋈ course))
Vis fasit
Riktig svar: C

SQL-spørringen joiner alle tre tabellene, filtrerer på grade > 80, og projiserer ut name og title. Det riktige RA-uttrykket bruker σ før π for at grade fortsatt skal være tilgjengelig som filterattributt, og projiserer ut akkurat de to ønskede kolonnene.

A bruker σ etter π — men da har π allerede fjernet grade, så σ kan ikke referere til den. B mangler course-joinen og dropper title. D er nesten riktig, men inkluderer grade i resultatet, som ikke matcher SQL-spørringens SELECT-liste.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 6 3 poeng Kap. 3

Når en SQL-spørring (uten nøstede subqueries) prosesseres, hvilken klausul evalueres først i den logiske evalueringsrekkefølgen?

  • A FROM
  • B WHERE
  • C SELECT
  • D ORDER BY
Vis fasit
Riktig svar: A

Logisk evalueringsrekkefølge i SQL: FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY → LIMIT. FROM kommer først fordi alle påfølgende klausuler trenger en kildetabell å jobbe med.

B (WHERE) kjøres etter FROM. C (SELECT) er nesten siste steg — derfor er aliaser definert i SELECT ikke synlige i WHERE. D (ORDER BY) er sist sammen med LIMIT.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 7 3 poeng Kap. 3

Hvilken term matcher best følgende beskrivelse?

"En constraint som automatisk sletter tilhørende rader i en barntabell når en rad i foreldretabellen slettes."

  • A CHECK constraint.
  • B NOT NULL.
  • C UNIQUE.
  • D ON DELETE CASCADE.
Vis fasit
Riktig svar: D

ON DELETE CASCADE er en handling tilknyttet en FOREIGN KEY-constraint. Den sier at når en rad i foreldretabellen slettes, skal tilhørende rader i barntabellen automatisk slettes. (Alternativene SET NULL og RESTRICT/NO ACTION er andre mulige handlinger.)

A (CHECK) håndhever et boolean-predikat på rader, men styrer ikke kaskade-sletting. B (NOT NULL) hindrer NULL-verdier i en kolonne. C (UNIQUE) håndhever unikhet i en kolonne eller kolonnesett.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 8 3 poeng Kap. 3

Vurder følgende DDL:

CREATE TABLE A (
    aid  varchar(20),
    val  integer,
    PRIMARY KEY (aid)
);

CREATE TABLE B (
    bid  varchar(20),
    ref  varchar(20),
    PRIMARY KEY (bid),
    FOREIGN KEY (ref) REFERENCES A
);

Hvilken av følgende setninger er sann?

  • A Spørringen feiler fordi ingen kolonne ble navngitt i fremmednøkkel-definisjonen.
  • B Spørringen lykkes; B.ref refererer A.aid (primærnøkkelen).
  • C Spørringen lykkes; B.ref refererer A.val siden den har samme posisjon.
  • D Spørringen feiler fordi A.val og B.ref har ulike domener.
Vis fasit
Riktig svar: B

Når en FOREIGN KEY skrives som REFERENCES <tabell> uten å spesifisere en kolonne, refererer den til primærnøkkelen til den nevnte tabellen. Her blir B.ref → A.aid. Typene matcher (varchar(20)) så constraint-en kan opprettes uten problemer.

A er feil — SQL-standarden tillater å droppe kolonnenavnet dersom man refererer PK. C er feil — SQL bruker ikke posisjon for å avgjøre referansen, kun primærnøkkelen som default. D er feil — typene matcher her, og uansett ville referansen gått til aid, ikke val.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 9 3 poeng Kap. 4

Vurder følgende ER-fragment: Entiteten Customer har en 1:N-relasjon "places" med entiteten Order. Det er total deltakelse fra Order og partial deltakelse fra Customer. Hvilken av påstandene under er sann?

  • A To ulike Order-rader kan ikke tilhøre samme Customer.
  • B Hver Order må være knyttet til nøyaktig én Customer.
  • C Hver Customer må ha minst én Order.
  • D Order er en svak entitet på grunn av total deltakelse.
Vis fasit
Riktig svar: B

1:N "places" mellom Customer og Order betyr én Customer kan plassere mange Orders, men hver Order tilhører maks én Customer. Total deltakelse fra Order betyr at hver Order må delta i relasjonen — altså må knyttes til én (og bare én) Customer.

A er feil — N-siden tillater nettopp at flere Orders deler samme Customer. C er feil — partial deltakelse fra Customer betyr at en Customer ikke trenger Orders. D er feil — total deltakelse alene gjør ikke en entitet svak; svake entiteter har ikke egen primærnøkkel og er identifisert via en sterk entitet via en identifying relationship.

Pensum: Kap. 4 — ER-modellen

Spørsmål 10 3 poeng Kap. 4

Et ER-diagram inneholder:

  • Entiteten Person med attributter name og ssn (PK).
  • Entiteten Vehicle med attributter regNo (PK) og color.
  • En M:N-relasjon Owns mellom Person og Vehicle, med relasjonsattributtet since.

Hva er minimum antall relasjoner (tabeller) som trengs for å mappe dette til relasjonsmodellen?

  • A 1
  • B 2
  • C 3
  • D 4
Vis fasit
Riktig svar: C

Hver entitet får sin egen tabell: Person og Vehicle. M:N-relasjoner kan ikke mappes ved å legge en fremmednøkkel inn i en av entitetstabellene; de krever en egen koblingstabell. Owns blir en tabell med kolonnene (ssn, regNo, since) der (ssn, regNo) er sammensatt PK + FKs til Person og Vehicle. Totalt 3 tabeller.

A og B undervurderer — to entiteter alene kan ikke uttrykke M:N med relasjonsattributt. D er for mange — vi trenger ikke ekstra tabell for since, det blir bare en kolonne i Owns.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 11 4 poeng Kap. 4

Vi har tabellen

Country(code, name, capital, population)
F = { code → name, capital, population;
      name → code }

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

  • A 1NF
  • B 2NF
  • C 3NF
  • D BCNF
Vis fasit
Riktig svar: D

Kandidatnøklene er {code} og {name} (begge er minimale supernøkler — fra code → ... og name → code → ...). Hver attributt er prim (alle 4 tilhører en kandidatnøkkel? Faktisk er bare code og name prim — capital og population er ikke-prim).

BCNF krever at venstresiden i hver ikke-triviell FD er en supernøkkel. Sjekk: code → alle: code er supernøkkel ✓. name → code: name er supernøkkel ✓ (siden name er kandidatnøkkel). Begge FDs har supernøkkel-LHS, så BCNF er oppfylt.

Siden BCNF impliserer 3NF, 2NF og 1NF, er BCNF det høyeste nivået som er oppfylt. A, B, C er alle "for lave" — vi har strengere holdt fremover enn 3NF.

Pensum: Kap. 4 — Normalformer

Spørsmål 12 4 poeng Kap. 3

Hvilken av påstandene om join-operasjoner er sann?

  • A Resultatet av en INNER JOIN er alltid mindre enn resultatet av kryssproduktet av samme tabeller.
  • B En LEFT OUTER JOIN gir alltid færre rader enn den tilsvarende INNER JOIN.
  • C En NATURAL JOIN fungerer kun på heltall-attributter.
  • D Resultatet av en LEFT OUTER JOIN har alltid minst like mange rader som tilsvarende INNER JOIN.
Vis fasit
Riktig svar: D

LEFT OUTER JOIN beholder alle rader fra venstre tabell — også de uten match (kompletteres med NULL i høyre kolonner). Inner-resultatet er en delmengde av outer-resultatet, så outer ≥ inner.

A er feil — INNER JOIN kan være lik kryssproduktet hvis predikatet alltid er sant (f.eks. JOIN B ON 1=1). B er omvendt riktig retning. C er feil — NATURAL JOIN matcher kolonner med samme navn, uavhengig av type så lenge typene er sammenlignbare.

Pensum: Kap. 2 — Joins og outer joins

Del 2 — Svein Erik (~60 %)

Konkrete regneoppgaver i samme stil som tidligere eksamener — B+-trær, hashing, access paths, join, sortering, 2PL og ARIES.

Spørsmål 13 4 poeng Kap. 6

Vi har et clustered B+-tre hvor vi setter inn 18 000 studentposter av størrelse 200 byte. Nøkkelen er studNr på 4 byte. En RecordID er 12 byte og en BlockId er 8 byte. En blokk er 4096 (4K) byte. Hvor mange blokker finnes på løvnivå (level=0) i B+-treet etter at alle postene er satt inn? Anta blokkene har 2/3 fyllgrad.

  • A 1385
  • B 90
  • C 1500
  • D Ingen av de andre alternativene er riktige
Vis fasit
Riktig svar: A

I et clustered B+-tre lagres hele postene på løvnivå. Tilgjengelig plass per blokk: 4096 · 2/3 ≈ 2730 byte. Poster per løvblokk: floor(2730 / 200) = 13. Antall løvblokker: ceil(18 000 / 13) = ceil(1384.6) = 1385.

B (90) deler 18000 på 200 — feil enhet. C (1500) bruker 100 % fyllgrad: floor(4096/200)=20 → 18000/20 = 900, men det er heller ikke konsistent.

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

Spørsmål 14 4 poeng Kap. 6

Samme oppsett som forrige oppgave: 18 000 poster på 200 byte, key = 4 byte, BlockId = 8 byte, blokker 4096 byte, 2/3 fyllgrad. Hvor mange blokker finnes på level=1 i B+-treet?

  • A 5
  • B 1
  • C 7
  • D 8
  • E Ingen av de andre alternativene er riktige
Vis fasit
Riktig svar: C

Indre nivåer lagrer (key, BlockId)-par på 4 + 8 = 12 byte. Ved 2/3 fyllgrad: floor(2730 / 12) = 227 par per indre blokk. Antall pekere som trengs på level 1 er antall løvblokker: 1385. Level 1: ceil(1385 / 227) = ceil(6.10) = 7 blokker.

A (5) er for lite — fan-out er ikke 277. B (1) er roten. D (8) er nær men feil — 1385/200 ≈ 6.9 rundes ned til 7, ikke opp til 8 (faktisk regnestykket er 1385/227 = 6.10 → ceil = 7).

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

Spørsmål 15 4 poeng Kap. 6

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

20, 21, 22, 23, 24, 25, 26, 27, 28

Hash-strukturen er tom fra før og har 4 blokker, der hver blokk kan inneholde to nøkler. Vi bruker separat lenket overløp hvis en blokk blir full. Bruk hashfunksjonen h(K) = K mod 4 til å sette inn nøklene i rekkefølgen gitt over. Hvor mange blokkaksesser får vi gjennomsnittlig per aksess av en tilfeldig nøkkel? Rund av svaret til to desimaler.

  • A 1.00
  • B 1.11
  • C 1.22
  • D 1.33
Vis fasit
Riktig svar: B

Plasser nøklene etter K mod 4:

  • Blokk 0: 20, 24 — full. Deretter 28 → overløpsblokk [28].
  • Blokk 1: 21, 25.
  • Blokk 2: 22, 26.
  • Blokk 3: 23, 27.

Aksesser per nøkkel: 8 nøkler i hovedblokkene gir 1 aksess hver; 28 i overløpet gir 2 aksesser. Snitt: (8·1 + 1·2) / 9 = 10/9 ≈ 1.11.

A (1.00) ville krevd at ingen er i overløp. C (1.22) regner med to nøkler i overløp — bare én er det. D (1.33) ville krevd 3 nøkler i overløp.

Pensum: Kap. 6 — Statisk hashing

Spørsmål 16 5 poeng Kap. 6

Vi starter med en extendible hashing-struktur hvor det er 4 pekere til 4 tomme blokker (lokal og global dybde = 2). Hver blokk har plass til to nøkler. Så settes følgende nøkler inn:

3, 5, 8, 16, 11, 4, 12, 1, 2

Når alle nøklene er satt inn, hvor mange blokker har lokal dybde = 3? Bruk h(K) = K mod 8.

  • A 0
  • B 4
  • C 1
  • D 2
  • E 3
  • F Ingen av de andre alternativene stemmer
Vis fasit
Riktig svar: D

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

  • 3 (011 → 11) → bucket 11 = [3]
  • 5 (101 → 01) → bucket 01 = [5]
  • 8 (000 → 00) → bucket 00 = [8]
  • 16 (10000 → 00) → bucket 00 = [8, 16] full
  • 11 (1011 → 11) → bucket 11 = [3, 11] full
  • 4 (100 → 00) → bucket 00 full, LD=GD=2 → directory dobles, GD=3. Rehash 8 (000) og 16 (000) — begge til 000. Ny bucket 100 tom. Sett inn 4 → bucket 100 = [4]. Begge LD=3.
  • 12 (1100 → 100) → bucket 100 = [4, 12] full
  • 1 (001 → 001) → bucket 01 (LD=2, peker både 001 og 101) = [5, 1] full
  • 2 (010 → 010) → bucket 10 (LD=2) = [2]

Sluttilstand: 5 blokker totalt. To av dem (000 og 100) har LD=3; de tre andre (01, 10, 11) har fortsatt LD=2.

A (0) glemmer doblingen ved innsetting av 4. C (1) regner bare den nye buckten, ikke begge. E (3) overdriver — det skjer kun én doubling. B (4) er for mye — vi har bare 2 buckets etter splitten.

Pensum: Kap. 6 — Extendible hashing

Spørsmål 17 4 poeng Kap. 7

Vi har et clustered B+-tre indeksert på OrdreId hvor vi lagrer ordreposter, hver post 200 byte. OrdreId er 4 byte. Blokkene er 4096 byte. Det er 1500 blokker på løvnivå (level=0) og 3 nivåer i B+-treet. I tillegg finnes et unclustered B+-tre på Kunde med 350 blokker på løvnivå og 3 nivåer.

Vi har queriet:

SELECT * FROM Ordre WHERE OrdreId = 8123;

Hvor mange blokker aksesseres ved optimal utføring?

  • A 1502
  • B 4
  • C 3
  • D 503
Vis fasit
Riktig svar: C

Optimal access path: bruk det clustered B+-treet på OrdreId. Traversér fra rot → level 1 → løvblokk = 3 blokkaksesser. Fordi treet er clustered, ligger hele raden på løvnivå — ingen ekstra heap-aksess nødvendig.

A (1502) ville vært full scan av løvnivået + en eller to blokker — meningsløst når vi har en B+-tree. B (4) inkluderer feilaktig en ekstra heap-blokk (riktig for unclustered, ikke clustered). D (503) brukerd det unclustered treet på Kunde, men WHERE-predikatet er på OrdreId — det treet hjelper ikke.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 18 4 poeng Kap. 7

Samme oppsett som forrige oppgave (clustered B+-tre på OrdreId med 1500 løvblokker og 3 nivåer; unclustered B+-tre på Kunde med 350 løvblokker og 3 nivåer). Vi har queriet:

SELECT OrdreId FROM Ordre WHERE Kunde = 'Hansen';

Antall ordre fra 'Hansen' er antatt nøyaktig 1. Hvor mange blokker aksesseres ved optimal utføring?

  • A 502
  • B 6
  • C 3
  • D 4
Vis fasit
Riktig svar: D

Bruk det unclustered treet på Kunde: 3 blokkaksesser (rot → level 1 → løv) for å finne (Kunde, RID)-paret. Deretter må vi følge RID til selve raden i det clustered treet — 1 blokkaksess (RID peker direkte til løvblokken). Totalt: 3 + 1 = 4.

A (502) er full scan av Kunde-indeksens løvnivå pluss en blokk — overflødig. B (6) ville krevd å traversere det clustered treet (3 blokker) etter unclustered (3) — men en RID gir oss direkte tilgang til løvblokken. C (3) glemmer at vi må hente selve raden for å få OrdreId.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 19 4 poeng Kap. 7

Samme oppsett som forrige oppgave. Vi har queriet:

SELECT Kunde FROM Ordre ORDER BY Kunde ASC;

Hvor mange blokker aksesseres ved optimal utføring?

  • A 1503
  • B 350
  • C 3
  • D 352
Vis fasit
Riktig svar: D

Det unclustered B+-treet på Kunde har allerede løvene sortert på Kunde. Vi trenger bare å lese hele løvnivået i sortert rekkefølge — ingen sortering kreves, og vi trenger ikke besøke selve heap-radene fordi Kunde ligger i indeksens løv.

Kostnad: traverser fra rot ned til venstre løvblokk = levels − 1 = 2 blokkaksesser, deretter walk gjennom alle 350 løvblokker = totalt 2 + 350 = 352.

A (1503) er full scan av clustered tree pluss noe — bortkastet siden vi har Kunde-indeks sortert. B (350) glemmer traverseringen ned til første løvblokk. C (3) er kun ett oppslag — ikke nok til å levere alle radene sortert.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 20 5 poeng Kap. 7

Vi skal joine to tabeller Bestilling og Vare med nested loop-join. Bestilling består av 25 blokker. Vare består av 800 blokker. Hvor mange blokker leses når vi skal joine disse to tabellene og vi har plass til 6 blokker i buffer?

  • A 825
  • B 4825
  • C 5625
  • D 20025
  • E Ingen av de andre alternativene stemmer
Vis fasit
Riktig svar: C

Plasser den minste tabellen ytterst (Bestilling, 25 blokker). Med B = 6 brukes 1 blokk til indre + 1 til output, så ytre chunk = B − 2 = 4 blokker.

Antall ytre chunks: ceil(25 / 4) = 7. For hver chunk leser vi hele indre tabell: 7 · 800 = 5600 blokker. Pluss ytre tabell leses én gang totalt: 25. Sum: 25 + 5600 = 5625.

A (825) ville vært bare ett pass av begge — feil med utilstrekkelig buffer. B (4825) feilteller chunks (6 i stedet for 7). D (20025) bruker Vare som ytre — verre fordi den er større. E er ikke aktuelt: 5625 finnes som alternativ.

Pensum: Kap. 7 — Join-algoritmer

Spørsmål 21 5 poeng Kap. 7

Vi har en usortert fil bestående av 800 blokker med poster og et buffer med plass til 6 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 1600
  • B 4800
  • C 8000
  • D 6400
  • E 16000
  • F Ingen av de andre alternativene stemmer
Vis fasit
Riktig svar: C

Sort-fasen lager n_R = ceil(800 / 6) = 134 initielle runs. Merge-grad d_M = min(6 − 1, 134) = 5.

Antall merge-passes: etter hver pass deles antall runs på d_M:

  • Pass 1: ceil(134/5) = 27 runs.
  • Pass 2: ceil(27/5) = 6 runs.
  • Pass 3: ceil(6/5) = 2 runs.
  • Pass 4: 1 run.

Totalt: 1 sort-pass + 4 merge-passes = 5 passes. Hver pass leser og skriver alle 800 blokker = 2 · 800 = 1600. Sum: 5 · 1600 = 8000.

A (1600) er kun én pass. B (4800) er 3 passes. D (6400) er 4 passes (glemmer sort-fasen som ekstra). E (16000) er 10 passes — for mange. F er ikke aktuelt.

Pensum: Kap. 7 — External merge sort

Spørsmål 22 3 poeng Kap. 8

Hva er recovery-egenskapen til følgende historie?

w1(A); w2(A); c1; c2;
  • A Strict
  • B Recoverable (gjenopprettbar)
  • C ACA (unngår galopperende abort)
  • D Unrecoverable (ikke gjenopprettbar)
Vis fasit
Riktig svar: C

Vi spør etter den mest spesifikke egenskapen som er oppfylt.

  • Strict? Nei: w2(A) skriver A mens T1's w1(A) ikke er committet. Strict krever at T2 venter på T1's commit/abort før den rører A.
  • ACA? Ja: ACA krever at man ikke leser en uncommitted skriving. Her er det ingen lesinger. ✓
  • Recoverable? Ja (følger av ACA), men ACA er strengere.

A (strict) er feil — w-w-konflikt med uncommitted T1. B (recoverable) er sann men ikke mest spesifikk. D (unrecoverable) ville krevd at T2 leste fra T1 og committet før T1.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 23 5 poeng Kap. 8

Hvilken av følgende historier er konfliktserialiserbar?

  • A r1(X); w1(Y); r2(Y); r3(Z); w3(X); w2(Z);
  • B r1(A); w2(A); r3(A); w1(A);
  • C r1(X); r2(Y); w2(X); w1(Y);
  • D w1(A); r2(B); w2(A); w1(B);
Vis fasit
Riktig svar: A

Bygg presedensgraf for hvert alternativ.

A: konflikter er r1(X)–w3(X) (T1→T3), w1(Y)–r2(Y) (T1→T2), r3(Z)–w2(Z) (T3→T2). Kanter: T1→T3, T1→T2, T3→T2. Ingen sykel → konfliktserialiserbar (T1, T3, T2). ✓

B: r1(A)–w2(A) (T1→T2), w2(A)–w1(A) (T2→T1). Sykel T1↔T2. ✗

C: r1(X)–w2(X) (T1→T2), r2(Y)–w1(Y) (T2→T1). Sykel T1↔T2. ✗

D: w1(A)–w2(A) (T1→T2), r2(B)–w1(B) (T2→T1). Sykel T1↔T2. ✗

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 24 5 poeng Kap. 8

Vi skal sette tofaselåser (2PL) ved hjelp av metoden rigorous. I hvilken rekkefølge committer de tre transaksjonene T1, T2 og T3? Følgende sekvens av operasjoner kommer inn til databasen:

r1(X); r2(Y); w1(Y); r3(Z); w2(Z); c1; c2; c3;
  • A T1; T2; T3;
  • B T2; T1; T3;
  • C T3; T2; T1;
  • D T1; T3; T2;
  • E Vranglås mellom T1 og T2.
Vis fasit
Riktig svar: C

Trace med rigorous 2PL:

  • r1(X): T1 tar rl(X).
  • r2(Y): T2 tar rl(Y).
  • w1(Y): T1 vil ha wl(Y), men T2 holder rl(Y) → T1 venter.
  • r3(Z): T3 tar rl(Z).
  • w2(Z): T2 vil ha wl(Z), men T3 holder rl(Z) → T2 venter.
  • c1, c2: begge venter. c3: T3 committer, slipper rl(Z). T2 vekkes, får wl(Z), gjør w2(Z), committer. T2 slipper rl(Y) og wl(Z). T1 vekkes, får wl(Y), gjør w1(Y), committer.

Rekkefølge: T3 → T2 → T1.

A og B går feil vei. D plasserer T2 sist. E er feil — det er ingen sykel: T2 venter på T3 (ikke T1), så vranglås oppstår ikke.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 25 5 poeng Kap. 8

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

LSNPrevLSNTIDOperasjonPageID
10099T1UpdateA
1010T2UpdateB
102100T1UpdateC
103101T2UpdateC
104102T1UpdateD
105Ckpt start
106Ckpt end
107104T1Commit
108103T2UpdateE
1090T3UpdateF
110108T2Commit

I sjekkpunktloggposten med LSN=106 ble TT funnet: (T1, LastLSN=104, Active), (T2, LastLSN=103, Active). DPT funnet: (B, recLSN=101), (C, recLSN=102). Hvilken DPT er korrekt etter at analysen er ferdig?

  • A {(B,101), (C,102), (D,104), (E,108), (F,109)}
  • B {(B,101), (C,102), (E,108), (F,109)}
  • C {(A,100), (B,101), (C,102), (E,108), (F,109)}
  • D {(E,108), (F,109)}
Vis fasit
Riktig svar: B

Analyse-fasen starter ved sjekkpunktets DPT/TT og leser loggen forover fra LSN 105. Eldre updates (100–104) trenger vi ikke behandle — de er allerede oppsummert i sjekkpunktets DPT.

  • LSN 107 (T1 commit): TT[T1] → Commit. DPT uendret.
  • LSN 108 (T2 update E): E ikke i DPT → legg til (E, 108). TT[T2].LastLSN = 108.
  • LSN 109 (T3 update F): T3 ikke i TT → legg til (T3, 109, Active). DPT: legg til (F, 109).
  • LSN 110 (T2 commit): TT[T2] → Commit.

Sluttinnhold DPT: (B,101), (C,102), (E,108), (F,109).

A legger feilaktig til D (LSN 104 var før sjekkpunktet, og siden D ikke er i sjekkpunktets DPT, ble den allerede flushet). C legger feilaktig til A av samme grunn. D mister carry-over fra sjekkpunktet.

Pensum: Kap. 8 — Recovery

Spørsmål 26 4 poeng Kap. 8

Med samme logg som forrige oppgave: hvilke loggposter genereres under undo-fasen av recovery? CLR betyr Compensating Log Record. Format på loggpostene under er (LSN, PrevLSN, TransactionID, Operation, PageID).

  • A (111, 109, T3, CLR av 109, F), (112, 111, T3, Abort, )
  • B (111, 110, T2, CLR av 110, ), (112, 111, T2, Abort, )
  • C (111, 104, T1, CLR av 104, D), (112, 111, T1, CLR av 102, C), (113, 112, T1, CLR av 100, A), (114, 113, T1, Abort, )
  • D Ingen loggposter genereres.
Vis fasit
Riktig svar: A

Etter analysen: vinnere = T1 og T2 (begge committet); taper = T3 (Active, LastLSN=109). Undo prosesserer kun tapere baklengs.

For T3, siste handling er LSN 109 (Update F). Skriv CLR for 109: (111, prevLSN=109, T3, CLR of 109, F). T3's prevLSN ved 109 er 0 → ingenting mer å undoe. Skriv abort-record: (112, prevLSN=111, T3, Abort).

B undoer T2 — feil, T2 committet. C undoer T1 — feil, T1 committet. D ignorerer at T3 var aktiv ved krasj og må undoes.

Pensum: Kap. 8 — Recovery

Slutt på øvingseksamen 05.