Axiomele lui Armstrong

Definiție

În teoria proiectării bazelor de date , Axiomele lui Armstrong , formalizate în 1974 , constituie un set de reguli care ne permit să înțelegem implicațiile logice care există între dependențele funcționale . Axiomele lui Armstrong sunt de reflexivitate , creștere și tranzitivitate . În toate cazurile, se presupune că se ia în considerare o schemă de relații cu un set de atribute $U$ ${\ displaystyle U}$ $U$ , cu $U$ ${\ displaystyle U}$ $U$ setul universal de atribute și un set $F.$ ${\ displaystyle F}$ $F.$ a dependențelor funcționale care implică numai atribute ale $U$ ${\ displaystyle U}$ $U$ .

Axioma reflexivității

De sine $Y\subseteq X\subseteq U$ ${\ displaystyle Y \ subseteq X \ subseteq U}$ ${\ displaystyle Y \ subseteq X \ subseteq U}$ asa de $X\to Y$ ${\ displaystyle X \ to Y}$ $X \ to Y$ este implicit logic de $F.$ ${\ displaystyle F}$ $F.$ .

Axioma creșterii

Dacă contează $X\to Y$ ${\ displaystyle X \ to Y}$ ${\ displaystyle X \ to Y}$ Și $Z$ ${\ displaystyle Z}$ $Z$ este orice subset de $U$ ${\ displaystyle U}$ $U$ asa de $XZ\to YZ$ ${\ displaystyle XZ \ to YZ}$ ${\ displaystyle XZ \ to YZ}$ .

Axioma tranzitivității

De sine $X\to Y$ ${\ displaystyle X \ to Y}$ $X \ to Y$ Și $Y\to Z$ ${\ displaystyle Y \ to Z}$ ${\ displaystyle Y \ to Z}$ asa de $X\to Z$ ${\ displaystyle X \ to Z}$ ${\ displaystyle X \ to Z}$ .

Reguli de inferență suplimentare

În plus față de Axiomele lui Armstrong, există și alte reguli de inferență suplimentare pentru derivările unei dependențe funcționale:

Uniune : ${\{}X\rightarrow Y,X\rightarrow Z{}\}\vdash X\rightarrow YZ$ ${\ displaystyle {\ {} X \ rightarrow Y, X \ rightarrow Z {} \} \ vdash X \ rightarrow YZ}$ ${\ displaystyle {\ {} X \ rightarrow Y, X \ rightarrow Z {} \} \ vdash X \ rightarrow YZ}$
Pseudotransitivitate : ${\{}X\rightarrow Y,WY\rightarrow Z{}\}\vdash XW\rightarrow Z$ ${\ displaystyle {\ {} X \ rightarrow Y, WY \ rightarrow Z {} \} \ vdash XW \ rightarrow Z}$ ${\ displaystyle {\ {} X \ rightarrow Y, WY \ rightarrow Z {} \} \ vdash XW \ rightarrow Z}$
Descompunere : ${\{}X\rightarrow Y,Z\subseteq Y{}\}\vdash X\rightarrow Z$ ${\ displaystyle {\ {} X \ rightarrow Y, Z \ subseteq Y {} \} \ vdash X \ rightarrow Z}$ ${\ displaystyle {\ {} X \ rightarrow Y, Z \ subseteq Y {} \} \ vdash X \ rightarrow Z}$

Închiderea unui set de atribute

Având în vedere un model $\langle R(X),F\rangle$ ${\ displaystyle \ langle R (X), F \ rangle}$ ${\ displaystyle \ langle R (X), F \ rangle}$ și un set de atribute $X\subseteq T$ ${\ displaystyle X \ subseteq T}$ ${\ displaystyle X \ subseteq T}$ , închiderea lui X față de F, notată cu X ⁺ , este setul de atribute:

${\{}A\in T|F\vdash X\rightarrow A{}\}$ ${\ displaystyle {\ {} A \ în T | F \ vdash X \ rightarrow A {} \}}$ ${\ displaystyle {\ {} A \ în T | F \ vdash X \ rightarrow A {} \}}$

Astfel ajungem la teorema fundamentală că pentru a determina dacă $X\to A$ ${\ displaystyle X \ to A}$ ${\ displaystyle X \ to A}$ poate fi diferențiată prin Axiomele lui Armstrong, poate fi rezolvată calculând închiderea setului X, formal:

Având în vedere un model $\langle R(X),F\rangle$ ${\ displaystyle \ langle R (X), F \ rangle}$ ${\ displaystyle \ langle R (X), F \ rangle}$ , să fie X și Y set de atribute conținute în T:

$F\vdash X\to A\Leftrightarrow Y\subseteq X^{+}$ ${\ displaystyle F \ vdash X \ to A \ Leftrightarrow Y \ subseteq X ^ {+}}$ ${\ displaystyle F \ vdash X \ to A \ Leftrightarrow Y \ subseteq X ^ {+}}$

Algoritm de închidere lentă sau algoritm X ⁺

Algoritm pentru calcularea închiderii unui set de atribute X față de F (X ⁺ ).

Intrare : $\langle R(X),F\rangle$ ${\ displaystyle \ langle R (X), F \ rangle}$ ${\ displaystyle \ langle R (X), F \ rangle}$ , $X\subseteq T$ ${\ displaystyle X \ subseteq T}$ ${\ displaystyle X \ subseteq T}$
Ieșire : X ⁺ , închiderea lui X față de F

Începe

X ⁺ : = X;

în timp ce X ⁺ s-a schimbat do

pentru fiecare $W\to V\in F$ ${\ displaystyle W \ to V \ în F}$ ${\ displaystyle W \ to V \ în F}$ cu $W\subseteq X^{+}$ ${\ displaystyle W \ subseteq X ^ {+}}$ ${\ displaystyle W \ subseteq X ^ {+}}$ și $V\not \subset X^{+}$ ${\ displaystyle V \ not \ subset X ^ {+}}$ ${\ displaystyle V \ not \ subset X ^ {+}}$ do

$X^{+}:=X^{+}\cup V$ ${\ displaystyle X ^ {+}: = X ^ {+} \ cup V}$ ${\ displaystyle X ^ {+}: = X ^ {+} \ cup V}$

Sfârșit

Exemplu

Se va da un model $\langle R(X),F\rangle$ ${\ displaystyle \ langle R (X), F \ rangle}$ ${\ displaystyle \ langle R (X), F \ rangle}$ , cu T = {A, B, C, D, E, G, H, I} e ${\textstyle F={\{}ADG\to GI,ACH\to ADG,BC\to AD,CE\to ACH{}\}}$ ${\ textstyle F = {\ {} ADG \ la GI, ACH \ la ADG, BC \ la AD, CE \ la ACH {} \}}$ ${\ textstyle F = {\ {} ADG \ la GI, ACH \ la ADG, BC \ la AD, CE \ la ACH {} \}}$ . De asemenea, fie el $X_{j}^{+}$ ${\ displaystyle X_ {j} ^ {+}}$ ${\ displaystyle X_ {j} ^ {+}}$ valoarea variabilei X ⁺ la sfârșitul iterației j-a buclei while:

Fie X = BCE:

$X_{0}^{+}(=X)=BCE$ ${\ displaystyle X_ {0} ^ {+} (= X) = BCE}$ ${\ displaystyle X_ {0} ^ {+} (= X) = BCE}$

$X_{1}^{+}=BCE\cup AD\cup ACH=ABCDEH$ ${\ displaystyle X_ {1} ^ {+} = BCE \ cup AD \ cup ACH = ABCDEH}$ ${\ displaystyle X_ {1} ^ {+} = BCE \ cup AD \ cup ACH = ABCDEH}$

$X_{2}^{+}=ABCDEH\cup ADG=ABCDEGH$ ${\ displaystyle X_ {2} ^ {+} = ABCDEH \ cup ADG = ABCDEGH}$ ${\ displaystyle X_ {2} ^ {+} = ABCDEH \ cup ADG = ABCDEGH}$

$X_{3}^{+}=ABCDEGH\cup GI=ABCDEGHI(=T)$ ${\ displaystyle X_ {3} ^ {+} = ABCDEGH \ cup GI = ABCDEGHI (= T)}$ ${\ displaystyle X_ {3} ^ {+} = ABCDEGH \ cup GI = ABCDEGHI (= T)}$

Algoritmul se termină cu BCE ⁺ = T (supercheie BCE).

Corectitudinea și completitudinea Axiomelor lui Armstrong

Axiomele lui Armstrong sunt corecte atunci când orice dependență funcțională derivată prin aplicarea axiomelor este implicită logic:

$F\vdash f\Rightarrow F\vDash f$ ${\ displaystyle F \ vdash f \ Rightarrow F \ vDash f}$ ${\ displaystyle F \ vdash f \ Rightarrow F \ vDash f}$

Axiomele lui Armstrong sunt complete atunci când orice dependență funcțională implicită logic este derivată prin aplicarea axiomelor:

$F\vdash f\Leftarrow F\vDash f$ ${\ displaystyle F \ vdash f \ Leftarrow F \ vDash f}$ ${\ displaystyle F \ vdash f \ Leftarrow F \ vDash f}$

Bibliografie

Jeffrey D. Ullman, Baze de date și baze de cunoștințe , Jackson Libri, Milano, 1991, ISBN 8825602154 .
Beneventano D. Bergamaschi S. Guerra F. Vincini M., Proiect de baze de date relaționale , Pitagora Editrice, Bologna, 2007/2, ISBN 88-371-1680-2 .

Elemente conexe

Portal IT

Portal de inginerie