Dependencia funcional

Concepto de teoría de bases de datos relacionales

En la teoría de bases de datos relacionales , una dependencia funcional es la siguiente restricción entre dos conjuntos de 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 cada valor de X está asociado con precisamente un valor de Y. 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, X se llama el conjunto determinante e Y el conjunto dependiente . Una dependencia funcional FD: X → Y se llama trivial si Y es un subconjunto de X. ${\displaystyle X,Y\subseteq R}$ ${\displaystyle \Pi _{X,Y}R}$

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 simple 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 de manera segura en dos relaciones que tienen la propiedad de descomposición de unión sin pérdida , es decir, en donde Z = U − XY son el resto de los atributos. ( Las uniones de conjuntos de atributos se denotan habitualmente por sus 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. ${\displaystyle \Pi _{XY}(R)\bowtie \Pi _{XZ}(R)=R}$

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 satisface todas las dependencias de también satisface todas las dependencias de ; esto se escribe habitualmente . La noción de implicación lógica para dependencias funcionales admite una axiomatización finita sólida y completa , conocida como axiomas de Armstrong . ${\displaystyle \Sigma }$ ${\displaystyle \Gamma }$ ${\displaystyle \Sigma }$ ${\displaystyle \Gamma }$ ${\displaystyle \Sigma \models \Gamma }$

Ejemplos

Coches

Supongamos que se está diseñando un sistema para hacer un seguimiento de los vehículos y la capacidad de sus motores. Cada vehículo tiene un número de identificación del vehículo (VIN) único. Se escribiría VIN → EngineCapacity porque no sería apropiado que el motor de un vehículo tuviera 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, esto puede no ser siempre apropiado. Por ejemplo, si esa dependencia funcional se produce como resultado de las dependencias funcionales transitivas VIN → VehicleModel y VehicleModel → EngineCapacity, entonces no se produciría 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 clases en cada una de las cuales se les asigna un asistente de enseñanza (TA). Supongamos además que cada estudiante está en un semestre y se lo identifica mediante un identificador entero único.

Observamos que siempre que dos filas de esta tabla tienen el mismo StudentID, necesariamente también tienen los mismos valores de Semestre. Este hecho básico se puede expresar mediante una dependencia funcional:

• ID de estudiante → Semestre.

Si se añadiera una fila en la que el estudiante tuviera un valor de semestre diferente, la dependencia funcional FD ya no existiría. Esto significa que la FD está implícita en los datos, ya que es posible que haya valores que invaliden la FD.

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

• {ID de estudiante, conferencia} → TA
• {ID de estudiante, conferencia} → {TA, semestre}

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

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 se incorporan múltiples dependencias funcionales 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.

• ID del empleado → Nombre del empleado
• ID de empleado → ID de 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 exista un ID de empleado → ID de departamento en el FD, 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 en función de los datos.

Propiedades y axiomatización de dependencias funcionales

Dado que X , Y y Z son conjuntos de atributos en una relación R , se pueden derivar varias propiedades de dependencias funcionales. Entre las más importantes se encuentran las siguientes, generalmente llamadas axiomas de Armstrong : ^[3]

• Reflexividad : Si Y es un subconjunto de X , entonces X → Y
• Aumento : Si X → Y , entonces XZ → YZ
• Transitividad : Si X → Y e Y → Z , entonces X → Z

La "reflexividad" puede debilitarse a simplemente , es decir, es un axioma real, donde los otros dos son reglas de inferencia adecuadas , dando lugar más precisamente a las siguientes reglas de consecuencia sintáctica: ^[4] ${\displaystyle X\rightarrow \varnothing }$

${\displaystyle \vdash X\rightarrow \varnothing }$
${\displaystyle X\rightarrow Y\vdash XZ\rightarrow YZ}$
${\displaystyle X\rightarrow Y,Y\rightarrow Z\vdash X\rightarrow Z}$.

Estas tres reglas constituyen una axiomatización sólida y completa de las dependencias funcionales. Esta axiomatización se describe a veces 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 básicos (conjuntos de atributos). ^[4]

Aplicando aumento y transitividad, se pueden derivar dos reglas adicionales:

• Pseudotransitividad : Si X → Y y YW → Z , entonces XW → Z ^[3]
• Composición : Si X → Y y Z → W , entonces XZ → YW ^[6]

También se pueden derivar las reglas de unión y descomposición de los axiomas de Armstrong: ^{[3] [7]}

X → Y y X → Z si y sólo si X → YZ

Cierre

Cierre de la 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 dada utilizando sus dependencias funcionales. Se utilizan los axiomas de Armstrong para proporcionar una prueba, es decir, reflexividad, aumento y transitividad.

Dado un conjunto de funciones diferenciales que se cumplen en : El cierre de en (denotado ⁺ ) es el conjunto de todas las funciones diferenciales que están lógicamente implicadas por . ^[8] ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle F}$

Cierre de un conjunto de atributos

El cierre de un conjunto de atributos X con respecto a es el conjunto X ⁺ de todos los atributos que están determinados funcionalmente por X usando ⁺ . ${\displaystyle F}$ ${\displaystyle F}$

Ejemplo

Imaginemos la siguiente lista de FD. Vamos a calcular un cierre para A (escrito como A ⁺ ) a partir de esta relación.

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

El cierre quedaría de la siguiente manera:

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

Por lo tanto, A ⁺ = ABCD. Como A ⁺ incluye todos los atributos de la relación, es una superclave .

Coberturas y equivalencias

Cubiertas

Definición : cubre si cada FD en puede inferirse de . cubre si ⁺ ⊆ ⁺ Cada conjunto de dependencias funcionales tiene una cobertura canónica . ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle F}$

Equivalencia de dos conjuntos de FD

Dos conjuntos de dependencias funcionales y su esquema 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í. ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$

Cubiertas no redundantes

Un conjunto de FD no es redundante si no hay un subconjunto propio de con ≡ . Si existe tal , es redundante. es una cubierta no redundante para si es una cubierta para y no es redundante. Una caracterización alternativa de la no redundancia es que es no redundante si no hay un FD X → Y en tal que - { X → Y } X → Y . Llamemos a un FD X → Y en redundante en si - { X → Y } X → Y . ${\displaystyle F}$ ${\displaystyle F'}$ ${\displaystyle F}$ ${\displaystyle F'}$ ${\displaystyle F}$ ${\displaystyle F'}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$
${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle \models }$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle \models }$

Aplicaciones de la normalización

Teorema de Heath

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 una dependencia funcional X → Y se cumple en R , entonces la relación se puede dividir de manera 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, una dependencia funcional proporciona una forma sencilla de construir una descomposición de unión sin pérdida de R en dos relaciones más pequeñas. Este hecho a veces se llama teorema de Heath ; es uno de los primeros resultados en la teoría de bases de datos. ^[9] ${\displaystyle R=\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$ ${\displaystyle \Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$

El teorema de Heath dice efectivamente que podemos extraer los valores de Y de la gran relación R y almacenarlos en una, , 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, tiene solo un lugar para actualizar la Y correspondiente a cada X a diferencia de la "gran" relación R donde hay potencialmente muchas copias de cada X , cada una con su copia de Y que deben mantenerse sincronizadas en las actualizaciones. (Esta eliminación de 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 una clave externa en el resto de la gran tabla . ${\displaystyle \Pi _{XY}(R)}$ ${\displaystyle \Pi _{XZ}(R)}$

Sin embargo, las dependencias funcionales no deben confundirse con las dependencias de inclusión , que son el formalismo para 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 . La aplicación de restricciones referenciales después de la descomposición del esquema de relación (normalización) requiere un nuevo formalismo, es decir, las dependencias de inclusión. En la descomposición resultante del teorema de Heath, no hay nada que impida la inserción de tuplas en tener algún valor de X que no se encuentre en . ${\displaystyle \Pi _{XZ}(R)}$ ${\displaystyle \Pi _{XY}(R)}$

Formas normales

Las formas normales son niveles de normalización de bases de datos que determinan la "bondad" de una tabla. Generalmente, la tercera forma normal se considera un estándar "bueno" para una base de datos relacional. ^{[ cita requerida ]}

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, un efecto mínimo en las aplicaciones que la utilizan. ^{[ cita requerida ]}

Conjunto dependiente de función irreducible

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

1. Cada conjunto derecho de una dependencia funcional de S contiene sólo un atributo.
2. Cada conjunto izquierdo de una dependencia funcional de S es irreducible. Esto significa que al reducir cualquier atributo del conjunto izquierdo, se modificará el contenido de S (S perderá parte de la 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 un conjunto de entrada S' proporcionado como entrada se denomina encontrar una cobertura mínima de S': este problema se puede resolver en tiempo polinomial. ^[10]

Véase también

• Persecución (algoritmo)
• Dependencia de inclusión
• Unirse a la dependencia
• Dependencia multivalorada (MVD)
• Normalización de bases de datos
• Primera forma normal

Referencias

1. Terry Halpin (2008). Modelado de información y bases de datos relacionales (2.ª ed.). Morgan Kaufmann. pág. 140. ISBN 978-0-12-373568-3.
2. Chris Date (2012). Diseño de bases de datos y teoría relacional: formas normales y todo eso. O'Reilly Media, Inc., pág. 21. ISBN 978-1-4493-2801-6.
3. Abraham Silberschatz ; Henry Korth ; S. Sudarshan (2010). Conceptos de sistemas de bases de datos (6.ª ed.). McGraw-Hill. pág. 339. ISBN 978-0-07-352332-3.
4. MY Vardi. Fundamentos de la teoría de la dependencia. En E. Borger, editor, Trends in Theoretical Computer Science, páginas 171–224. Computer Science Press, Rockville, MD, 1987. ISBN 0881750840 
5. Abiteboul, Serge ; Hull, Richard B.; Vianu, Victor (1995), Fundamentos de bases de datos, Addison-Wesley, págs. 164-168, ISBN 0-201-53771-0
6. SK Singh (2009) [2006]. Sistemas de bases de datos: conceptos, diseño y aplicaciones. Pearson Education India. pág. 323. ISBN 978-81-7758-567-4.
7. Hector Garcia-Molina; Jeffrey D. Ullman; Jennifer Widom (2009). Sistemas de bases de datos: el libro completo (2.ª ed.). Pearson Prentice Hall. pág. 73. ISBN 978-0-13-187325-4.Esto a veces se llama la regla de dividir/combinar.
8. Saiedian, H. (1996-02-01). "Un algoritmo eficiente para calcular las claves candidatas de un esquema de base de datos relacional". The Computer Journal . 39 (2): 124–132. doi :10.1093/comjnl/39.2.124. ISSN  0010-4620.
9. Heath, IJ (1971). "Operaciones de archivo inaceptables en una base de datos relacional". Actas del taller de 1971 de ACM SIGFIDET (ahora SIGMOD) sobre descripción, acceso y control de datos - SIGFIDET '71 . págs. 19–33. doi :10.1145/1734714.1734717. S2CID  22069259.citado en:
   • Ronald Fagin y Moshe Y. Vardi (1986). "La teoría de las dependencias de los datos: un estudio". En Michael Anshel y William Gewirtz (ed.). Matemáticas del procesamiento de la información: [Curso breve celebrado en Louisville, Kentucky, 23 y 24 de enero de 1984] . American Mathematical Soc. pág. 23. ISBN 978-0-8218-0086-7.
   • C. Date (2005). Base de datos en profundidad: teoría relacional para profesionales. O'Reilly Media, Inc., pág. 142. ISBN 978-0-596-10012-4.
10. Meier, Daniel (1980). "Coberturas mínimas en el modelo de base de datos relacional". Revista de la ACM . 27 (4): 664–674. doi : 10.1145/322217.322223 . S2CID  15789293.

Lectura adicional

• Codd, EF (1972). "Normalización adicional del modelo relacional de bases de datos" (PDF) . Transacciones ACM en sistemas de bases de datos . San José, California: Association for Computing Machinery .

Enlaces externos

• Gary Burt (verano de 1999). "Apuntes de la clase CS 461 (Sistemas de gestión de bases de datos)". Departamento de Ciencias de la Computación e Ingeniería Eléctrica de la Universidad de Maryland, Condado de Baltimore .
• Jeffrey D. Ullman. "Apuntes de la clase CS345" ( PostScript ) . Universidad de Stanford.
• Osmar Zaiane (9 de junio de 1998). "Capítulo 6: Restricciones de integridad". Apuntes de la clase CMPT 354 (Sistemas de bases de datos I) . Departamento de Ciencias de la Computación de la Universidad Simon Fraser .