Relasjonsalgebra

SQL er overflaten — algebraen er fundamentet

Når du skriver en SQL-spørring, parser DBMS-en den til et relasjons­algebra-tre. Optimalisatoren manipulerer dette treet: bytter rekkefølge på operatorer, presser σ ned mot tabellene, velger join-algoritmer. Skal du forstå hvorfor en spørring er treg eller rask, må du forstå algebraen.

Algebraen har fire egenskaper som gjør den nyttig:

• Lukket — input og output er begge relasjoner. Operasjoner kan komponeres som funksjoner: πname(σdept='Physics'(instructor)).
• Funksjonell — ingen sideeffekter. Samme input gir samme output.
• Algebraiske lover — σp(R ⋈ S) = σp(R) ⋈ S hvis p bare nevner attributter i R. Slike lover er det optimalisatoren utnytter.
• Komplett nok — alle SQL-spørringer (utenom aggregat og null-håndtering) kan oversettes til en relasjons­algebra-uttrykk.

Seks fundamentale, tre avledede

De seks fundamentale operasjonene utgjør et fullt språk. De resterende kan defineres ved hjelp av disse — men brukes så ofte at de regnes som førsteklasses.

Fundamentale

Avledede (utledes fra de fundamentale)

Hver operator har et input-skjema, et output-skjema og en presis semantikk. Vi går gjennom dem en for en med samme lille datasett, og avslutter med en interaktiv «bygg en spørring»-runner.

Filtrer rader: σ_p(R)

Notasjon: σp(R) — beholder de tuplene t ∈ R der predikatet p(t) er TRUE.

Predikat kan bygges av sammenligninger (=, ≠, <, ≤, >, ≥), konnektiver (∧, ∨, ¬), og kan referere til to attributter (σdept_name = building(department)) — ikke bare attributt mot konstant.

Output-skjema: uendret — Select fjerner aldri kolonner.

Eksempel — instruktører i Physics

Spørring: σdept_name = "Physics"(instructor)

Sammensatt predikat: σdept_name = "Physics" ∧ salary > 90000(instructor) gir bare Einstein.

Velg ut kolonner: π_L(R)

Notasjon: πA1, A2, …(R) — beholder bare de listede attributtene.

Output-skjema: bare attributtene i L.

Duplikater: fjernes — fordi resultatet er en mengde. Dette er en av de viktigste kildene til ulikhet mellom relasjons­algebra og SQL (bag-semantikk).

Eksempel — bare ID, navn og lønn

Spørring: πID, name, salary(instructor)

Når dukker duplikater opp?

Tabellen instructor har flere rader i samme avdeling. πdept_name(instructor) gir én rad per avdeling — ikke én per instruktør:

Sett alt mot alt: R × S

Notasjon: R × S — alle kombinasjoner av tupler. Hvis |R| = m og |S| = n, har resultatet m · n tupler.

Output-skjema: sammenstilling av begge skjemaene. Hvis et attributtnavn finnes i begge, prefikses det med relasjonsnavn (instructor.ID, teaches.ID).

Mini-eksempel

La A = {1, 2} og B = {x, y} (én attributt hver). Da er:

Kartesisk produkt alene gir nesten aldri det du vil — det blir veldig stort, og kobler ting som ikke har med hverandre å gjøre. Men kombinert med σ får vi join:

σinstructor.ID = teaches.ID(instructor × teaches)
   ≡   instructor ⋈instructor.ID = teaches.ID teaches

Algebraen utleder altså join fra to mer fundamentale operasjoner.

Sett tabeller sammen langs en betingelse

Det finnes flere join-varianter. De skiller seg bare i hvilket predikat som brukes — alle bygger ovenpå × og σ.

Theta-join

R ⋈θ S = σθ(R × S). θ er et vilkårlig predikat — kan inneholde <, >, ulikhet, sammensatte uttrykk.

Equijoin

Theta-join der predikatet kun bruker likhet: R ⋈R.A = S.B S. Den vanligste varianten.

Natural join

Notasjon: R ⋈ S (uten subskript). Match på alle attributter med samme navn, og slå sammen til én kolonne i resultatet.

For instructor(ID, name, dept_name, salary) og department(dept_name, building, budget) er det bare dept_name som er felles. Da:

instructor ⋈ department = σinstructor.dept_name = department.dept_name(instructor × department) — men med én dept_name-kolonne i resultatet, ikke to.

Outer joins — ikke kast bort «taperne»

I en vanlig (inner) join faller tupler uten match bort. Outer join bevarer dem ved å fylle inn NULL for de manglende attributtene.

• Left outer ⟕ — bevarer alle rader i venstre tabell.
• Right outer ⟖ — bevarer alle rader i høyre tabell.
• Full outer ⟗ — bevarer alle på begge sider.

Eksempel: instructor ⟕ teaches beholder også instruktører som ikke underviser noen kurs:

Mengde­operatorer — krever skjema-kompatibilitet

For at R ∪ S, R ∩ S eller R − S skal gi mening, må R og S være kompatible:

• Samme antall attributter (samme aritet).
• Samme type på den i-te attributten i begge.

Det er posisjon som teller, ikke navn — derfor må man ofte projisere først for å justere skjemaene.

Eksempel — kurs gitt i begge semestre

πcourse_id(σsemester="Fall" ∧ year=2017(section))
  ∩
πcourse_id(σsemester="Spring" ∧ year=2018(section))

Resultatet er kurser som ble undervist i begge perioder.

Gi navn til mellomresultater

Notasjon:

• ρx(E) — gir resultatet av uttrykk E navnet x.
• ρx(A1, A2, …)(E) — i tillegg gis attributtene nye navn.

Hvorfor trenger man dette? Fordi resultatet av en algebra-operasjon ikke har noe navn, og noen spørringer trenger å bruke samme relasjon to ganger.

Eksempel — instruktører som tjener mer enn instruktør 12121

πi.ID, i.name(σi.salary > w.salary(
   ρi(instructor) × σw.ID = 12121(ρw(instructor))
))

Vi navngir to «kopier» av instructor som i og w, slik at vi kan referere til i.salary og w.salary uten tvetydighet.

«Alle som …»-spørringer

Notasjon: R ÷ S — gitt at S's skjema er en delmengde av R's.

Semantikk: Resultatet er de t-verdiene fra R (over attributter ikke i S) der t kombinert med hver rad i S finnes i R.

Klassisk eksempel: «Finn alle studenter som har tatt alle CS-kurs.»

Konkret eksempel

La tatt(student, kurs) og påkrevd(kurs). Vi vil ha studenter som har tatt hvert kurs i påkrevd.

Cara har tatt CS-101 men ikke CS-102, så hun mangler en av de påkrevde — fjernes. Anna har tatt begge (pluss MA-100, som ikke disqualifiserer henne). Bo har tatt akkurat de to.

Avledning fra fundamentale operatorer

R ÷ S = πR−S(R) − πR−S((πR−S(R) × S) − R)

Tankegangen: «Alle kandidater» minus «de kandidatene som mangler en kombinasjon». Den siste står igjen som «alle som ikke mangler noen» = «alle som har alle».

I SQL — det dobbelte NOT EXISTS-trikset

SELECT DISTINCT t.student
FROM tatt t
WHERE NOT EXISTS (
  SELECT * FROM påkrevd p
  WHERE NOT EXISTS (
    SELECT * FROM tatt u
    WHERE u.student = t.student AND u.kurs = p.kurs
  )
);

«Det finnes ikke noe påkrevd kurs som ikke finnes blant studentens egne tatt-rader.» Skummelt å lese, men direkte oversettelse av division.

Bygg uttrykk og skriv dem om

Siden hver operator gir en relasjon ut, kan de stables. «Finn navnene på alle Physics-instruktører som underviser CS-101» kan skrives som:

πname(
  σdept_name="Physics"(instructor)
   ⋈instructor.ID = teaches.ID
  σcourse_id="CS-101"(teaches)
)

Ekvivalente uttrykk

Det finnes flere måter å skrive samme spørring på. Optimalisatoren bruker ekvivalens­regler for å finne en billigere form. To eksempler:

σdept="Physics"(instructor ⋈ teaches)
   ≡   (σdept="Physics"(instructor)) ⋈ teaches

πA,B(R ⋈ S)
   ≡   (πA, joinattr(R)) ⋈ (πB, joinattr(S))

Den første («push selection past join») reduserer størrelsen før den dyre joinen. Den andre («push projection past join») kutter unødige kolonner tidlig. Begge gjør joinen billigere uten å endre resultatet.

Interaktiv runner

Velg en operator-knapp under og se hvilke rader/kolonner som blir igjen. Bygges trinn for trinn på samme datasett. Reset nullstiller.

Du bør nå kunne …

• … liste de seks fundamentale operatorene og forklare semantikken til hver.
• … oversette en SQL-spørring uten aggregat til relasjons­algebra og motsatt.
• … skille natural join, theta-join og outer joins, og kjenne SQL-motstykkene.
• … skrive en division-spørring og vite hvorfor den er triks å skrive i SQL.
• … argumentere for hvorfor algebraen er nyttig: optimalisatoren manipulerer den.