Øvingseksamen 04

Hvilken komponent i et tradisjonelt RDBMS er hovedansvarlig for å oversette en SQL-tekst til en utførbar plan, gjennom parsing, omskriving (rewrite) og kostnadsbasert optimisering?

• A Query processor (parser + optimizer + executor).
• B Storage manager — den vet hvor blokkene ligger på disk.
• C Transaction manager — den koordinerer låser og logger.
• D Buffer manager — den styrer cachen og bestemmer hvilke blokker som ligger i RAM.

I en RIGHT OUTER JOIN mellom L og R på L.k = R.k, hva skjer med rader fra høyre tabell som ikke har match i venstre?

• A De forsvinner — bare matchede rader returneres (samme som inner join).
• B De returneres, og L-kolonnene fylles med tomme strenger.
• C De returneres dupliserte med hver L-rad — kryssprodukt.
• D De returneres, og L-kolonnene fylles med NULL.

Tabellene:

Hvor mange tupler returnerer A ⋈ B (naturlig join på y)?

• A 4
• B 6
• C 5
• D 12

Vurder spørringen:

SELECT lonn * 1.05 AS ny_lonn
FROM Ansatt
WHERE ny_lonn > 800000;

Hva skjer ved utføring i et standard-konformt RDBMS?

• A Spørringen fungerer som forventet — aliaset ny_lonn er tilgjengelig overalt ellers i spørringen.
• B Syntaks- eller kjøretidsfeil: ny_lonn finnes ikke i WHERE-fasen siden WHERE evalueres før SELECT.
• C Spørringen kjører, men returnerer alltid 0 rader fordi aliaset alltid er NULL ved evaluering av WHERE.
• D Spørringen optimeres helt bort av planneren og returnerer hele Ansatt-tabellen ufiltrert som resultat.

Tabellen Anmeldelse:

Hva returnerer:

SELECT kid, COUNT(*), COUNT(stjerner)
FROM Anmeldelse
GROUP BY kid;

• A Tre grupper: (10, 2, 1), (11, 1, 1), (NULL, 2, 1).
• B To grupper: (10, 2, 1), (11, 1, 1) — NULL-grupper utelates.
• C Tre grupper: (10, 2, 2), (11, 1, 1), (NULL, 2, 2) — COUNT teller NULL.
• D En enkelt rad med samtlige tellet sammen — GROUP BY funker ikke når NULL er til stede.

Skjema:

Bestilling(bid, kid, total)
Kunde(kid, navn, by)

Hvilken av disse spørringene er ikke ekvivalent med de andre? (Alle skal finne navn på kunder som har lagt inn minst én bestilling med total > 1000.)

• A SELECT DISTINCT k.navn FROM Kunde k JOIN Bestilling b ON k.kid = b.kid WHERE b.total > 1000;
• B SELECT navn FROM Kunde WHERE kid IN (SELECT kid FROM Bestilling WHERE total > 1000);
• C SELECT navn FROM Kunde k WHERE EXISTS (SELECT 1 FROM Bestilling b WHERE b.kid = k.kid AND b.total > 1000);
• D SELECT k.navn FROM Kunde k JOIN Bestilling b ON k.kid = b.kid WHERE b.total > 1000;

Skjema:

Student(sid, navn)
Kurs(kid, tittel)
Tar(sid, kid)

Vi vil finne studenter som tar alle kurs (relasjonsalgebra-divisjon). Hvilken SQL-spørring oppnår dette?

• A SELECT navn FROM Student s JOIN Tar t ON s.sid = t.sid GROUP BY s.sid, s.navn HAVING COUNT(*) = (SELECT COUNT(*) FROM Tar);
• B SELECT DISTINCT s.navn FROM Student s WHERE s.sid IN (SELECT t.sid FROM Tar t GROUP BY t.sid HAVING COUNT(*) >= 1);
• C SELECT navn FROM Student s WHERE NOT EXISTS (SELECT 1 FROM Kurs k WHERE NOT EXISTS (SELECT 1 FROM Tar t WHERE t.sid = s.sid AND t.kid = k.kid));
• D SELECT DISTINCT s.navn FROM Student s JOIN Kurs k ON 1 = 1 GROUP BY s.sid, s.navn ORDER BY s.navn;

Skjema:

CREATE TABLE Avdeling (
    aid  INT PRIMARY KEY,
    navn VARCHAR(50)
);
CREATE TABLE Prosjekt (
    pid  INT PRIMARY KEY,
    aid  INT NOT NULL,
    FOREIGN KEY (aid) REFERENCES Avdeling(aid) ON DELETE CASCADE
);
CREATE TABLE Oppgave (
    oid  INT PRIMARY KEY,
    pid  INT NOT NULL,
    FOREIGN KEY (pid) REFERENCES Prosjekt(pid) ON DELETE CASCADE
);

Hva skjer hvis vi sletter en rad fra Avdeling som har 2 prosjekter, der hvert prosjekt har 5 oppgaver?

• A Slettingen avvises fordi Prosjekt.aid er NOT NULL.
• B Avdelingsraden, de 2 prosjektene og alle 10 oppgavene slettes — kaskaderingen følger FK-kjeden.
• C Bare avdelingen og de 2 prosjektene slettes; oppgavene blir foreldreløse fordi kaskadering ikke krysser to nivåer.
• D Bare avdelingen slettes; prosjektene får aid satt til NULL.

Tabellen Forelder(barn, foreldre):

Spørringen:

WITH RECURSIVE Aner(person, aner) AS (
    SELECT barn, foreldre FROM Forelder WHERE barn = 'Anna'
  UNION
    SELECT a.person, f.foreldre FROM Aner a
    JOIN Forelder f ON a.aner = f.barn
)
SELECT aner FROM Aner;

Hvor mange rader returnerer den?

• A 4 (Berit, Cathrine, Diana, Eva).
• B 1 (bare Berit).
• C 5 (Anna selv pluss alle aner).
• D Spørringen termimerer ikke (uendelig løkke).

SQL definerer flere kategorier av rettigheter som kan tildeles via GRANT. Hvilken liste viser kun klassiske SQL-rettigheter på tabellnivå?

• A CONNECT, DISCONNECT, AUTHENTICATE, AUTHORIZE.
• B ENCRYPT, DECRYPT, SIGN, VERIFY.
• C START_TX, COMMIT_TX, ROLLBACK_TX.
• D SELECT, INSERT, UPDATE, DELETE, REFERENCES, TRIGGER.

I et ER-diagram er relasjonen "leder" mellom Avdeling og Ansatt 1:1. Total deltakelse fra Avdeling og partial fra Ansatt. Hva betyr dette i den konkrete databasen?

• A Hver ansatt må lede én avdeling, men en avdeling trenger ikke ha en leder.
• B Hver avdeling må ha en leder, og hver ansatt må lede en avdeling.
• C Hver avdeling må ha nøyaktig én leder, men en ansatt trenger ikke å være leder for noen avdeling.
• D Verken avdeling eller ansatt har krav om å delta — relasjonen er rent valgfri.

En kategori (også kalt union type) i utvidet ER er forskjellig fra en vanlig spesialisering (ISA). Hvordan?

• A En kategori har én superklasse og flere subklasser, mens en spesialisering har omvendt struktur i diagrammet.
• B En kategori er en subklasse hvis instanser er union fra flere ulike superklasser; spesialisering har én superklasse.
• C En kategori er det samme som en svak entitet i ER-modellen — det er bare to forskjellige notasjoner for begrepet.
• D En kategori er en ISA-relasjon der alle subklassene er disjunkte, mens spesialisering tillater overlapp mellom dem.

Tabellen Bestilling(bnr, kid, kby, totalpris) har FDs:

F = { bnr → kid,   bnr → totalpris,   kid → kby }

Kandidatnøkkelen er {bnr}. Hvilken normalform er Bestilling brutt mot?

• A 3NF — bnr → kid → kby er transitiv avhengighet av PK via en ikke-prim-attributt.
• B 2NF — kid → kby er en delvis avhengighet av en del av primærnøkkelen.
• C 1NF — kby er ikke atomær fordi feltet kan inneholde strukturerte data.
• D Ingen normalform — tabellen er allerede på BCNF og trenger ingen normalisering.

Hvorfor implementerer DBMS-er sin egen buffer manager i stedet for å stole utelukkende på operativsystemets filcache?

• A Operativsystemer har ikke filcache, og DBMS-et må derfor implementere all caching helt selv fra bunnen.
• B Bare for å spare RAM på maskinen — DB-bufferen er alltid mindre i størrelse enn operativsystemets cache i praksis.
• C DBMS-et trenger fin kontroll over evictions, prefetching basert på spørringsplanen og garantert tilstedeværelse av pinned sider.
• D Fordi OS-cachen lager ekstra kopier av data og bryter dermed med ACID-egenskapen Atomicity for transaksjoner.

I extendible hashing har en blokk lokal depth d. Hva betyr dette eksakt?

• A d angir antall datapostene som passer inn i blokken før den må splittes pga. plassmangel og overflyt mot directory.
• B d angir hvor mange splits denne spesifikke blokken har vært gjennom siden filen ble opprettet i utgangspunktet av systemet.
• C d angir antall directory-entries som peker direkte på nettopp denne blokken i hash-strukturen for filen totalt.
• D d angir antall hash-bits som trengs for å skille blokken fra andre — nøkler i blokken har samme prefiks av lengde d.

En post med flere variabel-lengde felter kan lagres med en delimiter mellom feltene (f.eks. NUL-byte). Hva er hovedulempen ved denne strategien sammenlignet med en offset-vektor?

• A Delimiter-strategien er treig fordi den krever zip-komprimering før hver eneste skriving til disk.
• B Vi må skanne posten lineært for å finne et bestemt felt — direkte aksess i konstant tid er ikke mulig.
• C Delimiter-strategien kan ikke representere felter som har variabel lengde i datapostene på disk.
• D Posten må padded til en fast størrelse, og dette unødig sløser med diskplass i datafilen.

Et clustered B+-tre lagrer 5 millioner poster på 200 byte. Blokker er 4 KiB med 2/3 fyllgrad. (key, BlockId)-poster på indre nivåer er 16 byte. Hvor mange nivåer (inkl. løv = level 0) har treet?

• A 2
• B 4
• C 5
• D 3

Hvorfor regnes B+-tre-blokker ofte med en 2/3 fyllgrad, og ikke 100 %?

• A Det er fordi DBMS-et alltid reserverer akkurat 1/3 av blokken til intern WAL-logging i seg selv.
• B Fordi en B+-tre-blokk har inntil 1/3 av plassen brukt opp til peker-hodet (parent, neste og prev pekere).
• C Empirisk gjennomsnittlig fyllgrad etter mange innsettinger og slettinger — splits gir 50/50, men over tid jevner det seg til ca. 67 %.
• D Fordi 1/3 av blokken alltid reserveres til neste forventede splits, slik at innsettinger blir raskere senere i bruk.

Hvilken påstand om "write amplification" i LSM-trær er korrekt?

• A Write amplification er null i LSM-trær — det er nettopp dette som er en av de vesentligste fordelene med dem.
• B Write amplification er nøyaktig 1 i alle tilfeller: hver post skrives kun én gang når memtable flushes til disk.
• C Write amplification i LSM er per definisjon høyere enn i B+-trær fordi compaction-prosessen ikke eksisterer i B+-trær.
• D Write amplification er hvor mange ganger samme post skrives totalt — i en N-nivå LSM med leveled compaction skrives en post N ganger.

Tabellen Salg har 200 000 rader, lagret i en heap (4000 blokker). Det finnes et unclustered B+-tre på belop med 3 nivåer og 800 løvblokker. Vi kjører:

SELECT * FROM Salg WHERE belop > 5000;

Anta at 70 % av radene oppfyller predikatet. Hvilken plan er optimal?

• A Full table scan av heapen — 4000 blokker.
• B Index range scan: traversér til riktig løv (3 blokker), skann 70 % av løvnivået (560 blokker), slå opp 140 000 RID-er i heap (140 000 blokker worst case).
• C Bitmap index scan med 70 % bitset, deretter 4000 heap-blokker — 4003 totalt.
• D Index seek til startposisjon (3 blokker) og deretter scan av 800 løvblokker.

Når lønner sort-merge join (J3) seg sammenlignet med hash join (J4) eller nested loop?

• A Når begge tabellene er små nok til å kunne passe samtidig i hovedminnet på maskinen som kjører spørringen.
• B Når join-attributtet er en lang streng, fordi sortering generelt håndterer kollisjoner bedre enn hashing gjør.
• C Når begge inputene allerede er sortert på join-attributtet (eller sorteringen kan brukes til ORDER BY) — kun lineær merge.
• D Sort-merge er alltid raskere enn hash join for store tabeller med svært mange rader på disken i praksis.

Hva er kjernemekanismen i partition-hash join (J4)?

• A Begge tabellene sorteres først etter join-attributtet, før de slås sammen med en lineær merge i en separat fase.
• B Join-attributtet hashes for å partisjonere begge tabellene; deretter bygges en hashtabell på minste partisjon som den større probes mot.
• C En hashtabell over join-attributtet vedlikeholdes permanent på disk og oppdateres ved hver innsetting i en av tabellene.
• D Tabellene leses parallelt fra disk og kombineres i en intern hash-bitmap som indikerer matchede par av rader mellom dem.

Recoverability-hierarkiet rangerer schedule-klasser fra mest til minst restriktiv. Hva er den korrekte strikt-til-svak rekkefølgen?

• A ACA ⊂ Strict ⊂ Recoverable ⊂ Alle.
• B Recoverable ⊂ ACA ⊂ Strict ⊂ Alle.
• C Strict ⊂ ACA ⊂ Alle ⊂ Recoverable.
• D Strict ⊂ ACA ⊂ Recoverable ⊂ Alle.

Vurder schedulen:

w1(X, 200); r2(X); w2(Y); a1; c2;

(a1 = T1 aborterer.) Hva er problemet?

• A T2 har lest en verdi T1 skrev (dirty read) og committet egen state. Når T1 aborterer kan ikke T2 rulles tilbake.
• B Lost update: T2 sin skriv overskriver T1 sin før T1 er ferdig committed, slik at endringen forsvinner.
• C Phantom: T2 ser en rad som T1 senere fjerner i sin egen pågående transaksjon før commit-tidspunkt.
• D Ingen problem — schedulen er allerede strict og dermed rekoverable og fri for anomalier her.

Hva er den kjerneideen i MVCC (Multi-Version Concurrency Control) sammenlignet med 2PL?

• A MVCC bruker både låser og versjoner samtidig — alt fra 2PL pluss en versjonskjede som vedlikeholdes per rad i tabellen i basen.
• B MVCC lagrer flere versjoner av hver rad — lesere ser konsistent snapshot uten lås, og bare skriv-skriv-konflikter krever låsing.
• C MVCC fjerner alt av låsing helt fra DBMS-et; konflikter løses utelukkende ved retry på applikasjonsnivå over i klienten.
• D MVCC og 2PL er bare to forskjellige navn på den samme grunnleggende mekanismen i mange moderne DBMS-er som finnes i dag.

Under snapshot isolation kan en kjent anomali oppstå: write skew. Hva karakteriserer den?

• A To transaksjoner overskriver hver sin verdi av samme rad uten å se hverandres skriv først, og siste skriv vinner.
• B En transaksjon leser samme rad to ganger og får forskjellige verdier mellom de to lesingene i samme transaksjon.
• C To transaksjoner leser et felles datasett, hver oppdaterer en annen del basert på lesingen, og effekten bryter en invariant som hver enkelt sjekket.
• D En transaksjon committer en skriv mens en annen er midt i en lengre lesing — dette er det samme som en dirty read.

Etter analyse-fasen i ARIES er DPT:

(P1, recLSN=80), (P2, recLSN=85), (P3, recLSN=90)

REDO-fasen vurderer loggpost LSN=82 som oppdaterer P2. På disk har P2 pageLSN=78. Skal loggposten redoes?

• A Nei, fordi DPT.recLSN(P2) = 85 > LSN = 82 — endringen er allerede kjent å være flushed til disk.
• B Ja, fordi transaksjonen fortsatt er aktiv etter at analyse-fasen er ferdig med sin skanning.
• C Ja, fordi pageLSN er mindre enn loggens LSN, og endringen er derfor ikke synlig på disk ennå.
• D Nei, fordi selve loggposten ligger før checkpointet og dermed allerede må være flushed til disk.

Buffer-management policies for transaksjoner kombineres i en 2 × 2-matrise: steal/no-steal × force/no-force. Hvilken kombinasjon bruker ARIES, og hvorfor?

• A No-steal + force: enkleste politikk å implementere, krever ikke logging og er enkel i daglig drift.
• B No-steal + no-force: gir best ytelse for små og raske transaksjoner som er korte i tid totalt.
• C Steal + force: kombinerer god fleksibilitet med Durability uten å trenge en egen REDO-logg.
• D Steal + no-force: maksimal fleksibilitet — buffer-manager kan flushe uncommitted endringer og trenger ikke flushe ved commit.