Relační algebra

Relační algebra je v informatice formální systém pro manipulaci s relacemi, který se používá zejména na popis operací v relačních databázích. Operandy algebry jsou relace, operátory jsou množinové operátory (jelikož každá relace je současně i množinou) a speciální relační operátory, jako selekce, projekce nebo join (v doslovném překladu spojení).

Historie

I když jisté obdoby relační algebry byly známy už dříve, do obecného povědomí se relační algebra dostala až v roce 1970, když Edgar Frank Codd přišel s tzv. Relačním modelem organizace údajů. Codd také dokázal tzv. Coddovu větu, podle které je relační algebra ekvivalentní (což se popisné síly týká) relačního kalkulu, a tedy i predikátová logika prvního řádu.

Na základě relační algebry bylo později vytvořeno několik dotazovacích jazyků. Na jejím základě je postaven i dotazovací jazyk SQL, vyvinutý v roce 1974, který je v současnosti jedním z nejpoužívanějších jazyků na manipulaci s databázemi.

Operátory

Operátory relační algebry se v zásadě dělí na dvě kategorie: primitivní a odvozené. Primitivní operátory jsou analogií konceptu úplného systému známého z matematické logiky, protože se z nich dají odvodit všechny odvozené operátory. Volba takové množiny operátorů není jednoznačná, Edgar Frank Codd za primitivní operátory zvolil selekci, projekci, kartézský součin, sjednocení množin, rozdíl množin a přejmenování. Přesněji, Codd původně přejmenování mezi primitivní operátory nezařadil, ale nutnost tohoto kroku se ukázala při tvorbě dotazovacího jazyka ISBL.

Šest primitivních operátorů tedy tvoří jakési jádro relační algebry. Ostatní operátory sice podstatně usnadňují práci, dají se však vynechat bez snížení popisné síly celého systému.

Množinové operátory

Množinové operátory fungují v podstatě stejně jako v teorii množin. V relační algebře se však na operandy některých množinových operaci kladou speciální požadavky. Především, operandy sjednocení a rozdílu (primitivních operací relační algebry) množin musí být kompatibilní, tzn. musí mít stejnou n-tici atributů. Zjednodušeně řečeno, pokud si relaci představíme jako databázovou tabulku, není možné provést sjednocení dvou tabulek v případě, že mají různé hlavičky.

Kompatibilita operandů se požaduje i v případě průniku, jelikož průnik se, jako odvozený operátor, definuje na základě sjednocení a rozdílu:

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

Kartézský součin v relační algebře sice sleduje základní myšlenku z teorie množin, je však definován odlišně. Neformálně řečeno, klasický kartézský součin by z n a m relace vytvořil množinu dvojic, kde každá dvojice obsahuje jednu n-tici a jednu m-tici. Kartézský součin v relační algebře ale z těchto dvou relaci vytvoří odpovídající množinu n + m-tic. Formálně řečeno, kartézský součin se v relační algebře definována takto:

$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\}.$

Projekce

Projekce je relační operace, která intuitivně odpovídá výběru sloupců z tabulky (tedy se omezíme pouze na některé atributy). Jde tedy o unární operaci $\Pi _{\mathbf {X} }(R)$, kde X je množina názvů atributů. Výsledkem je stejná relace omezena na atributy z X.

Selekce

Selekce je unární relační operace $\sigma _{\mathbf {X} }(R)$ odpovídající výběru řádků z tabulky na základě nějakého kritéria. Ať $R$ je relace typu $R(\mathbf {X} )$, ať $\varphi (\mathbf {X} )$ je predikátová formule hovořící o jednotlivých prvcích a jejich příslušnostech do relací, která kromě predikátů obsahuje pouze logické spojky $\lnot ,\lor ,\land$. Pak:

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

Přejmenování

Operace přejmenování, která se značí $\rho _{a/b}(R)$, má víceméně jen formální význam a využívá se zejména v souvislosti s join. Operace $\rho _{a/b}(R)$ přejmenuje atribut a na b.

Join

Join (značí se $R\bowtie S$) slouží ke spojování relací. Spojení relací lze uskutečnit i bez nového operátoru, jen pomocí kartézského součinu, ale jeho použití může být v mnoha případech paměťově neefektivní. Výsledkem je množina všech kombinací prvků relace R a S , které se shodují na společných atributech. Například:

Relace 1 Atribut 1 Atribut 2 Atribut 3 1 A a 2 B b 3 C a 4 D b

Relace 2 Atribut 3 Atribut 4 a 3 b 4 c 5

Relace 1$\bowtie$Relace 2 Atribut 1 Atribut 2 Atribut 3 Atribut 4 1 A a 3 2 B b 4 3 C a 3 4 D b 4

Takto definovaný join se přesněji nazývá přirozený join. Existuje několik variant operace join, jako např. Outer-join, semijoin apod.

Grupování a agregace

Relační algebra podporuje pět agregačních funkcí, které jsou implementovány ve většině databázových systémů. Tyto jsou: sum (součet hodnot), count (počet prvků), average (průměr), maximum a minimum. Samotná agregace se v relační algebře zapisuje pomocí agregačního operátora $\Gamma$ následujícím způsobem:

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

Kde pro všechny $X\in \mathbf {X}$ platí, že X je buď atribut (tzv. seskupovací atribut) nebo je tvaru AGG (Y) (agregovaný atribut), kde AGG je některá z pěti uvedených agregačních funkcí a Y je atribut. Operátor $\Gamma$ nejprve rozdělí pořad R na skupiny tak, že všechny řádky v každé skupině mají stejné hodnoty grupovacích atributů. Následně pro každou ze skupin vypočítá hodnoty agregovaných atributů a výsledkem je tabulka, která pro každou takovou skupinu obsahuje právě jeden řádek obsahující grupovací atributy a hodnoty daných agregačních funkcí.

Omezení relační algebry

Přesto, že relační algebra poskytuje dostatečně silný aparát na většinu praktických aplikací databázových systémů, existují i operace na relacích, které se pomocí ní nelze vyjádřit. Jedním takovým příkladem je např. tranzitivní uzávěr relace.

Reference

V tomto článku byl použit překlad textu z článku Relačná algebra na slovenské Wikipedii.

Literatura

• 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

• Obrázky, zvuky či videa k tématu relační algebra na Wikimedia Commons

• Přednáška o relační algebře (archivovaná verze)
• Stránka o relační algebře Archivováno 23. 9. 2015 na Wayback Machine. (anglicky)

Autoritní data	PSH: 7231