Øvingseksamen 02 · TDT4145

Øvingseksamen 02

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

Hovedfokus: arkitektur, fundamentale RA, GRANT/REVOKE, ISA, heap-header, J1, ACID, DPT.

Del 1 — Theodoros (~40 %)

Introduksjon, relasjonsmodell, SQL, ER-modellering, normalformer.

Spørsmål 1 3 poeng Kap. 1

I tre-skjema-arkitekturen skiller man mellom internt (fysisk), konseptuelt (logisk) og eksternt (view) skjema. Hva er forskjellen mellom logisk og fysisk datauavhengighet?

A Logisk datauavhengighet betyr at applikasjoner overlever endringer i fysisk lagring (f.eks. nye indekser); fysisk datauavhengighet at views kan endres uten å endre tabellene.
B Logisk datauavhengighet sikrer at lagringsstrukturen kan endres uten å påvirke det konseptuelle skjemaet, mens fysisk datauavhengighet sikrer at views ikke endres ved DDL-oppdateringer.
C Logisk datauavhengighet betyr at views overlever endringer i det konseptuelle skjemaet (f.eks. å splitte en tabell); fysisk datauavhengighet at det konseptuelle skjemaet overlever endringer i lagringsstrukturen.
D Logisk og fysisk datauavhengighet er to navn på samme egenskap — separasjonen mellom DDL og DML.

Vis fasit

Riktig svar: C

Logisk datauavhengighet beskytter views mot endringer i det konseptuelle skjemaet — du kan splitte en tabell i to og rekonstruere viewet med en join. Fysisk datauavhengighet beskytter det konseptuelle skjemaet mot endringer i lagringen — du kan legge til en B+-indeks eller skifte filorganisering uten å endre logiske spørringer.

A bytter om begrepene (logisk/fysisk er speilvendt). B snur retningen igjen og glemmer at det er views som beskyttes av logisk uavhengighet, ikke skjemaet. D blander datauavhengighet sammen med språkdefinisjonen DDL/DML.

Pensum: Kap. 1 — Introduksjon

Spørsmål 2 3 poeng Kap. 2

Hvilken mengde inneholder utelukkende fundamentale (primitive) operatorer i relasjonsalgebra — det vil si en minimal mengde som de øvrige operatorene kan defineres ut fra?

A { σ (selection), π (projection), ⋈ (natural join), ÷ (division), ∪ (union), ρ (rename) }
B { σ (selection), π (projection), × (cross product), − (set difference), ∪ (union), ρ (rename) }
C { σ (selection), π (projection), ⋈ (natural join), ⋈ₙ (theta join), ∩ (intersection), ÷ (division) }
D { σ (selection), π (projection), ⋈ (natural join), ∪ (union), ∩ (intersection), − (set difference) }

Vis fasit

Riktig svar: B

De seks fundamentale operatorene i Codds RA er σ, π, ×, −, ∪ og ρ. Resten kan utledes: ∩ = R − (R − S); enhver join er σ etterfulgt av π over et ×; ÷ er en kombinasjon av ×, π og −; theta-join er σ over ×.

A inkluderer ⋈ og ÷ — begge avledede. C blander to join-varianter og to avledede operatorer. D mangler både × og ρ, og inkluderer ∩ som er avledet.

Pensum: Kap. 2 — Relasjonsalgebra

Spørsmål 3 3 poeng Kap. 2

Tabellen R(a, b, c, d) har funksjonelle avhengigheter:

F = { a → b,   b → c,   c → d }

Hvilken mengde er kandidatnøkkelen(e) til R?

A {a} er den eneste kandidatnøkkelen.
B {a} og {b} er begge kandidatnøkler.
C {a, b} er den eneste kandidatnøkkelen — single attributter er aldri nok.
D Både {a} og {a, c} er kandidatnøkler.

Vis fasit

Riktig svar: A

Vi beregner attributthyller. a⁺ = {a, b, c, d} ved kjeden a→b→c→d, så {a} er supernøkkel og minimal — alstå kandidatnøkkel. b⁺ = {b, c, d} mangler a, så {b} er ikke supernøkkel. Ingen annen ekte mengde er minimal supernøkkel.

B overser at FD-pilene går én vei (vi har a→b, ikke b→a). C ignorerer at hyllen til {a} faktisk dekker alt. D inkluderer {a, c} som ikke er minimal — {a} alene er allerede supernøkkel.

Pensum: Kap. 4 — Normalformer

Spørsmål 4 3 poeng Kap. 3

Du oppretter:

CREATE TABLE Bok (
    isbn          CHAR(13) PRIMARY KEY,
    tittel        VARCHAR(200) NOT NULL,
    forfatter_id  INT,
    utgitt        INT CHECK (utgitt BETWEEN 1900 AND 2030),
    FOREIGN KEY (forfatter_id) REFERENCES Forfatter(id)
);

Forfatter-tabellen inneholder allerede id-ene 4, 7 og 12. Hvilken INSERT vil DBMS-et avvise?

A INSERT INTO Bok VALUES ('9780136091813', 'Refactoring', 7, 1999);
B INSERT INTO Bok VALUES ('9780262033848', 'CLRS', NULL, 2009);
C INSERT INTO Bok (isbn, tittel, forfatter_id, utgitt) VALUES ('9780131103627', 'C', 12, 1988);
D INSERT INTO Bok VALUES ('9780747532699', NULL, 4, 1997);

Vis fasit

Riktig svar: D

D bryter NOT NULL på tittel. A passerer alle constraints (forfatter 7 finnes, utgitt 1999 ∈ [1900, 2030]). B er gyldig fordi forfatter_id ikke har NOT NULL, og NULL i en FK-kolonne er tillatt — det betyr "ingen referanse". C passerer på samme måte (forfatter 12 finnes, utgitt 1988 i intervallet).

A og C kan friste dem som tror at "forfatter må alltid finnes" — men det er FK-en som krever det, og bare når kolonnen ikke er NULL. B kan friste fordi noen tror NULL alltid bryter en FK; SQL-standarden tillater det med mindre NOT NULL er satt eksplisitt.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 5 3 poeng Kap. 3

Tabellen Ordre:

oid	kunde	total
1	A	100
2	A	200
3	B	50
4	C	300
5	B	60
6	C	80

SELECT kunde, COUNT(*) AS antall, SUM(total) AS sum
FROM Ordre
GROUP BY kunde
HAVING SUM(total) > 100
ORDER BY sum DESC;

Hva blir første rad i resultatet?

A A, 2, 300
B B, 2, 110
C C, 2, 380
D A, 3, 350

Vis fasit

Riktig svar: C

Etter GROUP BY kunde: A→{antall=2, sum=300}, B→{2, 110}, C→{2, 380}. HAVING SUM(total) > 100 beholder alle tre (alle har sum > 100). Sortert DESC på sum: C(380) → A(300) → B(110). Første rad: C, 2, 380.

A overser sortering — A har lavere sum enn C. B har lavest sum og kommer sist. D antar at HAVING går på COUNT(*) (3 rader for A) og at A blander seg med B; ingen kunde har 3 ordrer.

Pensum: Kap. 3 — DDL og spørringer

Spørsmål 6 3 poeng Kap. 3

Tabellen Ansatt:

aid	navn	sjef_id
1	Anna	NULL
2	Bjørn	1
3	Cecilie	1
4	David	2
5	Eli	2

SELECT a.navn AS ansatt, s.navn AS sjef
FROM Ansatt a JOIN Ansatt s ON a.sjef_id = s.aid;

Hvor mange rader returnerer spørringen?

Vis fasit

Riktig svar: B

Anna har sjef_id = NULL, og NULL = aid evaluerer alltid til UNKNOWN — ingen match i en inner join. De fire andre har match: Bjørn→Anna, Cecilie→Anna, David→Bjørn, Eli→Bjørn. Resultat: 4 rader.

A glemmer at to ansatte deler én sjef (Anna eller Bjørn) — vi får én rad per ansatt-sjef-kobling, ikke per sjef. C inkluderer Anna ved å forveksle inner join med outer. D dobler eller tar kryssproduktet.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 7 3 poeng Kap. 3

Tabeller:

Studenter(sid, navn) = { (1, Anna), (2, Bjørn), (3, Cecilie) }
Stryk(sid)         = { (2), (NULL) }

Hvilken spørring (eller spørringer) returnerer Anna og Cecilie — det vil si studenter som ikke har strøket?

SELECT navn FROM Studenter WHERE sid NOT IN (SELECT sid FROM Stryk);
SELECT navn FROM Studenter s WHERE s.sid NOT IN (SELECT sid FROM Stryk WHERE sid IS NOT NULL);
SELECT navn FROM Studenter s WHERE NOT EXISTS (SELECT 1 FROM Stryk t WHERE t.sid = s.sid);

A Bare 1.
B Bare 1 og 3.
C Bare 2.
D Bare 2 og 3.

Vis fasit

Riktig svar: D

Spørring 1 feiler: NOT IN sammenlignes med en mengde som inneholder NULL, og evalueringen av sid <> NULL er UNKNOWN — derfor returnerer hele NOT IN aldri TRUE, og ingen rader kommer ut. Spørring 2 fjerner NULL eksplisitt og virker korrekt. Spørring 3 bruker NOT EXISTS: t.sid = s.sid evalueres til UNKNOWN når t.sid er NULL, men det blir ikke TRUE, så raden filtreres ikke ut — Anna og Cecilie returneres.

A og B feilaktig stoler på at NOT IN håndterer NULL trygt. C overser at NOT EXISTS løser samme problem på en annen måte.

Pensum: Kap. 3 — Joins og subqueries

Spørsmål 8 3 poeng Kap. 3

Hva er hovedforskjellen mellom en vanlig view og en materialisert view?

A En materialisert view lagrer resultatet fysisk på disk og må refreshes; en vanlig view re-evalueres ved hver bruk.
B En materialisert view kan oppdateres med UPDATE/INSERT/DELETE, mens en vanlig view alltid er read-only.
C En materialisert view fungerer kun mot heap-filer, mens en vanlig view kan brukes mot tabeller med indekser.
D En materialisert view kan kun inneholde en SELECT på én tabell, mens en vanlig view kan inneholde joins.

Vis fasit

Riktig svar: A

Forskjellen er persistens. En materialisert view lagrer resultatet av spørringen som ekte rader på disk — det gir rask lesing, men krever at viewet enten gjenoppbygges eller inkrementelt vedlikeholdes når kildene endres. En vanlig view er kun en navngitt spørringsdefinisjon (makro) som ekspanderes inn i den ytre spørringen og evalueres på nytt hver gang.

B forveksler updatability — det er en separat egenskap som gjelder begge view-typer. C og D er fabrikerte regler uten basis i SQL-standarden.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 9 3 poeng Kap. 3

Du vil opprettholde en aggregat-tabell BibliotekStat(filial_id, antall_lån) som teller antall utlån per filial. Hver gang det settes inn en rad i Lån(låne_id, filial_id, dato), skal det tilsvarende antall_lån økes med 1. Hvilken trigger-type passer best?

A BEFORE INSERT FOR EACH ROW på Lån.
B BEFORE STATEMENT på Lån.
C AFTER INSERT FOR EACH ROW på Lån.
D INSTEAD OF INSERT FOR EACH ROW på Lån.

Vis fasit

Riktig svar: C

AFTER INSERT FOR EACH ROW kjøres etter at hver innsatte rad er garantert skrevet og constraints er sjekket — eksakt riktig tidspunkt for å oppdatere derivert data. Triggeren bruker NEW-radens filial_id til en UPDATE BibliotekStat SET antall_lån = antall_lån + 1 WHERE filial_id = NEW.filial_id;.

A er feil — i en BEFORE-trigger er ikke raden ennå garantert å bli skrevet (en CHECK eller FK kan avvise den senere), så aggregatet kan ende opp inkonsistent. B kjøres før eller etter hele setningen, ikke per rad — vanskelig å avlede den enkelte filial-id-en. D brukes på views (eller for å overstyre en innsetting), ikke for å reagere på en innsetting.

Pensum: Kap. 3 — Prosedyrer, triggere, rekursjon

Spørsmål 10 3 poeng Kap. 3

Administrator A kjører:

GRANT SELECT, UPDATE ON Lønn TO B WITH GRANT OPTION;

Deretter kjører B:

GRANT SELECT ON Lønn TO C;

Til slutt kjører A:

REVOKE UPDATE ON Lønn FROM B;

Hvilke rettigheter har C på Lønn etterpå?

A SELECT og UPDATE.
B Ingen — REVOKE-en kaskaderer og fjerner alle rettigheter B har gitt videre.
C UPDATE.
D SELECT.

Vis fasit

Riktig svar: D

Kaskadering i REVOKE skjer kun for den spesifikke rettigheten som er trukket tilbake. A trekker tilbake UPDATE fra B; siden B aldri ga UPDATE videre til C, er det ingenting å kaskadere på den fronten. B sin SELECT-rett består fortsatt (den ble ikke revoket), og C har derfor fortsatt SELECT.

A overser at B aldri ga UPDATE til C. B feiltolker kaskadering — det handler om samme rett, ikke alle. C er et speilbilde av riktig svar.

Pensum: Kap. 3 — Views, transaksjoner, integritet

Spørsmål 11 4 poeng Kap. 4

Et ER-diagram inneholder:

Sterk entitet Kunde (PK kid)
Sterk entitet Bestilling (PK bid)
Sterk entitet Produkt (PK pid)
Relasjon "legger inn" (1:N) mellom Kunde og Bestilling, total deltakelse fra Bestilling
Relasjon "inneholder" (M:N) mellom Bestilling og Produkt, med attributtet kvantum

Hvor mange tabeller får vi i den mest kompakte mappingen til relasjonsmodellen?

A 4 (Kunde, Bestilling, Produkt, BestillingProdukt)
B 5 (Kunde, Bestilling, Produkt, LeggerInn, Inneholder)
C 3 (Kunde slått sammen med Bestilling, Produkt, Inneholder)
D 6 (én tabell per entitet og relasjon, pluss en hjelpetabell for kvantum)

Vis fasit

Riktig svar: A

1:N-relasjonen kan slås sammen med Bestilling-tabellen som en FK-kolonne kid — ingen ekstra tabell. M:N-relasjonen krever derimot en egen relasjonstabell BestillingProdukt(bid, pid, kvantum) med PK = (bid, pid) og FK-er til hver. Resultat: 4 tabeller.

B beholder LeggerInn som egen tabell unødvendig — det er bare en N-side med FK. C foreslår å slå sammen Kunde og Bestilling, men de har forskjellig kardinalitet (én kunde, mange bestillinger) — det blir umulig uten massiv redundans. D dupliserer kvantum.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 12 3 poeng Kap. 4

Et ISA-hierarki har superklassen Kjøretøy og subklassene Bil og Båt. Det mappes med strategien "én tabell per spesialisering" (også kalt class-table inheritance). Hvilket utsagn er korrekt?

A Bare Kjøretøy-tabellen finnes; Bil og Båt blir ekstra kolonner i den, og en type-kolonne diskriminerer mellom subklassene.
B Det opprettes én tabell totalt der alle attributter fra Kjøretøy, Bil og Båt slås sammen, med NULL der subklassene ikke matcher.
C Vi får tre tabeller: Kjøretøy med felles attributter, og Bil og Båt som hver inneholder subklasse-spesifikke attributter pluss en FK til Kjøretøy.
D Vi får to tabeller — én for Bil og én for Båt — med kopierte attributter fra Kjøretøy; superklassen har ingen egen tabell.

Vis fasit

Riktig svar: C

Class-table inheritance gir én tabell per klasse. Felles attributter (registreringsnummer, eier, ...) ligger i Kjøretøy. Hver subklasse-tabell inneholder kun de spesifikke feltene (Bil: antallHjul, Båt: skroglengde) pluss en FK til Kjøretøy. En rad om en konkret bil består av joinet mellom Kjøretøy og Bil.

A og B beskriver "single-table inheritance" (én tabell totalt med null-felt for ikke-relevante kolonner). D beskriver "class-per-leaf" / concrete-table inheritance — kompakt, men gir duplisering av Kjøretøys attributter.

Pensum: Kap. 4 — ER til relasjon

Spørsmål 13 3 poeng Kap. 4

Tabellen Salg(ordre_nr, varenr, vare_navn, antall) har FDs:

F = { (ordre_nr, varenr) → antall,   varenr → vare_navn }

PK = (ordre_nr, varenr). Hvilken normalform er Salg brutt mot, og hvorfor?

A Brutt mot 1NF — vare_navn er ikke atomær.
B Brutt mot BCNF, men ikke 3NF, fordi varenr → vare_navn har varenr som ikke-supernøkkel.
C Brutt mot 3NF — vare_navn avhenger transitivt av PK via en ikke-prim-attributt.
D Brutt mot 2NF — vare_navn er delvis avhengig av PK (avhenger av en del av PK, nemlig varenr).

Vis fasit

Riktig svar: D

2NF krever at ingen ikke-prim-attributt er delvis avhengig av en kandidatnøkkel. Her er vare_navn ikke-prim, og varenr → vare_navn er en delvis avhengighet av PK = (ordre_nr, varenr). Dette er per definisjon et 2NF-brudd. Tabellen er konsekvent også brutt mot 3NF og BCNF, men det spesifikke problemet er 2NF.

A er feil — vare_navn er en atomær streng. B kaller riktig BCNF-brudd, men feiltagger 3NF-status og overser at delvis avhengighet er det mer alvorlige bruddet. C beskriver en transitiv avhengighet (PK→X→Y), men her er varenr → vare_navn ikke transitiv via en ikke-prim — varenr er en del av PK.

Pensum: Kap. 4 — Normalformer

Del 2 — Svein Erik (~60 %)

Lagring, indekser, queries, transaksjoner og recovery.

Spørsmål 14 4 poeng Kap. 6

En heapfil lagrer 600 000 poster på 250 byte hver. Blokkstørrelsen er 4 KiB (4096 byte), men hver blokk har en header på 100 byte (link til neste blokk + ledig-liste). Hvor mange blokker brukes? (Anta blokkene fylles maksimalt med hele poster.)

A 37 500
B 40 000
C 18 750
D 60 000

Vis fasit

Riktig svar: B

Tilgjengelig dataområde per blokk: 4096 − 100 = 3996 byte. Poster per blokk: floor(3996 / 250) = 15. Antall blokker: ceil(600000 / 15) = 40000.

A (37 500) glemmer header-en og bruker floor(4096/250) = 16 poster per blokk. C (18 750) bruker en 50 % fyllgrad som ikke gjelder for heapfiler. D (60 000) tilsvarer feil divisjon (10 poster per blokk).

Pensum: Kap. 6 — Lagring

Spørsmål 15 4 poeng Kap. 6

En tabell Kommentar(id INT, tekst VARCHAR(2000), forfatter VARCHAR(50)) lagres med variabel-lengde poster. Hvilken kombinasjon er en typisk riktig representasjon?

A Hver post lagres med fast bredde 2070 byte (sum av alle maks-størrelser); ubrukt plass paddes med spaces.
B En post-header med lengdeindikator + offset-vektor til hvert variabel-felt; etterfulgt av selve feltverdiene konkatenert.
C Hver post lagres som JSON i blokken; DBMS-et parser ved hver lesing.
D Posten splittes i én blokk per attributt (kolonneorientert lagring) — kun måten å håndtere variabel lengde.

Vis fasit

Riktig svar: B

Standardimplementeringen er en post-header med record-lengde + en liten offset-vektor som peker inn i en samlet feltverdi-region (eller alternativt en delimiter mellom feltene). Da kan posten lese hver kolonne i konstant tid uten å reservere plass for maks-størrelse.

A beskriver fast-lengde, ikke variabel — sløser massivt med plass. C er en (sjelden, lite effektiv) tilnærming på applikasjonsnivå. D blander kolumnar lagring (DuckDB, ClickHouse) inn — det handler ikke om variabel lengde, men om aksess-mønster.

Pensum: Kap. 6 — Lagring

Spørsmål 16 4 poeng Kap. 6

I extendible hashing — i hvilken situasjon er det nødvendig å doble directoryet (øke global depth med 1)?

A Hver gang en hvilken som helst blokk fylles opp, uavhengig av lokale forhold.
B Når en innsetting forårsaker splitt på en blokk der lokal depth er strengt mindre enn global depth.
C Når antall poster i filen overstiger antall blokker × kapasitet per blokk.
D Når en innsetting forårsaker splitt på en blokk der lokal depth er lik global depth.

Vis fasit

Riktig svar: D

Doubling er bare nødvendig når den fulle blokken har lokal depth = global depth. Da har directoryet kun én entry som peker på blokken, og vi har ikke nok bits til å skille de to nye etterkommerne. Ved doubling økes global depth med 1, directoryet får dobbelt så mange entries, blokken splittes, og begge nye blokker får økt lokal depth med én. Hvis lokal depth < global depth peker allerede flere directory-entries på blokken, så vi kan splitte og oppdatere noen entries uten å utvide directoryet.

A overser tilfellet der lokal < global (ingen doubling). B er motsatt av riktig — det er nettopp det tilfellet som ikke trenger doubling. C beskriver "load factor"-tankegangen i statisk hashing.

Pensum: Kap. 6 — Lagring

Spørsmål 17 4 poeng Kap. 6

En tabell har 8 millioner poster. På løvnivå (level=0) i et clustered B+-tre er det 200 000 blokker. På indre nivåer er fan-out 100. Hvor mange nivåer har treet (inklusive løv = level 0)?

Vis fasit

Riktig svar: C

Level 0: 200 000 blokker. Level 1: ceil(200000 / 100) = 2000. Level 2: ceil(2000 / 100) = 20. Level 3: ceil(20 / 100) = 1 (rotnoden). Treet har dermed nivåer 0, 1, 2, 3 — totalt 4.

A og B undervurderer høyden. D telleren rotnoden som et eget ekstra nivå over.

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

Spørsmål 18 4 poeng Kap. 6

Du har et clustered B+-tre med komposittnøkkel (land, by, postnummer). Hvilken spørring vil ikke kunne bruke indeksen effektivt for å redusere blokk-aksesser via prefiks-søk?

A WHERE land = 'NO' AND by = 'Trondheim';
B WHERE land = 'NO';
C WHERE land = 'NO' AND postnummer = 7030;
D WHERE by = 'Trondheim' AND postnummer = 7030;

Vis fasit

Riktig svar: D

Et B+-tre på (land, by, postnummer) er sortert leksikografisk. Et søk må starte med første attributt (land) for at indekssøk skal være effektivt — uten ledetekst på land havner vi i en full skann av løvnivå. D har ingen land-betingelse og kan derfor ikke gjøre prefiks-seek.

A bruker første to attributter — perfekt prefiks. B bruker første attributt — gjør et range-seek på alle "NO"-rader. C bruker første attributt og hopper over det andre; indeksen kan fortsatt seek-e til "NO"-blokken og deretter filtrere på postnummer i løvet ("index range scan with residual filter") — fortsatt nyttig.

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

Spørsmål 19 4 poeng Kap. 6

Når en blokk på løvnivået i et B+-tre splittes ved innsetting, hva skjer med den nøkkelen som ligger i midten?

A Den kopieres opp som ny separator i indre nivå, og originalen blir værende i en av løvblokkene.
B Den flyttes opp til foreldernoden, og finnes etterpå kun i indre nivå og ikke i løvene.
C Den slettes fra løvnivået og erstattes av en pekertabell på indre nivå over de to nye blokkene.
D Den dupliseres i begge de nye løvblokkene, slik at begge løvblokkene har separatorverdien.

Vis fasit

Riktig svar: A

På løvnivå må alle datapostene fortsatt være tilgjengelige; derfor kopieres midt-nøkkelen opp som en separator. På indre nivåer (interne noder) er det motsatt: separator-nøkler eksisterer kun for å rute søket, så ved splitt på indre nivå flyttes midt-nøkkelen opp (ikke kopieres). Dette er en velkjent asymmetri i B+-tre-implementasjonen.

B beskriver indre-nivå-splitt, ikke løv. C er fri fantasi. D ville brutt søkesemantikken — én nøkkel-verdi tilhører én rad, og to løv med samme separatorverdi ville krevd ekstra disambiguasjon.

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

Spørsmål 20 4 poeng Kap. 7

Tabellen Bok har 50 000 rader, lagret som heap (300 blokker totalt). På sekundær-attributtet forfatter finnes et unclustered B+-tre med 3 nivåer og 80 løvblokker. Det er ingen klyngeindeks. Hvor mange blokker leses optimalt for:

SELECT * FROM Bok WHERE forfatter = 'Stroustrup';

Anta at 'Stroustrup' har skrevet 5 bøker, og at hver bok i verste fall ligger i sin egen heap-blokk (unclustered).

A 4
B 8
C 80
D 300

Vis fasit

Riktig svar: B

Vi traverserer det unclustered B+-treet fra rot til løv: 3 blokk-aksesser (treet har 3 nivåer totalt — rot, indre, løv). I løvet finner vi 5 (key, RID)-poster for 'Stroustrup'. For å hente selve bok-radene må vi i unclustered worst case besøke 5 separate heap-blokker. Totalt: 3 + 5 = 8.

A glemmer heap-aksessene. C ville lest hele indeksens løvnivå — ikke optimalt for en likhetsfilter. D er full table scan, kostnaden hvis indeksen ikke brukes.

Pensum: Kap. 7 — Spørringsutføring

Spørsmål 21 4 poeng Kap. 7

Vi joiner R (1000 blokker) med S (200 blokker) ved hjelp av block nested loop join (J1). Vi har 22 buffer-frames totalt: 1 for ytre blokk, 1 for utdata, 20 for indre. Hvilket av valgene gir lavest blokk-lesinger, og hvor mange?

A R som ytre, S som indre: 1000 + 1000 · 200 = 201 000.
B S som ytre, R som indre: 200 + 200 · 1000 = 200 200.
C S som ytre, R som indre: 200 + ceil(200/20) · 1000 = 10 200.
D R som ytre, S som indre: 1000 + ceil(1000/20) · 200 = 11 000.

Vis fasit

Riktig svar: C

Med M = 20 indre-buffere kan vi lese ytre i "chunks" av M-størrelse. Formelen for J1 med S som ytre er |S| + ceil(|S|/M) · |R|. Den minste tabellen bør være ytre — da minimerer man antall passes over den indre. Med S som ytre: 200 + ceil(200/20)·1000 = 200 + 10·1000 = 10200. R som ytre gir 1000 + ceil(1000/20)·200 = 1000 + 50·200 = 11000 — litt verre.

A og B regner med M=1 (klassisk nested loop, ikke block nested) og glemmer den store gevinsten av flere indre-buffere. D er nær men S som ytre er litt billigere (10 200 mot 11 000).

Pensum: Kap. 7 — Join-algoritmer

Spørsmål 22 4 poeng Kap. 7

Vi sorterer en fil på 600 blokker med 11 buffer-rammer tilgjengelig. Hvor mange merge-passer trengs (etter initial sort-passet)?

Vis fasit

Riktig svar: A

Initial-passet bygger nR = ceil(600/11) = 55 sorterte runs. Merge-graden er dM = min(11 − 1, 55) = 10. Antall merge-passer er ceil(log_10(55)) = 2, fordi 10¹ = 10 < 55 ≤ 10² = 100. Etter pass 1 har vi 6 runs; etter pass 2 har vi 1 — sortert.

B og C overestimerer — én ekstra pass for mye. D ville krevd at dM = 3 eller lignende.

Pensum: Kap. 7 — Sortering

Spørsmål 23 4 poeng Kap. 8

Hvilken sammenstilling kobler ACID-egenskapen riktig til mekanismen som hovedsakelig opprettholder den i et tradisjonelt RDBMS?

A Atomicity → integritetsbegrensninger; Consistency → låser; Isolation → logging; Durability → tx-loggen og buffer-pool.
B Atomicity → UNDO-loggen; Consistency → integritetsbegrensninger; Isolation → låser/MVCC; Durability → REDO-loggen.
C Atomicity → låser; Consistency → REDO-loggen; Isolation → MVCC-snapshots; Durability → periodiske checkpoints.
D Atomicity → triggere; Consistency → CHECK-constraints; Isolation → views; Durability → backups på disk.

Vis fasit

Riktig svar: B

Atomicity (alt-eller-ingenting) håndteres av UNDO — hvis en transaksjon aborterer, rulles handlingene tilbake. Consistency håndheves av integritetsbegrensninger (PK, FK, CHECK, triggere). Isolation realiseres av samtidighetskontroll (2PL, MVCC). Durability sikres av REDO-loggen og force-log-at-commit (write-ahead logging garanterer at committed transaksjoner overlever crash).

A bytter om Atomicity og Consistency, og setter logging på feil bokstav. C kobler Atomicity til låser (de garanterer Isolation, ikke Atomicity). D er overflatisk og misforstår — backup er disaster recovery, ikke Durability per transaksjon.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 24 4 poeng Kap. 8

Vurder schedulen under, der T1 leser X to ganger og T2 modifiserer X mellom dem:

r1(X); r2(X); w2(X); c2; r1(X); c1;

Hvilken anomali er dette et eksempel på?

A Lost update.
B Dirty read.
C Phantom.
D Unrepeatable read.

Vis fasit

Riktig svar: D

T1 leser X på r1(X) (verdi v1), så commit-er T2 en ny verdi for X, og T1 leser X igjen og får en annen verdi. Det er per definisjon "unrepeatable read" — samme transaksjon ser inkonsistente verdier av samme rad.

A (lost update) ville krevd at to transaksjoner begge skriver til X uten å se hverandres skriv. B (dirty read) ville krevd at T1 leste fra T2 før T2 committet — her venter T1 til etter c2. C (phantom) handler om at en ny rad dukker opp i et range-spørring, ikke at en eksisterende rad endres.

Pensum: Kap. 8 — Transaksjoner: teori

Spørsmål 25 4 poeng Kap. 8

Med rigorous 2PL kommer denne sekvensen inn til scheduleren:

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

Hva skjer?

A Deadlock: T1 holder S(A), T2 holder S(B); T1 trenger X(B) som T2 holder, og T2 trenger X(A).
B Sekvensen utføres uten venting fordi alle leselåser er gjensidig kompatible mellom transaksjonene.
C T1 må vente til T2 committer og frigir alle sine låser, og deretter kjører T1 ferdig.
D Bare en av transaksjonene aborterer — T1 aborterer fordi den startet først i sekvensen.

Vis fasit

Riktig svar: A

Etter r1(A); r2(B): T1 har S(A), T2 har S(B). Når w1(B) prøves trenger T1 X(B) — må vente på T2 sin S(B). Når w2(A) prøves trenger T2 X(A) — må vente på T1 sin S(A). Begge venter på den andre → deadlock. Deadlock-detektoren aborterer en av transaksjonene; valget er ikke deterministisk.

B overser at en X-lås ikke er kompatibel med en eksisterende S-lås på samme objekt. C antar feil retning. D påstår at T1 alltid taper — men hvilken tx som blir offer er DBMS-policy (yngste, minst arbeid, etc.).

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 26 4 poeng Kap. 8

Med strict 2PL kommer denne sekvensen til scheduleren:

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

Hvilket utsagn beskriver kjøringen mest presist?

A T2 må vente på T1 sin X-lås på X; ingen lock-konflikt finnes på Y, og det blir ingen deadlock i scenariet.
B r2(X) er kompatibel med r1(X) (begge S-låser), men w1(X) må vente på T2 sin S(X). Etter c2 får T1 X(X) og fullfører.
C Deadlock oppstår mellom T1 og T2 på objekt X siden begge venter på den andres lås på X.
D T1 aborterer fordi w1(X) skjer etter at T2 allerede har lest X, noe schedulen ikke tillater.

Vis fasit

Riktig svar: B

r1(X) gir T1 en S(X). w2(Y) gir T2 X(Y) — ingen konflikt. r2(X) er en S-lås, kompatibel med T1 sin S(X) — den gis. Når w1(X) prøves trenger T1 oppgradering til X(X), men T2 holder S(X) → T1 venter. T2 committer (c2), frigir S(X). T1 får X(X), gjør sin write, committer. Ingen deadlock fordi T2 ikke ventet på T1.

A overser at T2 også får S(X) — det blir ikke ventet ved r2(X). C ville krevd at T2 ventet på T1 også; det skjer ikke. D er en aborts-policy som ikke er en del av 2PL.

Pensum: Kap. 8 — Samtidighet og låser

Spørsmål 27 4 poeng Kap. 8

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

LSN	PrevLSN	Tx	Op	Page
50	—	T1	Update	P5
55	—	—	Begin_ckpt	—
60	—	—	End_ckpt	—
65	50	T1	Update	P7
70	—	T2	Update	P5
75	65	T1	Commit	—
80	70	T2	Update	P9
85	—	T3	Update	P7

End_ckpt (LSN=60) inneholder: Tx-tabell {(T1, last=50, active)}, DPT {(P5, recLSN=50)}. Hvilken DPT er korrekt etter analyse-fasen?

A {(P5, 50), (P7, 65), (P9, 80)}
B {(P5, 70), (P7, 65), (P9, 80), (—, —)}
C {(P5, 50), (P7, 65), (P9, 80), (P7, 85)}
D {(P5, 50), (P7, 85), (P9, 80)}

Vis fasit

Riktig svar: A

Vi starter med DPT={(P5,50)} fra checkpointet, skanner forover.

LSN 65 (T1 oppd. P7): P7 ikke i DPT → (P7, recLSN=65) legges til.
LSN 70 (T2 oppd. P5): P5 finnes allerede i DPT → behold recLSN=50 (vi flytter aldri recLSN frem).
LSN 75 (T1 commit): ingen DPT-effekt.
LSN 80 (T2 oppd. P9): P9 ikke i DPT → (P9, 80) legges til.
LSN 85 (T3 oppd. P7): P7 finnes → behold 65.

Resultat: {(P5, 50), (P7, 65), (P9, 80)}.

B flytter P5 frem til 70 — feil, recLSN settes ved første oppdatering siden flushen. C dupliserer P7. D oppdaterer P7 til LSN 85, igjen brudd på regelen.

Pensum: Kap. 8 — Recovery

Spørsmål 28 4 poeng Kap. 8

Bruk samme logg som forrige oppgave. Hvilke transaksjoner er losers (må undoes), og hvilke er winners (skal redoes som vanlig)?

A Winners: {T1}; Losers: {T2, T3}.
B Winners: {T1, T3}; Losers: {T2}.
C Winners: {T1, T2}; Losers: {T3}.
D Winners: ∅; Losers: {T1, T2, T3} (alle uten end-marker).

Vis fasit

Riktig svar: A

T1 har commit-loggpost (LSN 75) — winner. T2 og T3 har ingen commit-poster i loggen før krasjen — de er losers og må undoes (alle deres operasjoner reverseres bakover via prevLSN-pekere, og CLR-poster genereres for hver UNDO-handling).

B feilaktig markerer T3 som winner — T3 har ingen commit. C bytter om T2 og T3. D forveksler ARIES med en strict end-marker-regel; en commit-post er nok for å markere en winner.

Pensum: Kap. 8 — Recovery

Slutt på øvingseksamen 02.