Kapittel 2 · Forelesning 2 · Lærebok 2 + notater 3.2 og 4.1

Relasjonsmodellen og relasjonsalgebra

Det formelle fundamentet bak SQL: tabeller med skjema og nøkler, og operatorene som tar relasjoner inn og gir relasjoner ut.

Helhetsbilde

Hvorfor dette kapittelet er kritisk

Alt resten av kurset bygger på dette. SQL (kapittel 3–5), normalisering (7), querybehandling (13) og indekser (10–11) snakker alle om relasjoner, nøkler og algebra-uttrykk. Hvis vokabularet sitter løst her, blir resten kjempetungt.

Codd 1970 — én datatype (tabellen), én operasjonsfamilie (algebraen). Brukeren beskriver hva; systemet finner ut hvordan.
Relasjon = mengde av tupler over et skjema. Ingen rekkefølge, ingen duplikater, atomiske domener.
Nøkler binder modellen sammen. Primærnøkler identifiserer rader; fremmednøkler kobler tabeller.
SQL er overflaten — relasjonsalgebra er fundamentet. Optimalisatoren manipulerer algebra-uttrykk for å finne en rask plan.

Pensum

Lærebokas kapittel 2 + notater 3.2 og 4.1. Forelesningens slides ligger ikke under powerpoints/ — alt nødvendig stoff finnes på sidene 2A og 2B.

Læringssti

Anbefalt rekkefølge

Følger du denne rekkefølgen, har du modellen på plass før du møter operatorene som virker på den.

Hvorfor relasjoner

Codd 1970. Forskjellen mellom deklarativ og prosedyral tilgang.

~5 min

Strukturen

Tabell, attributt, tuppel, domene. Atomiske verdier (1NF).

~8 min

Skjema vs. instans

Hva som er stabilt og hva som endres med hver oppdatering.

~4 min

Nøkler

Supernøkkel, kandidatnøkkel, primærnøkkel — hierarkiet.

~10 min

Fremmednøkler

Skjemadiagram, referanseintegritet, CASCADE / SET NULL / RESTRICT.

~10 min

NULL og 3-verdig logikk

Hvorfor «ukjent» roter til både filter og NOT IN.

~8 min

Operator-oversikt

σ, π, ×, ∪, −, ρ + avledede ⋈, ∩, ← og utvidet γ.

~6 min

Join-varianter

Theta, equi, natural, outer. Når falle tupler bort?

~12 min

Aggregering

γ-operatoren: avg, min, max, sum, count — med og uten GROUP BY.

~6 min

Bygg en spørring

Interaktiv runner som viser hva σ → ⋈ → π gjør med datasettet.

~5 min

Deler

Utforsk kapittelet

Relasjonsmodellen

Skjema, attributter, domener, primær- og fremmednøkler, integritetskrav, NULL og 3-verdig logikk

→ 2B

Relasjonsalgebra

σ, π, ×, ∪, −, ρ, ⋈, ∩ + γ-aggregering — med eksempler, Venn-diagrammer og en interaktiv runner

→

Begreper

Et minimalt kart

Hvordan begrepene henger sammen — bruk det som sjekkliste.

Relasjonen er sentralt. SQL bygger på relasjonsalgebraen, som opererer på relasjonene.

Test deg selv

30 spørsmål som dekker hele kapittelet — fra modell til algebra. De første 15 er reveal-spørsmål; de neste 15 er flervalg med blandet vanskelighet, inkludert noen veldig vanskelige.

Spørsmål 1 · Lett · Modell

Hva betyr det at en relasjon er en mengde av tupler, og hvilke to praktiske konsekvenser har det?

Det betyr at (1) rekkefølgen på rader er irrelevant — du kan ikke spørre etter «den tredje raden», og (2) duplikater ikke finnes — to identiske rader er per definisjon én rad. SQL tar et praktisk avvik fra dette og bruker multimengder (bag-semantikk) — derfor må du skrive DISTINCT for å få mengdesemantikk.

Spørsmål 2 · Lett · Modell

Forklar forskjellen på skjema og instans.

Skjemaet er den logiske strukturen — attributtnavn, domener, nøkler, fremmednøkler. Det endres sjelden. Instansen er øyeblikksbildet av tuplene som finnes nå, og endres ved hver INSERT/UPDATE/DELETE. Sammenlign med programmering: skjema = type, instans = verdi.

Spørsmål 3 · Middels · Atomisitet

Hvilket av disse er ikke en gyldig relasjon i Codds forstand, og hvorfor?

Et eksempel som person(navn, telefoner) der telefoner inneholder en liste eller mengde, bryter med kravet om atomiske domener. Løsningen er en separat tabell person_phone(person_id, phone) med én rad per telefonnummer.

Spørsmål 4 · Middels · Nøkler

Skjemaet er enrollment(student_id, course_id, semester, year, grade). Hva er den minimale primærnøkkelen, og kan du ha to ulike kandidatnøkler her?

Primærnøkkel: {student_id, course_id, semester, year} — en student kan ta samme kurs på nytt i et annet semester. Andre kandidater er sjeldne her, men hvis hver student bare kan ta hvert kurs én gang totalt, kunne {student_id, course_id} fungert. Da må forretningsregelen være eksplisitt — kandidatnøkkel er en egenskap ved skjemaet, ikke ved en tilfeldig instans.

Spørsmål 5 · Vanskelig · Nøkler

En kollega argumenterer for at e-post kan være primærnøkkel for users. Hva er problemene med det?

(1) Ikke stabil — folk bytter e-post; det betyr cascading oppdateringer i alle FK-er som peker hit. (2) Personopplysning — havner alle steder primærnøkkelen brukes, gir GDPR-utfordringer. (3) Lengde — e-poster er lange og varierer; en syntetisk INT-id er raskere som indeksnøkkel. Praksis: bruk syntetisk id som primærnøkkel og legg UNIQUE på e-post.

Spørsmål 6 · Middels · Fremmednøkler

Du har orders → customers via fremmednøkkel. Hvilken delete-strategi er aldri god her, og hvorfor?

CASCADE er problematisk — sletter du en kunde, mister du hele ordrehistorikken, som du normalt trenger for regnskap, retur og rapportering. Bedre: RESTRICT (blokker sletting) eller bruk en «soft delete» (customers.deleted_at) slik at historikken blir bevart. SET NULL bryter referanseintegritet i nyttigheten — orden hører til noen, ikke ingen.

Spørsmål 7 · Lett · Integritet

Hva er entitetsintegritet, og hvorfor følger den naturlig fra hva primærnøkkelen skal gjøre?

Entitetsintegritet: ingen del av primærnøkkelen kan være NULL. Følger fordi primærnøkkelen skal identifisere en rad — og NULL betyr «ukjent» og er ikke engang lik seg selv. To rader med NULL i primærnøkkelen vil ikke kunne skilles.

Spørsmål 8 · Vanskelig · NULL

Hvorfor kan NOT IN med en sub-spørring som inneholder NULL gi ingen rader, selv om du venter mange?

Fordi x NOT IN (a, b, NULL) er ekvivalent med x ≠ a ∧ x ≠ b ∧ x ≠ NULL. Den siste er alltid UNKNOWN, og UNKNOWN i AND-kjede gir UNKNOWN totalt — som filtreres ut i WHERE. Bytt til NOT EXISTS eller filtrer NULL-er ut av sub-spørringen først.

Spørsmål 9 · Lett · Algebra

List de seks fundamentale operatorene i relasjonsalgebra, og en avledet operator du oftere bruker.

Fundamentale: σ select, π project, × kartesisk produkt, ∪ union, − differanse, ρ rename. Avledet: ⋈ join (= σ etter ×), ∩ intersect (= R − (R − S)). I tillegg har vi ← assignment for delresultater og den utvidede operatoren γ for aggregering.

Spørsmål 10 · Middels · Algebra

Skriv et relasjonsalgebra-uttrykk som finner navnet til alle Physics-instruktører som tjener mer enn 80 000.

π_name(σ_{dept_name = "Physics" ∧ salary > 80000}(instructor)). Alternativt kan du sammensette to selects: π_name(σ_{salary > 80000}(σ_{dept_name = "Physics"}(instructor))) — de gir samme resultat.

Spørsmål 11 · Middels · Join

Hva er forskjellen mellom natural join og theta-join? Når blir natural join farlig?

Natural join matcher implisitt på alle attributter med samme navn i begge relasjonene, og slår sammen til én kolonne. Theta-join lar deg oppgi et eksplisitt predikat. Natural join blir farlig når skjemaer endres — legges et nytt likt-navngitt attributt til (f.eks. created_at), endres semantikken stille uten at spørringen feiler. Eksplisitt JOIN ... ON er tryggere i produksjonskode.

Spørsmål 12 · Middels · Outer join

Hvilken instruktør-rad mister du i instructor ⋈ teaches, og hvilken algebra-operator beholder den?

Du mister enhver instructor uten match i teaches — altså instruktører som ikke underviser noe kurs. Left outer join instructor ⟕ teaches beholder alle rader fra venstre side; manglende attributter fra høyre fylles med NULL.

Spørsmål 13 · Vanskelig · Mengdeoperatorer

Hvorfor må R og S være «kompatible» for at R ∪ S skal være lov, og hva betyr kompatibel her?

Resultatet av union må selv være en relasjon — én klar liste av attributter med klare typer. Kompatibel betyr (1) samme aritet, og (2) samme type på den i-te attributten i begge. Det er posisjon som teller, ikke navn — du må projisere først for å justere skjemaene hvis de avviker.

Spørsmål 14 · Vanskelig · Aggregering

Skriv et algebra-uttrykk som finner gjennomsnittslønnen per avdeling for alle avdelinger som har minst tre instruktører. Hvilken SQL-konstruksjon blir den oversatt til?

σ_{cnt ≥ 3}(_{dept_name}γ_{avg(salary), count(*) AS cnt}(instructor)). SQL-motstykket: SELECT dept_name, AVG(salary) FROM instructor GROUP BY dept_name HAVING COUNT(*) ≥ 3. HAVING-klausen tilsvarer σ brukt etter γ — i motsetning til WHERE som filtrerer rader før gruppering.

Spørsmål 15 · Vanskelig · Optimalisering

Hvorfor er det nyttig at σ_p(R ⋈ S) ≡ (σ_p(R)) ⋈ S når p bare nevner attributter i R (for inner join)? Hva gjør optimalisatoren med dette?

Optimalisatoren bruker «push selection past join»: ved å filtrere R først reduseres antall rader som må joines, og dermed kostnaden av joinen (som er en av de dyreste operasjonene). Dette er en av flere ekvivalensregler som lar planleggeren bygge billigere fysiske planer uten å endre resultatet. Husk: regelen gjelder ikke ubetinget for outer joins — der introduseres NULL-er som kan endre semantikken.

Spørsmål 16 · Lett · σ vs. π

Hva er hovedforskjellen mellom σ (select) og π (project)?

σ_p (R) returnerer rader i R som tilfredsstiller predikatet p. π_attr_list (R) returnerer den projeksjonen av R på de gitte attributtene, med duplikater fjernet (siden RA jobber med mengder).

Spørsmål 17 · Middels · Project og duplikater

Tabellen instructor har 12 rader. Du beregner π_{dept_name}(instructor) der det finnes 6 distinkte avdelinger. Hvor mange rader får du?

RA-projeksjon fjerner duplikater. SQL SELECT dept_name FROM instructor ville derimot returnert 12 rader (multimengde) — du må eksplisitt skrive DISTINCT for samme oppførsel som π.

Spørsmål 18 · Vanskelig · Self-join uten ρ

Hvorfor må vi bruke ρ (rename) når vi vil sammenligne to rader i samme relasjon med hverandre — f.eks. «finn alle ansatte som tjener mer enn ansatt nr. 12121»?

Når en relasjon brukes to ganger i samme uttrykk, må vi navngi forekomstene ulikt. ρ_i(instructor) × ρ_w(instructor) gir oss i.salary og w.salary som distinkte kolonner. SQL-aliaset FROM instructor i, instructor w er det praktiske motstykket.

Spørsmål 19 · Middels · Kardinalitet av ×

|R| = 100 og |S| = 50. Hva er |R × S|, og hva blir kardinaliteten typisk redusert til etter σ_{R.id = S.id}(R × S) hvis matchen er 1-til-1?

|R × S| = |R| · |S|. Inner join gir maks |R|+|S|, og opptil min(|R|,|S|) ved 1-til-1. Dette er motivasjonen for at optimalisatoren aldri faktisk materialiserer det fullstendige kartesiske produktet — den evaluerer joinen direkte.

Spørsmål 20 · Vanskelig · Set difference

Hvilket av disse RA-uttrykkene gir «ansatte som ikke underviser noe emne» (anti-join)?

Set difference krever at begge sidene har samme skjema. Vi projiserer på id i begge for å få sammenlignbare relasjoner, og tar differansen. Direkte instructor − teaches ville krevd at de to relasjonene hadde identisk skjema, noe de ikke har.

Spørsmål 21 · Vanskelig · Theta-join

Hvilket uttrykk finner alle par av (instruktør, kurs) der instruktørens lønn er mindre enn kursets honorar?

Theta-join lar predikatet være vilkårlig — ikke bare likhet. Natural join begrenser til equijoin på likt-navngitte attributter. Generelt: R ⋈_θ S = σ_θ(R × S).

Spørsmål 22 · Veldig vanskelig · «For alle»-spørring

Hvordan uttrykker du i RA «studenter som har tatt alle emner i CS-avdelingen», når RA ikke har en forall-kvantor som primitiv?

Trikset er dobbel negasjon: «studenter for hvem det ikke finnes et CS-emne de ikke har tatt». I SQL skrives det med NOT EXISTS NOT EXISTS. Divisjonsoperatoren ÷ er en avledet operator nettopp for dette mønsteret. RA er like uttrykksfullt som førsteordens predikatlogikk — bare uten ferdig forall-syntaks.

Spørsmål 23 · Middels · γ aggregering

Hva betyr _{dept_name}γ_avg(salary)(instructor) i RA?

Notasjonen er _{grupperingsattributter}γ_{aggregatfunksjoner}. Dette tilsvarer SQL: SELECT dept_name, AVG(salary) FROM instructor GROUP BY dept_name.

Spørsmål 24 · Lett · ρ rename

Hva oppnår ρ_{employee(eid, ename, dept, lønn)}(instructor)?

ρ kan både gi nytt relasjonsnavn og navngi attributter om. Brukes blant annet for å gjøre union-kompatible relasjoner like, og for å skille forekomster i self-join.

Spørsmål 25 · Vanskelig · NULL i aggregat

Tabellen instructor(id, name, salary) har 5 rader, der 2 har NULL i salary. Hva returnerer SUM(salary) og COUNT(*)?

Aggregatfunksjoner unntatt COUNT(*) ignorerer NULL. COUNT(salary) ville derimot returnert 3 (hopper over NULL). Hvis ALLE verdier er NULL, returnerer SUM/AVG/MIN/MAX → NULL (ikke 0).

Spørsmål 26 · Middels · Tre integriteter

Hvilken type integritet brytes hvis man setter inn en rad med dept_name = 'Foo' i instructor, mens 'Foo' ikke finnes i department?

Entitetsintegritet = ingen NULL i PK. Domeneintegritet = verdier hører til kolonnens domene (type/CHECK). Referansiell integritet = FK-verdier må matche en eksisterende rad i refererte tabell — dette er det som brytes her.

Spørsmål 27 · Vanskelig · Composite candidate keys

En tabell Booking(rom, dato, time, brukerId) brukes for å reservere møterom. Hvilken er den naturlige minimale kandidatnøkkelen, og hvorfor ikke bare {brukerId}?

Kandidatnøkkelen følger forretningsregelen: «hva identifiserer en reservasjon entydig?». Det er kombinasjonen rom+dato+time. Composite keys kan være tre eller flere attributter — det er fullt lovlig så lenge de er minimale.

Spørsmål 28 · Veldig vanskelig · Optimization-ekvivalens

Optimalisatoren skal omforme π_name(σ_{salary>100000}(instructor ⋈ department)) til en billigere ekvivalent. Hvilken er faktisk ekvivalent?

«Push selection past join» er en sentral optimaliseringsregel: når predikatet bare nevner attributter fra én side av joinen, kan det evalueres før joinen — det reduserer størrelsen på relasjonen som skal joinres. NB: gjelder ikke ubetinget for outer joins der NULL kan endre semantikken.

Spørsmål 29 · Middels · Ekvivalente RA-uttrykk

Hvilke to uttrykk er ekvivalente?

Theta-join er definert som kartesisk produkt etterfulgt av seleksjon. Det er nettopp denne ekvivalensen som lar optimalisatoren omformulere mellom dem etter behov.

Spørsmål 30 · Veldig vanskelig · Fundamentale operatorer

RA har seks fundamentale operatorer. Resten (join, intersection, divisjon, ...) er avledede. Hvilken liste er nøyaktig de seks fundamentale?

De seks fundamentale: select (σ), project (π), kartesisk produkt (×), union (∪), differanse (−), rename (ρ). Avledet: join (= σ etter ×), intersection (= R−(R−S)), divisjon (= dobbel project + difference), aggregering γ (utvidelse, ikke i den fundamentale algebraen). Hvis du fjerner én av de seks, mister du uttrykksfullhet.

Klar for kapittel 3?

Når disse 30 sitter, er du klar for SQL — som tar hele algebraen og kler den i syntaks. Gå videre til kapittel 3.