relasjonsalgebra – Store norske leksikon

Relasjonsalgebra er en definert samling operasjoner for å manipulere data i relasjonsmodellen. Operasjonene utføres på relasjoner (tabeller), og resultatet av en slik operasjon er også en relasjon.

Faktaboks

Også kjent som: engelsk: relational algebra

Operasjoner som utføres i relasjonsdatabaser beskrevet i høynivåspråk som SQL og QBE (Query by Example) blir normalt oversatt til en sekvens av relasjonsalgebraoperasjoner. En relasjonsalgebra kan betraktes som instruksjonsettet til en database- eller søkemotor.

Relasjonsalgebraer egner seg godt for utførelse på parallellmaskiner, og de kan også brukes for å kommunisere databaseoperasjoner mellom for eksempel klient og databaseserver.

Relasjonsalgebra ble definert av Edgar Frank Codd tidlig på 1970-tallet.

De enkelte relasjonsalgebraoperasjoner

Oversikt

Alle algebraoperasjoner, unntatt divisjon, finnes igjen i databasespråket SQL ved sine engelske navn. Hver enkelt operasjon kan uttrykkes i et tegnspråk som gjør at en kan skrive sammensatte uttrykk på en kompakt måte.

\(A\) og \(B\) er operandtabeller, \(R\) er resultattabell.

Betegnelse	Funksjon	Oppgave	Engelsk
Seleksjon	\(R=\sigma _P A\)	Velg ut rader som oppfyller en gitt betingelse \(P\)	selection
Projeksjon	\(R=\pi _L A\)	Velg ut kolonner etter en gitt liste over kolonnenavn \(L\). Hvis det forekommer like rader i resultatet, blir de redusert til én rad (duplikatfjerning)	projection
Union	\(R = A \cup B \)	En ny tabell dannes ved å slå sammen to tabeller. \(A\) og \(B\) må ha de samme attributter og samme nøkkelattributter	union
Snitt	\(R = A \cap B\)	En ny tabell dannes ved snittet av to tabeller, altså innhold som finnes i begge. Det vil si at like rader i de to tabellene går inn i resultatet. \(A\) og \(B\) må ha de samme attributter og samme nøkkelattributter	intersection
Differanse	\(R = A - B\)	Rader i \(A\) som ikke finnes i \(B\) inngår i resultatet. \(A\) og \(B\) må ha de samme attributter og samme nøkkelattributter	difference
Naturlig forening	\( R = A * B \)	\(A\) og \(B\) må ha minst en attributt \(f\)med samme navn (og datatype). For alle kombinasjoner der \(A.f = B.f\) dannes det en resultatrad i \(R\) som settes sammen av \(f\) og de andre attributtene i de to radene. \(f\) er foreningsattributter.	natural join
Forening	\(R = A \bowtie_{C} B\)	Som naturlig forening, men hvilke attributter i \(A\) og \(B\) som skal ha samme verdi er gitt i betingelsen \(C\). Kalles også likhetsforening.	join, equijoin
Generell forening	\(R = A \bowtie_{\theta} B\)	Som naturlig forening, men sammenkoplingsbetingelse \( \theta\) er en generell betingelse mellom attributter i \(A\) og \(B\). Generell forening er skilt ut av to grunner: Den er mye mindre brukt enn vanlig likhetsforening, og den er mer krevende å utføre i praksis.
Kryssprodukt	\(R = A \times B\)	\(R\) inneholder alle kombinasjoner av \(A\) og \(B\). Antall poster i \(R\) blir altså antall poster i \(A\) multiplisert med antall poster i \(B\), \(\|R\| = \|A\|*\|B\|\). Antall rader i en tabell er uttrykt ved \(\|T\|\). De to vertikale strekene er det matematiske tegnet for tallverdi. Kryssprodukt kalles også kartesisk produkt	cross product
Divisjon	\(R = A \div B\) eller \(R = A / B\)	\(A\) har to attributtgrupper \(a,b\). \(B\) har én attributtgruppe \(b\). \(R\) inneholder én attributt eller attributtgruppe, \(a\). En \(a\)-attributt \(a_{j}\) skrives i \(R\) hvis det finnes \(<a_j,b>\)-par for alle \(b\) i \(B\). Litt upresist kan en si at \(R\) inneholder alle \(a\)-verdier med komplette sett for \(b\)-verdiene.	division

Eksempel på sammensatt algebraoperasjon

\(R=\pi_{a1,b3}(\sigma_{a2='Kari'}A*S*\sigma_{b2\ge 7000 \wedge b2 < 7050}B)\). \(A\), \(B\) og \(S\) er tabeller. Seleksjon og projeksjon har høyere prioritet enn forening. For å gjøre projeksjonen til slutt, er projeksjonens operand satt i parentes.

Analyse av operasjonene

Nedenfor følger en analyse av operasjonene med tanke på realisering. Databaser kan inneholde store datamengder, derfor er det også interessant å vurdere realisering på parallellmaskiner.

Seleksjon krever en gjennomgang av alle rader hvis det ikke er indekser til minst en av attributtene som inngår i seleksjonsuttrykket \(P\).

Projeksjon krever at \(R\) skrives. \(R\) har mindre datavolum enn enn \(A\) da minst én kolonne (attributt) blir projisert bort. Hvis minst én nøkkelattributt blir projisert bort blir operasjonen mer omfattende. Da kan duplikater oppstå, og duplikater skal fjernes. Det betyr at en må undersøke om det er like poster i hele tabellen.

Også i union må en kontrollere om det finnes duplikater som skal fjernes.

I snitt er det nettopp duplikater som skal tas vare på.

Differanse er temmelig lik snitt da like poster utelukkes fra resultattabellen.

For alle typer likhetsforening skal en finne poster som har samme verdi på foreningsnøkkelen, en gruppe attributter i den ene tabellen skal være lik en tilsvarende gruppe attributter i den andre tabellen.

For divisjon skal vi gruppere postene på likhet i \(A\) sin førsteattributt som også kan være en gruppe attributter.

Felles operasjon for alle relasjonsalgebraoperasjoner unntatt seleksjon og generell forening, er å finne poster eller rader som har samme verdi på attributter eller et sett attributter.

Hashing er en effektiv metode for å finne objekter som har samme verdi på et attributt eller en gruppe attributter. Hashing er også en metodegruppe som egner seg godt for parallellisering.

Les mer i Store norske leksikon

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

Du må være logget inn for å kommentere.

Fagansvarlig for Databaseteknologi

Tore Mallaug

Universitetslektor, NTNU – Norges teknisk-naturvitenskapelige universitet