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 ab 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:

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
Rok Î L Škola Î S Prospěch Î P
1972 ZŠ Dlouhá Dostatečný
1982 VUML Výtečný
řidič
15/06/1973 14 500 Novotný
Rok Î L Škola Î S Prospěch Î P
1963 ZŠ Dubí Vyhověl
1967 SPŠ Strojní Vyznamenání
1970 ČVUT Výtečný
vedoucí
... ... ...  ... ...
15/06/1978 17 800 Bratka
Rok Î L Škola Î S Prospěch Î P
1972 ZŠ Dlouhá Vyznamenání
1975 SVVŠ Příčná Uspěl
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.

 

 

Rev. 07 / 2002