Dependencia funcional

En teoría de bases de datos relacionales, una dependencia funcional es un limitación entre dos conjuntos de atributos en una relación de una base de datos. En otras palabras, una dependencia funcional es una limitación entre dos atributos en una relación. Dada una relación R y conjuntos de atributos X,Y⊆ ⊆ R{displaystyle X,Ysubseteq R., X se dice que funcionalmente determinar Y (written X → Y) si y sólo si cada uno X valor R está asociado con precisamente uno Y valor R; R entonces se dice que satisfacer satisfacción la dependencia funcional X → Y. Equivalentemente, la proyección ▪ ▪ X,YR{displaystyle Pi _{X,Y}R} es una función, es decir. Y es una función X. En palabras simples, si los valores para X atributos son conocidos (porque son x), entonces los valores para los Y atributos correspondientes a x puede ser determinado por mirar hacia arriba cualquiera tuple of R que contiene x. Personalmente X se llama determinante set and Y el dependiente Listo. 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 las 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 simple aplicación de las dependencias funcionales es El teorema de Heath; dice que una relación R sobre un conjunto de atributos U y la satisfacción de una dependencia funcional X → Y puede dividirse de forma segura en dos relaciones que tienen la propiedad de descomposición sin pérdidas, a saber, en ▪ ▪ XY()R)⋈ ⋈ ▪ ▪ XZ()R)=R{displaystyle Pi _{XY}(R)bowtie Pi _{XZ}(R)=R} Donde Z = U − XY son el resto de los atributos. (Las uniones de los conjuntos de atributos se denotan a la medida por allí yuxtaposiciones en la teoría de la base 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 los atributos, se seleccionan para generar limitaciones que excluyan tantos datos inapropiados al dominio del usuario del sistema como sea posible.

Una noción de implicación lógica se define para las dependencias funcionales de la siguiente manera: un conjunto de dependencias funcionales .. {displaystyle Sigma } lógicamente implica otro conjunto de dependencias .. {displaystyle "Gamma", si alguna relación R satisfacer todas las dependencias de .. {displaystyle Sigma } también satisface todas las dependencias de .. {displaystyle "Gamma"; esto generalmente está escrito .. ⊨ ⊨ .. {displaystyle Sigma models Gamma }. La noción de implicación lógica para las dependencias funcionales admite una axiomatización finita sólida y completa, conocida como Axiomas de Armstrong.

Ejemplos

Coches

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. Uno escribiría VIN → EngineCapacity porque sería inapropiado que el motor de un vehículo tenga más de una capacidad. (Suponiendo, en este caso, que los vehículos solo tienen 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, eso 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.

Conferencias

Este ejemplo ilustra el concepto de dependencia funcional. La situación modelada es la de estudiantes universitarios que asisten a 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 por una identificación de número entero única.

Observamos que cada vez que dos filas en esta tabla presentan el mismo Id. de estudiante, también tienen necesariamente los mismos valores Semestrales. Este hecho básico se puede expresar mediante una dependencia funcional:

• StudentID → Semester.

Tenga en cuenta que si se agregara una fila donde el estudiante tuviera un valor diferente de semestre, 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 invaliden el FD.

Se pueden identificar otras dependencias funcionales no triviales, por ejemplo:

• {StudentID, Lecture} → TA
• {StudentID, Lecture} → {TA, Semester}

Este último expresa el hecho de que el conjunto {StudentID, Lecture} es una superclave de la relación.

Modelo de departamento de empleados

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 incrustadas en una única representación de datos. Tenga en cuenta que debido a que un empleado solo puede ser miembro de un departamento, la identificación única de ese empleado determina el departamento.

• ID del empleado → Nombre del empleado
• ID del empleador → ID del departamento

Además de esta relación, la tabla también tiene una dependencia funcional a través de un atributo no clave

• ID del Departamento → Nombre del Departamento

Este ejemplo demuestra que aunque existe una ID de empleado de FD → ID de departamento, la 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 más lógicas basadas en los datos.

Propiedades y axiomatización de dependencias funcionales

Dado que X, Y y Z son conjuntos de atributos en una relación R, uno puede derivar varias propiedades de las dependencias funcionales. Entre los más importantes se encuentran los siguientes, generalmente llamados axiomas de Armstrong:

• ReflexividadSi Y es un subconjunto de X, entonces X → Y
• AumentoSi X → Y, entonces XZ → YZ
• TransitividadSi X → Y y Y → Z, entonces X → Z

"Reflexividad" se puede debilitar a X→ → ∅ ∅ {displaystyle Xrightarrow varnothing }, es decir, es un axioma real, donde los otros dos son reglas adecuadas de inferencia, dando lugar más precisamente a las siguientes reglas de consecuencia sintáctica:

⊢ ⊢ X→ → ∅ ∅ {displaystyle vdash Xrightarrow varnothing }
X→ → Y⊢ ⊢ XZ→ → YZ{displaystyle Xrightarrow Yvdash XZrightarrow YZ!
X→ → Y,Y→ → Z⊢ ⊢ X→ → Z{displaystyle Xrightarrow Y,Yrightarrow Zvdash Xrightarrow Z}.

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 finita, con la advertencia de que el axioma y las reglas de inferencia son todos esquemas, lo que significa que el x , y y z rango en todos los términos terrestres (conjuntos de atributos).

Al aplicar el aumento y la transitividad, uno puede derivar dos reglas adicionales:

• PseudotransitivitySi X → Y y YW → Z, entonces XW → Z
• CompositionSi X → Y y Z → W, entonces XZ → YW

También se pueden derivar las reglas de unión y descomposición de los axiomas de Armstrong:

X → Y y X → Z si X → YZ

Cierre de dependencia funcional

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. Uno usa los axiomas de Armstrong para proporcionar una prueba, es decir, reflexividad, aumento, transitividad.

Dado R{displaystyle R. y F{displaystyle F} un conjunto de FD que sostiene R{displaystyle R.: El cierre F{displaystyle F} dentro R{displaystyle R. (denominado F{displaystyle F}⁺) es el conjunto de todos los FD que son lógicamente implicados por F{displaystyle F}.

Cierre de un conjunto de atributos

Cierre de un conjunto de atributos X con respecto a F{displaystyle F} es el conjunto X⁺ de todos atributos que se determinan funcionalmente por X utilizando F{displaystyle F}⁺.

Ejemplo

Imagínese la siguiente lista de FD. Vamos a calcular un cierre para A a partir de esta relación.

1. A → B
2. B → C
3. AB → D

El cierre sería el siguiente:

a) A → A (por la reflexividad de Armstrong)
b) A → AB (por 1. y (a))
c) A → ABD (por (b), 3 y la transitividad de Armstrong)
d) A → ABCD (por (c), y 2)

El cierre es por lo tanto A → ABCD. Al calcular el cierre de A, hemos validado que A también es una buena clave candidata ya que su cierre es cada valor de datos individual en la relación.

Coberturas y equivalencia

Cubiertas

Definición: F{displaystyle F} cubiertas G{displaystyle G. si cada FD en G{displaystyle G. se puede inferir de F{displaystyle F}. F{displaystyle F} cubiertas G{displaystyle G. si G{displaystyle G.⁺ ⊆ F{displaystyle F}⁺
Cada conjunto de dependencias funcionales tiene una cubierta canónica.

Equivalencia de dos conjuntos de FD

Dos juegos de FDs F{displaystyle F} y G{displaystyle G. sobre el esquema R{displaystyle R. son equivalentes, escritos F{displaystyle F} ↑ G{displaystyle G., si F{displaystyle F}⁺ = G{displaystyle G.⁺. Si F{displaystyle F} ↑ G{displaystyle G., entonces F{displaystyle F} es una cubierta para G{displaystyle G. y viceversa. En otras palabras, se denominan conjuntos equivalentes de dependencias funcionales cubiertas uno del otro.

Cubiertas no redundantes

Un juego F{displaystyle F} de los FD no es redundante si no hay subconjunto adecuado F.{displaystyle F. de F{displaystyle F} con F.{displaystyle F. ↑ F{displaystyle F}. Si tal F.{displaystyle F. existe, F{displaystyle F} es redundante. F{displaystyle F} es una cubierta no redundante para G{displaystyle G. si F{displaystyle F} es una cubierta para G{displaystyle G. y F{displaystyle F} no es redundante.
Una caracterización alternativa de la no-redundancia es que F{displaystyle F} si no hay FD X → Y dentro F{displaystyle F} tales que F{displaystyle F} -X → Y} ⊨ ⊨ {displaystyle models } X → Y. Llame a un FD X → Y dentro F{displaystyle F} redundante en F{displaystyle F} si F{displaystyle F} -X → Y} ⊨ ⊨ {displaystyle models } X → Y.

Aplicaciones a la normalización

Teorema de Heath

Una propiedad importante (que permite una aplicación inmediata) de las dependencias funcionales es que si R es una relación con columnas nombradas de algún conjunto de atributos U y R satisfice alguna dependencia funcional X → Y entonces R=▪ ▪ XY()R)⋈ ⋈ ▪ ▪ XZ()R){displaystyle R=Pi _{XY}(R)bowtie Pi _{XZ}(R)} Donde Z = U − XY. Intuitivamente, si una dependencia funcional X → Y en R, entonces la relación puede dividirse con seguridad en dos relaciones junto a la columna X (que es una clave para ▪ ▪ XY()R)⋈ ⋈ ▪ ▪ XZ()R){displaystyle Pi _{XY}(R)bowtie Pi _{XZ}(R)}) asegurando que cuando se unen las dos partes no se pierdan datos, es decir, una dependencia funcional proporciona una manera sencilla de construir una descomposición sin pérdidas R en dos relaciones más pequeñas. Este hecho a veces se llama Heaths theorem; es uno de los primeros resultados en la teoría de la base de datos.

El teorema de Heath dice que podemos sacar los valores de Y de la gran relación R y guardarlos en uno, ▪ ▪ XY()R){displaystyle Pi _{XY}(R)}, que no tiene repeticiones de valor en la fila por X y es efectivamente una mesa de búsqueda para Y llave por X y por consiguiente sólo tiene un lugar para actualizar Y correspondiente a cada X a diferencia de la relación "grande" R donde hay potencialmente muchas copias de cada X, cada uno con su copia de Y que necesitan ser sincronizados en 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 sólo deja X para actuar como una llave extranjera en el resto de la mesa grande ▪ ▪ XZ()R){displaystyle Pi _{XZ}(R)}.

Sin embargo, las dependencias funcionales no deben confundirse con las dependencias de inclusión, que son el formalismo de las claves extranjeras; aunque se utilizan para la normalización, las dependencias funcionales expresan limitaciones respecto de una relación (schema), 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 relacionan con la clasificación de dependencias: las dependencias funcionales son dependencias que generan la igualdad, mientras que las dependencias de inclusión son dependencias que generan tuples. El cumplimiento de las limitaciones de referencia después de la descomposición de esquemas 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 tuples en ▪ ▪ XZ()R){displaystyle Pi _{XZ}(R)} tener algún valor X no encontrado en ▪ ▪ XY()R){displaystyle Pi _{XY}(R)}.

Formas normales

Los formularios normales son niveles de normalización de bases de datos que determinan la "bondad" de una mesa En general, la tercera forma normal se considera "buena" estándar para una base de datos relacional.

La normalización tiene como objetivo liberar la base de datos de anomalías de actualización, inserción y eliminación. También asegura que cuando se introduce un nuevo valor en la relación, tiene un efecto mínimo en la base de datos y, por lo tanto, un efecto mínimo en las aplicaciones que utilizan la base de datos.

Conjunto dependiente de función irreducible

Un conjunto S de dependencias funcionales es irreducible si el conjunto tiene las siguientes tres propiedades:

1. Cada conjunto adecuado de una dependencia funcional de S contiene sólo un atributo.
2. Cada conjunto izquierdo de una dependencia funcional de S es irreducible. Significa que reducir cualquier atributo de conjunto izquierdo cambiará el contenido de S (S perderá alguna información).
3. Reducir cualquier dependencia funcional cambiará el contenido de S.

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 entrada S' proporcionado como entrada se denomina encontrar una cobertura mínima de S': este problema se puede resolver en tiempo polinomial.