Relasjonsalgebra

Relasjonsalgebra er et formelt matematisk språk brukt til å beskrive matematiske relasjoner og til å konstruere nye relasjoner mellom relasjonene. Relasjonsalgebra er en type predikatlogikk.

Historie

Relasjonsalgebra ble først beskrevet av Edgar F. Codd i 1970, som et modelleringsspråk for hans relasjonsmodell for data. Dette språket var ment å være en basis for databasers spørrespråk. Senere databaseadministrasjonssystemer har brukt språk som i større eller mindre grad har vært bygget på Codds idéer, med enkelte tillegg. Språket SQL er delvis basert på relasjonsalgebraen.

Introduksjon

Som annen algebra er relasjonsalgebra basert på atomiske operander og på operatorer.

I relasjonsalgebraen er de atomiske operandene enten variable, som betegner relasjoner, eller konstanter, som er endelige relasjoner. I klassisk relasjonsalgebra er alle operander mengder, det samme vil da gjelde resultatene av relasjonsalgebraiske uttrykk.

Operasjoner

Det finnes fire hovedgrupper operasjoner:

1. De vanlige mengdeoperandene – union, snitt og differens
2. Operasjoner som fjerner deler av en relasjon – projeksjon og seleksjon
3. Operasjoner som kombinerer tupler – Kartesiske produkter og forskjellige skjøter (joins)
4. Operasjoner som ikke forandrer tuplene i relasjonene, men f.eks. endrer navn på attributter

Grunnleggende mengdeoperasjoner

De tre grunnleggende operasjonene i mengdelæren gjelder også i relasjonsalgebraen.

Unionen av relasjonene R og S er mengden elementer som finnes i R eller i S eller i begge. Et element som finnes i begge relasjonene vil bare finnes én gang i unionen av relasjonene. Notasjonen for en union mellom R og S er R ∪ S.

Snittet av relasjonene R og S er mengden elementer som finnes i både R og S. Notasjonen for dette er R ∩ S.

Differansen mellom relasjonene R og S er mengden elementer som er i R men ikke i S. Det finnes to måter å skrive dette på, enten R − S eller R $\setminus$ S.

For at disse tre operasjonene skal være gyldige må R og S har identiske attributter. Domenene til attributtene må også være like.

Eksempel

Har man de to relasjonene R og S

R: A B C 1 2 3 4 5 6

S: A B C 7 8 9 4 5 6

vil unionen, snittet og differansen bli som følger:

R ∪ S: A B C 7 8 9 4 5 6 1 2 3

R ∩ S: A B C 4 5 6

R \ S: A B C 1 2 3

Projeksjon

Projeksjonsoperatoren brukt på en relasjon R vil frembringe en ny relasjon som bare har enkelte av attributtene til R. En projeksjon skrives $\pi _{a_{1},...,a_{n}}(R)$, der $a_{1},...,a_{n}$ er en mengde attributtnavn og R er en relasjon.

Eksempel

R: A B C 1 2 3 4 5 6

$\pi _{A,B}(R)$: A B 1 2 4 5

$\pi _{A}(R)$: A 1 4

Gjør man projeksjonen $\pi _{A,B}(R)$ vil bare kolonnene A og B fra R komme med i den nye relasjonen. Med projeksjonen $\pi _{A}(R)$ vil bare kolonne A fra R beholdes.

Seleksjon

Seleksjonsoperatoren brukt på en relasjon R gir en ny relasjon som har en undermengde tuplene i R. Tuplene som blir med er de som tilfredsstiller en betingelse C som går på attributter i R. Seleksjon skrives $\sigma _{C}(R)$, der C er betingelsen og R en relasjon.

Eksempel

R: A B C 1 2 4 4 6 7 1 6 7 8 6 1

$\sigma _{A=1}(R)$: A B C 1 2 4 1 6 7

$\sigma _{C>6}(R)$: A B C 4 6 7 1 6 7

Gjør man seleksjonen $\sigma _{A=1}(R)$ vil alle tupler som ikke har verdien 1 for attributtet A forsvinne. Med seleksjonen $\sigma _{C>6}(R)$ vil alle tupler som ikke har en verdi større enn 6 for attributtet C forsvinne.

Kartesisk produkt

Det kartesiske produktet (også kalt kryssprodukt) av de to relasjonene R og S er mengden par som skapes ved å pare alle elementer i R med alle elementene i S. Dette skrives $R\times S$. Da elementene i R og S er tupler vil resultatet av å pare et tuppel fra R med et tuppel fra S bli et tuppel med en lengde som er lik summen av lengden på tuplene i R og i S. Komponentene i dette nye tuplet vil være komponentene i de to opprinnelige tuplene.

Eksempel

R: A B C D 1 2 3 4 4 5 6 7 7 8 9 0

S: E F G 1 2 3 7 8 9

$R\times S$: A B C D E F G 1 2 3 4 1 2 3 4 5 6 7 1 2 3 7 8 9 0 1 2 3 1 2 3 4 7 8 9 4 5 6 7 7 8 9 7 8 9 0 7 8 9

Omnavning

Man kan ofte ønske å gi relasjoner eller attributter nye navn. Vil man gi relasjonen R det nye navnet S skrives dette $\rho _{S(A_{1},...,A_{n})}(R)$, der $A_{1},...,A_{n}$ er attributtnavnene i den nye relasjonen S.

Eksempel

R: A B C 1 2 3 4 5 6

$\rho _{S(D,E,F)}(R)$: D E F 1 2 3 4 5 6

Her har relasjonen fått det nye navnet S, samtidig som attributtene har fått nye navn. Verdiene i tuplene har ikke blitt endret.

Skjøter

En skjøt (engelsk: join) er en spesiell form for produkt der relasjoner pares på bestemte måter.

I en naturlig skjøt mellom relasjonene R og S pares tuplene i de to relasjonene på de attributtene de har felles. Dette skrives $R\triangleright \!\!\triangleleft \,S$. Tupler som ikke matcher tupler i den andre relasjonen på ett eller flere felles attributter blir ikke med i den nye relasjonen.

En theta-skjøt mellom to relasjoner R og S fungerer som en naturlig skjøt, med det unntak at tupler pares på en bestemt betingelse, kalt theta (θ). Dette skrives $R\triangleright \!\!\triangleleft \,_{\mathrm {\theta } }S$.

En ytre skjøt (outer join) er en skjøt der tupler som ikke overholder kravet i skjøten likevel blir med i produktet. En ytre skjøt på relasjonene R og S gjøres ved å gjøre en skjøt mellom de to relasjonene, deretter legges de mistede tuplene inn igjen med en nullverdi i attributtene de mangler.

Eksempel

R: A B C D 1 2 3 4 4 5 6 7 7 8 9 0

S: A F G 1 2 3 7 8 9

$R\triangleright \!\!\triangleleft \,S$: A B C D F G 1 2 3 4 2 3 7 8 9 0 8 9

Tar man en naturlig skjøt på relasjonene R og S vil resultatet bli en ny relasjon der tuplene er matchet på felles attributter. I dette eksempelet vil tupler som har samme verdi for attributtet A bli paret.

R: A B C D 1 2 3 4 4 5 6 7 7 8 9 0

S: E F G 1 2 3 7 8 9

R x S: A B C D E F G 1 2 3 4 1 2 3 4 5 6 7 1 2 3 7 8 9 0 1 2 3 1 2 3 4 7 8 9 4 5 6 7 7 8 9 7 8 9 0 7 8 9

$R\triangleright \!\!\triangleleft \,_{\mathrm {A=E} }S$: A B C D E F G 1 2 3 4 1 2 3 7 8 9 0 7 8 9

En theta-skjøt mellom to relasjoner vil først føre med seg et kryssprodukt av relasjonene. Deretter fjernes alle tupler som ikke overholder betingelsen(e). Betingelsen i dette eksempelet er at tuplene må ha samme verdi for attributtene A og E.

Litteratur

• Codd, Edgar F. : «A Relational Model of Data for Large Shared Data Banks» i «Communications of the ACM» 6/13/1970, s. 377–387. (PDF-versjon, 1,4 MB)

Autoritetsdata