Dependencia funcional

Concepto de teoría de bases de datos relacionales

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. ${\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 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. ${\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 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 . ${\displaystyle \Sigma }$ ${\displaystyle \Gamma }$ ${\displaystyle \Sigma }$ ${\displaystyle \Gamma }$ ${\displaystyle \Sigma \models \Gamma }$

Ejemplos

Carros

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.

conferencias

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:

• ID de estudiante → Semestre.

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:

• {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.

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 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.

• ID de 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 que no es clave.

• ID de departamento → Nombre de departamento

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.

Propiedades y axiomatización de las 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 los más importantes se encuentran los siguientes, habitualmente llamados 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 propias , 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 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:

• Pseudotransitividad : si X → Y e 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 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. 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] ${\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 funcionalmente determinados por X usando ⁺ . ${\displaystyle F}$ ${\displaystyle F}$

Ejemplo

Imagine 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:

1. A → A (por 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 tanto, el cierre es 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 de la relación.

Coberturas y equivalencias

Cubiertas

Definición : cubre si se puede inferir cada FD . 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 FD y un esquema superior son equivalentes, escritos ≡ , si ⁺ = ⁺ . Si ≡ , entonces es una cobertura para y viceversa. En otras palabras, 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}$

Coberturas no redundantes

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 . ${\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 a 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 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] ${\displaystyle R=\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$ ${\displaystyle \Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$

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 implican principalmente consultas). La descomposición de Heath deja solo X para actuar como clave externa en el resto de la tabla grande. . ${\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 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 . ${\displaystyle \Pi _{XZ}(R)}$ ${\displaystyle \Pi _{XY}(R)}$

Formas normales

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 ]}

Función irreducible según conjunto.

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

1. Cada conjunto de derechos de una dependencia funcional de S contiene solo un atributo.
2. Cada conjunto izquierdo de una dependencia funcional de S es irreducible. Significa que reducir cualquier atributo del conjunto izquierdo cambiará 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 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]

Ver también

• Persecución (algoritmo)
• Dependencia de inclusión
• Unirse a la dependencia
• Dependencia multivalor (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 Kaufman. pag. 140.ISBN _ 978-0-12-373568-3.
2. Fecha de Chris (2012). Diseño de bases de datos y teoría relacional: formas normales y todo ese jazz. O'Reilly Media, Inc. pág. 21.ISBN _ 978-1-4493-2801-6.
3. Abraham Silberschatz ; Henry Korth ; S. Sudarshan (2010). Conceptos del sistema de bases de datos (6ª ed.). McGraw-Hill. pag. 339.ISBN _ 978-0-07-352332-3.
4. MI Vardi. Fundamentos de la teoría de la dependencia. En E. Borger, editor, Trends in Theoretical Computer Science, páginas 171–224. Prensa de Ciencias de la Computación, Rockville, MD, 1987. ISBN 0881750840 
5. Abiteboul, Serge ; Casco, Richard B.; Vianu, Victor (1995), Fundamentos de las 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. Educación Pearson India. pag. 323.ISBN _ 978-81-7758-567-4.
7. Héctor García-Molina; Jeffrey D. Ullman; Jennifer Widom (2009). Sistemas de bases de datos: el libro completo (2ª ed.). Pearson-Prentice Hall. pag. 73.ISBN _ 978-0-13-187325-4.A esto a veces se le llama regla de división/combinación.
8. Saiedian, H. (1 de febrero de 1996). "Un algoritmo eficiente para calcular las claves candidatas de un esquema de base de datos relacional". La revista informática . 39 (2): 124-132. doi : 10.1093/comjnl/39.2.124. ISSN  0010-4620.
9. Heath, IJ (1971). "Operaciones de archivos inaceptables en una base de datos relacional". Actas del taller ACM SIGFIDET (ahora SIGMOD) de 1971 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 datos: una encuesta". En Michael Anshel y William Gewirtz (ed.). Matemáticas del procesamiento de información: [curso corto celebrado en Louisville, Kentucky, 23 y 24 de enero de 1984] . Sociedad Matemática Estadounidense. pag. 23.ISBN _ 978-0-8218-0086-7.
   • C. Fecha (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.

Otras lecturas

• Codd, EF (1972). "Mayor normalización del modelo relacional de base de datos" (PDF) . Transacciones ACM en sistemas de bases de datos . San José, California: Asociación de Maquinaria de Computación .

enlaces externos

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