COMPUTERWORLD
pod kapotou
Dekompozice relací

Navrhovat relace pomocí transformace z konceptuálního návrhu je dnes běžný technologický postup navrhování databáze. V posledních pokračováních Databázové abecedy jsme zmiňovali normální formy relací, tj. 3NF, BCNF a 4NF. Představme si nyní, že máme již hotové schéma relační databáze a někdo nám uloží zkontrolovat, zdali všechny jeho části jsou v dané normální formě. Podrobnější analýza může ukázat že nikoliv, což má za následek dvě akce:

  • úprava schématu (obvykle dekompozicí chybně navrženého schématu),
  • následná úprava konceptuálního návrhu (existuje-li).

Kdykoli jsme chtěli dosáhnout 3NF nebo BCNF, museli jsme ale nahradit jedno schéma několika jinými schématy. Tato náhrada zachovává zatím pouze jednu vlastnost: je-li A množina atributů původního schématu relace a Ai, pro i = 1,2,...n, n>1, množina atributů i-tého schématu relace, pak sjednocení všech Ai je rovno A. Tomuto procesu se říká dekompozice schématu relace. Otázkou je, do jaké míry souvisí schémata získaná dekompozicí s původními schématy z hlediska jejich sémantiky a do jaké míry jsou si "podobná" data odpovídajících relací původní, resp. nové relační databáze. Jinými slovy řečeno, jde o problém korektnosti nové reprezentace dat.

Intuitivní představa korektní reprezentace vychází ze dvou idejí:

(1) výsledná schémata by měla mít "stejnou" sémantiku,

(2) výsledné relace by měly obsahovat "stejná" data, jaká by obsahovala původní databáze.

Vlastnost pokrytí závislostí

Zaměříme se nejdříve na bod (1). Sémantika schématu relace je dána pomocí integritních omezení (IO). Ta jsou na konceptuální úrovni vyjádřena různými způsoby, na úrovni jednoho schématu relace však vystačíme pouze z funkčními závislostmi mezi množinami atributů. Cílem tedy bude, aby původní schéma a schémata získaná dekompozicí nějak vhodně odrážely stejné funkční závislosti.

Připomeňme situaci s příkladem ADRESÁŘ(MĚSTO, ULICE, PSČ) a jeho dekompozici do BCNF. SEZNAM_ULIC(ULICE, PSČ), MĚSTA(PSČ, MĚSTO). Získaná schémata jsou jistě dekompozicí. V schématu MĚSTA lze kontrolovat funkční závislost PSČ-> MĚSTO. Bohužel, funkční závislost

{ULICE, PSČ}-> MĚSTO

již nepopisuje daná schémata. Levá strana závislosti je obsažena v jednom schématu, druhá strana v druhém schématu, tj. (poněkud zjednodušeně) tato závislost již ve světě vymezeném přípustnými databázemi pro obě schémata nemusí platit.

Pro plnější představu o problému ukážeme ještě jeden příklad. Vyjděme ze schématu

EVIDENCE(REŽISÉR, ATELIÉR, VEDOUCÍ_A)

a závislostí REŽISÉR -> ATELIÉR, ATELIÉR -> VEDOUCÍ_A, REŽISÉR -> VEDOUCÍ_A.

Provedeme-li dekompozici do 3NF

UMÍSTĚNÍ(REŽISÉR, ATELIÉR)

STRUKTURA(ATELIÉR, VEDOUCÍ_)

dostaneme se do jiné situace. Funkční závislost ATELIÉR -> VEDOUCÍ_A existuje dále, protože je odvoditelná z funkčních závislostí, které platí na schématech UMÍSTĚNÍ a STRUKTURA.

Formalizujme nyní požadavek (1). Mějme relační schéma databáze S(A,F), tj. na A je definována množina funkčních závislostí F) a dekompozici S, danou jako R={Ri(Ai,Fi), 1 £ i £ n, n > 1}. Řekneme, že R vlastnost pokrytí závislostí, jestliže všechny funkční závislosti, které se dají odvodit z F, jsou odvoditelné ze sjednocení závislostí Fi a naopak.

Zatím ještě není jasné, jak vzniknou Fi. Jde o závislosti, které platí na Ai, tj. o takové závislosti odvoditelné z F (nikoliv pouze ty z F), které lze "promítnout" do atributů Ai. Budeme je dále nazývat projekce závislostí.

Uvažujme schéma relace

PLÁN_F(REŽISÉR, FILM, TYP_F, MAX_DÉLKA) a

F: FILM -> TYP_F, TYP_F-> MAX_DÉLKA,

Typem filmu se rozumí například dokumentární, hraný, instruktážní apod.

Schéma PLÁN_F zřejmě není ve 3NF. Provedeme-li dekompozici

R1(REŽISÉR, FILM, MAX_DÉLKA), R2(REŽISÉR, TYP_F),

promítnou se do R1 původní funkční závislosti nepřímo, pouze prostřednictvím odvozené závislosti FILM -> MAX_DÉLKA. Další závislosti v R1, R2 už jsou jen závislosti na klíči. Ani jedna ze závislostí F se ale do F1 ani do F2 nedostala. Mimochodem, R1 ještě není ve 3NF, neboť atribut MAX_DÉLKA je částečně závislý na klíči. Dekompozice nemá vlastnost pokrytí závislostí.

Je jasné, že provádět podobné analýzy na větších příkladech je ručně náročně, odpovídající prostředky v CASE nástrojích nejsou, takže výsledky dekompozice, byť nesplňující vlastnost pokrytí závislostí se přijmou za vyhovující.

Bezztrátová dekompozice

Zaměříme se nyní na formalizaci druhého kritéria korektní reprezentace. Problém stejných dat lze vyjádřit velmi přirozeně pomocí operace spojení. Vyjdeme ze stejných předpokladů jako u formulace vlastnosti pokrytí závislostí. Všimněme si, že dekompozice schématu vlastně znamená na úrovni databáze vytvořit projekce původní relace na atributy odpovídající jednotlivým schématům po dekompozici. Pak můžeme požadovat, aby dekompozice měla vlastnost bezztrátového spojení, která říká, že pro každou přípustnou relaci S* by mělo platit

S* = S*[A1]* ... * S*[An]

tj. že se S* dá rekonstruovat pomocí přirozeného spojení projekcí S* na atributy jednotlivých relací dekompozice. Toto není vůbec samozřejmé, jak ukazuje následující situace vycházející z příkladu VÝUKA.

ZKOUŠKY

PŘEDNÁŠKA

STUDENT

ZNÁMKA

Líčení

Zíka

1

 

Líčení

Tupý

2

 

Líčení

Nový

2

 

Líčení

Bílý

1

 

Scénáře

Nový

2

 

Scénáře

Vorel

3

Provedeme-li dekompozici ZAPIS(PŘEDNÁŠKA, STUDENT) a HODNOCENÍ(PŘEDNÁŠKA, ZNÁMKA), pak odpovídající projekce Z* poskytující data v tabulkách ZKOUŠKY1 a ZKOUŠKY2.

ZKOUŠKY1

PŘEDNÁŠKA,

STUDENT

Scénáře

Nový

Scénáře

Vorel

Líčení

Zíka

Líčení

Tupý

Líčení

Nový

Líčení

Bílý

ZKOUŠKY2

PŘEDNÁŠKA,

ZNÁMKA

 

Líčení

1

 

Líčení

1

 

Scénáře

3

 

Scénáře

2

Je hned vidět, že výsledek spojení těchto relací bude obsahovat více řádků než původní relace ZKOUŠKY*. Bude např. obsahovat n-tici (Scénáře, Nový, 3). Spojení tedy není bezztrátové. Přestože obdržíme více řádků, informace je méně, neboť nevíme, co platí a co ne. Aby platila rovnost z definice bezztrátovosti, je třeba provést dekompozici dostatečně smysluplně. PŘEDNÁŠKA a ZNÁMKA v tabulce ZKOUŠKY2 bez dalších atributů nemá dobře definovanou sémantiku. Jistě je každému jasné, že by takovou “botu” při dekompozici schématu ZKOUŠKA neudělal. Ve trochu složitější realitě, či ne zcela jasné sémantice toho, co vlastně projektujeme, však může jít běžnou situaci.

Dekompozici, která má požadovanou vlastnost, lze provést podle následujícího významného tvrzení.

Tvrzení o bezztrátové dekompozici

Mějme schéma R(A,B,C), kde A,B,C jsou disjunktní množiny atributů,

a funkční závislost B -> C. Rozložíme-li R na schémata R1(B,C) a R2(A,B),

je takto provedená dekompozice bezztrátová. Naopak, je-li dekompozice

R1(B,C) a R2(A,B) bezztrátová, musí platit buď B-> C nebo B-> A.

Poznámka:

Z tvrzení vyplývá, že platí-li B -> C, dekompozice R1(B,C) a R2(C,A) není bezztrátová. (Neplatí totiž ani C-> B ani C-> A.)

Poznámka:

Dekompozice může mít vlastnost bezztrátového spojení, nemusí však mít vlastnost pokrytí závislostí. Takovou dekompozici obsahuje příklad ADRESÁŘ, kterou lze chápat tak, že byla provedena podle závislostí PSČ-> MĚSTO. Dekompozice, která má vlastnost pokrytí závislostí, zase nemusí být bezztrátová. To lze jednoduše vidět z příkladu schématu {R(A,B,C,D), F: A -> B, C -> D}, kde dekompozice je dána jako R1(C,D) a R2(A,B).

Dekompozice, která je bezztrátová, se dá systematicky provádět i podle multizávislosti. Ve tvrzení o bezztrátové dekompozici stačí nahradit -> znakem -> >.

Jaké z těchto úvah mohou plynout závěry pro projektanta databáze? Viděli jsme, že pokrývání závislostmi lze dosáhnout obtížně. Co však je reálné a mohlo by být jedním z cílů návrhu, je bezztrátová dekompozice. Protože dekomponujeme proto, aby výsledkem byla schémata alespoň ve 3NF, snažíme se separovat závislost od klíče (klíčů) schématu. Použití výše uvedeného tvrzení je přímočaré a máme záruku, že dekompozice je do jisté míry korektní.

Nenechme se zmýlit představou, že “selským rozumem” se vše vyřeší. Svět může být složitý a hlavně neznámý. Dekompozice je vlastně o tom, jak rozložit data do smysluplných tabulek. A to jde většinou mnoha způsoby. Jen některé z nich však jsou správné, tj. splňují jistá kritéria korektnosti.



<seznam dílů seriálu>   <COMPUTERWORLD>