axiomas de Armstrong

Los axiomas de Armstrong son un conjunto de referencias (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 al generar 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 el sentido de 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á lógicamente implicada por y la denotamos con si y sólo si para cada instancia de eso satisface las dependencias funcionales en , también satisface . Denotamos por el conjunto de todas las dependencias funcionales que están lógicamente implicadas 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 mediante el conjunto de reglas de inferencia , y la denotamos por si y sólo si se puede obtener mediante la aplicación repetida de las reglas de inferencia. en dependencias funcionales en . Denotamos por el conjunto de todas las dependencias funcionales que son derivables mediante 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 vá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 implicadas por . Se dice que el conjunto de reglas de inferencia es completo si se cumple lo siguiente: ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle A}$

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

En pocas palabras, podemos derivar todas las dependencias funcionales que están lógicamente implicadas en . ${\displaystyle A}$ ${\displaystyle F}$

Axiomas (reglas primarias)

Sea un esquema de relaciones sobre el conjunto de atributos . De ahora en adelante denotaremos con letras , , cualquier subconjunto de y, para abreviar, la unión de dos conjuntos de atributos y por en lugar de lo 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 la presente, sostiene [ ] 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 . 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 cualquiera . ${\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 se pueden derivar 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 deriva directamente del axioma de la 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 demostrarse a partir de la extensividad junto con los otros axiomas.

Prueba

relación 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 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
• Notas de conferencias CS345 de la Universidad de Stanford