Relačná algebra

Relačná algebra je, v informatike, formálny systém na manipuláciu s reláciami, ktorý sa používa najmä na popis operácií v relačných databázach. Operandami algebry sú relácie, operátormi sú množinové operátory (keďže každá relácia je súčasne aj množinou) a špeciálne relačné operátory, ako selekcia, projekcia alebo join (v doslovnom preklade spojenie).

História

Aj keď isté obdoby relačnej algebry boli známe už skôr, do všeobecného povedomia sa relačná algebra dostala až v roku 1970, keď Edgar Frank Codd prišiel s tzv. relačným modelom organizácie údajov. Codd tiež dokázal tzv. Coddovu vetu, podľa ktorej je relačná algebra ekvivalentná (čo sa popisnej sily týka) relačnému kalkulu, a teda aj predikátovej logike prvého rádu.

Na základe relačnej algebry bolo neskôr vytvorených viacero dotazovacích jazykov. Na jej základe je postavený aj dotazovací jazyk SQL, vyvinutý v roku 1974, ktorý je v súčasnosti jedným z najpoužívanejších jazykov na manipuláciu s databázami.

Operátory

Operátory relačnej algebry sa v zásade delia na dve kategórie: primitívne a odvodené. Primitívne operátory sú analógiou konceptu úplného systému známeho z matematickej logiky, keďže sa z nich dajú odvodiť všetky odvodené operátory. Voľba takejto množiny operátorov nie je jednoznačná, Edgar Frank Codd za primitívne operátory zvolil selekciu, projekciu, karteziánsky súčin, zjednotenie množín, rozdiel množín a premenovanie. Presnejšie, Codd pôvodne premenovanie medzi primitívne operátory nezaradil, ale nevyhnutnosť tohto kroku sa ukázala pri tvorbe dotazovacieho jazyka ISBL.

Šesť primitívnych operátorov teda tvorí akési jadro relačnej algebry. Ostatné operátory síce podstatne uľahčujú prácu, dajú sa však vynechať bez zníženia popisnej sily celého systému.

Množinové operátory

Množinové operátory fungujú v podstate rovnako ako v teórii množín. V relačnej algebre sa však na operandy niektorých množinových operácii kladú špeciálne požiadavky. Predovšetkým, operandy zjednotenia a rozdielu (primitívnych operácií relačnej algebry) množín musia byť kompatibilné, tzn. musia mať rovnakú množinu atribútov. Zjednodušene povedané, ak si reláciu predstavíme ako databázovú tabuľku, nie je možné vykonať zjednotenie dvoch tabuliek v prípade, že majú rôzne hlavičky.

Kompatibilita operandov sa požaduje aj v prípade prieniku, keďže prienik sa, ako odvodený operátor, definuje na základe zjednotenia a rozdielu:

A\cap B=(A\cup B)\setminus ((A\setminus B)\cup (B\setminus A)).

Karteziánsky súčin v relačnej algebre síce sleduje základnú myšlienku z teórie množín, je však definovaný odlišne. Neformálne povedané, klasický karteziánsky súčin by z n-árnej a m-árnej relácie vytvoril množinu dvojíc, kde každá dvojica obsahuje jednu n-ticu a jednu m-ticu. Karteziánsky súčin v relačnej algebre ale z týchto dvoch relácii vytvorí zodpovedajúcu množinu n+m-tíc. Formálne povedané, karteziánsky súčin sa v relačnej algebre definuje nasledovne:

R\times S=\{[x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m}]\ |\ X=(x_{1},\ldots ,x_{n})\in R\ \land \ Y=(y_{1},\ldots ,y_{m})\in S\}.

Projekcia

Projekcia je relačná operácia, ktorá intuitívne zodpovedá výberu stĺpcov z tabuľky (teda sa obmedzíme iba na niektoré atribúty). Ide teda o unárnu operáciu $\Pi _{\mathbf {X} }(R)$ , kde X je množina názvov atribútov. Výsledkom je tá istá relácia obmedzená na atribúty z X.

Selekcia

Selekcia je unárna relačná operácia $\sigma _{\mathbf {X} }(R)$ zodpovedajúca výberu riadkov z tabuľky na základe nejakého kritéria. Nech $R$ je relácia typu $R(\mathbf {X} )$ , nech $\varphi (\mathbf {X} )$ je predikátová formula hovoriaca o jednotlivých prvkoch a ich príslušnostiach do relácií, ktorá okrem predikátov obsahuje len logické spojky $\lnot ,\lor ,\land$ . Potom:

\sigma _{\varphi (\mathbf {X} )}(R)=\{\mathbf {X} \ |\ R(\mathbf {X} )\land \varphi (\mathbf {X} )\}.

Premenovanie

Operácia premenovania, ktorá sa značí $\rho _{a/b}(R)$ , má viac-menej len formálny význam a využíva sa najmä v súvislosti s joinom. Operácia $\rho _{a/b}(R)$ premenuje atribút a na b.

Join

Join (značí sa $R\bowtie S$ ) slúži na spájanie relácií. Spojenie relácií sa dá uskutočniť aj bez nového operátoru, len pomocou karteziánskeho súčinu, ale jeho použitie môže byť v mnohých prípadoch pamäťovo neefektívne. Výsledkom je množina všetkých kombinácií prvkov relácie R a S, ktoré sa zhodujú na spoločných atribútoch. Napríklad:

*Relácia 1*
Atribút 1	Atribút 2	Atribút 3
1	A	a
2	B	b
3	C	a
4	D	b

*Relácia 2*
Atribút 3	Atribút 4
a	3
b	4
c	5

*Relácia 1* $\bowtie$ *Relácia 2*
Atribút 1	Atribút 2	Atribút 3	Atribút 4
1	A	a	3
2	B	b	4
3	C	a	3
4	D	b	4

Takto definovaný join sa presnejšie nazýva prirodzený join. Existuje viacero viarantov operácie join, ako napr. outer-join, semijoin a pod.

Grupovanie a agregácia

Relačná algebra podporuje päť agregačných funkcií, ktoré sú implementované vo väčšine databázových systémov. Tieto sú: sum (súčet hodnôt), count (počet prvkov), average (priemer), maximum a minimum. Samotná agregácia sa v relačnej algebre zapisuje pomocou agregačného operátora $\Gamma$ nasledujúcim spôsobom:

\Gamma _{\mathbf {X} }(R)

,

kde pre všetky $X\in \mathbf {X}$ platí, že X je buď atribút (tzv. grupovací atribút) alebo je tvaru AGG(Y) (agregovaný atribút), kde AGG je niektorá z piatich uvedených agregačných funkcií a Y je atribút. Operátor $\Gamma$ najprv rozdelí reláciu R na skupiny tak, že všetky riadky v každej skupine majú rovnaké hodnoty grupovacích atribútov. Následne pre každú zo skupín vypočíta hodnoty agregovaných atribútov a výsledkom je tabuľka, ktorá pre každú takúto skupinu obsahuje práve jeden riadok obsahujúci grupovacie atribúty a hodnoty daných agregačných funkcií.

Obmedzenia relačnej algebry

Napriek tomu, že relačná algebra poskytuje dostatočne silný aparát na väčšinu praktických aplikácií databázových systémov, existujú aj operácie na reláciach, ktoré sa pomocou nej nedajú vyjadriť. Jedným takým príkladom je napr. tranzitívny uzáver relácie.

Literatúra

J. Ullman, J. Widom: A First Course in Database Systems, Prentice-Hall, Englewood Cliffs, NJ, 1997.
H. Garcia-Molina, J. Ullman, Jennifer Widom: Database Systems: The Complete Book, Prentice-Hall, Englewood Cliffs, NJ, 2009.

Externé odkazy

Prednáška o relačnej algebre Archivované 2011-01-24 na Wayback Machine
Stránka o relačnej algebre Archivované 2015-09-23 na Wayback Machine (po anglicky)