Teoretický základ relačních databází
Doc. Dr. Vladimír Homola, Ph.D.
Úvod
Tato kapitola se snaží o pokud možno jednoduché přiblížení teoretického základu toho, co je běžně označováno jako "tabulka dat relační databáze". Protože jde o kapitolu publikace pojednávající o databázích v počítačovém prostředí, soustřeďuje se na konečné množiny a rovněž definice některých pojmů přizpůsobuje praktickým databázovým aplikacím. Používá sice běžný matematický aparát známý z teorie množin, autor však doufá, že připojené komentáře vysvětlí dostatečně podstatu problému i těm, kteří matematiku nemají moc rádi - což je vlastně celý národ.
Kartézský součin
Zavedení pojmu
Definice: Kartézský součin množin A, B (značení: A ´ B) je množina všech uspořádaných dvojic takových, že první prvek dvojice je prvkem množiny A a druhý prvek dvojice prvkem množiny B:
A ´ B = { [a,b] ˝ a Î A Ů b Î B }
Obdobně kartézský součin množin A, B, C (značení: A ´ B ´ C) je množina všech uspořádaných trojic takových, že první prvek trojice je prvkem množiny A, druhý prvek trojice prvkem množiny B a třetí prvek trojice prvkem množiny C:
A ´ B ´ C = { [a,b,c] ˝ a Î A Ů b Î B Ů c Î C }
atd. Je-li jedna z množin prázdná, je i kartézský součin prázdná množina.
Označení: Součin A ´ A označujeme také A2, M ´ M ´ M ´ M ´ M označujeme také M5 atd.
Jsou-li množiny A a B konečné s počty prvků nA a nB, je i jejich kartézský součin A ´ B konečná množina; počet jejich prvků (=počet uspořádaných dvojic) je roven nA ´ nB.
Komentář
Kartézský součin množin A a B je tedy množina dvojic obsahující kombinace “každý z A s každým z B”. Je-li například množina A tříprvková množina obsahující tři barvy:
A = {červené, zelené, žluté}
a množina B dvouprvková množina obsahující dva kusy ovoce:
B = {jablko, hruška}
pak kartézským součinem A x B je množina šesti dvojic - každá barva s každým ovocem:
A ´ B = { [červené,jablko], [červená,hruška], [zelené,jablko], [zelená,hruška], [žluté,jablko], [žlutá,hruška] }
Tento zápis je však poněkud nepřehledný, pro přehlednější zobrazení kartézského součinu
se pro množiny s malým počtem prvků může použít tabulka; např.
| jablko | hruška | |
| červené | červené jablko | červená hruška |
| zelené | zelené jablko | zelená hruška |
| žluté | žluté jablko | žlutá hruška |
I v některých případech nekonečných množin lze s výhodou kartézský součin dvou množin znázornit graficky. Jsou-li např. A a B uzavřené intervaly reálných čísel, A=<2,6> a B=<1,4>, pak znázornění kartézského součinu A ´ B může být např. následující:
Problematičtější je znázornění kartézského součinu tří nebo více množin - zde by se jednalo o tří- a vícerozměrné útvary znázorňované v rovině papíru obtížně. Proto lze u konečných množin použít i tabulkového znázornění tohoto typu:
| barva Î A | ovoce Î B |
| červené | jablko |
| červená | hruška |
| zelené | jablko |
| zelená | hruška |
| žluté | jablko |
| žlutá | hruška |
Kartézský součin tří množin je pak tabulka se třemi sloupci, čtyř množin se čtyřmi sloupci atd. Důležité je, že 1) v každém sloupci jsou prvky jen jedné konkrétní množiny, 2) první sloupec obsahuje prvky první množiny, druhý druhé atd.
Relace
Zavedení pojmu
Definice: Binární relace R v množinách A a B je libovolná podmnožina kartézského součinu A ´ B:
R Í A ´ B
Označení: Je-li [a,b] Î R, píšeme: aRb a čteme: prvku a
je v relaci R přiřazen prvek b, nebo: prvek a je v relaci R s prvkem b. Je-li
naopak [a,b] Ď R, píšeme a
b a čteme:
prvek a není v relaci R s prvkem b.
Označení: Je-li R Í A ´ A, pak R nazýváme relací v množině A.
Definice: Ternární relace R v množinách A, B a C je libovolná podmnožina kartézského součinu A ´ B ´ C:
R Í A ´ B ´ C
Definice: Obecně pak n-ární relace R v množinách A, B, ..., Z je libovolná podmnožina kartézského součinu A ´ B ´ ... ´ Z:
R Í A ´ B ´ ... ´ Z
Komentář
Definice říká: je-li kartézský součin např. A ´ B tvořen všemi kombinacemi prvků z A a B, pak relace je tvořena jen některými kombinacemi prvků z A a B, např.
| barva Î A | ovoce Î B |
| červené | jablko |
| zelené | jablko |
| zelená | hruška |
nebo
| barva Î A | ovoce Î B |
| červené | jablko |
| žlutá | hruška |
Omezme se nyní jen na binární relaci R a na jedinou množinu A. V množině
A = {3, 5, 7, 9}
je dána relace
R = { [3,5], [3,7], [3,9], [5,7], [5,9], [7,9] }
Je tedy např. 3R7, 7R9, ale 93.
Jsou-li množiny A a B konečné, lze pro znázornění relací použít několika způsobů. Nejčastěji používané jsou dva: maticový a tabulkový. Maticovým zápisem relace R z předchozího příkladu je následující matice 4x4 (nad matici resp. před matici byly pro přehlednost přidány nadpisy sloupců resp. řádků); v ní hodnota 0 značí, že prvky v relaci nejsou, hodnota 1 značí, že prvky v relaci jsou:
| (aŻ) R (b®) | 3 | 5 | 7 | 9 |
| 3 | 0 | 1 | 1 | 1 |
| 5 | 0 | 0 | 1 | 1 |
| 7 | 0 | 0 | 0 | 1 |
| 9 | 0 | 0 | 0 | 0 |
Tabulkovým zápisem relace R z předchozího příkladu je následující tabulka:
| a Î A | b Î B |
| 3 | 5 |
| 3 | 7 |
| 3 | 9 |
| 5 | 7 |
| 5 | 9 |
| 7 | 9 |
Vlastnosti binárních relací
Poznámka: Tento odstavec je vložen jen pro úplnost, zájemce jen o databáze ho může přeskočit. Nicméně je dobré si ho přečíst proto, že ukazuje teoretický základ některých zcela běžně používaných symbolů.
Zavedení pojmu
Definice: V následující tabulce jsou definovány některé základní typy relací podle svých vlastností; relace R je vždy v těchto případech relací v množině A:
| Relace R je ... | ... právě když platí: |
| reflexivní | " x Î A : xRx |
| symetrická | " x,y Î A : xRy ® yRx |
| tranzitivní | " x,y,z Î A : xRy Ů yRz ® xRz |
| areflexivní | " x,y Î A : xRy ® x ą y |
| antisymetrická | " x,y Î A : xRy Ů yRx ® x=y |
| ekvivalence | R je reflexivní, symetrická, tranzitivní |
| (neostré) uspořádání | R je reflexivní, antisymetrická, tranzitivní |
| ostré uspořádání | R je areflexivní, tranzitivní |
Komentář
Kartézský součin A x A je množina kombinací každého prvku z A se všemi ostatními prvky A, ale i sám se sebou. Binární relace R v A je pak množina jen některých takových kombinací. Komentujme jen některé vlastnosti.
Relace R je reflexivní, jestliže v množině některých takových kombinací jsou určitě všechny kombinace všech prvků A samy se sebou (a třeba ještě některé jiné kombinace).
Naopak relace R je areflexivní, jestliže v množině některých takových kombinací určitě není žádná kombinace nějakého prvku A sama se sebou. Definice to říká takto: je-li v relaci nějaká kombinace [a,b], pak je určitě a různé od b (protože kdyby b bylo stejné jako a, je tam kombinace [a,a] a to bylo vyloučeno).
Relace R je symetrická, jestliže v množině některých takových kombinací platí toto: je-li tam [a,b], určitě je tam taky [b,a].
Naopak relace R je antisymetrická, jestliže v množině některých takových kombinací platí toto: je-li tam [a,b], určitě tam není [b,a] a naopak. Definice to říká takto: Je-li tam [a,b] i [b,a], pak určitě a i b jsou stejné prvky.
Zjišťování, zda nějaká daná relace má nějakou konkrétní vlastnost, znamená ověření podle definice v hořejší tabulce.
Důležitý příklad: Nechť je dána relace - viz příklad A x A shora. Tato relace je areflexivní (pro všechna [x,y] Î R je x ą y) a tranzitivní (3R5 Ů 5R7 ® 3R7; 3R7 Ů 7R9 ® 3R9; 5R7 Ů 7R9 ® 5R9). Relace je tedy ostré uspořádání; tato relace se často místo obecného R značí “<”. Je tedy 3<5, 3<7, 3<9, 5<7, 5<9, 7<9.
Relační databáze
Na shora zavedeném pojmu relace jsou konstruovány tzv. relační databáze. Nechť například množiny D, C a N značí po řadě množinu všech datumů, množinu všech řetězců (řetězec = posloupnost jednoho nebo více písmen, cifer a jiných znaků) a množinu všech racionálních čísel. Mějme relaci R definovanou jako podmnožinu kartézského součinu K = D ´ N ´ C ´ C. Množina K je (teoreticky nekonečná) množina všech uspořádaných čtveřic, kde první prvek čtveřice je datum, druhý racionální číslo, třetí je řetěz a čtvrtý je rovněž řetěz. Množinu R vytvořme tak, že vybereme jen některé čtveřice. Z hlediska praktického použití jakékoliv náhodná čtveřice, např.
[12/04/1543, 0, blabla, gaga]
asi nebude příliš zajímavá. Ovšem čtveřice
[01/01/1992, 9200, Novák, řidič]
už může vypovídat o jisté reálné situaci: prvního ledna 92 byl přijat Novák jako řidič s platem 9200 Kč. Tabulkový zápis relace R pak může vypadat např. takto:
| Datum Î D | Plat Î N | Jméno Î C | Profese Î C |
| 01/01/1992 | 9 200 | Novák | řidič |
| 15/06/1973 | 14 500 | Novotný | vedoucí |
| 01/11/1990 | 8 300 | Nováček | vrátný |
| ... | ... | ... | ... |
| 15/06/1978 | 17 800 | Bratka | analytik |
Každá čtveřice v tabulce podává jisté informace o jednom konkrétním pracovníkovi. Všechny čtveřice tvořící tuto tabulku pak podávají informace o všech pracovnících nějaké organizační jednotky.
Relační databáze tedy může být chápána jako obdélníkové schéma tvořené řádky a sloupci řídící se následujícími pravidly:
-
Řádků je libovolný počet (i třebas nula - relace jako množina může být prázdná). Pro praktické databázové aplikace je však oproti definici relace vhodné, aby byla připuštěna možnost násobného výskytu stejných řádků.
-
Sloupců je libovolný počet (nejméně však jeden - kartézský součin v "minimálním" případě je alespoň A1).
-
Sloupce mají "nadpisy" identifikující množiny, ze kterých pochází prvky daného sloupce. Podle definice nic nebrání tomu, aby se v kartézském součinu nevyskytovala jedna množina vícekrát (viz v příkladu shora množina C). Pak však musí být "nadpisem" rozlišeno, na jakém místě v kartézském součinu se množina vyskytuje - je totiž nepraktické označení "množina C třetího sloupce" apod. V příkladě shora nadpis "Jméno" identifikuje množinu C na třetí a nadpis "Profese" na čtvrté pozici kartézského součinu D x N x C x C.
Poznámka: Důsledkem teoretického základu relační databáze je to, že v jednom sloupci se nemohou vyskytovat dva prvky z různých množin.
Příklad shora demonstrující pojem relační databáze je jedním z nejjednodušších. Obecně
jsou totiž množiny tvořící kartézský součin skutečně libovolné množiny - množina obrázků, množina
psychických stavů, množina vůní apod. Nic tedy nebrání např. tomu, aby jedna z nich byla množina uspořádaných
n-tic (tedy nějaká relace). Může to být např. relace z kartézského součinu L x S x P,
kde L je množina všech kalendářních let, S množina všech škol a P množina všech prospěchů.
Označme tuto relaci (=množinu uspořádaných trojic) písmenem A. Konkrétně může být A rovno
| Rok Î L | Škola Î S | Prospěch Î P |
| 1972 | ZŠ Dlouhá | Vyznamenání |
| 1975 | SVVŠ Příčná | Uspěl |
| 1983 | ZŠ Dubí | Vyhověl |
| ... | ... | ... |
| 1982 | VUML | Výtečný |
Tabulka zaměstnanců pak může být obrazem následující relace:
| Datum Î D | Plat Î N | Jméno Î C | Absolvent Î A | Profese Î C | ||||||||||||
| 01/01/1992 | 9 200 | Novák |
| řidič | ||||||||||||
| 15/06/1973 | 14 500 | Novotný |
| vedoucí | ||||||||||||
| ... | ... | ... | ... | ... | ||||||||||||
| 15/06/1978 | 17 800 | Bratka |
| analytik |
Databázové názvosloví
V počítačových databázových aplikacích se většinou používá uživatelsky zaměřená terminologie na rozdíl od matematické terminologie podané shora. V následujícím textu jsou tučně označeny termíny používané v databázových aplikacích.
-
Tabulka relační databáze - konkrétní relace v konkrétním kartézském součinu.
-
Záznam - konkrétní prvek relace, tj. uspořádaná n-tice, také řádek tabulky relační databáze.
-
Hodnota - konkrétní prvek uspořádané n-tice, tj. konkrétní prvek záznamu, řádku.
-
Datový typ - hovorové označení některých konkrétních (reálných i abstraktních) množin figurujících v kartézském součinu (např. datumový pro množinu všech kalendářních datumů, textový pro množinu všech znakových řetězců apod.). Z hlediska uživatele databází klíčové místo. Databázové systémy poskytují totiž velmi omezený počet množin (většinou hardwarově determinovaných), ze kterých může uživatel umísťovat hodnoty ve svých tabulkách.
-
Typ hodnoty - stejné jako datový typ; používá se pro zdůraznění toho, že hodnota pochází z určité konkrétní množiny.
Orig. 8 / 1999
Rev. 07 / 2002