En la teoría de bases de datos relacionales , una dependencia funcional es una restricción entre dos conjuntos de atributos en una relación de una base de datos. En otras palabras, una dependencia funcional es una restricción entre dos atributos en una relación. Dada una relación R y conjuntos de atributos , se dice que X determina funcionalmente Y (escrito X → Y ) si y sólo si cada valor de X en R está asociado precisamente con un valor de Y en R ; Entonces se dice que R satisface la dependencia funcional X → Y . De manera equivalente, la proyección es una función , es decir, Y es una función de X. [1] [2] En palabras simples, si se conocen los valores de los atributos X (digamos que son x ), entonces los valores de los atributos Y correspondientes a x se pueden determinar buscándolos en cualquier tupla de R que contenga x . Habitualmente a X se le llama conjunto determinante y a Y conjunto dependiente . Una dependencia funcional FD: X → Y se llama trivial si Y es un subconjunto de X.
En otras palabras, una dependencia FD: X → Y significa que los valores de Y están determinados por los valores de X. Dos tuplas que comparten los mismos valores de X necesariamente tendrán los mismos valores de Y.
La determinación de dependencias funcionales es una parte importante del diseño de bases de datos en el modelo relacional y en la normalización y desnormalización de bases de datos . Una aplicación sencilla de las dependencias funcionales es el teorema de Heath ; dice que una relación R sobre un conjunto de atributos U y que satisface una dependencia funcional X → Y se puede dividir con seguridad en dos relaciones que tienen la propiedad de descomposición de unión sin pérdidas , es decir, en donde Z = U − XY están el resto de los atributos. ( Las uniones de conjuntos de atributos se denotan habitualmente mediante yuxtaposiciones en la teoría de bases de datos). Una noción importante en este contexto es una clave candidata , definida como un conjunto mínimo de atributos que determinan funcionalmente todos los atributos en una relación. Las dependencias funcionales, junto con los dominios de atributos , se seleccionan para generar restricciones que excluirían del sistema la mayor cantidad posible de datos inapropiados para el dominio del usuario.
Una noción de implicación lógica se define para dependencias funcionales de la siguiente manera: un conjunto de dependencias funcionales implica lógicamente otro conjunto de dependencias , si cualquier relación R que satisfaga todas las dependencias de también satisface todas las dependencias de ; esto suele estar escrito . La noción de implicación lógica para las dependencias funcionales admite una sólida y completa axiomatización finita , conocida como axiomas de Armstrong .
Supongamos que uno está diseñando un sistema para rastrear vehículos y la capacidad de sus motores. Cada vehículo tiene un número de identificación de vehículo (VIN) único. Se escribiría VIN → EngineCapacity porque sería inapropiado que el motor de un vehículo tuviera más de una capacidad. (Suponiendo, en este caso, que los vehículos solo tengan un motor). Por otro lado, EngineCapacity → VIN es incorrecto porque podría haber muchos vehículos con la misma capacidad de motor.
Esta dependencia funcional puede sugerir que el atributo EngineCapacity se coloque en una relación con la clave candidata VIN. Sin embargo, esto puede no ser siempre apropiado. Por ejemplo, si esa dependencia funcional ocurre como resultado de las dependencias funcionales transitivas VIN → VehicleModel y VehicleModel → EngineCapacity, entonces eso no daría como resultado una relación normalizada.
Este ejemplo ilustra el concepto de dependencia funcional. La situación modelada es la de estudiantes universitarios que visitan una o más conferencias en cada una de las cuales se les asigna un asistente de enseñanza (TA). Supongamos además que cada estudiante está en algún semestre y está identificado mediante un ID entero único.
Observamos que siempre que dos filas en esta tabla presentan el mismo StudentID, también necesariamente tienen los mismos valores de Semestre. Este hecho básico se puede expresar mediante una dependencia funcional:
Tenga en cuenta que si se agregara una fila donde el estudiante tuviera un valor de semestre diferente, entonces la dependencia funcional FD ya no existiría. Esto significa que el FD está implícito en los datos, ya que es posible tener valores que invalidarían el FD.
Se pueden identificar otras dependencias funcionales no triviales, por ejemplo:
Este último expresa el hecho de que el conjunto {StudentID, Lecture} es una superclave de la relación.
Un ejemplo clásico de dependencia funcional es el modelo de departamento de empleados.
Este caso representa un ejemplo en el que múltiples dependencias funcionales están integradas en una única representación de datos. Tenga en cuenta que, dado que un empleado solo puede ser miembro de un departamento, el ID único de ese empleado determina el departamento.
Además de esta relación, la tabla también tiene una dependencia funcional a través de un atributo que no es clave.
Este ejemplo demuestra que, aunque existe un ID de empleado de FD → ID de departamento, el ID de empleado no sería una clave lógica para determinar el nombre del departamento. El proceso de normalización de los datos reconocería todos los FD y permitiría al diseñador construir tablas y relaciones que sean más lógicas basadas en los datos.
Dado que X , Y y Z son conjuntos de atributos en una relación R , se pueden derivar varias propiedades de dependencias funcionales. Entre los más importantes se encuentran los siguientes, habitualmente llamados axiomas de Armstrong : [3]
La "reflexividad" puede debilitarse a simplemente , es decir, es un axioma real , donde los otros dos son reglas de inferencia propias , dando lugar más precisamente a las siguientes reglas de consecuencia sintáctica: [4]
.
Estas tres reglas son una axiomatización sólida y completa de las dependencias funcionales. Esta axiomatización a veces se describe como finita porque el número de reglas de inferencia es finito, [5] con la salvedad de que el axioma y las reglas de inferencia son todos esquemas , lo que significa que X , Y y Z abarcan todos los términos fundamentales (conjuntos de atributos). . [4]
Al aplicar aumento y transitividad, se pueden derivar dos reglas adicionales:
También se pueden derivar las reglas de unión y descomposición de los axiomas de Armstrong: [3] [7]
El cierre es esencialmente el conjunto completo de valores que se pueden determinar a partir de un conjunto de valores conocidos para una relación determinada utilizando sus dependencias funcionales. Se utilizan los axiomas de Armstrong para proporcionar una prueba: es decir, reflexividad, aumento, transitividad.
Dado y un conjunto de FD que se cumple en : El cierre de in (denotado + ) es el conjunto de todos los FD que están lógicamente implicados por . [8]
El cierre de un conjunto de atributos X con respecto a es el conjunto X + de todos los atributos que están funcionalmente determinados por X usando + .
Imagine la siguiente lista de FD. Vamos a calcular un cierre para A (escrito como A + ) a partir de esta relación.
El cierre sería el siguiente:
Por tanto, A + = ABCD. Debido a que A + incluye todos los atributos de la relación, es una superclave .
Definición : cubre si se puede inferir cada FD . cubre si + ⊆ +
Cada conjunto de dependencias funcionales tiene una cobertura canónica .
Dos conjuntos de FD y un esquema superior son equivalentes, escritos ≡ , si + = + . Si ≡ , entonces es una cobertura para y viceversa. En otras palabras, los conjuntos equivalentes de dependencias funcionales se denominan coberturas entre sí.
Un conjunto de FD no es redundante si no existe un subconjunto adecuado de con ≡ . Si tal existe, es redundante. es una cobertura no redundante para si es una cobertura para y no es redundante.
Una caracterización alternativa de no redundancia es que no es redundante si no hay FD X → Y de modo que - { X → Y } X → Y . Llame a un FD X → Y en redundante si - { X → Y } X → Y .
Una propiedad importante (que produce una aplicación inmediata) de las dependencias funcionales es que si R es una relación con columnas nombradas a partir de algún conjunto de atributos U y R satisface alguna dependencia funcional X → Y entonces donde Z = U − XY . Intuitivamente, si se cumple una dependencia funcional X → Y en R , entonces la relación se puede dividir de forma segura en dos relaciones junto con la columna X (que es una clave para ) asegurando que cuando las dos partes se vuelvan a unir no se pierdan datos, es decir, La dependencia funcional proporciona una forma sencilla de construir una descomposición conjunta sin pérdidas de R en dos relaciones más pequeñas. Este hecho a veces se denomina teorema de Heath ; es uno de los primeros resultados en la teoría de bases de datos. [9]
El teorema de Heath efectivamente dice que podemos extraer los valores de Y de la gran relación R y almacenarlos en uno, que no tiene repeticiones de valores en la fila para X y es efectivamente una tabla de búsqueda para Y codificada por X y, en consecuencia, solo tiene una lugar para actualizar la Y correspondiente a cada X a diferencia de la relación "grande" R donde hay potencialmente muchas copias de cada X , cada una con su copia de Y que debe mantenerse sincronizada en las actualizaciones. (Esta eliminación de la redundancia es una ventaja en contextos OLTP , donde se esperan muchos cambios, pero no tanto en contextos OLAP , que involucran principalmente consultas). La descomposición de Heath deja solo X para actuar como clave externa en el resto de la tabla grande. .
Sin embargo, las dependencias funcionales no deben confundirse con las dependencias de inclusión , que son el formalismo de las claves externas; aunque se utilizan para la normalización, las dependencias funcionales expresan restricciones sobre una relación (esquema), mientras que las dependencias de inclusión expresan restricciones entre esquemas de relación en un esquema de base de datos . Además, las dos nociones ni siquiera se cruzan en la clasificación de las dependencias: las dependencias funcionales son dependencias generadoras de igualdad, mientras que las dependencias de inclusión son dependencias generadoras de tuplas . Hacer cumplir restricciones referenciales después de la descomposición del esquema de relación (normalización) requiere un nuevo formalismo, es decir, dependencias de inclusión. En la descomposición resultante del teorema de Heath, no hay nada que impida la inserción de tuplas que tengan algún valor de X que no se encuentre en .
Las formas normales son niveles de normalización de la base de datos que determinan la "bondad" de una tabla. Generalmente, la tercera forma normal se considera un "buen" estándar para una base de datos relacional. [ cita necesaria ]
La normalización tiene como objetivo liberar la base de datos de anomalías de actualización, inserción y eliminación. También garantiza que cuando se introduce un nuevo valor en la relación, tenga un efecto mínimo en la base de datos y, por lo tanto, en las aplicaciones que utilizan la base de datos. [ cita necesaria ]
Un conjunto S de dependencias funcionales es irreducible si el conjunto tiene las tres propiedades siguientes:
Los conjuntos de dependencias funcionales con estas propiedades también se denominan canónicos o mínimos . Encontrar un conjunto S de dependencias funcionales que sea equivalente a algún conjunto de entradas S' proporcionado como entrada se denomina encontrar una cobertura mínima de S': este problema se puede resolver en tiempo polinomial. [10]