Redigerer Relasjonsalgebra

'''Relasjonsalgebra''' er et formelt [[matematikk|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 [[Relasjonsmodellen|relasjonsmodell]] for [[data]]. Dette språket var ment å være en basis for [[database]]rs [[spørrespråk]]. Senere [[Databasehåndteringssystem|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 [[Structured Query Language|SQL]] er delvis basert på relasjonsalgebraen.

==Introduksjon==

Som annen [[algebra]] er relasjonsalgebra basert på atomiske [[operand]]er og på [[operator]]er. 

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

==Operasjoner==

Det finnes fire hovedgrupper operasjoner:
# De vanlige mengdeoperandene &ndash; [[union (matematikk)|union]], [[snitt]] og [[differens]]
# Operasjoner som fjerner deler av en relasjon &ndash; projeksjon og seleksjon
# Operasjoner som kombinerer [[tupel|tupler]] &ndash; [[Kartesisk produkt|Kartesiske produkter]] og forskjellige skjøter (''joins'')
# Operasjoner som ikke forandrer tuplene i relasjonene, men f.eks. endrer navn på attributter

===Grunnleggende mengdeoperasjoner===

De tre grunnleggende operasjonene i [[mengdelære]]n 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'' &cup; ''S''.  

''Snittet'' av relasjonene R og S er mengden elementer som finnes i både R og S. Notasjonen for dette er ''R'' &cap; ''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'' <math>\setminus</math> ''S''.

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

====Eksempel====

Har man de to relasjonene R og S

{| cellpadding="8"
 |- valign="top"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! A || B || C
   |-
   | 7 || 8 || 9
   |-
   | 4 || 5 || 6
   |}
|}

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

{| cellpadding="8"
 |- valign="top"
 |
{| class="wikitable"
 |+ R ∪ S:
 ! A || B || C
 |-
 | 7 || 8 || 9
 |-
 | 4 || 5 || 6
 |-
 | 1 || 2 || 3
 |}
 ||
{| class="wikitable"
 |+ R ∩ S:
 ! A || B || C
 |-
 | 4 || 5 || 6
 |}
 ||
{| class="wikitable"
 |+ 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 <math>\pi_{a_1, ...,a_n}( R )</math>, der <math>a_1,...,a_n</math> er en mengde attributtnavn og R er en relasjon. 

====Eksempel====

{| cellpadding="8"
 |- valign="top"
 |
  {| class="wikitable"
   |+  R:
   ! A || B || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ <math>\pi_{A,B}(R)</math>:
   ! A || B
   |-
   | 1 || 2
   |-
   | 4 || 5
   |}
 ||
  {| class="wikitable"
   |+ <math>\pi_{A}(R)</math>:
   ! A
   |-
   | 1
   |-
   | 4
   |}
 |}

Gjør man projeksjonen <math>\pi_{A,B}( R )</math> vil bare kolonnene A og B fra R komme med i den nye relasjonen. Med projeksjonen <math>\pi_{A}( R )</math> 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 <math>\sigma_{C}(R)</math>, der C er betingelsen og R en relasjon. 

====Eksempel====

{| cellpadding="8"
 |- valign="top"
 |
  {| class="wikitable"
   |+  R:
   ! A || B || C
   |-
   | 1 || 2 || 4
   |-
   | 4 || 6 || 7
   |-
   | 1 || 6 || 7
   |-
   | 8 || 6 || 1
   |}
 ||
  {| class="wikitable"
   |+ <math>\sigma_{A=1}(R)</math>:
   ! A || B || C
   |-
   | 1 || 2 || 4
   |-
   | 1 || 6 || 7
   |}
 ||
  {| class="wikitable"
   |+ <math>\sigma_{C>6}(R)</math>:
   ! A || B || C
   |-
   | 4 || 6 || 7
   |-
   | 1 || 6 || 7
   |}
 |}

Gjør man seleksjonen <math>\sigma_{A=1}(R)</math> vil alle tupler som ikke har verdien 1 for attributtet A forsvinne. Med seleksjonen <math>\sigma_{C>6}(R)</math> 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 <math>R\times S</math>. 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====

{| cellpadding="8"
 |- valign="top"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! E || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |}
 ||
  {| class="wikitable"
   |+ <math>R\times S</math>:
   ! 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 <math>\rho_{S(A_1, ...,A_n)}(R)</math>, der <math>A_1, ...,A_n</math> er attributtnavnene 
i den nye relasjonen S.

====Eksempel====

{| cellpadding="8"
 |- valign="top"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ <math>\rho_{S(D,E,F)}(R)</math>:
   ! 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''<ref>{{Kilde www|url=https://matematikkradet.no/ordliste/|tittel=Matematisk ordliste|besøksdato=2024-09-28|verk=matematikkradet.no}}</ref>) 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 <math> R \triangleright\!\!\triangleleft\, S</math>. Tupler som ikke matcher tupler i den andre relasjonen på ett eller flere felles attributter blir ikke med i den nye relasjonen.

En [[Theta|''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 (&theta;). Dette skrives <math>R \triangleright\!\!\triangleleft\,_{\mathrm{\theta}} S</math>.

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

{| cellpadding="8"
 |- valign="top"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! A || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |}
||
  {| class="wikitable"
   |+ <math> R \triangleright\!\!\triangleleft\, S</math>:
   !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.

{| cellpadding="8"
 |- valign="top"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! E || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |}
 ||
  {| class="wikitable"
   |+ 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
   |}
||
  {| class="wikitable"
   |+ <math>R \triangleright\!\!\triangleleft\,_{\mathrm{A=E}} S</math>:
   ! 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.

== Referanser ==
<references />

==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. ([https://web.archive.org/web/20060512054145/http://web.f4.fhtw-berlin.de/morcinek/unterlagen/codd1970.pdf PDF-versjon, 1,4 MB])

{{Databaser}}
{{Autoritetsdata}}

[[Kategori:Matematisk modellering]]
[[Kategori:Databaser]]