title: Assiomi di Armstrong
text: # 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 $U$, con $U$ l'insieme universale di attributi, ed un insieme $F$ di dipendenze funzionali che implichino solo attributi di $U$.
  
  ### Assioma di Riflessività
  
  Se $Y\subseteq X\subseteq U$ allora $X\to Y$ è logicamente implicato da $F$.
  
  ### Assioma di Aumento
  
  Se vale $X\to Y$ e $Z$ è un qualunque sottoinsieme di $U$ allora $XZ\to YZ$.
  
  ### Assioma di Transitività
  
  Se $X\to Y$ e $Y\to Z$ allora $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: ${\X\rightarrow Y,X\rightarrow Z\}\vdash X\rightarrow YZ$
  * Pseudotransitività:${\X\rightarrow Y,WY\rightarrow Z\}\vdash XW\rightarrow Z$
  * Decomposizione:${\X\rightarrow Y,Z\subseteq Y\}\vdash X\rightarrow Z$
  
  ## Chiusura di un insieme di attributi
  
  Dato uno schema $\langle R(T),F\rangle$ e un insieme di attributi $X\subseteq T$, la chiusura di X rispetto a F, denotata con $X^+,$ è l'insieme di attributi:
  
  ${\A\in T|F\vdash X\rightarrow A\}$
  
  Si arriva così al teorema fondamentale che per determinare se $X\to A$ sia derivabile attraverso gli Assiomi di Armstrong, è risolvibile calcolando la chiusura dell'insieme X, formalmente:
  
  Dato uno schema $\langle R(T),F\rangle$, siano X e Y insieme di attributi contenuti in T:
  
  $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: $\langle R(X),F\rangle$, $X\subseteq T$
  * Output: $X^+,$ chiusura di X rispetto F
  
  Begin
  
  $X^+$ := X;
  
  while $X^+$ è cambiato do
  
  for each $W\to V\in F$ with $W\subseteq X^{+}$ and $V\not \subset X^{+}$ do
  
  $X^{+}:=X^{+}\cup V$
  
  End
  
  ### Esempio
  
  Sia dato uno schema $\langle R(X),F\rangle$, con T={A,B,C,D,E,G,H,I} e F={ADG→GI, ACH→ADG, BC→AD, CE→ACH}{\textstyle F={\ADG\to GI, ACH\to ADG, BC\to AD, CE\to ACH\}}. Inoltre, sia $X_{j}^{+}$ il valore della variabile $X^+$ alla fine della j-esima iterazione del ciclo while:
  
  Sia X = BCE:
  
  $X_{0}^{+}(=X)=BCE$
  
  $X_{1}^{+}=BCE\cup AD\cup ACH=ABCDEH$
  
  $X_{2}^{+}=ABCDEH\cup ADG=ABCDEGH$
  
  $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:
  
  $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:
  
  $F\vdash f\Leftarrow F\vDash f$
  
  