Relasjonsalgebra

Fra Wikipedia, den frie encyklopedi

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

Innhold 1 Historie 2 Introduksjon 3 Operasjoner 3.1 Grunnleggende mengdeoperasjoner 3.1.1 Eksempel 3.2 Projeksjon 3.2.1 Eksempel 3.3 Seleksjon 3.3.1 Eksempel 3.4 Kartesisk produkt 3.4.1 Eksempel 3.5 Omnavning 3.5.1 Eksempel 3.6 Joiner 3.6.1 Eksempel 4 Litteratur

[rediger] 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 databasehåndteringssystemer 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.

[rediger] Introduksjon

Som annen algebra er relasjonsalgebra basert på atomiske operanderer 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.

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

[rediger] 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 S.

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

[rediger] 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

[rediger] Projeksjon

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

[rediger] Eksempel

R: A B C 1 2 3 4 5 6

πA,B(R): A B 1 2 4 5

πA(R): A 1 4

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

[rediger] 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 σ_C(R), der C er betingelsen og R en relasjon.

[rediger] Eksempel

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

σA = 1(R): A B C 1 2 4 1 6 7

σC > 6(R): A B C 4 6 7 1 6 7

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

[rediger] 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 . 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.

[rediger] 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

: 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

[rediger] Omnavning

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

[rediger] Eksempel

R: A B C 1 2 3 4 5 6

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

[rediger] Joiner

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 Outerjoin er en join der tupler som ikke overholder kravet i joinen likevel blir med i produktet. En outerjoin 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 i mangler.

[rediger] 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

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

[rediger] 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)