Funkční závislost - Functional dependency

v relační databáze teorie, a funkční závislost je omezení mezi dvěma sadami atributů v a vztah z databáze. Jinými slovy, funkční závislost je omezením mezi dvěma klíči R, sada atributů X v R říká se funkčně určit další sada atributů Y, také v R, (psaný X → Y) pokud, a pouze pokud, každý X hodnota v R je spojen s právě jedním Y hodnota v R; R pak se říká uspokojit funkční závislost X → Y. Ekvivalentně projekce ${ displaystyle Pi _ {X, Y} R}$ je funkce, tj. Y je funkce X.^[1]^[2] Jednoduše řečeno, pokud jsou hodnoty pro X atributy jsou známé (řekněme, že jsou) X), pak hodnoty pro Y atributy odpovídající X lze určit jejich vyhledáním v žádný n-tice z R obsahující X. Obvykle X se nazývá určující nastavit a Y the závislý soubor. Funkční závislost FD: X → Y je nazýván triviální -li Y je podmnožina z X.

Jinými slovy, závislost FD: X → Y znamená, že hodnoty Y jsou určeny hodnotami X. Dvě n-tice sdílející stejné hodnoty X bude nutně mít stejné hodnoty Y.

Stanovení funkčních závislostí je důležitou součástí navrhování databází v EU relační model a v normalizace databáze a denormalizace. Jednoduchá aplikace funkčních závislostí je Heathova věta; říká, že vztah R přes sadu atributů U a uspokojení funkční závislosti X → Y lze bezpečně rozdělit na dva vztahy, které mají bezztrátový rozklad majetek, jmenovitě do ${ displaystyle Pi _ {XY} (R) bowtie Pi _ {XZ} (R) = R}$ kde Z = U − XY jsou zbytek atributů. (Odbory sad atributů se v teorii databází obvykle označuje pouhými juxtapozicemi.) Důležitým pojmem v této souvislosti je klíč kandidáta, definovaný jako minimální sada atributů, které funkčně určují všechny atributy ve vztahu. Funkční závislosti spolu s atributové domény, jsou vybrány tak, aby generovaly omezení, která by vylučovala tolik dat nevhodných pro uživatelská doména ze systému.

Pojem logická implikace je definován pro funkční závislosti následujícím způsobem: sada funkčních závislostí ${ displaystyle Sigma}$ logicky implikuje další sadu závislostí ${ displaystyle Gamma}$ , pokud existuje nějaký vztah R uspokojení všech závislostí od ${ displaystyle Sigma}$ také splňuje všechny závislosti od ${ displaystyle Gamma}$ ; to je obvykle psáno ${ displaystyle Sigma modely Gamma}$ . Pojem logické implikace pro funkční závislosti připouští a zvuk a kompletní konečný axiomatizace, známý jako Armstrongovy axiomy.

Příklady

Auta

Předpokládejme, že jeden navrhuje systém pro sledování vozidel a kapacity jejich motorů. Každé vozidlo má svůj vlastní identifikační číslo vozidla (VIN). Jeden by psal VIN → Kapacita motoru protože by bylo nevhodné, aby motor vozidla měl více než jednu kapacitu. (Za předpokladu, v tomto případě, že vozidla mají pouze jeden motor.) Na druhou stranu, Kapacita motoru → VIN je nesprávné, protože by mohlo být mnoho vozidel se stejným objemem motoru.

Tato funkční závislost může navrhnout, aby byl atribut EngineCapacity umístěn ve vztahu s klíč kandidáta VIN. To však nemusí být vždy vhodné. Například pokud k této funkční závislosti dojde v důsledku tranzitivní funkční závislosti VIN → VehicleModel a VehicleModel → EngineCapacity, které by neměly za následek normalizovaný vztah.

Přednášky

Tento příklad ilustruje koncept funkční závislosti. Modelována je situace vysokoškolských studentů, kteří navštěvují jednu nebo více přednášek, na každé z nich je přidělen asistent učitele (TA). Dále předpokládejme, že každý student je v nějakém semestru a je identifikován jedinečným celočíselným ID.

ID studenta	Semestr	Přednáška	TA
1234	6	Numerické metody	John
1221	4	Numerické metody	Kovář
1234	6	Vizuální výpočty	Bob
1201	2	Numerické metody	Petr
1201	2	Fyzika II	Simone

Všimli jsme si, že kdykoli dva řádky v této tabulce obsahují stejné StudentID, musí mít nutně stejné hodnoty Semestru. Tento základní fakt lze vyjádřit funkční závislostí:

StudentID → Semestr.

Všimněte si, že pokud byl přidán řádek, kde měl student jinou hodnotu semestru, funkční závislost, FD, by už neexistovala. To znamená, že FD je implikováno daty, protože je možné mít hodnoty, které by FD zneplatnily.

Lze identifikovat další netriviální funkční závislosti, například:

{StudentID, Lecture} → TA
{StudentID, Lecture} → {TA, Semester}

Ten vyjadřuje skutečnost, že množina {StudentID, Lecture} je a superklíč vztahu.

Model zaměstnaneckého oddělení

Klasickým příkladem funkční závislosti je model oddělení zaměstnanců.

ID zaměstnance	Jméno zaměstnance	ID oddělení	Název oddělení
0001	John Doe	1	Lidské zdroje
0002	Jane Doe	2	Marketing
0003	John Smith	1	Lidské zdroje
0004	Jane Goodall	3	Odbyt

Tento případ představuje příklad, kdy je více funkčních závislostí vloženo do jedné reprezentace dat. Vzhledem k tomu, že zaměstnancem může být pouze člen jednoho oddělení, určuje toto oddělení jedinečné ID tohoto zaměstnance.

ID zaměstnance → Jméno zaměstnance
ID zaměstnance → ID oddělení

Kromě tohoto vztahu má tabulka také funkční závislost prostřednictvím neklíčového atributu

ID oddělení → Název oddělení

Tento příklad ukazuje, že i když existuje ID zaměstnance FD → ID oddělení - ID zaměstnance by nebylo logickým klíčem pro určení ID oddělení. Proces normalizace dat by rozpoznal všechny FD a umožnil návrháři postavit tabulky a vztahy, které jsou logičtější na základě dat.

Vlastnosti a axiomatizace funkčních závislostí

Vzhledem k tomu X, Y, a Z jsou sady atributů ve vztahu R, lze odvodit několik vlastností funkčních závislostí. Mezi nejdůležitější patří následující, obvykle nazývané Armstrongovy axiomy:^[3]

Reflexivita: Pokud Y je podmnožinou X, pak X → Y
Augmentace: Pokud X → Y, pak XZ → YZ
Přechodnost: Pokud X → Y a Y → Z, pak X → Z

„Reflexivita“ může být oslabena na spravedlivou ${ displaystyle X rightarrow varnothing}$ , tj. je to skutečný axiom kde jsou další dva správné odvozovací pravidla, přesněji vznikající následující pravidla syntaktických důsledků:^[4]

${ displaystyle vdash X rightarrow varnothing}$
${ displaystyle X rightarrow Y vdash XZ rightarrow YZ}$
${ displaystyle X rightarrow Y, Y rightarrow Z vdash X rightarrow Z}$ .

Tato tři pravidla jsou a zvuk a kompletní axiomatizace funkčních závislostí. Tato axiomatizace je někdy popisována jako konečná, protože počet odvozovacích pravidel je konečný,^[5] s výhradou, že axiom a pravidla závěru jsou všechna schémata, což znamená, že X, Y a Z rozsah přes všechny základní pojmy (sady atributů).^[4]

Z těchto pravidel můžeme odvodit tato sekundární pravidla:^[3]

svaz: Pokud X → Y a X → Z, pak X → YZ
Rozklad: Pokud X → YZ, pak X → Y a X → Z
Pseudotranzitivita: Pokud X → Y a WY → Z, pak WX → Z

Pravidla sjednocení a rozkladu lze kombinovat v a logická ekvivalence s uvedením tohoX → YZ, drží iff X → Y a X → Z. Toto se někdy nazývá pravidlo rozdělení / kombinování.^[6]

Další pravidlo, které je někdy užitečné, je:^[7]

Složení: Pokud X → Y a Z → Ž, pak XZ → YW

Uzavření funkční závislosti

Uzávěr je v podstatě úplná sada hodnot, které lze určit ze sady známých hodnot pro daný vztah pomocí jeho funkčních závislostí. Jeden používá Armstrongovy axiomy poskytnout důkaz - tj. reflexivitu, augmentaci, tranzitivitu.

Dáno ${ displaystyle R}$ a ${ displaystyle F}$ sada FD, která drží ${ displaystyle R}$ : Uzavření ${ displaystyle F}$ v ${ displaystyle R}$ (označeno ${ displaystyle F}$ ⁺) je sada všech FD, z nichž logicky vyplývá ${ displaystyle F}$ .

Uzavření sady atributů

Uzavření sady atributů X vzhledem k ${ displaystyle F}$ je množina X⁺ allattributů, které jsou funkčně určeny pomocí X pomocí ${ displaystyle F}$ ⁺.

Příklad

Představte si následující seznam FD. Z tohoto vztahu budeme počítat uzávěr pro A.

1. A → B
2. B → C
3. AB → D

Uzávěr by byl následující:

a) A → A (podle Armstrongovy reflexivity)
b) A → AB (podle 1. a (a))
c) A → ABD (podle (b), 3 a Armstrongova tranzitivita)
d) A → ABCD (podle (c) a 2)

Uzávěr je tedy A → ABCD. Výpočtem uzavření A jsme ověřili, že A je také dobrým kandidátským klíčem, protože jeho uzavření je každá jednotlivá hodnota dat ve vztahu.

Kryty a rovnocennost

Kryty

Definice: ${ displaystyle F}$ kryty ${ displaystyle G}$ pokud každý FD v ${ displaystyle G}$ lze odvodit z ${ displaystyle F}$ . ${ displaystyle F}$ kryty ${ displaystyle G}$ -li ${ displaystyle G}$ ⁺ ⊆ ${ displaystyle F}$ ⁺
Každá sada funkčních závislostí má a kanonický obal.

Ekvivalence dvou sad FD

Dvě sady FD ${ displaystyle F}$ a ${ displaystyle G}$ přes schéma ${ displaystyle R}$ jsou rovnocenné, písemné ${ displaystyle F}$ ≡ ${ displaystyle G}$ , pokud ${ displaystyle F}$ ⁺ = ${ displaystyle G}$ ⁺. Li ${ displaystyle F}$ ≡ ${ displaystyle G}$ , pak ${ displaystyle F}$ je kryt pro ${ displaystyle G}$ a naopak. Jinými slovy se nazývají ekvivalentní sady funkčních závislostí kryty navzájem.

Neredundantní kryty

Sada ${ displaystyle F}$ FD není zbytečné, pokud neexistuje správná podmnožina ${ displaystyle F '}$ z ${ displaystyle F}$ s ${ displaystyle F '}$ ≡ ${ displaystyle F}$ . Pokud takový ${ displaystyle F '}$ existuje, ${ displaystyle F}$ je nadbytečné. ${ displaystyle F}$ je nepotřebný kryt pro ${ displaystyle G}$ -li ${ displaystyle F}$ je kryt pro ${ displaystyle G}$ a ${ displaystyle F}$ není nepotřebný.
Je to alternativní charakterizace nepotřebnosti ${ displaystyle F}$ není zbytečné, pokud neexistuje FD X → Y v ${ displaystyle F}$ takhle ${ displaystyle F}$ - {X → Y} ${ displaystyle models}$ X → Y. Zavolejte FD X → Y v ${ displaystyle F}$ nadbytečný v ${ displaystyle F}$ -li ${ displaystyle F}$ - {X → Y} ${ displaystyle models}$ X → Y.

Aplikace k normalizaci

Heathova věta

Důležitou vlastností (poskytující okamžitou aplikaci) funkčních závislostí je, že pokud R je vztah se sloupci pojmenovanými z nějaké sady atributů U a R uspokojuje určitou funkční závislost X → Y pak ${ displaystyle R = Pi _ {XY} (R) motýlek Pi _ {XZ} (R)}$ kde Z = U − XY. Intuitivně, pokud funkční závislost X → Y drží se R, pak lze vztah bezpečně rozdělit na dva vztahy vedle sloupce X (což je klíč pro ${ displaystyle Pi _ {XY} (R) motýlek Pi _ {XZ} (R)}$ ) zajištění, že když se obě části spojí zpět, neztratí se žádná data, tj. funkční závislost poskytuje jednoduchý způsob konstrukce a bezztrátový rozklad rozkladu z R ve dvou menších vztazích. Tato skutečnost se někdy nazývá Heathsova věta; je to jeden z prvních výsledků v teorii databází.^[8]

Heathova věta skutečně říká, že můžeme vytáhnout hodnoty Y z velkého vztahu R a uložit je do jednoho, ${ displaystyle Pi _ {XY} (R)}$ , který nemá žádná opakování hodnot v řádku pro X a je ve skutečnosti vyhledávací tabulka pro Y klíčováno uživatelem X a následně má pouze jedno místo pro aktualizaci Y odpovídající každému X na rozdíl od „velkého“ vztahu R kde je potenciálně mnoho kopií každého z nich X, každý s kopií Y které je třeba při aktualizacích synchronizovat. (Toto odstranění nadbytečnosti je výhodou v OLTP kontexty, kde se očekává mnoho změn, ale ne tolik v OLAP kontexty, které zahrnují převážně dotazy.) Heathův rozklad ponechává pouze X jednat jako cizí klíč ve zbytku velkého stolu ${ displaystyle Pi _ {XZ} (R)}$ .

Funkční závislosti by však neměly být zaměňovány závislosti na začlenění, což je formalismus pro cizí klíče; i když se používají pro normalizaci, funkční závislosti vyjadřují omezení nad jedním vztahem (schématem), zatímco závislosti závislostí vyjadřují omezení mezi relačními schématy v databázové schéma. Navíc se tyto dva pojmy v EU ani neprotínají klasifikace závislostí: funkční závislosti jsou závislosti vytvářející rovnost zatímco závislosti na začlenění jsou závislosti generující n-tici. Prosazování referenčních omezení po dekompozici (normalizaci) schématu relace vyžaduje nový formalismus, tj. Závislosti na začlenění. V rozkladu vyplývajícím z Heathovy věty nic nebrání vložení n-tic dovnitř ${ displaystyle Pi _ {XZ} (R)}$ s určitou hodnotou X nebyl nalezen v ${ displaystyle Pi _ {XY} (R)}$ .

Normální formy

Normální formy jsou normalizace databáze úrovně, které určují „dobrotu“ tabulky. Obecně platí, že třetí normální forma je považován za „dobrý“ standard pro relační databázi.^{[Citace je zapotřebí ]}

Normalizace si klade za cíl osvobodit databázi od anomálií aktualizace, vkládání a mazání. Rovněž zajišťuje, že při zavedení nové hodnoty do relace bude mít minimální vliv na databázi, a tedy minimální účinek na aplikace využívající databázi.^{[Citace je zapotřebí ]}

Neredukovatelná funkce v závislosti na sadě

Sada S funkčních závislostí je neredukovatelná, pokud má sada následující tři vlastnosti:

Každá správná sada funkční závislosti S obsahuje pouze jeden atribut.
Každá levá sada funkční závislosti S je neredukovatelná. To znamená, že zmenšení kteréhokoli atributu z levé sady změní obsah S (S ztratí některé informace).
Snížení jakékoli funkční závislosti změní obsah S.

Sady funkčních závislostí s těmito vlastnostmi se také nazývají kanonický nebo minimální. Nalezení takové sady S funkčních závislostí, která je ekvivalentní nějaké vstupní sadě S 'poskytované jako vstup, se nazývá hledání a minimální krytí z S ': tento problém lze vyřešit v polynomiálním čase.^[9]

Viz také

Reference

^ Terry Halpin (2008). Informační modelování a relační databáze (2. vyd.). Morgan Kaufmann. str. 140. ISBN 978-0-12-373568-3.
^ Chris Date (2012). Návrh databáze a relační teorie: Normální formy a All That Jazz. O'Reilly Media, Inc. str. 21. ISBN 978-1-4493-2801-6.
^ ^A ^b Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Koncepty databázového systému (6. vydání). McGraw-Hill. str. 339. ISBN 978-0-07-352332-3.
^ ^A ^b M. Y. Vardi. Základy teorie závislosti. E. Borger, editor, Trends in TheoreticalComputer Science, strany 171–224. Computer Science Press, Rockville, MD, 1987. ISBN 0881750840
^ Abiteboul, Serge; Hull, Richard B.; Vianu, Victor (1995), Základy databází, Addison-Wesley, str.164–168, ISBN 0-201-53771-0
^ Hector Garcia-Molina; Jeffrey D. Ullman; Jennifer Widom (2009). Databázové systémy: celá kniha (2. vyd.). Pearson Prentice Hall. str. 73. ISBN 978-0-13-187325-4.
^ S. K. Singh (2009) [2006]. Databázové systémy: koncepty, design a aplikace. Pearson Education India. str. 323. ISBN 978-81-7758-567-4.
^
Heath, I. J. (1971). Msgstr "Nepřijatelné operace se soubory v relační databázi". Sborník workshopů ACM SIGFIDET (nyní SIGMOD) z roku 1971 o popisu, přístupu a kontrole dat - SIGFIDET '71. 19–33. doi:10.1145/1734714.1734717. citováno v:
- Ronald Fagin a Moshe Y. Vardi (1986). „Theory of Data Dependencies - A Survey“. V Michael Anshel a William Gewirtz (ed.). Matematika zpracování informací: [krátký kurz konaný v Louisville, Kentucky, 23. – 24. Ledna 1984]. American Mathematical Soc. str.23. ISBN 978-0-8218-0086-7.
- C. Datum (2005). Databáze do hloubky: relační teorie pro odborníky. O'Reilly Media, Inc. str. 142. ISBN 978-0-596-10012-4.
^ Meier, Daniel (1980). Msgstr "Minimální krytí v modelu relační databáze". Deník ACM. doi:10.1145/322217.322223.

externí odkazy

Gary Burt (léto 1999). „Poznámky k přednášce CS 461 (Database Management Systems)“. University of Maryland Baltimore County Ústav výpočetní techniky a elektrotechniky.
Jeffrey D. Ullman. „Poznámky k přednášce CS345“ (PostScript ). Stanfordská Univerzita.
Osmar Zaiane (9. června 1998). „Kapitola 6: Omezení integrity“. Skripty CMPT 354 (Database Systems I). Univerzita Simona Frasera Ústav výpočetní techniky.

[HalpinMorgan2008-1] Terry Halpin (2008). Informační modelování a relační databáze (2. vyd.). Morgan Kaufmann. str. 140. ISBN 978-0-12-373568-3.

[Date2012-2] Chris Date (2012). Návrh databáze a relační teorie: Normální formy a All That Jazz. O'Reilly Media, Inc. str. 21. ISBN 978-1-4493-2801-6.

[SilberschatzKorth2010a-3] A ^b Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Koncepty databázového systému (6. vydání). McGraw-Hill. str. 339. ISBN 978-0-07-352332-3.

[Vardi-4] A ^b M. Y. Vardi. Základy teorie závislosti. E. Borger, editor, Trends in TheoreticalComputer Science, strany 171–224. Computer Science Press, Rockville, MD, 1987. ISBN 0881750840

[alice-5] Abiteboul, Serge; Hull, Richard B.; Vianu, Victor (1995), Základy databází, Addison-Wesley, str.164–168, ISBN 0-201-53771-0

[Garcia-MolinaUllman2009-6] Hector Garcia-Molina; Jeffrey D. Ullman; Jennifer Widom (2009). Databázové systémy: celá kniha (2. vyd.). Pearson Prentice Hall. str. 73. ISBN 978-0-13-187325-4.

[Singh2009-7] S. K. Singh (2009) [2006]. Databázové systémy: koncepty, design a aplikace. Pearson Education India. str. 323. ISBN 978-81-7758-567-4.

[8] Heath, I. J. (1971). Msgstr "Nepřijatelné operace se soubory v relační databázi". Sborník workshopů ACM SIGFIDET (nyní SIGMOD) z roku 1971 o popisu, přístupu a kontrole dat - SIGFIDET '71. 19–33. doi:10.1145/1734714.1734717. citováno v:
Ronald Fagin a Moshe Y. Vardi (1986). „Theory of Data Dependencies - A Survey“. V Michael Anshel a William Gewirtz (ed.). Matematika zpracování informací: [krátký kurz konaný v Louisville, Kentucky, 23. – 24. Ledna 1984]. American Mathematical Soc. str.23. ISBN 978-0-8218-0086-7.
C. Datum (2005). Databáze do hloubky: relační teorie pro odborníky. O'Reilly Media, Inc. str. 142. ISBN 978-0-596-10012-4.

[9] Ronald Fagin a Moshe Y. Vardi (1986). „Theory of Data Dependencies - A Survey“. V Michael Anshel a William Gewirtz (ed.). Matematika zpracování informací: [krátký kurz konaný v Louisville, Kentucky, 23. – 24. Ledna 1984]. American Mathematical Soc. str.23. ISBN 978-0-8218-0086-7.

[10] C. Datum (2005). Databáze do hloubky: relační teorie pro odborníky. O'Reilly Media, Inc. str. 142. ISBN 978-0-596-10012-4.

[9] Meier, Daniel (1980). Msgstr "Minimální krytí v modelu relační databáze". Deník ACM. doi:10.1145/322217.322223.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]