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 claves. Dada una relación R y conjuntos de atributos, Se dice que X determina funcionalmente Y (escrito X → Y ) si y solo si cada valor de X en R está asociado precisamente con un valor de Y en R ; R Se dice entonces que satisfacer 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 ax se pueden determinar buscándolos en cualquier tupla de R que contenga x . Habitualmente X se llama el determinante conjunto y Y el dependiente conjunto. A FD dependencia funcional: 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 se determinan por los valores de X . Dos tuplas que comparten los mismos valores de X tendrán necesariamente 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 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 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, endonde Z = U - XY son el resto de los atributos. (Las uniones de conjuntos de atributos se denotan habitualmente por meras 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 tantos datos inapropiados para el dominio del usuario 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 implica lógicamente otro conjunto de dependencias , si alguna relación R satisface 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 axiomatización finita sólida y completa , conocida como axiomas de Armstrong .
Ejemplos de
Carros
Suponga 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 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 relación con la clave candidata VIN. Sin embargo, puede que eso no siempre sea apropiado. Por ejemplo, si esa dependencia funcional ocurre como resultado de las dependencias funcionales transitivas VIN → VehicleModel y VehicleModel → EngineCapacity, entonces eso no resultaría en una relación normalizada.
Conferencias
Este ejemplo ilustra el concepto de dependencia funcional. La situación modelada es la de los 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 todos los estudiantes están en algún semestre y se identifican con un ID entero único.
Identificación del Estudiante | Semestre | Conferencia | ejército de reserva |
---|---|---|---|
1234 | 6 | Métodos numéricos | John |
1221 | 4 | Métodos numéricos | Herrero |
1234 | 6 | Computación visual | Beto |
1201 | 2 | Métodos numéricos | Pedro |
1201 | 2 | Física II | Simón |
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 puede expresarse mediante una dependencia funcional:
- StudentID → Semestre.
Tenga en cuenta que si se agrega una fila donde el estudiante tiene un valor de semestre diferente, 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.
ID de empleado | Nombre de empleado | ID de departamento | Nombre de Departamento |
---|---|---|---|
0001 | John Doe | 1 | Recursos humanos |
0002 | fulano de tal | 2 | Márketing |
0003 | John Smith | 1 | Recursos humanos |
0004 | Jane Goodall | 3 | Ventas |
Este caso representa un ejemplo en el que se incrustan múltiples dependencias funcionales 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 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 no clave
- ID de departamento → Nombre de 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 la ID de 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 , se pueden derivar varias propiedades de las dependencias funcionales. Entre los más importantes se encuentran los siguientes, generalmente 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" se puede debilitar a solo , es decir, es un axioma real , donde las otras 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 básicos (conjuntos de atributos) . [4]
Al aplicar el aumento y la 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 solo 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 y un conjunto de FD que se mantiene en : El cierre de en (denotado + ) es el conjunto de todos los FD que están implícitos lógicamente en.
Cierre de un conjunto de atributos
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+ .
Ejemplo
Imagínese la siguiente lista de DF. 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)
Por tanto, el cierre es A → ABCD. Al calcular el cierre de A, hemos validado que A también es una clave candidata buena, ya que su cierre es cada valor de datos en la relación.
Coberturas y equivalencia
Cubiertas
Definición : cubre si cada FD en se puede inferir de . cubre Si + ⊆+
Cada conjunto de dependencias funcionales tiene una cobertura canónica .
Equivalencia de dos conjuntos de FD
Dos juegos de FD y sobre el esquema son equivalentes, escritos ≡ , Si + =+ . Si ≡ , luego es una tapadera para y viceversa. En otras palabras, los conjuntos equivalentes de dependencias funcionales se denominan coberturas entre sí.
Cubiertas no redundantes
Un conjunto de FD no es redundante si no hay un subconjunto adecuado de con ≡ . Si tal existe es redundante. es una cobertura no redundante para Si es una tapadera para y no es redundante.
Una caracterización alternativa de la no redundancia es queno es redundante si no hay FD X → Y en tal que - { X → Y } X → Y . Llame a un FD X → Y en redundante en Si - { X → Y } X → Y .
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 entoncesdonde Z = U - XY . Intuitivamente, si una dependencia funcional X → Y se cumple en R , entonces la relación se puede dividir con seguridad en dos relaciones junto a la columna X (que es una clave para) asegurando que cuando las dos partes se vuelven a unir no se pierden datos, es decir, una dependencia funcional proporciona una forma sencilla de construir una descomposición de unión 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. [8]
El teorema de Heath dice efectivamente que podemos extraer los valores de Y de la gran relación R y almacenarlos en uno,, que no tiene repeticiones de valor en la fila para X y es efectivamente una tabla de búsqueda para Y con clave de X y, en consecuencia, solo tiene un 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 uno con su copia de Y que deben mantenerse sincronizados 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 a 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 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, dependencias de inclusión. En la descomposición resultante del teorema de Heath, nada impide la inserción de tuplas entener algún valor de X no encontrado en.
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 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 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. [ cita requerida ]
Función irreducible según set
Un conjunto S de dependencias funcionales es irreducible si el conjunto tiene las siguientes tres propiedades:
- Cada conjunto correcto de una dependencia funcional de S contiene solo un atributo.
- 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á algo de información).
- 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 tal conjunto S de dependencias funcionales que sea equivalente a algún conjunto de entrada S 'proporcionado como entrada se llama encontrar una cobertura mínima de S': este problema se puede resolver en tiempo polinomial. [9]
Ver también
- Chase (algoritmo)
- Dependencia de inclusión
- Unirse a la dependencia
- Dependencia multivalor (MVD)
- Normalización de la base de datos
- Primera forma normal
Referencias
- ^ Terry Halpin (2008). Modelado de información y bases de datos relacionales (2ª ed.). Morgan Kaufmann. pag. 140. ISBN 978-0-12-373568-3.
- ^ Chris Date (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.
- ^ a b c Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Conceptos del sistema de base de datos (6ª ed.). McGraw-Hill. pag. 339. ISBN 978-0-07-352332-3.
- ^ a b M. Y. 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
- ^ Abiteboul, Serge ; Hull, Richard B .; Vianu, Victor (1995), Fundamentos de bases de datos , Addison-Wesley, págs. 164-168 , ISBN 0-201-53771-0
- ^ SK Singh (2009) [2006]. Sistemas de bases de datos: conceptos, diseño y aplicaciones . Pearson Education India. pag. 323. ISBN 978-81-7758-567-4.
- ^ 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. Esto a veces se denomina regla de división / combinación.
- ^ Heath, IJ (1971). "Operaciones de archivo inaceptables en una base de datos relacional". Actas del taller de 1971 ACM SIGFIDET (ahora SIGMOD) sobre descripción, acceso y control de datos - SIGFIDET '71 . págs. 19–33. doi : 10.1145 / 1734714.1734717 . 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 la información: [curso corto celebrado en Louisville, Kentucky, del 23 al 24 de enero de 1984] . American Mathematical Soc. 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.
- ^ Meier, Daniel (1980). "Coberturas mínimas en el modelo de base de datos relacional". Revista de la ACM . doi : 10.1145 / 322217.322223 .
enlaces externos
- Gary Burt (verano de 1999). "Notas de la conferencia CS 461 (sistemas de gestión de bases de datos)" . Universidad de Maryland Departamento de Ciencias de la Computación e Ingeniería Eléctrica del Condado de Baltimore .
- Jeffrey D. Ullman. "CS345 Lecture Notes" ( PostScript ) . Universidad Stanford.
- Osmar Zaiane (9 de junio de 1998). "Capítulo 6: Restricciones de integridad" . CMPT 354 (Sistemas de bases de datos I) . Departamento de Ciencias de la Computación de la Universidad Simon Fraser .