Åpne hovedmenyen

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

HistorieRediger

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.

IntroduksjonRediger

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.

OperasjonerRediger

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 tuplerKartesiske produkter og forskjellige «joiner»
  4. Operasjoner som ikke forandrer tuplene i relasjonene, men f.eks. endrer navn på attributter

Grunnleggende mengdeoperasjonerRediger

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 RS.

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

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 RS eller R   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.

EksempelRediger

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

ProjeksjonRediger

Projeksjonsoperatoren brukt på en relasjon R vil frembringe en ny relasjon som bare har enkelte av attributtene til R. En projeksjon skrives  , der   er en mengde attributtnavn og R er en relasjon.

EksempelRediger

R:
A B C
1 2 3
4 5 6
 :
A B
1 2
4 5
 :
A
1
4

Gjør man projeksjonen   vil bare kolonnene A og B fra R komme med i den nye relasjonen. Med projeksjonen   vil bare kolonne A fra R beholdes.

SeleksjonRediger

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  , der C er betingelsen og R en relasjon.

EksempelRediger

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

Gjør man seleksjonen   vil alle tupler som ikke har verdien 1 for attributtet A forsvinne. Med seleksjonen   vil alle tupler som ikke har en verdi større enn 6 for attributtet C forsvinne.

Kartesisk produktRediger

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  . 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.

EksempelRediger

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
 :
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

OmnavningRediger

Man kan ofte ønske å gi relasjoner eller attributter nye navn. Vil man gi relasjonen R det nye navnet S skrives dette  , der   er attributtnavnene i den nye relasjonen S.

EksempelRediger

R:
A B C
1 2 3
4 5 6
 :
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.

JoinerRediger

En join er en spesiell form for produkt der relasjoner pares på bestemte måter.

I en naturlig join mellom relasjonene R og S pares tuplene i de to relasjonene på de attributtene de har felles. Dette skrives  . Tupler som ikke matcher tupler i den andre relasjonen på ett eller flere felles attributter blir ikke med i den nye relasjonen.

En Theta-join mellom to relasjoner R og S fungerer som en naturlig join, med det unntak at tupler pares på en bestemt betingelse, kalt θ. Dette skrives  .

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

EksempelRediger

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
 :
A B C D F G
1 2 3 4 2 3
7 8 9 0 8 9

Tar man en naturlig join 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
 :
A B C D E F G
1 2 3 4 1 2 3
7 8 9 0 7 8 9

En theta-join 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.


LitteraturRediger

  • 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)