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:

De vanlige mengdeoperandene – union, snitt og differens
Operasjoner som fjerner deler av en relasjon – projeksjon og seleksjon
Operasjoner som kombinerer tupler – Kartesiske produkter og forskjellige «joiner»
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 
  
    
      
        ∖
      
    
    {\displaystyle \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

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


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


==== Eksempel ====
Gjør man projeksjonen 
  
    
      
        
          π
          
            A
            ,
            B
          
        
        (
        R
        )
      
    
    {\displaystyle \pi _{A,B}(R)}
   vil bare kolonnene A og B fra R komme med i den nye relasjonen. Med projeksjonen 
  
    
      
        
          π
          
            A
          
        
        (
        R
        )
      
    
    {\displaystyle \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 
  
    
      
        
          σ
          
            C
          
        
        (
        R
        )
      
    
    {\displaystyle \sigma _{C}(R)}
  , der C er betingelsen og R en relasjon. 


==== Eksempel ====
Gjør man seleksjonen 
  
    
      
        
          σ
          
            A
            =
            1
          
        
        (
        R
        )
      
    
    {\displaystyle \sigma _{A=1}(R)}
   vil alle tupler som ikke har verdien 1 for attributtet A forsvinne. Med seleksjonen 
  
    
      
        
          σ
          
            C
            >
            6
          
        
        (
        R
        )
      
    
    {\displaystyle \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
        ×
        S
      
    
    {\displaystyle 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 ====


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


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


=== 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 
  
    
      
        R
        ▹
        
        
        ◃
        
        S
      
    
    {\displaystyle 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-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 
  
    
      
        R
        ▹
        
        
        ◃
        
          
          
            
              θ
            
          
        
        S
      
    
    {\displaystyle R\triangleright \!\!\triangleleft \,_{\mathrm {\theta } }S}
  .
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.


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

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.


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