Axiomas de Armstrong

Axiomas de Armstrong son un conjunto de referencias (o, más precisamente, reglas de inferencia) utilizadas para inferir todas las dependencias funcionales en una base de datos relacional. Fueron desarrollados por William W. Armstrong en su periódico de 1974. Los axiomas son sólidos en la generación de sólo dependencias funcionales en el cierre de un conjunto de dependencias funcionales (denotados como ${\displaystyle F^{+}$) cuando se aplica a ese conjunto (denotado como ${\displaystyle F}$). También están completos en que la aplicación reiterada de estas reglas generará todas las dependencias funcionales en el cierre ${\displaystyle F^{+}$.

Más formalmente, vamos ${\displaystyle \langle R(U),F\rangle }$ denota un esquema relacional sobre el conjunto de atributos ${\displaystyle U}$ con un conjunto de dependencias funcionales ${\displaystyle F}$. Decimos que una dependencia funcional ${\displaystyle f}$ lógicamente implicado por ${\displaystyle F}$, y denotarlo con ${\displaystyle F\models f}$ si y sólo si por cada caso ${\displaystyle r}$ de ${\displaystyle R.$ que satisface las dependencias funcionales en ${\displaystyle F}$, ${\displaystyle r}$ también satisfice ${\displaystyle f}$. Denotamos ${\displaystyle F^{+}$ el conjunto de todas las dependencias funcionales que lógicamente están implicadas ${\displaystyle F}$.

Además, con respecto a un conjunto de reglas de inferencia ${\displaystyle A}$, decimos que una dependencia funcional ${\displaystyle f}$ es derivable de las dependencias funcionales en ${\displaystyle F}$ por el conjunto de reglas de inferencia ${\displaystyle A}$, y lo denotamos ${\displaystyle F\vdash _{A}f}$ si ${\displaystyle f}$ se puede obtener mediante la aplicación repetidamente de las reglas de inferencia en ${\displaystyle A}$ a las dependencias funcionales ${\displaystyle F}$. Denotamos ${\displaystyle F.$ el conjunto de todas las dependencias funcionales que son derivadas de ${\displaystyle F}$ por reglas de inferencia ${\displaystyle A}$.

Entonces, un conjunto de reglas de inferencia ${\displaystyle A}$ es sonido si y sólo si el siguiente sostiene:

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

es decir, no podemos derivar por medio de ${\displaystyle A}$ dependencias funcionales que no están lógicamente implicadas ${\displaystyle F}$. El conjunto de reglas de inferencia ${\displaystyle A}$ se dice que está completo si se sostiene lo siguiente:

${\displaystyle F^{+}\subseteq F.$

más simple, somos capaces de derivar por ${\displaystyle A}$ todas las dependencias funcionales que lógicamente están implicadas ${\displaystyle F}$.

Axiomas (reglas primarias)

Vamos. ${\displaystyle R(U)}$ ser un esquema de relación sobre el conjunto de atributos ${\displaystyle U}$. De ahora en adelante nos denotaremos por cartas ${\displaystyle X}$, ${\displaystyle Sí.$, ${\displaystyle Z}$ cualquier subconjunto de ${\displaystyle U}$ y, por breve, la unión de dos conjuntos de atributos ${\displaystyle X}$ y ${\displaystyle Sí.$ por ${\displaystyle XY.$ en lugar de lo habitual ${\displaystyle X\cup Y}$; esta notación es bastante estándar en la teoría de la base de datos al tratar con conjuntos de atributos.

Axioma de reflexividad

Si ${\displaystyle X}$ es un conjunto de atributos y ${\displaystyle Sí.$ es un subconjunto de ${\displaystyle X}$Entonces ${\displaystyle X}$ ostenciones ${\displaystyle Sí.$. Por la presente, ${\displaystyle X}$ ostenciones ${\displaystyle Sí.$ [${\displaystyle X\to Y}$Significa que ${\displaystyle X}$ funcionalmente determina ${\displaystyle Sí.$.

Si ${\displaystyle Y 'subseteq X'$ entonces ${\displaystyle X\to Y}$.

Axioma de aumento

Si ${\displaystyle X}$ ostenciones ${\displaystyle Sí.$ y ${\displaystyle Z}$ es un conjunto de atributos, entonces ${\displaystyle XZ}$ ostenciones ${\displaystyle YZ!$. Significa que el atributo en dependencias no cambia las dependencias básicas.

Si ${\displaystyle X\to Y}$Entonces ${\displaystyle XZ\to YZ}$ para cualquier ${\displaystyle Z}$.

Axioma de transitividad

Si ${\displaystyle X}$ ostenciones ${\displaystyle Sí.$ y ${\displaystyle Sí.$ ostenciones ${\displaystyle Z}$Entonces ${\displaystyle X}$ ostenciones ${\displaystyle Z}$.

Si ${\displaystyle X\to Y}$ y ${\displaystyle Y\to Z}$Entonces ${\displaystyle X\to Z}$.

Reglas adicionales (Reglas secundarias)

Estas reglas se pueden derivar de los axiomas anteriores.

Descomposición

Si ${\displaystyle X\to YZ}$ entonces ${\displaystyle X\to Y}$ y ${\displaystyle X\to Z}$.

Prueba

1. ${\displaystyle X\to YZ}$	(Given)
2. ${\displaystyle YZ\to Y}$	(Reflexividad)
3. ${\displaystyle X\to Y}$	(Transitividad de 1 y 2)

Composición

Si ${\displaystyle X\to Y}$ y ${\displaystyle A\to B}$ entonces ${\displaystyle XA\to YB}$.

Prueba

1. ${\displaystyle X\to Y}$	(Given)
2. ${\displaystyle A\to B}$	(Given)
3. ${\displaystyle XA\to YA}$	(Aumentación de 1 A)
4. ${\displaystyle XA\to Y}$	(Descomposición de 3)
5. ${\displaystyle XA\to XB}$	(Aumentación de 2 y X)
6. ${\displaystyle XA\to B}$	(Descomposición de 5)
7. ${\displaystyle XA\to YB}$	(Unión 4 y 6)

Unión

Si ${\displaystyle X\to Y}$ y ${\displaystyle X\to Z}$ entonces ${\displaystyle X\to YZ}$.

Prueba

1. ${\displaystyle X\to Y}$	(Given)
2. ${\displaystyle X\to Z}$	(Given)
3. ${\displaystyle X\to XZ}$	(Aumentación de 2 y X)
4. ${\displaystyle XZ\to YZ}$	(Aumentación de 1 Z)
5. ${\displaystyle X\to YZ}$	(Transitividad de 3 y 4)

Pseudo transitividad

Si ${\displaystyle X\to Y}$ y ${\displaystyle YZ\to W}$ entonces ${\displaystyle XZ\to W}$.

Prueba

1. ${\displaystyle X\to Y}$	(Given)
2. ${\displaystyle YZ\to W}$	(Given)
3. ${\displaystyle XZ\to YZ}$	(Aumentación de 1 Z)
4. ${\displaystyle XZ\to W}$	(Transitividad de 3 y 2)

Autodeterminación

${\displaystyle I 'to I'$ para cualquier ${\displaystyle I}$. Esto se deriva directamente del axioma de la reflexividad.

Extensividad

La propiedad siguiente es un caso especial de aumento cuando ${\displaystyle Z=X}$.

Si ${\displaystyle X\to Y}$Entonces ${\displaystyle X\to XY}$.

La extensividad puede reemplazar al aumento como axioma en el sentido de que el aumento puede demostrarse a partir de la extensividad junto con los otros axiomas.

Prueba

1. ${\displaystyle XZ\to X}$	(Reflexividad)
2. ${\displaystyle X\to Y}$	(Given)
3. ${\displaystyle XZ\to Y}$	(Transitividad de 1 y 2)
4. ${\displaystyle XZ\to XYZ}$	(Extensividad de 3)
5. ${\displaystyle XYZ\to YZ}$	(Reflexividad)
6. ${\displaystyle XZ\to YZ}$	(Transitividad de 4 " 5)

Relación Armstrong

Dado un conjunto de dependencias funcionales ${\displaystyle F}$, un Armstrong relation es una relación que satisface todas las dependencias funcionales en el cierre ${\displaystyle F^{+}$ y sólo esas dependencias. Lamentablemente, la relación Armstrong de tamaño mínimo para un determinado conjunto de dependencias puede tener un tamaño que es una función exponencial del número de atributos en las dependencias consideradas.