Dependencia multivaluada

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 2 de junio de 2019; las comprobaciones requieren 2 ediciones .

La dependencia multivaluada (también MZZ ) es una generalización del concepto de dependencia funcional , ampliamente utilizado en la teoría de bases de datos . En el concepto de formas normales , se introduce para definir formalmente la cuarta forma normal

Definiciones

Que haya alguna relación con el esquema , así como dos subconjuntos arbitrarios de atributos . deja _ $r$ $R$ $A,B\subseteq R$ $C{\overset {\mahop {=} }{\,}}R\barra invertida (A\cup B)$

En este caso, depende de , si y solo si el conjunto de valores de los atributos correspondientes al par de relaciones dado depende y no depende de . $B$ $A$ $B$ ${\ estilo de visualización [a: A; c: C]}$ $r$ $a$ $C$

Expresado simbólicamente por escrito

A\twoheadrightarrow B

Formalmente

{\begin{alineado}&r\left(R\right),\ A,B\subseteq R,\ C=R\backslash (A\cup B)\\&\left(A\twoheadrightarrow B\right )\Leftrightarrow \forall {{t}_{1}},{{t}_{2}}\en r\ \existe {{t}_{3}},{{t}_{4}}\ en r\ :\ \left\{{\begin{alineado}&{{t}_{1}}\left(A\right)={{t}_{2}}\left(A\right)= {{t}_{3}}\left(A\right)={{t}_{4}}\left(A\right)\\&{{t}_{3}}\left(B\ derecha)={{t}_{1}}\izquierda(B\derecha)\\&{{t}_{3}}\izquierda(C\derecha)={{t}_{2}}\izquierda (C\derecha)\\&{{t}_{4}}\izquierda(B\derecha)={{t}_{2}}\izquierda(B\derecha)\\&{{t}_{ 4}}\left(C\right)={{t}_{1}}\left(C\right)\\\end{alineado}}\right.\\\end{alineado}}

Una dependencia multivaluada se llama trivial si al menos una de las siguientes condiciones es verdadera: $A\twoheadrightarrow B$

El conjunto es un superconjunto ; $A$ $B$ $B\subconjunto A$
Unión y forma el encabezado completo de la relación. $A$ $B$ $A\taza B=R$

Ejemplo

Supongamos que tenemos una relación que incluye una lista de disciplinas académicas, literatura recomendada y los nombres de los profesores que imparten los cursos correspondientes:

Disciplinas academicas

Disciplina	Libro	Conferenciante
Matan	Kudryavtsev	Ivanov A.
Matan	Fikhtengolts	Petrov B.
Matan	Kudryavtsev	Petrov B.
Matan	Fikhtengolts	Ivanov A.
Matan	Kudryavtsev	Smirnov V.
Matan	Fikhtengolts	Smirnov V.
máquina virtual	Kudryavtsev	Ivanov A.
máquina virtual	Kudryavtsev	Petrov B.

Dado que los profesores que leen el tema y los libros recomendados sobre el tema no dependen el uno del otro, esta relación contiene una dependencia multivaluada. Esta actitud tiene una serie de anomalías. Una de ellas es que si queremos recomendar un libro nuevo en un curso de MatAn, tendremos que añadir tantas entradas nuevas como profesores haya en MatAn y viceversa.

Formalmente, hay dos MZZ: {Disciplina} {Libro}|{Profesor} . ${\ estilo de visualización \ flecha derecha de dos cabezas}$

Primero, es redundante. Y en segundo lugar, para tal relación, es necesario desarrollar un mecanismo de control de integridad adicional. La solución óptima al problema sería descomponer la relación en dos con los encabezados {Disciplina, Libro} y {Disciplina, Profesor} . Tal descomposición estaría en 4NF . La admisibilidad de la descomposición se establece mediante el teorema de Fagin (ver más abajo).

Teoremas

Pares conectados

Fagin mostró que las dependencias multivaluadas forman pares conectados (en notación de definición):

\left(A\twoheadrightarrow B\right)\Leftrightarrow \left(A\twoheadrightarrow C\right)

Por lo tanto, a menudo se representan juntos en notación simbólica:

A\twoheadrightarrow B|C

Dependencias funcionales

Cualquier dependencia funcional es multivaluada. En otras palabras, una dependencia funcional es una dependencia multivaluada en la que el conjunto de valores dependientes correspondientes a un valor dado del determinante siempre tiene potencia unitaria .

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

Reglas de salida

En 1977, Bury, Fagin y Howard encontraron que las reglas de inferencia de Armstrong pueden generalizarse y extenderse tanto a dependencias funcionales como multivaluadas.

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$

Grupo 1: reglas básicas.

Suma $\left(A\cup B\cup C=R\right)\wedge \left(B\cap C\subseteq A\right)\Rightarrow \left(\left(A\twoheadrightarrow B\right)\Leftrightarrow \left(A\twoheadrightarrow C\right)\right)$
transitividad $\left(A\twoheadrightarrow B\right)\wedge \left(B\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow C\backslash B\right)$
reflexividad $\left(B\subseteq A\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
Incremento $\left(A\twoheadrightarrow B\right)\wedge \left(C\subseteq D\right)\Rightarrow \left(AD\twoheadrightarrow BC\right)$

Grupo 2: se derivan varias reglas adicionales para simplificar la tarea de inferir dependencias multivaluadas.

pseudotransitividad $\left(A\twoheadrightarrow B\right)\wedge \left(BC\twoheadrightarrow D\right)\Rightarrow \left(AC\twoheadrightarrow D\backslash BC\right)$
Una asociación $\left(A\twoheadrightarrow B\right)\wedge \left(A\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow BC\right)$
Descomposición $\left(A\twoheadrightarrow BC\right)\Rightarrow \left(A\twoheadrightarrow B\cap C\right)\wedge \left(A\twoheadrightarrow B\backslash C\right)\wedge \left(A\ flecha derecha de dos cabezas C\barra invertida B\derecha)$

Grupo 3: Se establece un vínculo entre dependencias funcionales y polivalentes.

Replicación (copia) $\left(A\to B\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
fusión $\left(A\twoheadrightarrow B\right)\wedge \left(C\to D\right)\wedge \left(D\subseteq B\right)\wedge \left(B\cap C=\varnothing \ derecha) \ Flecha derecha \ izquierda (A \ a D \ derecha)$

Grupo 4: para dependencias funcionales, derivadas de las reglas anteriores.

$\left(A\twoheadrightarrow B\right)\wedge \left(AB\to C\right)\Rightarrow \left(A\to C\backslash B\right)$

Las reglas de inferencia de Armstrong, junto con las reglas de los grupos 1 y 3 descritas aquí, forman una relación completa (usándolas, uno puede derivar todas las demás dependencias multivaluadas implícitas en su conjunto dado) y confiable (las dependencias multivaluadas "extra" no pueden ser deducida; la dependencia multivaluada derivada es válida siempre que sea un conjunto de dependencias multivaluadas del que se derivó) un conjunto de reglas para inferir dependencias multivaluadas.

Aplicación

Descomposición de relaciones

Teorema de Fagin

Sea dada la proporción . Una relación será igual a la unión de sus proyecciones si y solo si la relación satisface una dependencia multivaluada no trivial . ${\ estilo de visualización r \ izquierda (A, B, C \ derecha)}$ $r$ $r\izquierda[A,B\derecha]$ ${\ estilo de visualización r \ izquierda [A, C \ derecha]}$ $r$ $A\twoheadrightarrow B|C$

\left(r\left(A,B,C\right)=r\left[A,B\right]\ {\text{ÚNETE))\ r\left[A,C\right]\right )\Leftrightarrow \left(A\twoheadrightarrow B|C\right)

Este teorema es una versión más estricta del teorema de Heath .

Véase también

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 .