Hay dos algoritmos para calcular la unión natural y la unión condicional de dos relaciones en la base de datos: unión de bucle anidado y unión de bucle anidado en bloque.
Para entender estos algoritmos supondremos que hay dos relaciones, la relación R y la relación S. La relación R tiene tuplas T R y ocupa bloques B R. La relación S tiene T S tuplas y ocupa B S bloques. También supondremos que la relación R es la relación externa y S es la relación interna.
Unión de bucle anidado
En el algoritmo de unión de bucle anidado, para cada tupla en la relación externa, tenemos que compararla con todas las tuplas en la relación interna y luego solo se considera la siguiente tupla de la relación externa. Todos los pares de tuplas que satisfacen la condición se agregan al resultado de la unión.
for each tuple tR in TR do for each tuple ts in Ts do compare (tR, ts) if they satisfies the condition add them in the result of the join end end
Este algoritmo se denomina unión anidada porque consiste en bucles for anidados.
Veamos algunos casos para entender el desempeño de este algoritmo,
Caso-1: suponga que solo hay dos bloques de memoria principal disponibles para almacenar bloques de la relación R y S.
Para cada tupla en relación con R, tenemos que transferir todos los bloques de la relación S y cada bloque de la relación R debe transferirse solo una vez.
Entonces, el total de transferencias en bloque necesarias = T R * B S + B R
Caso-2: suponga que una relación cabe completamente en la memoria principal y hay al menos espacio para un bloque adicional.
En este caso, los bloques de la relación S (es decir, la relación interna) solo se transfieren una vez y se mantienen en la memoria principal y los bloques de la relación R se transfieren secuencialmente. Entonces, todos los bloques de ambas relaciones se transfieren solo una vez.
Entonces, el total de transferencias en bloque necesarias = B R + B S
La relación con un menor número de bloques debe ser la relación externa para minimizar el número total de bloques de acceso necesarios en la memoria principal para completar la unión.
Es decir, min(B R , B S )+1 es el número mínimo de bloques en la memoria principal necesarios para unir dos relaciones de modo que ningún bloque se transfiera más de una vez.
En la unión de bucle anidado, se requiere un mayor costo de acceso para unir las relaciones si el espacio de memoria principal asignado para la unión es muy limitado.
Unión de bucle anidado en bloque:
En la combinación de bucles anidados en bloque, para un bloque de relación externa, todas las tuplas de ese bloque se comparan con todas las tuplas de la relación interna, luego solo se considera el siguiente bloque de relación externa. Todos los pares de tuplas que satisfacen la condición se agregan al resultado de la unión.
for each block bR in BR do
for each block bs in BS do
for each tuple tR in TR do
for each tuple ts in Ts do
compare (tR, ts) if they satisfies the condition
add them in the result of the join
end
end
end
end
Veamos algunos casos similares como unión de bucle anidado,
Caso-1: suponga que solo hay dos bloques de memoria principal disponibles para almacenar bloques de la relación R y S.
Para cada bloque de la relación R, tenemos que transferir todos los bloques de la relación S y cada bloque de la relación R debe transferirse solo una vez.
Entonces, el total de transferencias en bloque necesarias = B R + B R * B S
Caso-2: suponga que una relación cabe completamente en la memoria principal y hay al menos espacio para un bloque adicional.
En este caso, las transferencias de bloques totales necesarias son similares a la unión de bucle anidado.
El algoritmo de unión de bucles anidados en bloques reduce el costo de acceso en comparación con la unión de bucles anidados si el espacio de memoria principal asignado para la unión es limitado.
Preguntas GATE relacionadas:
Publicación traducida automáticamente
Artículo escrito por SreejitBose y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA