Assiomi di Armstrong

Definizione

Nella teoria della progettazione di una base di dati gli Assiomi di Armstrong, formalizzati nel 1974, costituiscono un insieme di regole che permettono di comprendere le implicazioni logiche che intercorrono tra dipendenze funzionali. Gli assiomi di Armstrong sono di Riflessività, Aumento e Transitività. In tutti i casi si suppone di considerare uno schema di relazione con un insieme di attributi ${\displaystyle U}$, con ${\displaystyle U}$ l'insieme universale di attributi, ed un insieme ${\displaystyle F}$ di dipendenze funzionali che implichino solo attributi di ${\displaystyle U}$.

Assioma di Riflessività

Se ${\displaystyle Y\subseteq X\subseteq U}$ allora ${\displaystyle X\to Y}$ è logicamente implicato da ${\displaystyle F}$.

Assioma di Aumento

Se vale ${\displaystyle X\to Y}$ e ${\displaystyle Z}$ è un qualunque sottoinsieme di ${\displaystyle U}$ allora ${\displaystyle XZ\to YZ}$.

Assioma di Transitività

Se ${\displaystyle X\to Y}$ e ${\displaystyle Y\to Z}$ allora ${\displaystyle X\to Z}$.

Regole di inferenza addizionali

Oltre agli Assiomi di Armstrong esistono altre regole di inferenza addizionali per derivazioni di una dipendenza funzionali:

• Unione: ${\displaystyle {\{}X\rightarrow Y,X\rightarrow Z{}\}\vdash X\rightarrow YZ}$
• Pseudotransitività:${\displaystyle {\{}X\rightarrow Y,WY\rightarrow Z{}\}\vdash XW\rightarrow Z}$
• Decomposizione:${\displaystyle {\{}X\rightarrow Y,Z\subseteq Y{}\}\vdash X\rightarrow Z}$

Chiusura di un insieme di attributi

Dato uno schema ${\displaystyle \langle R(T),F\rangle }$ e un insieme di attributi ${\displaystyle X\subseteq T}$, la chiusura di X rispetto a F, denotata con X⁺, è l'insieme di attributi:

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

Si arriva così al teorema fondamentale che per determinare se ${\displaystyle X\to A}$ sia derivabile attraverso gli Assiomi di Armstrong, è risolvibile calcolando la chiusura dell'insieme X, formalmente:

Dato uno schema ${\displaystyle \langle R(T),F\rangle }$, siano X e Y insieme di attributi contenuti in T:

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

Algoritmo di chiusura lenta o Algoritmo X⁺

Algoritmo per il calcolo della chiusura di un insieme di attributi X rispetto ad F (X⁺).

• Input: ${\displaystyle \langle R(X),F\rangle }$, ${\displaystyle X\subseteq T}$
• Output: X⁺, chiusura di X rispetto F

Begin

X⁺ := X;

while X⁺ è cambiato do

for each ${\displaystyle W\to V\in F}$ with ${\displaystyle W\subseteq X^{+}}$ and ${\displaystyle V\not \subset X^{+}}$ do

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

End

Esempio

Sia dato uno schema ${\displaystyle \langle R(X),F\rangle }$, con T={A,B,C,D,E,G,H,I} e ${\textstyle F={\{}ADG\to GI,ACH\to ADG,BC\to AD,CE\to ACH{}\}}$. Inoltre, sia ${\displaystyle X_{j}^{+}}$ il valore della variabile X⁺ alla fine della j-esima iterazione del ciclo while:

Sia X = BCE:

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

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

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

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

L'algoritmo termina con BCE⁺=T (BCE superchiave).

Correttezza e completezza degli Assiomi di Armstrong

Gli assiomi di Armstrong sono corretti quando ogni dipendenza funzionale derivata attraverso l'applicazione degli assiomi è implicata logicamente:

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

Gli assiomi di Armstrong sono completi quando ogni dipendenza funzionale implicata logicamente è derivata attraverso l'applicazione degli assiomi:

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

Bibliografia

• Jeffrey D. Ullman, Basi di dati e basi di conoscenza, Jackson Libri, Milano, 1991, ISBN 8825602154.
• Beneventano D. Bergamaschi S. Guerra F. Vincini M., Progetto di basi di dati relazionali, Pitagora Editrice, Bologna, 2007/2, ISBN 88-371-1680-2.

Voci correlate

• Base di dati
• Dipendenza funzionale

Portale Informatica

Portale Ingegneria