Funkční závislost (programování)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 30. června 2018; kontroly vyžadují 13 úprav .

Funkční závislost je binární vztah mezi sadami atributů daného vztahu a je ve skutečnosti vztahem jedna k mnoha. Jeho použití je způsobeno tím, že umožňuje formálně a striktně řešit mnoho problémů.

Funkční závislost je koncept, který je základem mnoha problémů souvisejících s relačními databázemi , včetně zejména jejich návrhu.

Definice

Funkční závislost

Nechť je vztah uveden se schématem (záhlavím) , a jsou některé podmnožiny sady atributů vztahu . Množina je funkčně závislá na tom, zda a pouze je každá hodnota množiny spojena s právě jednou hodnotou množiny . Určeno . $r$ $R$ $A$ $B$ $r$ $B$ $A$ $A$ $B$ $A až B$

Jinými slovy, pokud dvě n-tice mají stejnou hodnotu v , pak mají stejnou hodnotu v . $A$ $B$

r\left(R\right),\ A\subseteq R,\ B\subseteq R

\left(A\to B\right)\Leftrightarrow \left(\left(\forall {{t}_{1}},{{t}_{2}}\in r:{{t} _{1}}\left(A\right)={{t}_{2}}\left(A\right)\right)\Rightarrow \left({{t}_{1}}\left(B \right)={{t}_{2}}\left(B\right)\right)\right)

V tomto případě je determinantem závislá část. $A$ $B$

O funkční závislosti se říká , že je triviální , pokud je závislá část podmnožinou determinantu.

\left(B\subseteq A\right)\Rightarrow \left(A\to B\right)

Uzavření sady závislostí

Některé funkční závislosti mohou znamenat jiné funkční závislosti. Například funkční závislost,

\left(A\to B\right)\wedge \left(B\to C\right)\Rightarrow \left(A\to C\right)

Množina všech funkčních závislostí, které jsou implikovány danou sadou funkčních závislostí, se nazývá uzávěr množiny . ${{S}^{+}}$ $S$ $S$

Uzavření sady atributů

Dovolit být nějaký soubor atributů vztahu , a být soubor funkčních závislostí tohoto vztahu. Uzávěr množiny atributů v mezích je takový soubor všech atributů relace , že funkční závislost je členem uzávěru . $Z$ $r$ $S$ ${{Z}^{+}}$ $Z$ $S$ ${{A}_{i))$ $r$ $Z\to {{A}_{i))$ ${{S}^{+}}$

r\left(R\right),\ S,\ Z\subseteq R,\ {{A}_{i}}\subseteq R,\ i={\overline {1,n}}

{{Z}^{+}}=\left\{{{A}_{i}}:\left(Z\to {{A}_{i}}\right)\in {{S }^{+}}\right\}

Neredukovatelné sady závislostí

Nechť a být nějaké množiny funkčních závislostí. ${{S}_{1}}$ ${{S}_{2))$

Pokud nějaká funkční závislost z vstoupí a do , pak se nazývá kryt množiny funkčních závislostí . ${{S}_{1}}$ ${{S}_{2}^{+}}$ ${{S}_{2))$ ${{S}_{1}}$
Jestliže je kryt pro , a je kryt pro (tj. ), pak se takové množiny nazývají ekvivalentní . ${{S}_{2))$ ${{S}_{1}}$ ${{S}_{1}}$ ${{S}_{2))$ ${\displaystyle S_{1}^{+}=S_{2}^{+))$
O množině funkčních závislostí se říká, že je neredukovatelná tehdy a pouze tehdy, jsou-li splněny následující podmínky: $S$
- V každé funkční závislosti obsahuje závislá část pouze jeden prvek;
- Determinant každé funkční závislosti je neredukovatelný (žádný atribut nelze z determinantu odstranit bez změny uzávěru ); ${{S}^{+}}$
- Žádnou z funkčních závislostí nelze odstranit bez změny uzávěru . $S$ ${{S}^{+}}$
Pro jakoukoli sadu funkčních závislostí existuje alespoň jedna ekvivalentní sada, která je neredukovatelná. Takový ekvivalentní soubor se nazývá neredukovatelný kryt .

Hodnocení uzávěrky

Armstrongova odvozená pravidla

V roce 1974 William Armstrong navrhl soubor pravidel pro vyvozování nových funkčních závislostí z dat.

Řekněme, že máme vztah a sadu atributů . Pro zkrácení záznamu napíšeme místo toho jednoduše . $r\left(R\right)$ $A,B,C,D\subseteq R$ $X\cup Y$ $XY$

Reflexivita : $\left(B\subseteq A\right)\Rightarrow \left(A\to B\right)$
Doplnění : $\left(A\to B\right)\Rightarrow \left(AC\to BC\right)$
Přechodnost : $\left(A\to B\right)\wedge \left(B\to C\right)\Rightarrow \left(A\to C\right)$

Armstrongova inferenční pravidla jsou úplná (s jejich pomocí lze odvodit všechny ostatní funkční závislosti implikované danou množinou) a spolehlivá (nelze odvodit „nadbytečné“ funkční závislosti: odvozená funkční závislost platí všude tam, kde byly původní funkční závislosti (ze kterých byla odvozené) jsou platné).

Kromě toho je z těchto pravidel zcela jednoduše odvozeno několik dalších pravidel, která zjednodušují úlohu odvození funkčních závislostí.

Sebeurčení : $A\to A$
rozklad : $\left(A\to BC\right)\Rightarrow \left(A\to B\right)\wedge \left(A\to C\right)$
konsolidace : $\left(A\to B\right)\wedge \left(A\to C\right)\Rightarrow \left(A\to BC\right)$
Složení : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(AC\to BD\right)$
Darwenova věta o univerzálním sjednocení : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(A\cup \left(CB\right)\to BD\right)$

Věta: Funkční závislost je odvozena z dané sady funkčních závislostí podle Armstrongových inferenčních pravidel tehdy a jen tehdy, když . $A až B$ $S$ $B\subseteq {{A}^{+}}$

Uzavření sady atributů

Pokud aplikujeme pravidla z předchozí části, dokud se vytváření nových funkčních závislostí samo nezastaví, pak dostaneme uzavření pro danou sadu funkčních závislostí. V praxi je málokdy nutné tuto uzávěrku vypočítat samostatně, nejčastěji nás mnohem více zajímá, zda bude do uzávěrky zahrnuta ta či ona funkční závislost. K tomu nám stačí vypočítat uzávěr determinantu. Na to existuje poměrně jednoduchý algoritmus.

Nechť je souborem atributů, které se nakonec stanou uzavřením. $X$
Hledáme funkční závislosti formuláře , where , a . Závislou část každé nalezené závislosti přidáme do . ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\to C$ ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\subseteq X$ $C\not \subset X$ $X$
Opakujte krok 2, dokud nebude možné přidat atributy do sady. $X$
Sada , ke které nelze přidat žádné atributy, bude uzávěrkou. $X$

Aplikace

Návrh databáze

Funkční závislosti jsou omezení integrity a definují sémantiku dat uložených v databázi. Při každé aktualizaci musí DBMS zkontrolovat jejich soulad. Proto je přítomnost velkého množství funkčních závislostí nežádoucí, jinak zpomaluje práci. Pro zjednodušení úlohy je nutné zredukovat sadu funkčních závislostí na požadované minimum.

Pokud je neredukovatelné krytí počáteční sady funkčních závislostí , pak kontrola splnění funkčních závislostí od automaticky zaručuje splnění všech funkčních závislostí od . Úkol najít minimální potřebnou množinu se tak redukuje na nalezení neredukovatelného krytu množiny funkčních závislostí, který bude použit místo původní množiny. $já$ $S$ $já$ $S$

Viz také

Relační datový model
Návrh databáze
normální forma
Vícehodnotová závislost je zobecněním funkční závislosti.

Literatura

K. J. Datum. Úvod do databázových systémů = Introduction to Database Systems. - 8. vyd. - M .: "Williams" , 2006. - S. 1328. - ISBN 0-321-19784-4 .