Dependencia funcional (programación)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de junio de 2018; las comprobaciones requieren 13 ediciones .

La dependencia funcional es una relación binaria entre conjuntos de atributos de una relación dada y es, de hecho, una relación de uno a muchos. Su uso se debe a que permite resolver de manera formal y estricta muchos problemas.

La dependencia funcional es un concepto que subyace en muchas cuestiones relacionadas con las bases de datos relacionales , incluido, en particular, su diseño.

Definiciones

Dependencia funcional

Sea una relación dada con un esquema (encabezado) , y sean algunos subconjuntos del conjunto de atributos de la relación . Un conjunto depende funcionalmente de si y sólo si cada valor del conjunto está asociado con exactamente un valor del conjunto . designado _ $r$ $R$ $A$ $B$ $r$ $B$ $A$ $A$ $B$ $De la A, a la B$

En otras palabras, si dos tuplas tienen el mismo valor en , entonces tienen el mismo valor en . $A$ $B$

r\left(R\right),\ A\subseteq R,\ B\subseteq R

\left(A\to B\right)\Leftrightarrow \left(\left(\forall {{t}_{1}},{{t}_{2}}\in r:{{t} _ {1}}\left(A\right)={{t}_{2}}\left(A\right)\right)\Rightarrow \left({{t}_{1}}\left(B \right)={{t}_{2}}\left(B\right)\right)\right)

En este caso , el determinante es la parte dependiente. $A$ $B$

Se dice que una dependencia funcional es trivial si la parte dependiente es un subconjunto del determinante.

\left(B\subseteq A\right)\Rightarrow \left(A\to B\right)

Cerrar un conjunto de dependencias

Algunas dependencias funcionales pueden implicar otras dependencias funcionales. Por ejemplo, la dependencia funcional,

{\ estilo de visualización \ izquierda (A \ a B \ derecha) \ cuña \ izquierda (B \ a C \ derecha) \ Rightarrow \ izquierda (A \ a C \ derecha)}

El conjunto de todas las dependencias funcionales implícitas en un conjunto dado de dependencias funcionales se denomina cierre del conjunto . ${\ estilo de visualización {{S}^{+}}}$ $S$ $S$

Cierre del conjunto de atributos

Sea algún conjunto de atributos de la relación y sea el conjunto de dependencias funcionales de esta relación. La clausura del conjunto de atributos dentro de los límites es tal conjunto de todos los atributos de la relación que la dependencia funcional es miembro de la clausura . $Z$ $r$ $S$ ${\ estilo de visualización {{Z}^{+}}}$ $Z$ $S$ ${\ estilo de visualización {{A}_{i))}$ $r$ $Z\to {{A}_{i))$ ${\ estilo de visualización {{S}^{+}}}$

r\left(R\right),\ S,\ Z\subseteq R,\ {{A}_{i}}\subseteq R,\ i={\overline {1,n}}

{{Z}^{+}}=\left\{{{A}_{i}}:\left(Z\to {{A}_{i}}\right)\in {{S }^{+}}\derecho\}

Conjuntos irreducibles de dependencias

Sean y sean algunos conjuntos de dependencias funcionales. ${\ estilo de visualización {{S}_{1}}}$ ${\ estilo de visualización {{S}_{2))}$

Si alguna dependencia funcional entra y entra , entonces se llama la cubierta del conjunto de dependencias funcionales . ${\ estilo de visualización {{S}_{1}}}$ ${\ estilo de visualización {{S}_{2}^{+}}}$ ${\ estilo de visualización {{S}_{2))}$ ${\ estilo de visualización {{S}_{1}}}$
Si es una tapa para , y es una tapa para (es decir, ), entonces tales conjuntos se llaman equivalentes . ${\ estilo de visualización {{S}_{2))}$ ${\ estilo de visualización {{S}_{1}}}$ ${\ estilo de visualización {{S}_{1}}}$ ${\ estilo de visualización {{S}_{2))}$ ${\ estilo de visualización S_{1}^{+}=S_{2}^{+))$
Se dice que un conjunto de dependencias funcionales es irreducible si y solo si se cumplen las siguientes condiciones: $S$
- En cada dependencia funcional, la parte dependiente contiene solo un elemento;
- El determinante de toda dependencia funcional es irreducible (no se puede quitar ningún atributo del determinante sin cambiar la clausura ); ${\ estilo de visualización {{S}^{+}}}$
- Ninguna de las dependencias funcionales de puede eliminarse sin cambiar el cierre . $S$ ${\ estilo de visualización {{S}^{+}}}$
Para cualquier conjunto de dependencias funcionales, existe al menos un conjunto equivalente que es irreducible. Tal conjunto equivalente se llama cobertura irreducible .

Evaluación de cierre

Reglas de inferencia de Armstrong

En 1974, William Armstrong propuso un conjunto de reglas para inferir nuevas dependencias funcionales de los datos.

Digamos que tenemos una relación y un conjunto de atributos . Para acortar el registro, escribiremos simplemente . ${\ estilo de visualización r \ izquierda (R \ derecha)}$ $A,B,C,D\subseteq R$ ${\ estilo de visualización X \ copa Y}$ $XY$

reflexividad : $\left(B\subseteq A\right)\Rightarrow \left(A\to B\right)$
Reposición : $\left(A\to B\right)\Rightarrow \left(AC\to BC\right)$
transitividad : ${\ estilo de visualización \ izquierda (A \ a B \ derecha) \ cuña \ izquierda (B \ a C \ derecha) \ Rightarrow \ izquierda (A \ a C \ derecha)}$

Las reglas de inferencia de Armstrong son completas (usándolas, uno puede derivar todas las demás dependencias funcionales implícitas en el conjunto dado) y confiables (las dependencias funcionales "superfluas" no se pueden deducir: la dependencia funcional derivada es válida siempre que las dependencias funcionales originales (de las cuales fue derivados) son válidos).

Además, varias reglas adicionales se derivan simplemente de estas reglas, lo que simplifica la tarea de derivar dependencias funcionales.

Autodeterminación : ${\ estilo de visualización A \ a A}$
Descomposición : $\left(A\to BC\right)\Rightarrow \left(A\to B\right)\wedge \left(A\to C\right)$
Consolidación : $\left(A\to B\right)\wedge \left(A\to C\right)\Rightarrow \left(A\to BC\right)$
Composición : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(AC\to BD\right)$
Teorema de unificación universal de Darwen : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(A\cup \left(CB\right)\to BD\right)$

Teorema: Se infiere una dependencia funcional a partir de un conjunto dado de dependencias funcionales de acuerdo con las reglas de inferencia de Armstrong si y solo si . $De la A, a la B$ $S$ $B\subseteq {{A}^{+}}$

Cierre del conjunto de atributos

Si aplicamos las reglas de la sección anterior hasta que la creación de nuevas dependencias funcionales se detenga por sí sola, obtendremos un cierre para un conjunto dado de dependencias funcionales. En la práctica, rara vez es necesario calcular este cierre por sí mismo, la mayoría de las veces estamos mucho más interesados en saber si esta o aquella dependencia funcional se incluirá en el cierre. Para ello, basta con que calculemos la clausura del determinante. Hay un algoritmo bastante simple para esto.

Sea un conjunto de atributos que eventualmente se convertirán en un cierre. $X$
Buscamos dependencias funcionales de la forma , where y . Agregamos la parte dependiente de cada dependencia encontrada a . ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\to C$ ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\subseteq X$ $C\no \subconjunto X$ $X$
Repita el paso 2 hasta que sea imposible agregar atributos al conjunto. $X$
Un conjunto al que no se le pueden agregar atributos será un cierre. $X$

Aplicación

Diseño de base de datos

Las dependencias funcionales son restricciones de integridad y definen la semántica de los datos almacenados en la base de datos. Con cada actualización, el DBMS debe verificar su cumplimiento. Por lo tanto, la presencia de una gran cantidad de dependencias funcionales no es deseable, de lo contrario, ralentiza el trabajo. Para simplificar la tarea, es necesario reducir el conjunto de dependencias funcionales al mínimo requerido.

Si es una cobertura irreducible del conjunto inicial de dependencias funcionales , la comprobación del cumplimiento de las dependencias funcionales de automáticamente garantiza el cumplimiento de todas las dependencias funcionales de . Así, la tarea de encontrar el conjunto mínimo necesario se reduce a encontrar una cobertura irreducible del conjunto de dependencias funcionales, que se utilizará en lugar del conjunto original. $yo$ $S$ $yo$ $S$

Véase también

modelo de datos relacionales
Diseño de base de datos
forma normal
La dependencia multivaluada es una generalización de la dependencia funcional.

Literatura

K. J. Fecha. Introducción a los Sistemas de Base de Datos = Introducción a los Sistemas de Base de Datos. - 8ª edición. - M .: "Williams" , 2006. - S. 1328. - ISBN 0-321-19784-4 .