Unión de bucles anidados

Una unión de bucle anidado es un algoritmo ingenuo que une dos relaciones utilizando dos bucles anidados . ^{[ 1 ]} Las operaciones de unión son importantes para la administración de bases de datos .

Dos relaciones${\displaystyle R}$y${\displaystyle S}$se unen de la siguiente manera:

El algoritmo nested_loop_join es para cada tupla r en R hacer para cada tupla s en S hacer si r y s satisfacen la condición de unión entonces generar tupla < r , s >

Este algoritmo implicará n _r *b _s + b _r transferencias de bloques y n _r +b _r búsquedas, donde b _r y b _s son el número de bloques en las relaciones R y S respectivamente, y n _r es el número de tuplas en la relación R.

El algoritmo se ejecuta en${\displaystyle O(|R||S|)}$E/S, donde${\displaystyle |R|}$y${\displaystyle |S|}$es el número de tuplas contenidas en${\displaystyle R}$y${\displaystyle S}$respectivamente y se pueden generalizar fácilmente para unir cualquier número de relaciones...

El algoritmo de unión de bucles anidados en bloques ^{[ 2 ]} es una generalización del algoritmo de bucles anidados simples que aprovecha la memoria adicional para reducir la cantidad de veces que el${\displaystyle S}$Se escanea la relación. Se cargan grandes fragmentos de la relación R en la memoria principal. Para cada fragmento, se escanea S y se evalúa la condición de unión en todos los pares de tuplas que se encuentran en memoria. Esto reduce la cantidad de veces que se escanea S a una vez por fragmento.

Si la relación interna tiene un índice en los atributos utilizados en la unión, entonces la unión de bucle anidado ingenua puede reemplazarse por una unión de índice.

El algoritmo index_join es para cada tupla r en R hacer para cada tupla s en S en la búsqueda de índice hacer generar tupla < r , s >

La complejidad temporal para esta variación mejora de${\displaystyle O(|R||S|){\text{ a }}O(|R|\log |S|)}$

• Hash join
• Unión por ordenación y fusión