Spørringsutføring

A — Atomicity: alt eller ingenting. Mekanisme: UNDO-logging + abort/rollback.

C — Consistency: databasens integritetsregler holder før og etter. Mekanisme: integritetssjekk (constraints, triggere) + at hver transaksjon er korrekt skrevet.

I — Isolation: samtidige transaksjoner ser ut til å kjøre etter hverandre. Mekanisme: concurrency control (2PL eller MVCC).

D — Durability: committed effekter overlever krasj. Mekanisme: WAL (write-ahead log) + force-log-at-commit.

Merk at en kortvarig serialiserbar utførelse kan være «konsistent» selv om et enkelt mellomtilstand bryter constraints — viktig at C måles ved commit, ikke midt i en transaksjon.

Pensum: Kap. 8 — ACID

Tre lag mellom bruker og bits:

Eksternt skjema (view): hva en bestemt brukergruppe ser. En tabell kan være delvis skjult, et JOIN-resultat kan være eksponert som «én tabell», kolonner kan renames.

Konseptuelt skjema: den logiske, hele beskrivelsen — alle tabeller, kolonner, constraints, integritetsregler. Dette er det DDL-en din bygger.

Internt skjema: hvordan dataene faktisk er lagret — heap eller B+-tre, hvilke indekser finnes, blokkstørrelse, partisjonering.

Poenget er data-uavhengighet:
Logisk uavhengighet — endre konseptuelt skjema (legg til en kolonne) uten å bryte views.
Fysisk uavhengighet — endre interne strukturer (legg til indeks, repartisjoner) uten å endre SQL-en.

Pensum: Kap. 1 — DBMS-arkitektur

1. Parser: sjekker syntaks, slår opp tabeller og kolonner i SQL-katalogen, lager et logisk algebra-tre.

2. Optimizer: genererer kandidatplaner, beregner forventet kostnad ved hjelp av statistikk, velger den billigste planen. Eier kap. 7.

3. Executor: utfører den valgte planen — kaller aksessmetoder, kjører join-algoritmer, sorterer, projiserer.

4. Storage manager: oversetter blokkforespørsler til faktiske disk-I/O, går via buffer pool. Eier kap. 6.

I tillegg: concurrency control og recovery manager jobber parallelt over alle disse (kap. 8). SQL-katalogen (data dictionary) leses av parser og optimizer.

Pensum: Reisen gjennom DBMS-en

Supernøkkel: en mengde attributter som unikt identifiserer hver tuppel. Kan inneholde overflødige attributter (f.eks. {SSN, navn} er supernøkkel hvis SSN er det).

Kandidatnøkkel: en minimal supernøkkel — fjerner du ett attributt mister du unikheten. {SSN} er kandidatnøkkel, {SSN, navn} er ikke.

Primærnøkkel: én valgt kandidatnøkkel. DBMS-en lager typisk en clustered B+-indeks på den, og NULL er forbudt.

En relasjon kan ha flere kandidatnøkler (f.eks. både SSN og e-post er unike). Alle kandidatnøkler har samme egenskap (minimal+unik), men bare én er primærnøkkel — de andre kalles ofte alternate keys.

Pensum: Kap. 2 — Relasjonsmodellen

Fundamentale (6): σ (selection), π (projection), ∪ (union), − (set difference), × (cross product), ρ (rename).

Avledede: ∩ (intersection) = R − (R − S). Theta-join og natural join (⋈) = σ over ×. Divisjon (÷) kan uttrykkes via ×, − og π.

Merk: outer joins (⟕, ⟖, ⟗) er heller ikke fundamentale — de utvider natural join med tupler som ikke matcher, fylt ut med NULL.

Pensum: Kap. 2 — Relasjonsalgebra

Riktig: B — 5 tupler.

Natural join produserer én resultattuppel per (R, S)-par som matcher på b. Hver av de 5 S-tuplene har eksakt én matchende R-tuppel, så antallet par = 5.

(Hvis flere R-tupler hadde delt samme b-verdi som en S-tuppel, hadde tallet vært høyere — generelt: summer over hver delt b-verdi v antallet R-tupler med b=v ganget med antallet S-tupler med b=v.)

A (3) teller antall R-tupler som kan matche, men ikke selve parene. C (8) er 3 + 5 — typisk hvis man tror join er en union. D (20) er |R| × |S|, kartesisk produkt uten matching — feil med mindre alle b-verdier samsvarer.

Pensum: Kap. 2 — Relasjonsalgebra

R og S må være union-kompatible: samme antall attributter, og de korresponderende attributtene må ha samme domene (datatype).

Dette er strengere enn SQL-ens UNION, som krever samme antall kolonner og kompatible typer (typeparing). I RA er kolonnenavnene ikke nødvendigvis like — det er posisjonen som teller.

Samme krav gjelder for R − S og R ∩ S. (Cross product R × S krever ikke union-kompatibilitet — den lager bare en bredere relasjon.)

Pensum: Kap. 2 — Set-operasjoner

R ⟕ S = alle resultater fra R ⋈ S, pluss hver tuppel fra R som ikke matchet noen tuppel i S — utvidet med NULL i alle S-attributter.

Symmetrisk: right outer join (⟖) bevarer alle S-tupler. Full outer join (⟗) bevarer alle fra begge sider.

Brukstilfelle: «vis alle ansatte og deres avdeling, også de uten avdeling». Ved natural join faller de uten match ut — outer join holder dem inne.

I SQL: LEFT JOIN, RIGHT JOIN, FULL OUTER JOIN. NULL fra outer join er ikke det samme som NULL i originaldataene — semantisk skille som av og til betyr noe i aggregatfunksjoner (f.eks. COUNT(*) teller NULL-rader, COUNT(col) ignorerer NULL).

Pensum: Kap. 2 — Outer join

R ÷ S finner de verdiene i R som er paret med alle verdier i S.

Definisjon: La R(A, B) og S(B). Resultatet er en relasjon over A der hver a-verdi i resultatet oppfyller: for hver b i S finnes (a, b) i R.

Klassisk brukstilfelle: «finn studenter som har tatt alle kurs i en bestemt liste». R = (student, kurs) takings-tabellen, S = listen av påkrevde kurs. R ÷ S = studenter som har tatt alle.

I SQL uttrykkes dette typisk med dobbelt NOT EXISTS: «ingen kurs i S som studenten ikke har tatt». Det er den samme logikken — universell kvantor utrykt som dobbel negasjon av eksistens.

Pensum: Kap. 2 — Divisjon

NULL = NULL evalueres til UNKNOWN, ikke TRUE. SQL bruker tre-verdig logikk (TRUE / FALSE / UNKNOWN). For å sjekke om en kolonne er NULL: col IS NULL.

WHERE beholder bare rader der predikatet er TRUE. UNKNOWN-rader filtreres bort, akkurat som FALSE.

Aggregatfunksjoner ignorerer NULL — bortsett fra COUNT(*) som teller alle rader. COUNT(col), SUM(col), AVG(col) hopper over NULL-verdier. Konsekvens: SUM(x) / COUNT(x) ≠ AVG(x) hvis det er NULL i x.

Ekstra felle: NOT IN (subquery) kan returnere ingen rader hvis subqueryen inneholder NULL — fordi x NOT IN {a, NULL} blir x ≠ a AND x ≠ NULL, og det siste er UNKNOWN. Bruk NOT EXISTS i stedet.

Pensum: Kap. 3 — NULL og 3-verdig logikk

Logisk utføringsrekkefølge: FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY → LIMIT.

WHERE filtrerer rader før gruppering. Kan ikke referere til aggregatfunksjoner — de eksisterer ikke ennå.

HAVING filtrerer grupper etter at GROUP BY har samlet dem. Får referere til aggregatfunksjoner: HAVING SUM(salary) > 1 000 000.

Tommelfingerregel: hører predikatet til en enkeltrad, bruk WHERE; hører det til hele gruppa, bruk HAVING. Optimizeren kan flytte enkle ikke-aggregat-predikater fra HAVING til WHERE — men semantikken er definert i denne rekkefølgen.

Pensum: Kap. 3 — Gruppering

x IN (subq) = TRUE hvis x er lik noen verdi i subqueryen. Tilsvarer x = ANY (subq).

EXISTS (subq) = TRUE hvis subqueryen returnerer minst én rad. Bryr seg ikke om kolonneverdier — typisk korrelerte subqueries der vi sjekker «finnes det en match?».

= ANY / = SOME = synonym for IN. = ALL = TRUE hvis x er lik alle verdier i subqueryen (inkludert tom subquery, der ALL er trivielt TRUE).

NOT IN er farlig med NULL: x NOT IN (a, NULL) blir alltid UNKNOWN → 0 rader. Bruk NOT EXISTS i stedet — det håndterer NULL korrekt og er ofte raskere.

Pensum: Kap. 3 — Subqueries

En view er updatable når DBMS-en utvetydig kan oversette en INSERT/UPDATE/DELETE på viewet til en operasjon på underliggende tabeller. Typiske krav:

• Bygges på én tabell.
• Inneholder primærnøkkelen til den tabellen.
• Ingen aggregat, GROUP BY, DISTINCT, eller utregnede uttrykk i SELECT.
• Ingen subquery i WHERE som korrelerer med viewet selv.

Multi-tabell-views med JOIN er typisk read-only, eller krever INSTEAD OF-triggere.

WITH CHECK OPTION sørger for at en INSERT eller UPDATE på viewet ikke produserer en rad som ikke ville vært synlig gjennom viewet. F.eks. view HighEarners = SELECT * FROM Emp WHERE salary > 1 000 000; uten WITH CHECK OPTION kan jeg sette inn en rad med salary=500 000 (den havner i tabellen, men ikke i viewet); med WITH CHECK OPTION blir INSERT-en avvist.

Pensum: Kap. 3 — Views

Row-level (FOR EACH ROW): trigger-koden kjøres én gang for hver rad som påvirkes. Pseudovariablene NEW og OLD refererer til den enkelte raden.

• OLD: gammel verdi (i UPDATE og DELETE).
• NEW: ny verdi (i INSERT og UPDATE).
• BEFORE-triggere kan endre NEW; AFTER-triggere kan ikke (raden er allerede skrevet).

Statement-level: kjøres én gang per setning, uansett antall rader berørt. NEW/OLD finnes ikke direkte; man bruker transition tables (NEW TABLE / OLD TABLE) som inneholder alle endrede rader.

Typisk valg: row-level for fine-grained logging og kaskaderegler; statement-level for å oppdatere et aggregert mellomresultat (f.eks. en sum-tabell), der man bare vil ha én oppdatering pr. statement.

Pensum: Kap. 3 — Triggere

WITH GRANT OPTION: mottakeren får ikke bare privilegiet, men også retten til å videregi det. Hvis Alice får SELECT på Emp WITH GRANT OPTION, kan hun GRANTe SELECT videre til Bob.

REVOKE … CASCADE: når et privilegium tilbakekalles, tilbakekalles også alle privilegier som er videregitt fra det. Hvis vi revoker SELECT fra Alice CASCADE, mister Bob det også (forutsatt at han ikke har SELECT fra en annen kilde).

REVOKE … RESTRICT: motsatt — REVOKE feiler hvis privilegiet er videregitt. Du må først rydde opp manuelt.

DBMS-en holder en grant-graf for å vite hvem som har gitt hva til hvem. CASCADE traverserer grafen; et privilegium beholdes hvis brukeren har det fra en alternativ kilde.

Pensum: Kap. 3 — Autorisasjon

WITH RECURSIVE r(...) AS (
  -- 1. base case: ikke-rekursiv start-spørring
  SELECT ... FROM ...
  UNION [ALL]
  -- 2. recursive step: refererer til r selv
  SELECT ... FROM r JOIN ...
)
SELECT ... FROM r;

DBMS-en gjør fixed-point iteration: start med base case, kjør recursive step gjentatte ganger, akkumuler nye rader i r. Stopp når en iterasjon ikke produserer flere nye rader.

UNION ALL beholder duplikater — vanlig hvis grafen er asyklisk. UNION de-dupliserer og fungerer som naturlig terminator i sykliske grafer (f.eks. forfedre i en familietre der en person ikke er sin egen forfar).

Klassisk brukstilfelle: transitive closure (alle forfedre, alle understående underavdelinger, korteste vei). Ofte mye penere enn pleie å gjøre flere selv-joiner manuelt.

Pensum: Kap. 3 — Rekursjon

Fremmednøkkelen B → A (B referer A) bestemmer hva som skjer i B når en referert rad i A slettes:

CASCADE: slett alle rader i B som peker på den slettede A-raden. Kan utløse en kaskade videre hvis B også er referert.

SET NULL: sett fremmednøkkelen i B til NULL. Krever at kolonnen er nullable.

RESTRICT (eller NO ACTION): avvis slettingen av A hvis det finnes refererende rader i B. Sikreste valget; brukes når man vil hindre dataforringelse.

Tilsvarende ON UPDATE-varianter finnes for primærnøkkel-endringer. RESTRICT sjekker umiddelbart, NO ACTION er deferrable til commit (i full SQL-standard, men ikke alle DBMS-er støtter dette).

Pensum: Kap. 3 — Integritet

En svak entitet har ikke en unik identifikator i seg selv. Den må kombineres med en eier-entitet via en identifying relationship for å bli identifiserbar.

Eksempel: Dependent (forsørget familiemedlem) har attributt name, men to ansatte kan ha hver sitt barn med samme navn. Sammen med Employee via «is dependent of» blir (SSN_emp, name) unik. Det partielle nøkkelattributtet (name) kalles discriminator.

Mapping til skjema: én relasjon med kombinert primærnøkkel: eierens primærnøkkel + svakens partielle nøkkel. Eierens nøkkel blir samtidig fremmednøkkel med ON DELETE CASCADE — sletter eieren, slettes også de avhengige.

I ER-diagram: dobbel rektangel for svak entitet, dobbel diamant for identifying relationship.

Pensum: Kap. 4 — ER-modellen

1. Én tabell per type, inkl. superklasse: Person(id, navn) + Student(id, snitt) + Ansatt(id, lønn). Hver subklasse har FK til superklassen.
Fordeler: ren modell, støtter overlapping og partial. Ulemper: mange joiner ved spørringer som krysser hierarkiet.

2. Én tabell per subklasse (uten superklasse): Student(id, navn, snitt), Ansatt(id, navn, lønn). Krever disjoint+total: hver person er enten student eller ansatt, ikke begge.
Fordeler: ingen joiner. Ulemper: duplisert kolonne (navn); UNION ved spørringer på alle personer.

3. Én stor tabell med union types: Person(id, navn, type, snitt, lønn). Bruker NULL i felt som ikke gjelder.
Fordeler: ingen joiner. Ulemper: mange NULL, vanskelig å håndheve at student har snitt og ansatt har lønn.

Pensum bruker disjoint vs overlapping og total vs partial som constraints på spesialiseringa.

Pensum: Kap. 4 — ER-mapping

Algoritme:

1. Start med X⁺ = X.
2. Gå gjennom alle FD-er i F. Hvis venstre side Y ⊆ X⁺, legg høyre side Z til X⁺.
3. Repeter til X⁺ ikke vokser.

Brukes til:

• Sjekke om X er supernøkkel: X⁺ = R (alle attributter) ⇔ X er supernøkkel.
• Finne alle kandidatnøkler: sjekk hver minimal mengde X med X⁺ = R.
• Sjekke en FD Y → Z: Z ⊆ Y⁺ ⇔ FD-en holder.
• Bestemme normalform: for BCNF, sjekk at hver ikke-triviell FD har en supernøkkel som venstre side.

Pensum: Kap. 4 — FD og lukning

BCNF: for hver ikke-triviell FD X → A, må X være en supernøkkel.

3NF: for hver ikke-triviell FD X → A, må én av disse holde:
(a) X er supernøkkel, eller
(b) A er en del av en kandidatnøkkel («prime attribute»).

3NF er altså strengere svakere enn BCNF — den tillater FD-er der venstresiden ikke er supernøkkel, så lenge høyresiden er prime.

Hvorfor 3NF noen ganger? Det er ikke alltid mulig å dekomponere til BCNF samtidig som vi bevarer alle FD-er. 3NF kan alltid oppnås tap-fritt OG dependency-bevarende; BCNF garanterer bare tap-fritt. Den klassiske eksempel-relasjonen er Address(by, postnummer, gate) der {by, gate} → postnummer og postnummer → by: kan dekomponeres til BCNF, men da kan ikke FD-en {by, gate} → postnummer håndheves uten å rejoine.

Pensum: Kap. 4 — Normalformer

Riktig: C — 3 kandidatnøkler.

D er ikke i høyresiden av noen FD, så D må være med i hver kandidatnøkkel.

Sjekk hver kandidat:

• {A,D}⁺: A → B → C, så lukning = ABCD ✓
• {B,D}⁺: B → C, og {C,D} → A, så lukning = ABCD ✓
• {C,D}⁺: CD → A → B, så lukning = ABCD ✓
• Bare D: lukning = D ✗

Alle tre er minimale (fjerner du D, eller den andre attributten, blir lukningen ufullstendig). Derfor 3 kandidatnøkler.

D (4) teller med en ikke-minimal supernøkkel.

Pensum: Kap. 4 — Kandidatnøkler

Dekomponeringen er lossless hvis fellesattributtene R₁ ∩ R₂ er supernøkkel for minst én av delrelasjonene.

Formelt: (R₁ ∩ R₂) → R₁ ELLER (R₁ ∩ R₂) → R₂ må holde i F⁺.

Hvorfor: hvis fellesattributtene unikt bestemmer den ene siden, finnes det bare én måte å koble en R₁-tuppel tilbake til R₂-tupler — vi taper ingen informasjon ved natural join. Hvis ingen av sidene er supernøkkel for fellesnøkkelen, kan vi få spurious tupler ved rejoin.

Eksempel: R(SSN, navn, by) med {SSN → navn, SSN → by}. Splitt til R₁(SSN, navn) og R₂(SSN, by) — fellesnøkkel SSN er supernøkkel for begge → lossless. Splitt i stedet til R₁(SSN, navn) og R₂(navn, by) — felles er navn, som ikke er supernøkkel → potensielt tap (hvis to personer har samme navn).

For dekomponering i mer enn to relasjoner: bruk chase-algoritmen.

Pensum: Kap. 4 — Lossless decomposition

RID = (BlockId, slot), en peker fra en indeks ned til en konkret rad.

Hadde RID-en vært en absolutt byte-offset, ville hver kompaktering av blokken (etter sletting f.eks.) krevd at alle indekser ute i systemet ble oppdatert. Det er praktisk umulig.

Ved å bruke en logisk slot-indeks som indirekteringspunkt, kan radene flyttes inni blokken uten at indekspekerne blir ugyldige — bare blokkens slot directory må oppdateres.

Pensum: Kap. 6A — Block-format

DBMS-en kjenner semantikken og kan derfor velge bedre policy enn et generisk OS:

• Pinning: hold en blokk i bufferet så lenge en B+-traversering eller transaksjon trenger den.
• Smart prefetching: ved table scan kan flere blokker leses inn i forkant.
• WAL-håndhevelse: sørg for at logg-blokker skrives før commit (force-log-at-commit).
• Bedre replacement enn LRU ved store sekvensielle scans (LRU forurenses ellers).

OS-et ser bare anonyme sidefeil og kan ikke skille en B+-rotnode fra en sjelden brukt arkivblokk.

Pensum: Kap. 6A — Buffer pool

Pensums kanoniske funksjon: h(K) = K mod N, der N er antallet bøtter (faste, satt på forhånd).

Når en bøtte fylles opp, lenkes en overflow-blokk bak — fortsetter videre til en kjede hvis overflow-blokken også fylles.

Problemet: et oppslag «skulle» være én blokk-aksess, men kan ende opp som en lineær traversering av kjeden — verste fall blir like dårlig som heap-scan.

Statisk hashing har derfor en fastlåst kapasitet: vokser dataene utover det N er dimensjonert for, kollapser ytelsen. Løsningen er extendible hashing som lar antall bøtter doble seg dynamisk.

Pensum: Kap. 6A — Statisk hashing

Global depth (d): antall bits av hash-verdien som directoryen ser på. Directoryen har 2^d innslag.

Local depth (d_b): antall bits som faktisk skiller bøttene fysisk — d_b ≤ d for hver bøtte.

Når en bøtte må splittes:

• Hvis d_b < d: bøtta kan splittes uten å berøre directoryen. To eksisterende directory-innslag som tidligere pekte på samme bøtte, peker nå på hver sin nye bøtte. Local depth øker med 1.
• Hvis d_b = d: directoryen må dobles først — alle innslag dupliseres, deretter splittes bøtta. Global depth øker med 1.

Slik vokser og krymper directoryen dynamisk uten å rehashe alle nøkler — bare den splittete bøtta og dens 2^(d - d_b) directory-pekere oppdateres.

Pensum: Kap. 6A — Extendible hashing

Riktig: A — 7813 blokker.

Heapfilen pakker fullt uten fyllgrad-marg.

rec_per_blokk = ⌊4096 / 64⌋ = 64
antall_blokker = ⌈500 000 / 64⌉ = 7813

B (11 719) bruker fyllgrad 2/3: 64 · 2/3 ≈ 42 rec/blokk. Det gjelder for B+-tre-blader, ikke for heap.
C (15 625) deler 500 000 / 32 — som om hver blokk bare hadde halv kapasitet.
D (500 000) antar én rad per blokk — glemmer pakking.

Pensum: Kap. 6A — Heap file

LSM-tre er optimalisert for tunge skrivelaster. Hovedidé: skriv aldri i tilfeldig rekkefølge — saml opp endringer i RAM, og skriv ut sekvensielt til disk.

• Memtable: en sortert struktur (ofte rød-svart-tre eller skip-list) i RAM. Alle writes går hit først.
• SSTable (sorted string table): når memtable fylles, skrives den ut som én sortert, immutable disk-fil. Sekvensiell skriving — mye raskere enn random writes på en HDD.
• Compaction: i bakgrunnen merges små SSTables til større, sorterte SSTables. Sletter overskrevne rader.

Trade-off: writes er svært raske (write amplification lav), men reads kan måtte sjekke flere SSTables på flere nivåer (read amplification). B+-trær er motsatt: raske reads, dyrere random writes.

Brukes i Cassandra, RocksDB, LevelDB, HBase. Ikke MySQL/PostgreSQL — de bruker B+-trær.

Pensum: Kap. 6A — LSM

Fanout = maks antall barn per intern node = ⌊B · 2/3 / S⌋ der B er blokkstørrelse og S er størrelsen på (key, BlockId)-paret.

Høy fanout gir lavt tre. Med 4 KiB-blokker, 16 byte per indekspost og fyllgrad 2/3 får vi fanout = 170. Et 3-nivåers tre dekker da opp til 170³ ≈ 4,9 millioner blader.

Hvert nivå koster én blokk-aksess ved likhetsoppslag. Stor fanout = få nivåer = få diskaksesser = rask. B+-trær er typisk 3-4 nivåer dype selv med milliarder av rader.

Sammenligning: en binær søketre over samme data ville vært ~log₂(milliarder) = 30 nivåer. 30 diskaksesser per oppslag = uakseptabelt.

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

Clustered: radene er fysisk sortert i nøkkelorden. Bladene er tabellen. Ett oppslag → ett blad → ferdig. Range-scans = sammenhengende blokker.

Unclustered: radene er sortert annerledes (typisk innsettingsrekkefølge i en heap). Bladene inneholder (key, RID), ikke selve raden. Hvert oppslag følger RID-en til en (potensielt tilfeldig) heap-blokk.

Hvorfor kan unclustered være verre enn full scan? Hvis spørringen treffer mange rader, blir det én tilfeldig heap-aksess per treff. 50 000 treff på en 1961-blokks heap kan bety 50 000 blokker (med duplikater). Full scan = 1961 blokker. Optimizeren ser dette via statistikk og velger full scan.

Tommelfingerregel: unclustered indeks lønner seg bare ved selektive predikater (få treff). Clustered er bra også ved range-spørringer.

Pensum: Kap. 6B — Clustered vs unclustered

Riktig: B — 3 nivåer.

Poster per blokk: ⌊4096 · 2/3 / 16⌋ = ⌊170.67⌋ = 170 (fanout og bladkapasitet).

• Bladnivå: ⌈800 000 / 170⌉ = 4706 blokker.
• Nivå 1: ⌈4706 / 170⌉ = 28 blokker.
• Rotnivå: ⌈28 / 170⌉ = 1 blokk.

Tre nivåer totalt. Likhetsoppslag = 3 indeks-aksesser + 1 heap-aksess for selve raden = 4 blokker.

A er for få: 4706 blader passer ikke under én rot (maks 170 barn).
C/D er for mange: fanouten på 170 er stor nok til at 4706 ruller seg ned til 1 rot på 2 hopp.

Pensum: Kap. 6B — Tre-høyde

Anta blad har plass til 4 nøkler og fylles til 5 etter innsetting:

1. Splitt bladet: de 5 nøklene fordeles på to blader. Vanlig pensumkonvensjon: ⌈5/2⌉ = 3 i venstre blad, 2 i høyre (eller motsatt — mindre viktig hva som velges, så lenge det er konsistent).

2. Oppdater bladlenker: det nye høyre-bladet lenkes inn i den lenkede listen (venstre.next = nytt blad; nytt.next = gamle høyre).

3. Send opp én nøkkel til foreldren: minste nøkkelen i det høyre nye bladet kopieres opp og settes inn som separator i forelderen — sammen med peker til det nye bladet.

4. Hvis forelderen overskrider sin kapasitet, splittes også den — men der flyttes midt-nøkkelen oppover (ikke kopieres). Splitten kan kaskadere helt opp til rota; hvis rota må splittes, vokser treet med ett nivå.

Konsekvens: én innsetting kan i verste fall trigge log(n) blokk-skrivinger.

Pensum: Kap. 6B — Innsetting

Sammensatte indekser er sortert leksikografisk — først på land, så by, så postnr. Indeksen kan brukes når spørringen filtrerer på et venstre prefiks:

✓ WHERE land = 'NO' — kun første kolonne, OK.
✓ WHERE land = 'NO' AND by = 'Trondheim' — to første, OK.
✓ WHERE land = 'NO' AND by = 'Trondheim' AND postnr = 7012 — alle tre, optimalt.
✓ Også range på siste leddet: WHERE land='NO' AND by='Trondheim' AND postnr BETWEEN 7000 AND 7099.

✗ WHERE by = 'Trondheim' alene — hopper over land, indeksen er ubrukelig.
✗ WHERE postnr = 7012 — hopper over begge, ubrukelig.
✗ WHERE land = 'NO' AND postnr = 7012 — bruker land, men kan ikke sno seg til postnr uten å gå gjennom hele by-rangen for NO.

Tommelfingerregel: kolonnerekkefølgen i indeksen avgjør hvilke spørringer den støtter.

Pensum: Kap. 6B — Composite key

Selektivitetsfaktoren = andelen rader som overlever predikatet (mellom 0 og 1).

Likhet (col = c): antar uniform fordeling, sf = 1 / V(col, R) der V er antallet distinkte verdier.

Range (col > c): sf = (high − c) / (high − low).

BETWEEN c1 AND c2: sf = (c2 − c1) / (high − low).

Kombinasjon:

• P1 AND P2 (uavhengige): sf = sf₁ · sf₂.
• P1 OR P2: sf = sf₁ + sf₂ − sf₁·sf₂ (inklusjon-eksklusjon).
• NOT P: sf = 1 − sf.

Forventet antall treff: |R| · sf. Bedre estimater fås med histogrammer — DBMS-en kan da slippe uniform-antagelsen.

Pensum: Kap. 7 — Statistikk

En cost-based optimizer enumererer kandidatplaner og regner en forventet kostnad (typisk antall blokk-aksesser) for hver. Velger den billigste.

Statistikk i SQL-katalogen:

• |R|: antall rader i tabellen.
• b_R: antall blokker tabellen bruker.
• V(A, R): antall distinkte verdier av attributt A.
• min(A), max(A): lavest/høyest forekommende verdi (lowkey/highkey).
• h_R: høyde av et eventuelt B+-tre på R.
• Histogrammer: bredde- eller høydebalanserte buckets med radtellere — gir bedre selektivitetsestimater enn antagelsen om uniform fordeling.

Statistikken er ikke alltid fersk: ANALYZE TABLE i MySQL eller VACUUM ANALYZE i PostgreSQL oppdaterer den. Foreldet statistikk er en klassisk grunn til at optimizeren plutselig velger en dårlig plan.

Pensum: Kap. 7 — SQL-katalog

Riktig: A — 12 000 blokker.

Initial-passet leser inn n_B blokker om gangen, sorterer i RAM, skriver ut som en run.
n_R = ⌈b / n_B⌉ = ⌈2000 / 11⌉ = 182 initial runs.

Merge-faktor: d_M = n_B − 1 = 10 (én buffer brukes til output).
Antall merge-passes: ⌈log_d_M(n_R)⌉ = ⌈log_10(182)⌉ = ⌈2.26⌉ = 3.

Total I/O: 2b · (1 + passes) = 2·2000·(1+2) = 12 000 blokker.

Merk: «1 + passes» — initial-passet teller som ett pass; deretter kommer 2 ekte merge-passes (etter «log_10(182) ≈ 2.26» rundes opp til 3, men det er fordi vi tester med log_d_M(n_R/n_B) i noen kompendier — sjekk hvilken konvensjon kurset bruker. Pensum-formelen ⌈log_d_M(n_R)⌉ over n_R = 182 gir 3 passes; «1 + 2» merge-passes er en alternativ telling). Tommelregel: les fasiten i pensum-eksemplet og bruk samme telling konsekvent.

I dette tilfellet med 2 merge-passes: total = 2·2000·(1+2) = 12 000.

Pensum: Kap. 7 — External merge sort

1. Filscan (full table scan): les alle blokker. Vinner hvis predikatet matcher mange rader, eller om det ikke finnes en passende indeks.

2. Indeks-lookup (likhet på indekset attributt): traverser ned indeksen, finn én eller få rader. Vinner ved selektive likhetspredikater og clustered eller få-treff unclustered.

3. Range-scan på indeks: traverser ned til startnøkkel, gå sekvensielt gjennom bladnoder til stoppnøkkel. Vinner ved range-predikater på en clustered indeks.

4. Indeksscan (full indeks-scan): les alle blader uten å gå via heap. Vinner når spørringen kan besvares fra kun indeksen (covering index) — f.eks. SELECT col FROM R der col er indeksert, eller COUNT(*) som bare trenger antall.

Optimizeren regner kostnad for hver lovlige aksessvei og velger den billigste basert på selektivitet og statistikk.

Pensum: Kap. 7 — Aksessveier

Riktig: A — 1208 blokker.

Formel: b_ytre + ⌈b_ytre / (n_B − 2)⌉ · b_indre (én buffer til indre, én til output, resten til ytre).

= 8 + ⌈8 / 10⌉ · 1200 = 8 + 1 · 1200 = 1208

Hele Department får plass i én «chunk» på 10 buffere, så Employee leses bare én gang.

B (9608) tar Employee som ytre: 1200 + ⌈1200/10⌉ · 8 = 1200 + 120·8 = 2160 — eller med n_B=2 gir 1200 + 1200·8 = 10 800. Disse tallene matcher ikke nøyaktig — en typisk distraktor med feil ytre-tabell.
C (2408) regner med 200 (n_B/2) i stedet for n_B−2.
D (9600) = 1200 · 8: glemmer at ytre Department leses bare én gang.

Lærdom: velg den minste tabellen som ytre for å minimere antall passes over indre tabell.

Pensum: Kap. 7 — J1 block nested loop

J2 vinner når det finnes en indeks på indre tabells join-attributt, og ytre tabell er liten eller predikat-filtrert.

Algoritme: for hver rad i ytre R, slå opp matchende rader i indre S via indeksen.

Kostnad (clustered indeks på S):
kost = b_R + |R| · (h_S + 1)
der h_S = høyden på B+-treet på S og «+ 1» er heap-aksessen (eventuelt mer enn 1 hvis flere rader matcher per oppslag).

Kostnad (unclustered indeks på S):
kost = b_R + |R| · (h_S + matcher_per_R)
der hver match koster én ekstra heap-blokk (med duplikater).

Sammenligning med J1: J2 sparer hele scan av S, men betaler én indekstraversering per ytre rad. Vinner når |R| er liten relativt til b_S / (h_S + 1).

Pensum: Kap. 7 — J2 index nested loop

Algoritme:

1. Sorter R på join-attributtet (hvis ikke allerede sortert).
2. Sorter S på join-attributtet.
3. Merge: to pekere som beveger seg parallelt gjennom de sorterte tabellene; emittér par når nøklene matcher.

Kostnad: sort(R) + sort(S) + b_R + b_S.

Sort-koster: 2·b · (1 + ⌈log_d_M(n_R)⌉) for hver tabell (samme som external merge sort).

Sort-merge vinner når:
• Begge tabeller er store og ingen indeks finnes.
• Tabellene allerede er sortert på join-attributtet (fra et clustered indeks eller en tidligere ORDER BY) — da blir kosten bare b_R + b_S, dramatisk billig.
• Output-en skal sorteres på join-attributtet uansett — sortering blir gratis.

Hvis bare én av tabellene er sortert, sorter den andre.

Pensum: Kap. 7 — J3 sort-merge

To faser:

Build / partition: bruk en hash-funksjon h₁ på join-attributtet, partisjoner R og S i samme antall partisjoner. Hver partisjon havner i én bucket-fil — radene fra R og S med samme hash-verdi havner i samme bucket-par.

Probe: for hvert par av partisjoner (R_i, S_i): bygg en hash-tabell på den minste i RAM, probe med den større. Bruk en annen hash-funksjon h₂ for å unngå kollisjoner som allerede ble brukt til partisjonering.

Kostnad: 3 · (b_R + b_S) — les begge én gang (partisjonere), skriv begge én gang, les begge én gang (probe). Antar at hver partisjon får plass i RAM.

Hvis en partisjon er for stor: rekursiv re-partisjonering (recursive hash join) eller hybrid hash join.

Vinner over sort-merge når det ikke finnes nyttig sortering, og over nested loop når begge tabeller er store.

Forutsetter ekvi-join (likhetsbetingelse). Theta-join som R.a < S.b kan ikke gjøres med hash.

Pensum: Kap. 7 — J4 hash join

J1 — Block nested loop: liten ytre tabell, indre uten indeks. Robust «fallback» når ingenting annet passer.

J2 — Index nested loop: liten ytre tabell, og indeks finnes på indre tabells join-attributt. Klart raskest når ytre er svært selektiv (få rader).

J3 — Sort-merge: begge tabeller er store og ingen indeks. Spesielt bra når tabellene allerede er sortert (f.eks. fra en clustered indeks eller en tidligere ORDER BY).

J4 — Hash: begge tabeller store, ingen sortering, ingen indeks. Vinner over sort-merge ved store datamengder; forutsetter ekvi-join.

Optimizeren regner kostnaden for alle de aktuelle algoritmene (gitt aksessveier, indekser og sortering) og velger den billigste — det er hele jobben i kapittel 7.

Pensum: Kap. 7 — Join-algoritmer

To operasjoner er i konflikt hvis:
(a) de tilhører forskjellige transaksjoner,
(b) de aksesserer samme dataobjekt, og
(c) minst én av dem er en write.

Konflikttypene: r-w, w-r, w-w. To reads (r-r) er aldri i konflikt.

Test for konfliktserialiserbarhet:

1. Bygg presedensgraf: én node per transaksjon. Tegn kant T_i → T_j hvis det finnes en konflikt der T_i sin operasjon kommer før T_j sin.
2. Schedule-en er konfliktserialiserbar ⇔ presedensgrafen er asyklisk.
3. Hvis asyklisk: enhver topologisk sortering av grafen gir et serielt schedule som er konfliktekvivalent.

Konfliktserialiserbart ⊂ view-serialiserbart ⊂ serialiserbart. I praksis bruker DBMS-er konfliktserialiserbarhet, fordi det er polynomisk avgjørbart (mens view-serialiserbarhet er NP-komplett).

Pensum: Kap. 8 — Serialiserbarhet

Recoverable: en transaksjon T_j som leser fra T_i må commit'e etter T_i. Hvis ikke kan en abort av T_i etter T_j sin commit ikke rulles tilbake — vi har committed et resultat basert på data som ble fjernet.

ACA (Avoids Cascading Aborts): stricter — T_j kan ikke i det hele tatt lese en write fra T_i før T_i har commit'et. Dermed kan en abort aldri kaskadere til andre transaksjoner.

Strict: enda strictere — T_j kan verken lese eller overskrive en write fra T_i før T_i har commit'et. Dette gir også enkel before-image recovery (UNDO trenger bare den siste verdien).

Inklusjonen er ekte: alle Strict er ACA, alle ACA er Recoverable, alle Recoverable er gyldige schedules — men ikke omvendt.

Strict 2PL (rigorous 2PL) gir Strict schedules. Basic 2PL gir bare Recoverable.

Pensum: Kap. 8 — Recoverability

Basic 2PL: alle låser tas før den første låsen slippes (én vekstfase, så én skrumpefase). Garanterer konfliktserialiserbarhet, men ikke recoverable schedules. Kan ha kaskaderende abort.

Conservative 2PL: alle låser tas før transaksjonen starter. Hvis en lås er opptatt, blokkerer transaksjonen helt før den begynner. Deadlock-fri, men krever at hele lock-settet er kjent på forhånd.

Strict 2PL: alle X-låser beholdes til commit/abort. Garanterer Strict schedules + serialiserbarhet. Vanligst i praksis.

Rigorous 2PL: alle låser (S og X) beholdes til commit/abort. Slipper at conflicts kan oppstå sent. Implementeringsmessig enklere enn strict; samme egenskaper.

Alle fire kan deadlocke (unntatt conservative). Strict og rigorous er de eneste som garanterer både serialiserbarhet OG strict schedules.

Pensum: Kap. 8 — 2PL

Basic S/X-matrise:

          S      X
   S      ✓      ✗
   X      ✗      ✗

To S kan eksistere samtidig (mange lesere). En X eksluderer alt.

Intent-låser brukes ved hierarkisk låsing (database → tabell → blokk → rad):

• IS (Intent Shared): «jeg planlegger å ta en S-lås på en under-node».
• IX (Intent Exclusive): «jeg planlegger en X-lås nedover».
• SIX (Shared + Intent Exclusive): «leser hele tabellen, men vil oppdatere noen rader».

Utvidet matrise:

         IS    IX    S    SIX    X
   IS    ✓    ✓    ✓    ✓     ✗
   IX    ✓    ✓    ✗    ✗     ✗
   S     ✓    ✗    ✓    ✗     ✗
   SIX   ✓    ✗    ✗    ✗     ✗
   X     ✗    ✗    ✗    ✗     ✗

Før T tar en S-lås på en rad, må den først ta IS på tabellen og databasen. Slik vet andre transaksjoner som vil ta X på hele tabellen at de må vente.

Pensum: Kap. 8 — Låser

Wait-for graph: én node per aktiv transaksjon; kant T_i → T_j hvis T_i venter på en lås holdt av T_j. Sykel = deadlock. DBMS-en sjekker periodisk; ved sykel velges en victim (typisk yngst transaksjon, eller den som har gjort minst arbeid) og aborts.

Forebygging i stedet for deteksjon: gi hver transaksjon et tidsstempel ved start. Eldre tidsstempel = høyere prioritet.

Wait-die (preemption-fri): hvis T_i ber om lås holdt av T_j:
• T_i eldre: T_i venter (eldre prioriteres).
• T_i yngre: T_i aborts og restartes med samme tidsstempel.

Wound-wait (preemptiv): hvis T_i ber om lås holdt av T_j:
• T_i eldre: T_j aborts (eldre «sårer» yngre).
• T_i yngre: T_i venter.

Begge garanterer deadlock-frihet fordi venting kun skjer i én retning av tidsstempel-orden. Wound-wait færre restarts (eldre fullfører raskere); wait-die enklere implementasjon.

Pensum: Kap. 8 — Deadlock

MVCC (multi-version concurrency control): hver write skaper en ny versjon av raden, merket med tidsstempel for transaksjonen som skrev den. Reads ser den versjonen som var nyest ved transaksjonens start (snapshot).

Konsekvens: readers blokkerer aldri writers, og writers blokkerer aldri readers. Bare write-write-konflikter krever koordinering — typisk via en sjekk ved commit (first-committer-wins).

Snapshot isolation: isolasjonsnivå basert på MVCC. Forhindrer dirty read, non-repeatable read, lost update — men ikke alle anomalier.

Write skew (klassisk anomali under SI): to transaksjoner leser overlappende data og skriver til forskjellige objekter, basert på et felles invariant. Eksempel: «minst én lege må være på vakt». T1 og T2 ser begge to leger på vakt; begge bestemmer at det er trygt å ta seg fri; begge oppdaterer sin egen status. Ingen konflikt på samme rad → begge committer → ingen lege på vakt. Invariant brutt.

Løsning: serializable snapshot isolation (SSI) — sjekker også r-w-konflikter via en SI-utvidet wait-for graph. PostgreSQL SERIALIZABLE.

Pensum: Kap. 8 — MVCC

Dirty read: T_j leser en uncommitted write fra T_i. Hvis T_i abortes, så T_j leste data som aldri eksisterte. Hindret av READ COMMITTED og oppover.

Non-repeatable read: T_i leser X, T_j endrer X og committer, T_i leser X igjen og får annen verdi. Hindret av REPEATABLE READ og oppover (typisk via S-låser holdt til commit).

Lost update: T_i leser X = 100, T_j leser X = 100, begge øker med 1, begge skriver tilbake X = 101 — én oppdatering tapt. Hindret av REPEATABLE READ i mange DBMS-er, eller via SELECT … FOR UPDATE.

Phantom read: T_i kjører SELECT … WHERE p og får 5 rader; T_j inserter en ny rad som matcher p og committer; T_i kjører samme SELECT og får 6 rader. Hindret av SERIALIZABLE (typisk via predicate locking eller index-range locking).

Anomalier som ikke hindres av SERIALIZABLE i SI: write skew (se MVCC-kortet) — kreves SSI eller eksplisitt SELECT FOR UPDATE.

Pensum: Kap. 8 — Isolasjonsnivåer

Matrisen handler om når dirty pages skrives til disk.

Force: alle endrede sider må være på disk før commit. Ingen REDO trengs (det er allerede skrevet) — men commit blir tregt.
No-force: sider kan forbli i bufferet ved commit. Krever REDO ved krasj — vi må kunne reapply committed transaksjoner som ikke nådde disk.

Steal: en uncommitted transaksjons sider kan kastes ut av bufferet og skrives til disk. Krever UNDO ved krasj — vi må kunne reverse skrivinger fra ikke-committed transaksjoner.
No-steal: en sides side beholdes pinnet til commit. Trenger ikke UNDO.

             Force         No-force
Steal        UNDO          UNDO + REDO  ← ARIES
No-steal     ingen recovery  REDO

ARIES = Steal + No-force: maksimal fleksibilitet for buffer manageren (kan kaste ut hva som helst, kan utsette skriving til etter commit), men krever full UNDO+REDO via WAL.

WAL-regelen sikrer at logg-postene som beskriver en endring er på disk før selve siden — det er det som gjør UNDO mulig selv ved en steal-eviction.

Pensum: Kap. 8 — Recovery

1. Analysis: les loggen fra siste checkpoint til slutten. Bygg opp:
• Transaction Table (TT): alle transaksjoner som var aktive ved krasjet (ingen commit/abort-post sett).
• Dirty Page Table (DPT): sider som var skitne (modifisert i bufferet, kanskje ikke skrevet til disk).
Etter analyse: vi vet hvem som var winners (committed) og losers (aktive ved krasj).

2. Redo: start fra min(recLSN) i DPT. For hver loggpost fremover:
• Hvis side i DPT, recLSN ≤ LSN, og PageLSN < LSN — utfør operasjonen på siden, sett PageLSN = LSN.
• Ellers: hopp over (allerede på disk, eller ikke i DPT).
Resultat: alle committed endringer er nå på disk.

3. Undo: start fra slutten av loggen, gå bakover. For hver loser-transaksjon: utfør UNDO av hver av deres write-poster. Skriv en CLR (compensation log record) for hver UNDO — sikrer at en ny krasj midt i recovery kan fortsette. Ferdig når alle losers er UNDO-et.

Merk rekkefølgen: REDO først (selv losers), så UNDO. Slik blir disk konsistent med loggen før vi reverserer.

Pensum: Kap. 8 — ARIES

Riktig: A — REDO-es.

ARIES REDO-test krever alle tre kriterier:

1. Side i DPT — ✓ (P5 er der).
2. recLSN ≤ LSN: 80 ≤ 90 — ✓.
3. PageLSN < LSN: 70 < 90 — ✓.

Alle tre kriterier matcher → utfør REDO, og oppdater PageLSN til 90.

Tolkning: P5 ble første gang skitnet av en loggpost ≥ recLSN (80). Endringen i LSN 90 er ikke ennå reflektert på disk (PageLSN = 70). Den må derfor reapplies.

B sjekker første kriterium feil. C: recLSN = 80, LSN = 90 → 80 ≤ 90 OK. D: PageLSN = 70 < LSN = 90, så test 3 bestås — vi må redo.

Pensum: Kap. 8 — REDO-fase

WAL (write-ahead logging): før en endret side skrives til disk, må alle loggposter med LSN ≤ PageLSN være på disk. Konkret: før P kan flushes, må log[i] for alle i ≤ P.PageLSN være persistente.

Dette gir: hvis vi finner en endring på disk uten en korresponderende loggpost, er det en feil. Hvis vi ikke finner endringen på disk men har loggposten, kan vi REDO-e.

Ved commit: alle T_i sine loggposter — inkludert «commit T_i» — må være på disk. Force-log-at-commit. Selve datasidene kan ligge igjen i bufferet (no-force).

CLR (compensation log record): ved UNDO i recovery skriver ARIES en CLR for hver inverterte handling. CLR har en UndoNxtLSN-peker til neste loggpost som skal UNDO-es.

Hvorfor: hvis det krasjer midt i recovery, kan neste recovery se hvor langt forrige UNDO var kommet (via CLR-pekerne) og fortsette derfra — uten å undo'e samme operasjon to ganger. CLR er redo-only, aldri undo-et.

Pensum: Kap. 8 — WAL + CLR

LSN (Log Sequence Number): unikt nummer som hver loggpost får ved skriving. Monotont voksende. Lever i loggposten.

PrevLSN: peker fra en loggpost til forrige loggpost for samme transaksjon. Tillater UNDO å traversere transaksjonens skrivinger bakover uten å skanne hele loggen. Lever i loggposten.

PageLSN: LSN-en til den siste endringen som er reflektert på en disk-side. Lagres i sidens header. Brukes i REDO-testen: hvis PageLSN ≥ LSN av loggposten, er endringen allerede på disk — ikke gjør den igjen.

recLSN: i Dirty Page Table. Den første loggposten som skitnet siden etter at den sist ble skrevet til disk. recLSN er nedre grense for REDO-fasen — hvis LSN < recLSN, er endringen på disk allerede.

Til sammen lar disse feltene ARIES vite nøyaktig hva som er på disk, hva som mangler, og hva som må reapplies eller reverseres etter et krasj.

Pensum: Kap. 8 — LSN-feltene

Sharp checkpoint: stopp alle transaksjoner, flush hele bufferet til disk, skriv en checkpoint-post. Garantert konsistent disk-state, men blokkerer alt i mange sekunder for store buffere — uakseptabelt i produksjon.

Fuzzy checkpoint (ARIES): ikke flushet, ikke konsistent — bare en snapshot av metadata:
• Skriv BEGIN_CHKPT-loggpost.
• Skriv END_CHKPT med kopi av aktuell Transaction Table + Dirty Page Table.
• I master record (egen disk-lokasjon): peker til BEGIN_CHKPT.

Transaksjoner kjører videre under hele prosessen.

Recovery starter analyse-fasen fra denne BEGIN_CHKPT. Det er TT og DPT vi finner som er utgangspunktet — de sannsynligvis litt utdaterte, men oppdateres ved å lese loggen videre.

Trade-off: fuzzy checkpoints påvirker neppe ytelsen, men recovery må fortsatt prosessere alt fra begin-checkpoint og fremover.

Pensum: Kap. 8 — Checkpoints

Riktig: A — konfliktserialiserbart, ekvivalent med T1 → T2.

Identifiser konflikter (ulike T, samme objekt, minst én write):

• w1(B) før w2(B) → kant T1 → T2 (w-w på B).
• r1(A) før w2(A) → kant T1 → T2 (r-w på A).
• r2(A) før w2(A) — samme transaksjon, ikke konflikt.
• r1(A) og r2(A) — to reads, ikke konflikt.

Presedensgraf: T1 → T2. Asyklisk → konfliktserialiserbart. Eneste topologiske sortering: T1 før T2.

B ville krevd kant T2 → T1, men det finnes ingen konflikt der T2 kommer først.
C: ingen sykel.
D: bare én sortering er gyldig.

Pensum: Kap. 8 — Presedensgraf

Rad-låser kan bare låse eksisterende rader. Et phantom-problem oppstår når en ny rad insertes som matcher et tidligere predikat — det fantes ingen rad å låse.

Eksempel: T1 kjører SELECT COUNT(*) FROM Emp WHERE dept = 5 og får 3. T2 inserterer en ny ansatt med dept = 5 og committer. T1 kjører samme SELECT igjen, får 4. Selv med S-lås på de tre opprinnelige radene har ikke T1 hindret T2 fra å sette inn en ny.

To løsninger:

1. Predicate locking: lås predikatet selv (dept = 5) — enhver INSERT/UPDATE som matcher predikatet må vente. Konseptuelt rent, men dyrt å sjekke (krever predikat-evaluering).

2. Index-range locking: hvis spørringen bruker en B+-indeks på dept, lås intervallet [5, 5] i indeksen. INSERT med dept = 5 må navigere ned i indeksen, treffer låsen, blokkerer. Standard i MySQL InnoDB, PostgreSQL.

I praksis bruker DBMS-er index-range locking. Hvis ingen indeks finnes, faller man tilbake til tabell-lås — koster mer i samtidighet.

Pensum: Kap. 8 — Phantoms

Winner: transaksjon T som har en commit-post i loggen før krasjet. Endringene skal redo-es; T skal ikke reverseres.

Loser: transaksjon T som var aktiv ved krasjet — har skrevet write-poster, men ingen commit-post. Endringene må undo-es.

Etter analyse: transaction table-en inneholder bare losers. Winners har allerede en commit-post og er fjernet fra TT i analyse-passet.

REDO-fasen redo-er alle loggposter som matcher kriteriene — også fra losers, fordi vi vil at disk-bildet skal samsvare med loggen før UNDO. UNDO-fasen reverserer så loser-postene fra slutten av loggen og bakover, og skriver CLR for hver.

Etter recovery: winners er reflektert på disk; losers er som om de aldri kjørte. Database er konsistent.

Pensum: Kap. 8 — Analyse-fasen

Riktig: C — ~103 blokker.

Selektivitet for likhet: sf = 1/V = 1/1000 = 0.001.
Forventet antall treff: 100 000 · 0.001 = 100 rader.

Med unclustered indeks ligger de 100 radene på 100 forskjellige heap-blokker (worst case, men det er det som regnes i pensum).

Total: 3 (B+-traversering) + 100 (heap-aksesser) = 103 blokker.

Sammenligning: full scan = 1500 blokker. Indeksen vinner — knapt — fordi treffmengden er liten nok til at random heap-aksesser ikke koster mer enn full scan.

A: full scan ville vært dyrere.
B: ville stemt for clustered eller for et unikt predikat med ett treff. Her er det ~100 treff.
D: forutsetter en hash-indeks med null kollisjon — vi har et B+-tre.

Hvis V hadde vært 10 (sf = 0.1, 10 000 treff), ville full scan vunnet med god margin.

Pensum: Kap. 7 — Aksessveger

Pipelined: hver operator i plantreet sender rader videre til neste operator én om gangen, uten å lagre mellomresultatet. Ofte implementert som iterator-modellen (next()-kall). Lavt minneforbruk, lav latens for første rad.

Materialized: en operator beregner hele mellomresultatet og lagrer det (i RAM eller på disk) før neste operator starter. Brukes når neste operator må ha hele input-en.

Tvunget materialisering:

• Sortering (ORDER BY, sort-merge join build) — må se alle rader før output.
• Hash join build-fase — hele build-relasjonen partisjoneres før probe.
• Aggregering med GROUP BY hvis output ikke er pre-sortert eller hashet.
• DISTINCT uten sortert input.
• Subquery uten korrelasjon som blir kjørt én gang.

Generelt: blokkerende operatorer materialiserer; ikke-blokkerende pipeliner. Plan-trær med mange blocking nodes har høy minne-/disk-bruk og høy latens for første rad.

Pensum: Kap. 7 — Plan-utføring

Filter pushdown = utfør WHERE-predikater så tidlig som mulig i plantreet, før joins og aggregering.

Eksempel: SELECT * FROM A JOIN B ON A.id = B.aid WHERE A.year = 2020.

• Naivt plantre: σ_year=2020(A ⋈ B) — joiner først, filtrerer etter. Dyrt hvis A og B er store.
• Optimalisert: σ_year=2020(A) ⋈ B — filtrerer A først, joiner bare det som overlever.

Hvorfor virker det: |σ(A)| ≤ |A|. Mindre input til join → færre rader å sammenligne, mindre data å materialisere/sortere/hashe i join-algoritmen.

Optimalisatoren gjør dette via relasjonsalgebra-ekvivalenser (kommutativitet av σ med ⋈ når predikatet bare bruker attributter fra én side). Også projection pushdown — eliminer kolonner tidlig.

Push-down stoppes hvis predikatet bruker kolonner fra begge sider av join-en — da må joinen utføres først.

Pensum: Kap. 7 — Algebra-omskriving

1. Lagringsplass: en B+-indeks på en kolonne lagrer 16 byte (eller mer for sammensatte) per rad — kan være 30-100 % av tabellens størrelse for store tabeller med flere indekser.

2. Skrive-overhead: hver INSERT/UPDATE/DELETE må oppdatere alle relevante indekser. En tabell med 5 indekser har 5× skrive-amplifikasjon. INSERT som ville vært én blokk-skriving blir 5+1 = 6 (eller flere ved kaskaderende splitt).

3. Optimizer-overhead og feilvalg: flere indekser betyr flere kandidatplaner. Optimizeren kan velge en suboptimal indeks hvis statistikken er dårlig — eller en spørring som ville matchet en av indeksene 100 % perfekt blir ikke valgt fordi en annen ser billigere ut.

Tommelfingerregel: indekser kolonner som brukes ofte i WHERE eller JOIN og som er selektive. Indekser ikke kolonner med få distinkte verdier (f.eks. kjønn, status) — selektiviteten er for lav.

Et OLTP-system med tunge skrivelaster bør ha få, gode indekser; et OLAP-system med sjeldne writes og mange spørringer kan ha mange.

Pensum: Kap. 6B + Kap. 7

1. SQL-tekst (Kap. 3): brukeren skriver et SELECT.

2. Parser → relasjonsalgebra-tre (Kap. 2): oversetter SQL til σ/π/⋈/etc., med tabeller og kolonner slått opp i SQL-katalogen.

3. Algebra-ekvivalenser (Kap. 7): push-down filtere, omorganiser joins. Fortsatt et logisk tre.

4. Cost-based optimizer (Kap. 7): generer fysiske planer med konkrete aksessveier (J1–J4, full scan, indeks-lookup, sort) og kostnadsregn dem mot statistikk i SQL-katalogen.

5. Executor (Kap. 7): kjør valgt plan ved å kalle aksessmetoder.

6. Buffer pool (Kap. 6A): oversett blokk-forespørsler til faktisk disk-I/O eller bufferhit.

7. Disk (Kap. 6A/B): heapfil eller B+-tre returnerer blokker.

Parallelt: concurrency control (Kap. 8 §1–2) låser eller bruker MVCC; recovery manager (Kap. 8 §3) logger writes via WAL.

Schemaet for hele kurset er denne pipelinen — alle øvinger og eksamener er drilling på enkeltledd.

Pensum: Reisen gjennom DBMS-en

A — Atomicity: UNDO-logging (kap. 8). En aktiv transaksjon kan rulles tilbake fordi WAL har lagret før-bildene; recovery undo-er ufullførte transaksjoner.

C — Consistency: integritetsregler (FK, CHECK, NOT NULL, UNIQUE — kap. 3) håndheves av executoren ved hver INSERT/UPDATE/DELETE. Triggere kan utvide. Selve transaksjonen må være korrekt skrevet.

I — Isolation: concurrency control (kap. 8 §2). Strict 2PL eller MVCC (snapshot isolation) sikrer at samtidige transaksjoner ser ut som en serialiserbar utførelse.

D — Durability: WAL + force-log-at-commit (kap. 8 §3). Selv om sider ligger i bufferet ved commit, vil REDO-fasen rekonstruere committed endringer fra loggen etter krasj.

Knytningen er ikke 1:1 — UNDO bidrar også til konsistens (rollback ved constraint-brudd), og MVCC bruker også versjonering for å hjelpe atomicity. Men de fire mekanismene over er hovedansvarlige for hver bokstav.

Pensum: Kap. 8

O-notasjon ignorerer konstantfaktorer, men i praksis er antallet diskaksesser det som dominerer.

• B+ med høyde 3: 3 diskaksesser garantert. Rotnoden ligger ofte i bufferet (frequently accessed) — i praksis 2 reads.

• Hash med overflow-kjede på 5: 5 diskaksesser. «O(1)» er teoretisk gjennomsnitt over godt fordelt input, men når dataene har vokst forbi N, vokser kjeden lineært.

• Hash uten overflow: 1 diskaksess — vinner over B+. Det er derfor extendible hashing er attraktiv for likhetsoppslag når man kan dimensjonere godt.

Hash taper imidlertid på range-spørringer: hash-en mister ordning. WHERE x BETWEEN 5 AND 10 krever full hashtabell-scan. B+-tre gjør dette i ett tre-traversal + linkliste-traversering på blader.

I et virkelig DBMS ser du derfor:
• B+-trær for primær- og sekundærindekser (default).
• Hash-indekser tilbudt som opsjon for ren-likhet (PostgreSQL har USING HASH; MySQL bruker B+ alltid på InnoDB).
• Extendible hashing internt i page directory og partition hash join.

Pensum: Kap. 6B + Kap. 6A — Hashing