Dependencia multivaluada

En la teoría de bases de datos , una dependencia multivaluada es una restricción completa entre dos conjuntos de atributos en una relación .

A diferencia de la dependencia funcional , la dependencia multivaluada requiere que ciertas tuplas estén presentes en una relación. Por lo tanto, una dependencia multivaluada es un caso especial de dependencia generadora de tuplas . La dependencia multivaluada desempeña un papel en la normalización de bases de datos 4NF .

Una dependencia multivaluada es un caso especial de una dependencia de unión , en la que solo intervienen dos conjuntos de valores, es decir, es una dependencia de unión binaria.

Existe una dependencia multivaluada cuando hay al menos tres atributos (como X, Y y Z) en una relación y para un valor de X existe un conjunto bien definido de valores de Y y un conjunto bien definido de valores de Z. Sin embargo, el conjunto de valores de Y es independiente del conjunto de Z y viceversa.

La definición formal es la siguiente: ^{[ 1 ]}

Sea un esquema de relaciones y sean y conjuntos de atributos. La dependencia multivaluada (" multidetermina ") se cumple si, para cualquier relación válida y para todos los pares de tuplas y en tales que , existen tuplas y en tales que:${\displaystyle R}$${\displaystyle \alpha \subsetequ R}$${\displaystyle \beta \subsetequ R}$${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle R}$${\displaystyle r(R)}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle r}$${\displaystyle t_{1}[\alpha ]=t_{2}[\alpha ]}$${\displaystyle t_{3}}$${\displaystyle t_{4}}$${\displaystyle r}$

${\displaystyle {\begin{matrix}t_{1}[\alpha ]=t_{2}[\alpha ]=t_{3}[\alpha ]=t_{4}[\alpha ]\\t_{1}[\beta ]=t_{3}[\beta ]\\t_{2}[\beta ]=t_{4}[\beta ]\\t_{1}[R-\beta ]=t_{4}[R-\beta ]\\t_{2}[R-\beta ]=t_{3}[R-\beta ]\end{matrix}}}$

De manera informal, si se denota por la tupla cuyos valores son colectivamente iguales a , entonces siempre que las tuplas y existan en , las tuplas y también deberían existir en .${\displaystyle (x,y,z)}$${\displaystyle \alpha ,}$${\displaystyle \beta ,}$${\displaystyle R-\alpha -\beta }$${\displaystyle x,}$${\displaystyle y,}$${\displaystyle z}$${\displaystyle (a,b,c)}$${\displaystyle (a,d,e)}$${\displaystyle r}$${\displaystyle (a,b,e)}$${\displaystyle (a,d,c)}$${\displaystyle r}$

La dependencia multivaluada se puede representar esquemáticamente como se muestra a continuación:

${\displaystyle {\begin{matrix}{\text{tupla}}&\alpha &\beta &R-\alpha -\beta \\t_{1}&a_{1}..a_{n}&b_{1}..b_{m}&d_{1}..d_{k}\\t_{2}&a_{1}..a_{n}&c_{1}..c_{m}&e_{1}..e_{k}\\t_{3}&a_{1}..a_{n}&b_{1}..b_{m}&e_{1}..e_{k}\\t_{4}&a_{1}..a_{n}&c_{1}..c_{m}&d_{1}..d_{k}\end{matrix}}}$

Consideremos este ejemplo de relación entre los cursos universitarios, los libros recomendados para el curso y los profesores que lo impartirán:

Debido a que los profesores asociados al curso y los libros asociados al curso son independientes entre sí, este diseño de base de datos tiene una dependencia multivaluada; si añadiéramos un nuevo libro al curso AHA, tendríamos que añadir un registro para cada uno de los profesores de ese curso, y viceversa. Dicho formalmente, hay dos dependencias multivaluadas en esta relación: {curso} {libro} y, equivalentemente, {curso} {profesor}. Las bases de datos con dependencias multivaluadas presentan, por lo tanto, redundancia. En la normalización de bases de datos , la cuarta forma normal requiere que para cada dependencia multivaluada no trivial X Y , X sea una superclave . Una dependencia multivaluada X Y es trivial si Y es un subconjunto de X , o si es el conjunto completo de atributos de la relación. ${\displaystyle \twoheadrightarrow }$  ${\displaystyle \twoheadrightarrow }$  ${\displaystyle \twoheadrightarrow }$ ${\displaystyle \twoheadrightarrow }$${\displaystyle X\cup Y}$

• Si , entonces${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \alpha \twoheadrightarrow R-\beta }$
• Si y , entonces${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \gamma \subseteq \delta }$${\displaystyle \alpha \delta \twoheadrightarrow \beta \gamma}$
• Si y , entonces${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \beta \twoheadrightarrow \gamma }$${\displaystyle \alpha \twoheadrightarrow \gamma -\beta }$

Las siguientes también implican dependencias funcionales :

• Si , entonces${\displaystyle \alpha \rightarrow \beta }$${\displaystyle \alpha \twoheadrightarrow \beta }$
• Si y , entonces${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \beta \rightarrow \gamma }$${\displaystyle \alpha \twoheadrightarrow \gamma -\beta }$

Las reglas anteriores son sólidas y completas.

• Una descomposición de R en ( X , Y ) y ( X , R − Y ) es una descomposición de unión sin pérdida si y solo si X Y se cumple en R .     ${\displaystyle \twoheadrightarrow }$  
• Cada FD ( dependencia funcional ) es una MVD (dependencia multivaluada) porque si X Y, entonces intercambiar Y entre tuplas que coinciden en X no crea nuevas tuplas.${\displaystyle \rightarrow }$
• La división no es posible. Al igual que con los descriptores de archivo (FD), generalmente no podemos dividir el lado izquierdo de un MVD. Pero a diferencia de los FD, tampoco podemos dividir el lado derecho; a veces es necesario dejar varios atributos en el lado derecho.
• El cierre de un conjunto de MVD es el conjunto de todos los MVD que se pueden inferir utilizando las siguientes reglas ( axiomas de Armstrong ):
  • Complementación : Si X Y, entonces X R - Y${\displaystyle \twoheadrightarrow }$${\displaystyle \twoheadrightarrow }$
  • Aumento : Si X Y y Z W, entonces XW YZ${\displaystyle \twoheadrightarrow }$${\displaystyle \subseteq }$${\displaystyle \twoheadrightarrow }$
  • Transitividad : Si X Y y Y Z, entonces X Z - Y${\displaystyle \twoheadrightarrow }$${\displaystyle \twoheadrightarrow }$${\displaystyle \twoheadrightarrow }$
  • Replicación : Si X Y, entonces X Y${\displaystyle \rightarrow }$${\displaystyle \twoheadrightarrow }$
  • Coalescencia : Si X Y y W st W Y = , W Z, y Z Y, entonces X Z${\displaystyle \twoheadrightarrow }$${\displaystyle \exists }$${\displaystyle \cap }$${\displaystyle \emptyset }$${\displaystyle \rightarrow }$${\displaystyle \subseteq }$${\displaystyle \rightarrow }$

Restricción total

Una restricción que expresa algo sobre todos los atributos en una base de datos. (En contraste con una restricción incrustada ). Que una dependencia multivaluada sea una restricción completa se deduce de su definición, ya que dice algo sobre los atributos .${\displaystyle R-\beta }$

Dependencia generadora de tuplas

Una dependencia que requiere explícitamente que ciertas tuplas estén presentes en la relación.

Dependencia multivaluada trivial 1

Una dependencia multivaluada que involucra todos los atributos de una relación, es decir , . Una dependencia multivaluada trivial implica, para las tuplas y , tuplas y que son iguales a y .${\displaystyle R=\alpha \cup \beta }$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle t_{3}}$${\displaystyle t_{4}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$

Dependencia multivaluada trivial 2

Una dependencia multivaluada para la cual .${\displaystyle \beta \subseteq \alpha }$

• Dependencias multivaluadas y una nueva forma normal para bases de datos relacionales (PDF) - Ronald Fagin, Laboratorio de Investigación de IBM
• Sobre la estructura de las relaciones de Armstrong para dependencias funcionales (PDF) - CATRIEL BEERI (Universidad Hebrea), MARTIN DOWD (Universidad de Rutgers), RONALD FAGIN (Laboratorio de Investigación de IBM) Y RICHARD STATMAN (Universidad de Rutgers)
• Sobre un problema de Fagin relativo a las dependencias multivaluadas en bases de datos relacionales (PDF) - Sven Hartmann, Universidad de Massey