Assiomi di Armstrong

Da Wikipedia, l'enciclopedia libera.

Definizione[modifica | modifica wikitesto]

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à[modifica | modifica wikitesto]

Se Y \subseteq X \subseteq U allora X \to Y è logicamente implicato da F.

Assioma di Aumento[modifica | modifica wikitesto]

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

Assioma di Transitività[modifica | modifica wikitesto]

Se X \to Y e Y \to Z allora X \to Z.

Regole di inferenza addizionali[modifica | modifica wikitesto]

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 YZ
  • Decomposizione:{\{}X \rightarrow Y, Z \subseteq Y{}\} \vdash X \rightarrow Z

Chiusura di un insieme di attributi[modifica | modifica wikitesto]

Dato uno schema \langle R(X),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 Armostrong, è risolvibile calcolando la chiusua dell'insieme X, formalmente:

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

F \vdash X \to A  \Leftrightarrow Y \subseteq X^+

Algoritmo X+[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Sia dato uno schema \langle R(X),F \rangle, con T={A,B,C,D,E,F,G,H,I} e {\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[modifica | modifica wikitesto]

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 quanto ogni dipendenza funzionale implicata logicamente è derivata attraverso l'applicazione degli assiomi:

F \vdash f \Leftarrow F \vDash f

Voci correlate[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

  • 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.