Logická organizace báze dat

Historický vývoj směřoval od prvotního zpracování dat na úrovni fyzických záznamů přes datové záznamy bez vzájemných vazeb (na úrovni dat) až po báze dat obsahující v sobě popis dat včetně vazeb ([3], [7]).

V současné době má smysl rozebírat dva dominantní modely logické organizace bází dat: hierarchický (také hierarchicko - síťový) model a relační model ([10]).

Hierarchicko - síťový model

Model vychází z použité hierarchické struktury dat tak, jak byla kdysi zavedena pro potřeby jazyka Cobol pro zobrazení hodnot dat a jejich vzájemných vztahů (nadřízenosti a podřízenosti). Tento model se neopírá o matematickou teorii, i když přejímá část terminologie z teorie grafů. Přesto nalezl v praxi široké uplatnění.

Na hierarchickém modelu je založena řada systémů řízení báze dat, např. IMS firmy IBM, český DBS používaný kdysi v řadě EC apod.

Hierarchická struktura je taková, kde záznamy jsou v hierarchickém vztahu nadřazenosti a podřízenosti. Přitom se používá "rodinná" terminologie rodič a potomek ve zřejmém významu.

V hierarchické struktuře má každý potomek jediného rodiče, existuje jediný rodič, který není potomkem a potomek v jednom vztahu může být rodičem v jiném vztahu.

Pokud je zapotřebí popsat, na kterém místě hierarchické struktury se nějaký záznam nalézá, používá se k tomu tzv. přístupová cesta. To je možno díky popsaným vlastnostem hierarchické struktury, které zaručují, že od kořene lze dojít k danému záznamu jediným způsobem ([9]).

Často se vyžaduje (většinou z ryze praktických důvodů např. sběru dat), aby v každém záznamu existoval klíč. V takovém případě lze přístupovou cestu popsat jednoduše jako posloupnost klíčů počínaje klíčem kořenového záznamu přes klíče všech nadřízených až po klíč daného záznamu včetně.

Zmíněné pojmy z teorie grafů se při popisu hierarchických struktur využívají v tomto smyslu:

• záznam = uzel grafu

• vztah rodič - potomek = hrana grafu

• rodič a potomek = incidenční uzly hrany

• hierarchická struktura = souvislý graf, který je stromem

• báze dat hierarchického modelu = graf, který je les (tj. množina disjunktních stromů)

• přístupová cesta k záznamu = cesta v grafu od kořene k danému uzlu.

Obr. 3.1: Stromová struktura

Nevýhodou hierarchických systémů je velmi obtížná implementace odkazů. V takových případech se sice rozšiřují možnosti, snižuje redundance dat, ale současně dochází k nutnosti promíchávat otázky uložení na médiu s otázkami struktury modelu, ke znepřehlednění a zvláště ke snížení abstrakce při práci s daty.

Poznámka 1 z oblasti VS: V kapitole o grafech shora byla uvedena řada příkladů týkajících se právě VS. Je však nutno zdůraznit, že zatímco tam se grafová struktura uplatňovala pro model systému jako takový, zde slouží grafové struktury pro uložení - z hlediska teorie grafů - ohodnocení uzlů a hran grafového modelu, tedy informací o uzlech a hranách.

Poznámka 2 z oblasti VS: Tato metoda byla uvedena jen pro úplnost. V oblasti hospodaření s vodou, zvláště při modelování vodohospodřáských subsystémů, není vhodná pro základní bázi uchování dat; není totiž zřejmé, co by měl být kořenový segment (celkem vyrovnaně se přistupuje k datům jednak z hlediska míst, jednak z hlediska transportních cest). Při vlastním zpracování se však často vytváří virtuální datové struktury mající základ právě v hierarchickém modelu, i když jsou realizovány v prostředí relačních databázových systémů - o tom viz dále, zvláště poznámku o vzájemné transformaci hierarchického modelu na relační a naopak.

Relační model

Jedním z nejjednodušších zápisů dat je zápis do klasické tabulky. Takto převážně vznikají zápisy dat v terénu, obecně v neautomatizovaných částech systému. Charakteristický pro tento zápis je její členění do sloupců, z nich každý má nadpis. To je velmi podstatné, protože nadpis ve smyslu identifikace údajů automaticky indukuje také typ údajů v daném sloupci. Sloupce jsou tedy "homogenní co do typu". Snad nejpodstatnější vlastností je možnost vytvářet mezi jednotlivými tabulkami vazby ([6], [4]). Klasickým příkladem je výňatek z komplexní petrologické databáze ([35]), uvedený na následujícím obrázku.

Pevným počtem n sloupců tvoří data v řádcích uspořádané n-tice. Každý prvek n-tice, nazývaný pole, je toho typu, jaký odpovídá typu sloupce. Je tedy prvkem (konečné nebo nekonečné) jednoznačně určené množiny D _i (např. množiny všech datumů, množiny všech racionálních čísel, množiny {Ano;Ne} apod).

Obr. 3.2: Příklad relačního modelu

Příklady z oblasti vodohospodářských systémů (VS)

V celém dalším textu budou uváděny příklady z oblasti VS. Modelovou situaci tvoří fiktivní síť studní, které do nějakého subsystému dodávají pitnou vodu. Studny jsou realizovány na základě hydrogeologických vrtů, mají jistou polohu v terénu a sleduje se jejich hladina a čerpání z nich. Vzorky vody odebírané v náhodných intervalech se analyzují v různých laboratořích.

Matematický základ relačního modelu

Množina všech uspořádaných n-tic <a₁, a₂, ... , a_n>, kde A_i jsou libovolné množiny, a_i Î A_i a n je přirozené číslo, je z teorie množin známa jako kartézský součin K = A₁ x A₂ x ... x A_n, a každá podmnožina R Í K je známa jako n-ární relace v K. Je tedy možno pohlížet na každou tabulku, která je vytvořena obdobně jako tabulka shora, jako na n-ární relaci.

Pro určení relace R pro potřeby modelu báze dat je zapotřebí zadat

• konečnou množinu atributů F - což jsou jména polí s případnými dalšími specifikacemi (šířka sloupce, počet desetinných míst ap) využitelných pro uživatelskou i programovou identifikaci

• domény A _i, tj. množiny možných hodnot každého pole

• podmnožinu kartézského součinu domén, tj. vlastní relaci (z hlediska tabulky je tím určen počet polí a pořadí sloupců).

Relaci je tedy možno definovat jako trojici R = <F, D, T>, kde

• F je konečná množina jmen atributů

• D je zobrazení, přiřazující každému f Î F doménu D(f) atributu f. Domény jsou libovolné neprázdné množiny (konečné nebo nekonečné); je-li f, g Î F, f různé od g, nemusí být D(f) různé od D(g).

• T je konečná podmnožina kartézského součinu X [D(f)] všech domén atributů, f Î F.

Tabulky dat, které reprezentují relace, mají - jak již bylo uvedeno - následující vlastnosti:

1. Každému prvku relace odpovídá jeden řádek tabulky

2. Žádné dva řádky nejsou identické

3. Sloupec s atributem f z F v záhlaví obsahuje jen hodnoty z domény D(f).

Okolnost, že v praxi často nebývá splněna vlastnost ad 2), se řeší "očíslováním řádků"; přidá se jeden sloupec, jehož doména je podmnožina přirozených čísel ([15]).

První normální forma

Přestože domény mohou být libovolné množiny, používá se z čistě praktických důvodů většinou jen množin, jejichž prvky jsou

• číselné hodnoty (vzhledem ke zpracování v počítačovém prostředí výhradně racionální)

• datumové hodnoty (uspořádané trojice <d,m,r> přirozených čísel s příslušně definovaným oborem a operacemi)

• textové hodnoty (posloupnosti prvků z Î Z, kde Z je konečná neprázdná množina)

• binární hodnoty (prvky dvouprvkové množiny {Ano, Ne})

• relace.

Domény obsahující jen prvky analogické prvním čtyřem vyjmenovaným se nazývají jednoduché. Jestliže relace obsahuje pouze jednoduché domény, nazývá se relace v první normální formě. Proces převedení relace do první normální formy se nazývá normalizace ([11]).

Příklad z oblasti VS: Nechť do VS přispívají studny realizované jednotlivými vrty; nepravidelně je prováděno měření hladiny a sekundového odběru. Relace, která není v první normální formě, je dána např. následující tabulkou:

Obr. 3.3: Nenormalizovaná relace

Normalizace této relace může vést k jediné relaci, která již v první normální formě je:

Obr. 3.4: Normalizovaná relace

Jde o poměrně jednoduchý příklad; je však nutno upozornit na to, že procesem normalizace zvláště u složitě logicky strukturovaných relací mohou často vznikat redundantní údaje. I v tomto příkladu se redundanci dat nevyhneme: souřadnice jednoho vrtu jsou uloženy na několika různých místech. Pokud např. se posléze zjistí, že souřadnice X vrtu A12 byla zaznamenána chybně, je nutno hodnotu opravit ne na jediném, ale na několika různých místech. To je přesně ta situace, kterých by v reálné praxi mělo být co nejméně.

Některé atributy nebo jejich spojení lze v případě potřeby použít jako klíče. Označme je jako možné klíče. Klíče se používají jednak pro vyhledávání, jednak pro uspořádání. Jestliže se některý možný klíč skutečně pro daný účel použije, stává se po dobu použití primárním klíčem. Je-li klíč tvořen jediným atributem, označuje se jako jednoduchý klíč; je-li tvořen spojením dvou a více atributů, nazývá se spojený klíč. Je-li klíč vytvořen pomocí operací definovaných na hodnotách polí a na konstantách, nazývá se obecný klíč.

Pomocí klíčů lze nahradit jednu nenormalizovanou relaci více normalizovanými relacemi se stejným datovým obsahem, jak to ukazuje následující obrázek. Klíčem (a to jednoduchým) je v tomto případě atribut Vrt.

Obr. 3.5: Rozklady relace

Zápis struktury databáze

Pro formalizaci zápisu struktury se často používá notace, která je základem některých dotazovacích jazyků. V této notaci se zapíše struktura relací následovně:

VRTY (^VRT, X, Y, LABORATOŘ)
ČERPÁNÍ (^VRT, ^DATUM, HLADINA, L/SEC)

Identifikátor relace je uveden před kulatými závorkami; uvnitř nich jsou uvedeny jednotlivé atributy. Je-li před některým z nich uveden znak ^, je tím označen klíč.

Nenormalizovaná relace se pak v této notaci zapíše následovně:

VRTY (^VRT, X, Y, ČERPÁNÍ (^DATUM, HLADINA, L/SEC), LABORATOŘ)

Porovnáním zápisů obou struktur lze odhalit jeden z možných postupů tvorby klíčů při procesu normalizace, kterým vzniká více relací: každá hierarchicky vnořená relace předřadí svému vlastnímu klíči (klíčům) klíč (klíče) relace bezprostředně hierarchicky nadřazené.

Operace s relacemi

V relačním modelu je báze dat definována jako n-ární relace; takových bází dat se tedy týkají všechny vlastnosti, které lze odvodit matematickým aparátem pro relace. Tento aparát jako obecný aparát matematický je pro účely počítačového zpracování velmi dobře algoritmicky propracován. S relacemi jako takovými se pracuje poměrně jednoduše; výhoda relačních modelů databází spočívají právě v jednoduchosti práce s relacemi.

Pro relace se zavádí především operace; ze základních operací uveďme projekci a spojení jako nejčastěji vyžadované operace.

Nechť P a Q jsou relace. Operaci x nazýváme projekcí tehdy, je-li P x Q relace, která vznikne z P vynecháním atributů P, které nejsou současně atributy Q, a následným vynecháním shodných řádků. Tato operace se používá pro zbavení se nepodstatných nebo v danou chvíli nedůležitých informací.

Příklad :

VRTY x (^VRT, LABORATOŘ) = (^VRT, LABORATOŘ)

Nechť P a Q jsou relace, které mají alespoň jeden shodný atribut. Operaci + nazýváme spojením tehdy, je-li P + Q relací, která vznikne z P přidáním atributů Q, které nejsou současně atributy P, a následným vynecháním shodných řádků. Spojení vytvoří relaci z hodnot atributů obou relací, které odpovídají hodnotám shodného (shodných) atributů.

Příklad:

VRTY + (^VRT, ^DATUM, L/SEC) = (^VRT, X, Y, LABORATOŘ, ^DATUM, L/SEC)

Tyto a další operace vytváří algebru relací. Kromě operací lze vytvářet další relace také relačním kalkulem. Přitom se využívá symboliky používané obdobně v jiných partiích matematiky: