Relacijska algebra

Skoči na: navigacija, iskanje

Relacijska algebra je množica operacij nad relacijami, definiranimi z relacijskim podatkovnim modelom. Zaradi algebraičnih lastnosti teh operacij se le-te pogosto uporabljajo pri optimizaciji poizvedb v podatkovnih bazah.

• Relacijska algebra in relacijski račun sta formalna jezika povezana z relacijskim modelom
• Neformalno je relacijska algebra visoko-nivojski postopkovni jezik, relacijski račun pa nepostopkovni ali deklarativni jezik
• Formalno sta ekvivalentna
• Vsak jezik, s katerim lahko pridobimo relacije, ki jih je moč pridobiti z relacijskim računom, je relacijsko popoln (relationally complete)
• Operacije relacijske algebre se izvedejo na eni ali več relacij, z namenom, da bi pridobili novo relacijo. Pri tem se osnovna relacija ne spremeni
• Tako operandi kot tudi rezultat so relacije -> izhod ene operacije je lahko vhod v drugo
• Omogoča gnezdenje izrazov – tako kot velja za aritmetične izraze. Tej lastnosti jezika pravimo zaprtje (closure)

Vsebina 1 Osnovne operacije 1.1 Selekcija 1.2 Projekcija 1.3 Kartezijski produkt 1.4 Unija 1.5 Razlika 1.6 Preimenovanje 2 Izvedene operacije 2.1 Presek 2.2 Naravni stik 2.3 Količnik 2.4 θ-stik 3 Za tiskanje 4 Povezave

Osnovne operacije

Relacijska algebra definira šest osnovnih operacij. Lastnosti osnovnih operacij so, da lahko z njimi definiramo katero koli drugo operacijo in, da ne moremo nobeno izmed njih izpustiti, brez izgube izrazne moči.

• Selekcija
• Projekcija
• Kartezijski produkt
• Unija
• Razlika
• Preimenovanje

Selekcija

Selekcija je unarni operator, definiran kot σ_F(R), kjer je R relacija, F pa pogoj oblike aθb. a in b sta atributa (ali pa je eden izmed njiju konstanta), θ pa je operator iz množice {<, ≤, =, >, ≥, } (gre torej za primerjavo dveh atributov ali atributa in konstante). Rezultat selekcije so vse n-terice relacije R, za katere je izjava F pravilna (po domače: vse vrstice tabele nad katero delamo selekcijo, za elemente katerih velja pogoj F).

Rezultat selekcije je definiran samo, če so imena atributov, nad katerimi operira, prisotna v glavi relacije, nad katero operira.

Formalni zapis selekcije z relacijskim računom:

Primerjava dveh atributov: σ_aθb(R) = { t^(k): t ∈ R, t[a] θ t[b] }

Primerjava atributa s konstanto: σ_aθv(R) = { t^(k): t ∈ R, t[a] θ v }

Zapis selekcije z SQL stavkom:

SELECT * FROM `R` WHERE a θ b
SELECT * FROM `R` WHERE a θ v

Primer:

P Ime Starost Teža Jože 34 80 Špela 28 64 Janez 29 70 Helena 54 54 Peter 34 80

σStarost≥34(P) Ime Starost Teža Jože 34 80 Helena 54 54 Peter 34 80

σStarost=Teža(P) Ime Starost Teža Helena 54 54

Projekcija

Projekcija je unarni operator, definiran kot π_a1,..,an(R), kjer so a₁,..,a_n is a set of imena atributov. Rezultat projekcije so vse n-terice (vrstice v tabeli), ki pa so sestavljene samo iz komponent, ki pripadajo atributom {a₁,..,a_n} (po domače: iz tabele odrežemo vse stolpce ki niso navedeni pri projekciji).

Rezultat projekcije je definiran samo, če je množica atributov a₁,..,a_n podmnožica atributov relacije R.

Formalni zapis projekcije z relacijskim računom:

π_a1,..,ak(R) = { t^(k): ∃ u (u ∈ R ∧ t[1] = u[a₁] ∧ ... ∧ t[k] = u[a_k]) }

Zapis projekcije z SQL stavkom:

SELECT a1, ... ,ak FROM `R`

Primer:

P Ime Starost Teža Jože 34 80 Špela 28 64 Janez 29 70 Helena 54 54 Peter 34 80

πStarost,Teža(P) Weight 34 80 28 64 29 70 54 54

Pozor: Jože in Peter imata isto starost in težo. Ker je rezultat projekcije relacija, torej množica, se ta kombinacija teže in starosti pojavi samo enkrat.

Kartezijski produkt

Kartezijski produkt se pogosto imenuje tudi križni produkt ali križni stik. Zapišemo ga kot R × S, kjer sta R in S relaciji. Rezultat kartezijskega produkta je množica vseh kombinacij n-teric iz R in S.

Formalni zapis kartezijskega produkta z relacijskim računom:

R × S = { t^(n+m): ∃ u (u &isin R ∧ t[1] = u[1] ∧ ... ∧ t[n] = u[n]) ∧ ∃ v (v &isin S ∧ t[n+1] = v[1] ∧ ... ∧ t[n+m] = v[m])}

Zapis kartezijskega produkta z SQL stavkom:

SELECT * FROM `R`, `S`

Primer:

Zaposleni Ime Id Jože 3415 Špela 2241

O Oddelek Manager Finance Janez Prodaja Anja

Zaposleni × Oddelek Ime Id Oddelek Manager Jože 3415 Finance Janez Jože 3415 Prodaja Anja Špela 2241 Finance Janez Špela 2241 Prodaja Anja

Kartezijski produkt navadno omejimo s selekcijo.

Unija

Unija je binarni operator, definiran enako kot unija nad množicami.

Rezultat unije je definiran samo, če so imena atributov, nad katerimi operira, prisotna v glavi relacije, nad katero operira.

Formalni zapis unije z relacijskim računom:

R ∪ S = { t⁽ⁿ⁾ : t ∈ R ∨ t ∈ S }

Zapis unije z SQL stavkom:

... (SELECT * FROM `R`) UNION (SELECT * FROM `S`) ...

Rezultat je definiran samo ko imata oba operanda isti shemi (ujemata se v istoležečih atributih).

P Ime Id Jože 3415 Špela 2241 Anja 2202

M Ime Id Janez 3401 Anja 2202

P ∪ M Ime Id Jože 3415 Špela 2241 Janez 3401 Anja 2202

Pozor: Anja se pojavi v rezultatu samo enkrat (rezultat je namreč množica).

Razlika

Razlika je binarni operator nad dvema relacijama, ki je definiran enako kot razlika nad množicami.

Rezultat razlike je definiran samo, če so imena atributov, nad katerimi operira, prisotna v glavi relacije, nad katero operira.

Formalni zapis razlike z relacijskim računom:

R - S = { t⁽ⁿ⁾ : t ∈ R ∧ ¬ t ∈ S }

Zapis razlike z SQL stavkom:

... (SELECT * FROM `R`) MINUS (SELECT * FROM `S`) ...

Rezultat je definiran samo ko imata oba operanda isti shemi (ujemata se v istoležečih atributih).

P Ime Id Jože 3415 Špela 2241 Anja 2202

M Ime Id Janez 3401 Anja 2202

P - M Ime Id Jože 3415 Špela 2241

Preimenovanje

Tega operatorja na predavanjih nismo omenili.

Zapis preimenovanja z SQL stavkom:

SELECT a1 AS b1, ... ,ak AS bn FROM `R`

Izvedene operacije

Poleg šestih osnovnih operatorjev poznamo tudi mnoge operatorje, ki jih lahko zapišimo kot kombinacijo osnovnih. Zaradi njihovih zanimivih algebraičnih lastnosti (in boljše preglednosti zapisa) jih pogosto uporabljamo v zapisih operacij.

• Stik
• Presek
• Količnik (razlika)

Presek

Presek je binarni operator nad dvema relacijama, ki je definiran enako kot presek nad množicami.

Rezultat preseka je definiran samo, če so imena atributov, nad katerimi operira, prisotna v glavi relacije, nad katero operira.

Zapis preseka z osnovnimi operacijami:

R ∩ S = R - (R - S)

Formalni zapis preseka z relacijskim računom:

R ∩ S = { t⁽ⁿ⁾ : t ∈ R ∧ t ∈ S }

Zapis preseka z SQL stavkom:

... (SELECT * FROM `R`) INTERSECT (SELECT * FROM `S`) ...

Rezultat je definiran samo ko imata oba operanda isti shemi (ujemata se v istoležečih atributih).

P Ime Id Jože 3415 Špela 2241 Anja 2202

M Ime Id Janez 3401 Anja 2202

P ∩ M Ime Id Anja 2202

Naravni stik

Naravni stik je binarna operacija, zapisana kot: R [X] S, kjer sta R in S relaciji. Rezultat naravnega stika so vse kombinacije n-teric iz R in S, ki se ujemajo v vseh skupnih atributih. Če relaciji R in S nimata skupnih atributov, potem je naravni stik enak kartezijskemu produktu.

Primer:

P Ime Id Oddelek Jože 3415 Finance Špela 2241 Prodaja Janez 3401 Finance Anja 2202 Prodaja

D Oddelek Manager Finance Janez Prodaja Anja Proizvodnja Franci

P [X]  D Ime Id Oddelek Manager Jože 3415 Finance Janez Špela 2241 Prodaja Anja Janez 3401 Finance Janez Anja 2202 Prodaja Anja

Količnik

θ-stik

R F S Stik Theta med relacijama R in S vrne n-terice (vrstice), ki zadoščajo predikatu F kartezijskega produkta R in S Predikat F je oblike R.ai  S.bi, kjer je  aritmetična operacija (<, ≤, =, >, ≥, ).

Theta stik lahko izpeljemo s pomočjo selekcije in kartezijskega produkta: R F S = F(R  S)

Stopnja Theta stika med R in S je seštevek stopenj operandov relacij R in S. Če predikat F vsebuje zgolj enakost (=), gre za stik tipa Equijoin

Za tiskanje

Del članka je na voljo v obliki skripte v pdf formatu.

Povezave

• Relational algebra (en Wikipedia)
• Prosojnice s predavanj (datoteka 06)