Asociatividad de la unión natural

Question

Una "relación" es un objeto con un cuerpo que es un conjunto de tuplas, y una cabecera que es un conjunto de identificadores de atributos. Este tipo de objeto se utiliza en la teoría de las "bases de datos relacionales". Una relación es como una tabla en una hoja de cálculo, pero la colección de columnas ("atributos") es un conjunto, y la colección de filas ("tuplas") es un conjunto.

Que la relación $A$ tienen atributos $X_1, X_2, \dots, X_m, Y_1, Y_2, \dots, Y_n$ y $B$ tienen atributos $Y_1, Y_2, \dots, Y_n, Z_1, Z_2, \dots, Z_p$ . Así, $A$ y $B$ pueden unirse en un conjunto compartido de atributos, $Y_i$ .

Ahora considere $X, Y, Z$ como tres atributos compuestos (pensando en cada grupo de atributos como un único atributo). Entonces la unión natural de $A$ y $B$ , A JOIN B es una relación con encabezamiento $X,Y,Z$ y un cuerpo formado por todas las tuplas ( $x$ , $y$ , $z$ ) tal que una tupla aparezca en $A$ con $X$ valor $x$ (es decir, los atributos no compartidos con B) y $Y$ valor $y$ (es decir, los atributos de la clave compartida), y aparece una tupla en $B$ con $Y$ valor $y$ y $Z$ valor $z$ . [Citando algunos de los IDBS de C.J. Date.]

¿Podemos demostrar que la unión natural es asociativa? Es decir, una tupla $t$ está en A JOIN (B JOIN C) si $t$ está en (A JOIN B) JOIN C ?

Answer 1

Intentaré seguir con su terminología. Sin embargo, yo uso $\in$ para decir que una tupla está en el cuerpo de una relación, y escribiré $\circ$ para la unión (véase más abajo). Por lo tanto, supongamos que $C$ es una relación con atributos $Z_1,\dots,Z_p,U_1,\dots,U_l$ . Escribamos $X,Y,Z,U$ para los atributos compuestos. Queremos demostrar que $A\circ(B\circ C)=(A\circ B)\circ C$ .

Supongamos que $(x,y,z,u)\in A\circ(B\circ C)$ . Esto significa que $(x,y)\in A$ y $(y,z,u)\in B\circ C$ y por lo tanto $(x,y)\in A$ y $(y,z)\in B$ y $(z,u)\in C$ . Así que tenemos $(x,y,z)\in A\circ B$ y por lo tanto $(x,y,z,u)\in (A\circ B)\circ C$ . La otra dirección es análoga.

Aquí hay que hacer dos comentarios:

• Nótese que realmente tenemos, si $(x,y,z)\in A\circ B$ y $(z,u)\in C$ que $((x,y),z,u)\in (A\circ B)\circ C$ , y de forma similar $(x,y,(z,u))\in A\circ (B\circ C)$ . Dependiendo de cómo se definan las tuplas, podrían no ser lo mismo. No sé si estas sutilezas son importantes para ti.
• Normalmente, si $A,B$ son relaciones binarias, se define $A\circ B=\{(x,y)\mid \exists z((x,z)\in B\wedge (z,y)\in A)\}$ (esto puede parecer confuso, pero piensa en la definición de las funciones), pero pensé que esto es lo suficientemente cerca de la unión para justificar el abuso de la notación. Si quieres comprobar tu comprensión, puede ser un buen ejercicio demostrar que esto también es asociativo.