Los axiomas de Armstrong

Los axiomas de Armstrong son un conjunto de axiomas (o, más precisamente, reglas de inferencia ) que se utilizan para inferir todas las dependencias funcionales de una base de datos relacional . Fueron desarrollados por William W. Armstrong en su artículo de 1974. ^[1] Los axiomas son sólidos en cuanto a que generan solo dependencias funcionales en el cierre de un conjunto de dependencias funcionales (denotadas como ) cuando se aplican a ese conjunto (denotado como ). También son completos en cuanto a que la aplicación repetida de estas reglas generará todas las dependencias funcionales en el cierre . ${\displaystyle F^{+}}$ ${\displaystyle F}$ ${\displaystyle F^{+}}$

Más formalmente, denotemos un esquema relacional sobre el conjunto de atributos con un conjunto de dependencias funcionales . Decimos que una dependencia funcional está implícita lógicamente por , y la denotamos con si y solo si para cada instancia de que satisface las dependencias funcionales en , también satisface . Denotamos por el conjunto de todas las dependencias funcionales que están implícitas lógicamente por . ${\displaystyle \langle R(U),F\rangle }$ ${\displaystyle U}$ ${\displaystyle F}$ ${\displaystyle f}$ ${\displaystyle F}$ ${\displaystyle F\models f}$ ${\displaystyle r}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle r}$ ${\displaystyle f}$ ${\displaystyle F^{+}}$ ${\displaystyle F}$

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

Entonces, un conjunto de reglas de inferencia es sólido si y sólo si se cumple lo siguiente: ${\displaystyle A}$

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

es decir, no podemos derivar mediante dependencias funcionales que no estén lógicamente implícitas en . Se dice que el conjunto de reglas de inferencia está completo si se cumple lo siguiente: ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle A}$

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

En términos más simples, podemos derivar de todas las dependencias funcionales que están lógicamente implicadas por . ${\displaystyle A}$ ${\displaystyle F}$

Axiomas (reglas primarias)

Sea un esquema de relación sobre el conjunto de atributos . De ahora en adelante denotaremos con las letras , , cualquier subconjunto de y, para abreviar, la unión de dos conjuntos de atributos y con en lugar de la notación habitual ; esta notación es bastante estándar en la teoría de bases de datos cuando se trata de conjuntos de atributos. ${\displaystyle R(U)}$ ${\displaystyle U}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle U}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle XY}$ ${\displaystyle X\cup Y}$

Axioma de reflexividad

Si es un conjunto de atributos y es un subconjunto de , entonces se cumple . Por tanto, se cumple [ ] significa que determina funcionalmente . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\to Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

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

Axioma de aumento

Si se cumple y es un conjunto de atributos, entonces se cumple . Esto significa que el atributo en las dependencias no cambia las dependencias básicas. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle XZ}$ ${\displaystyle YZ}$

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

Axioma de transitividad

Si se mantiene y se mantiene , entonces se mantiene . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle X}$ ${\displaystyle Z}$

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

Reglas adicionales (Reglas secundarias)

Estas reglas pueden derivarse de los axiomas anteriores.

Descomposición

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

Prueba

Composición

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

Prueba

Unión

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

Prueba

Pseudo transitividad

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

Prueba

Autodeterminación

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

Extensividad

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

Si , entonces . ${\displaystyle X\to Y}$ ${\displaystyle X\to XY}$

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

Prueba

Relación de Armstrong

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

Referencias

1. William Ward Armstrong: Estructuras de dependencia de las relaciones de bases de datos , páginas 580-583. Congreso IFIP, 1974.
2. Beeri, C.; Dowd, M.; Fagin, R.; Statman, R. (1984). "Sobre la estructura de las relaciones de Armstrong para dependencias funcionales" (PDF) . Revista de la ACM . 31 : 30–46. CiteSeerX  10.1.1.68.9320 . doi :10.1145/2422.322414. Archivado desde el original (PDF) el 23 de julio de 2018.

Enlaces externos

• UMBC CMSC 461 Primavera '99
• Apuntes de la clase CS345 de la Universidad de Stanford