Armstrongovy axiomy - Armstrongs axioms - Wikipedia

Armstrongovy axiomy jsou souborem odkazů (nebo přesněji odvozovací pravidla ) slouží k odvození všech funkční závislosti na relační databáze. Byly vyvinuty William W. Armstrong ve svém příspěvku z roku 1974.^[1] Axiomy jsou zvuk při generování pouze funkčních závislostí v uzavření sady funkčních závislostí (označených jako ${ displaystyle F ^ {+}}$) při použití na tuto sadu (označeno jako ${ displaystyle F}$). Jsou taky kompletní v tom opakované použití těchto pravidel vygeneruje všechny funkční závislosti v závěru ${ displaystyle F ^ {+}}$.

Více formálně, pojďme ${ displaystyle langle R (U), F rangle}$ označují relační schéma nad množinou atributů ${ displaystyle U}$ se sadou funkčních závislostí ${ displaystyle F}$. Říkáme, že funkční závislost ${ displaystyle f}$ logicky implikuje ${ displaystyle F}$a označte to pomocí ${ displaystyle F modely f}$ právě když pro každou instanci ${ displaystyle r}$ z ${ displaystyle R}$ který splňuje funkční závislosti v ${ displaystyle F}$, ${ displaystyle r}$ také uspokojuje ${ displaystyle f}$. Označujeme ${ displaystyle F ^ {+}}$ sada všech funkčních závislostí, z nichž logicky vyplývá ${ displaystyle F}$.

Dále s ohledem na soubor odvozovacích pravidel ${ displaystyle A}$, říkáme, že funkční závislost ${ displaystyle f}$ je odvozitelný z funkčních závislostí v ${ displaystyle F}$ sadou pravidel odvození ${ displaystyle A}$a označujeme to ${ displaystyle F vdash _ {A} f}$ kdyby a jen kdyby ${ displaystyle f}$ je možné získat opakovaným uplatňováním odvozovacích pravidel v ${ displaystyle A}$ na funkční závislosti v ${ displaystyle F}$. Označujeme ${ displaystyle F_ {A} ^ {*}}$ sada všech funkčních závislostí, z nichž lze odvodit ${ displaystyle F}$ podle pravidel odvození v ${ displaystyle A}$.

Pak sada odvozovacích pravidel ${ displaystyle A}$ je zvuk právě tehdy, když platí toto:

${ displaystyle F_ {A} ^ {*} subseteq F ^ {+}}$

to znamená, že nemůžeme odvodit pomocí ${ displaystyle A}$ funkční závislosti, které nejsou logicky implikovány ${ displaystyle F}$Sada pravidel odvození ${ displaystyle A}$ se říká, že je kompletní, pokud platí:

${ displaystyle F ^ {+} subseteq F_ {A} ^ {*}}$

jednodušeji řečeno, jsme schopni odvodit ${ displaystyle A}$ všechny funkční závislosti, z nichž logicky vyplývá ${ displaystyle F}$.

Axiomy (primární pravidla)

Nechat ${ displaystyle R (U)}$ být relačním schématem nad množinou atributů ${ displaystyle U}$. Od nynějška budeme označovat písmeny ${ displaystyle X}$, ${ displaystyle Y}$, ${ displaystyle Z}$ jakákoli podmnožina ${ displaystyle U}$ a zkrátka spojení dvou sad atributů ${ displaystyle X}$ a ${ displaystyle Y}$ podle ${ displaystyle XY}$ místo obvyklých ${ displaystyle X cup Y}$; tato notace je spíše standardní teorie databáze při práci se sadami atributů.

Axiom reflexivity

Li ${ displaystyle X}$ je sada atributů a ${ displaystyle Y}$ je podmnožinou ${ displaystyle X}$, pak ${ displaystyle X}$ drží ${ displaystyle Y}$. Tímto, ${ displaystyle X}$ drží ${ displaystyle Y}$ [${ displaystyle X až Y}$] znamená, že ${ displaystyle X}$ funkčně určuje ${ displaystyle Y}$.

Li ${ displaystyle Y subseteq X}$ pak ${ displaystyle X až Y}$.

Axiom augmentace

Li ${ displaystyle X}$ drží ${ displaystyle Y}$ a ${ displaystyle Z}$ je tedy sada atributů ${ displaystyle XZ}$ drží ${ displaystyle YZ}$. To znamená, že atribut v závislostech nemění základní závislosti.

Li ${ displaystyle X až Y}$, pak ${ displaystyle XZ až YZ}$ pro všechny ${ displaystyle Z}$.

Axiom přechodnosti

Li ${ displaystyle X}$ drží ${ displaystyle Y}$ a ${ displaystyle Y}$ drží ${ displaystyle Z}$, pak ${ displaystyle X}$ drží ${ displaystyle Z}$.

Li ${ displaystyle X až Y}$ a ${ displaystyle Y až Z}$, pak ${ displaystyle X až Z}$.

Další pravidla (sekundární pravidla)

Tato pravidla lze odvodit z výše uvedených axiomů.

Rozklad

Li ${ displaystyle X to YZ}$ pak ${ displaystyle X až Y}$ a ${ displaystyle X až Z}$.

Důkaz

1. ${ displaystyle X to YZ}$	(Dáno)
2. ${ displaystyle YZ až Y}$	(Reflexivita)
3. ${ displaystyle X až Y}$	(Přechodnost 1 a 2)

Složení

Li ${ displaystyle X až Y}$ a ${ displaystyle A až B}$ pak ${ displaystyle XA to YB}$.

Důkaz

1. ${ displaystyle X až Y}$	(Dáno)
2. ${ displaystyle A až B}$	(Dáno)
3. ${ displaystyle XA to YA}$	(Augmentation of 1 & A)
4. ${ displaystyle XA až Y}$	(Rozklad 3)
5. ${ displaystyle XA až XB}$	(Augmentace 2 a X)
6. ${ displaystyle XA do B}$	(Rozklad 5)
7. ${ displaystyle XA to YB}$	(Unie 4 a 6)

Union (notace)

Li ${ displaystyle X až Y}$ a ${ displaystyle X až Z}$ pak ${ displaystyle X to YZ}$.

Pseudo tranzitivita

Li ${ displaystyle X až Y}$ a ${ displaystyle YZ to W}$ pak ${ displaystyle XZ to W}$.

Důkaz

1. ${ displaystyle X až Y}$	(Dáno)
2. ${ displaystyle YZ to W}$	(Dáno)
3. ${ displaystyle XZ až YZ}$	(Augmentation of 1 & Z)
4. ${ displaystyle XZ to W}$	(Přechodnost 3 a 2)

Sebeurčení

${ displaystyle I to I}$ pro všechny ${ displaystyle I}$. To vyplývá přímo z axiomu reflexivity.

Rozsáhlost

Následující vlastnost je speciální případ augmentace, když ${ displaystyle Z = X}$.

Li ${ displaystyle X až Y}$, pak ${ displaystyle X až XY}$.

Extensivita může nahradit augmentaci jako axiom v tom smyslu, že augmentaci lze dokázat z extenzivity společně s ostatními axiomy.

Důkaz

1. ${ displaystyle XZ až X}$	(Reflexivita)
2. ${ displaystyle X až Y}$	(Dáno)
3. ${ displaystyle XZ až Y}$	(Přechodnost 1 a 2)
4. ${ displaystyle XZ až XYZ}$	(Rozsáhlost 3)
5. ${ displaystyle XYZ až YZ}$	(Reflexivita)
6. ${ displaystyle XZ až YZ}$	(Přechodnost 4 a 5)

Armstrongův vztah

Vzhledem k souboru funkčních závislostí ${ displaystyle F}$, an Armstrongův vztah je vztah, který uspokojuje všechny funkční závislosti v závěru ${ displaystyle F ^ {+}}$ a jen ty závislosti. Bohužel Armstrongův poměr minimální velikosti pro danou sadu závislostí může mít velikost, která je exponenciální funkcí počtu atributů v uvažovaných závislostech.^[2]

Reference

externí odkazy

• UMBC CMSC 461 jaro '99
• CS345 Lecture Notes from Stanford University