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 aplica 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..
Más formalmente, dejemos denotar un esquema relacional sobre el conjunto de atributos con un conjunto de dependencias funcionales . Decimos que una dependencia funcional está lógicamente implícito en , y denotarlo con si y solo si para cada instancia de que satisfaga las dependencias funcionales en , también satisface . Denotamos por el conjunto de todas las dependencias funcionales que están implícitas lógicamente por .
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 lo 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 se derivan de por reglas de inferencia en .
Luego, un conjunto de reglas de inferencia es sólido si y solo si se cumple lo siguiente:
es decir, no podemos derivar por medio de dependencias funcionales que no están implícitas lógicamente por . El conjunto de reglas de inferencia se dice que está completo si se cumple lo siguiente:
dicho de manera más simple, podemos derivar por todas las dependencias funcionales que están implícitas lógicamente en .
Axiomas (reglas primarias)
Dejar ser un esquema de relación sobre el conjunto de atributos . De ahora en adelante denotaremos por 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.
Axioma de reflexividad
Si es un conjunto de atributos y es un subconjunto de , luego sostiene . Por la presente, sostiene [] significa que determina funcionalmente .
- Si luego .
Axioma de aumento
Si sostiene y es un conjunto de atributos, entonces sostiene . Significa que el atributo en las dependencias no cambia las dependencias básicas.
- Si , luego para cualquier .
Axioma de transitividad
Si sostiene y sostiene , luego sostiene .
- Si y , luego .
Reglas adicionales (Reglas secundarias)
Estas reglas pueden derivarse de los axiomas anteriores.
Descomposición
Si luego y .
Prueba
1. | (Dado) |
2. | (Reflexividad) |
3. | (Transitividad de 1 y 2) |
Composición
Si y luego .
Prueba
1. | (Dado) |
2. | (Dado) |
3. | (Aumento de 1 y A) |
4. | (Descomposición de 3) |
5. | (Aumento 2 y X) |
6. | (Descomposición de 5) |
7. | (Unión 4 y 6) |
Unión (notación)
Si y luego .
Prueba
1. | (Dado) |
2. | (Dado) |
3. | (Aumento de 2 y X) |
4. | (Aumento de 1 y Z) |
5. | (Transitividad de 3 y 4) |
Pseudo transitividad
Si y luego .
Prueba
1. | (Dado) |
2. | (Dado) |
3. | (Aumento de 1 y Z) |
4. | (Transitividad de 3 y 2) |
Autodeterminación
para cualquier . Esto se deriva directamente del axioma de la reflexividad.
Extensividad
La siguiente propiedad es un caso especial de aumento cuando .
- Si , luego .
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
1. | (Reflexividad) |
2. | (Dado) |
3. | (Transitividad de 1 y 2) |
4. | (Extensividad de 3) |
5. | (Reflexividad) |
6. | (Transitividad de 4 y 5) |
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 cierrey 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]
Referencias
- ^ William Ward Armstrong: estructuras de dependencia de las relaciones de la base de datos , página 580-583. Congreso IFIP, 1974.
- ↑ Beeri, C .; Dowd, M .; Fagin, R .; Statman, R. (1984). "Sobre la estructura de las relaciones de Armstrong para las dependencias funcionales" (PDF) . Revista de la ACM . 31 : 30–46. CiteSeerX 10.1.1.68.9320 . doi : 10.1145 / 2422.322414 .