La combinación de clasificación y combinación (también conocida como combinación de combinación) es un algoritmo de combinación y se utiliza en la implementación de un sistema de administración de bases de datos relacionales .
El problema básico de un algoritmo de combinación es encontrar, para cada valor distinto del atributo de combinación, el conjunto de tuplas en cada relación que muestra ese valor. La idea clave del algoritmo sort-merge es ordenar primero las relaciones por el atributo de unión, de modo que los escaneos lineales intercalados encuentren estos conjuntos al mismo tiempo.
En la práctica, la parte más cara de realizar una combinación de clasificación y fusión es disponer que ambas entradas del algoritmo se presenten en orden clasificado. Esto se puede lograr mediante una operación de ordenación explícita (a menudo una ordenación externa ) o aprovechando un ordenamiento preexistente en una o ambas relaciones de unión. La última condición, llamada orden interesante, puede ocurrir porque una entrada a la combinación puede ser producida por un escaneo de índice de un índice basado en árbol, otra combinación de combinación o algún otro operador de plan que produce una salida ordenada en una clave apropiada. Las órdenes interesantes no tienen por qué ser fortuitas: el optimizador puede buscar esta posibilidad y elegir un plan que no sea óptimo para una operación anterior específica si produce una orden interesante que uno o más nodos posteriores pueden explotar.
Digamos que tenemos dos relaciones y y . encaja páginas de memoria y encaja páginas de memoria. Por lo tanto, en el peor de los casos , la combinación de combinación y clasificación se ejecutará enE / S. En el caso de que y no se ordenan, el costo de tiempo en el peor de los casos contendrá términos adicionales de tiempo de clasificación: , que es igual a (como linearithmic términos son mayores que los términos lineales, véase Big O notación - Órdenes de funciones comunes ).
Pseudocódigo
Para simplificar, el algoritmo se describe en el caso de una unión interna de dos relaciones en un solo atributo. La generalización a otros tipos de combinación, más relaciones y más claves es sencilla.
function sortMerge ( relación izquierda, relación derecha, atributo a) var salida de relación lista var left_sorted: = sort (left, a) // Relación izquierda ordenada en atributo a var list right_sorted: = sort (derecha, a) var atributo left_key, right_key var set left_subset, right_subset // Estos conjuntos se descartan excepto cuando se cumple el predicado de unión avance (subconjunto_izquierda, ordenado_izquierda, tecla_izquierda, a) avance (subconjunto_derecha, ordenado_derecha, tecla_derecha, a) while no vacío (left_subset) y no vacío (right_subset) if left_key = right_key // predicado de unión satisfecho agregue el producto cartesiano de left_subset y right_subset a la salida avance (subconjunto_izquierda, ordenado_izquierda, tecla_izquierda, a) avance (subconjunto_derecha, ordenado_derecha, tecla_derecha, a) de lo contrario, si tecla_izquierdaavance (subconjunto_izquierda, ordenado_izquierda, tecla_izquierda, a) else // tecla_izquierda> tecla_derecha avance (subconjunto_derecha, ordenado_derecha, tecla_derecha, a) salida de retorno
// eliminar tuplas de ordenadas en el subconjunto hasta ordenados [1] .a valor cambia la función de avance (subconjunto cabo , ordenados inout , clave a cabo , una en ) clave: = ordenado [1] .a subconjunto: = vacío Establecer mientras no está vacío (ordenado) y ordenado [1] .a = clave insertar ordenado [1] en un subconjunto eliminar ordenado [1]
Implementación simple de C #
Tenga en cuenta que esta implementación asume que los atributos de unión son únicos, es decir, no hay necesidad de generar múltiples tuplas para un valor dado de la clave.
public class MergeJoin { // Suponga que la izquierda y la derecha ya están ordenadas public static Relation Merge ( Relación izquierda , Relación derecha ) { Relación salida = nueva Relación (); while (! left . IsPastEnd () && ! right . IsPastEnd ()) { if ( izquierda . Tecla == derecha . Tecla ) { salida . Añadir ( izquierda . Tecla ); a la izquierda . Avance (); bien . Avance (); } else if ( izquierda . Tecla < derecha . Tecla ) izquierda . Avance (); else // if (left.Key> right.Key) derecha . Avance (); } retorno de salida ; } } public class Relation { lista privada < int > lista ; public const int ENDPOS = - 1 ; posición pública int = 0 ; public int Position { get { posición de retorno ; } } public int Key { obtener { lista de retorno [ posición ]; } } public bool Advance () { if ( position == list . Count - 1 || position == ENDPOS ) { position = ENDPOS ; devolver falso ; } posición ++; devuelve verdadero ; } public void Agregar ( clave int ) { lista . Agregar ( clave ); } public bool IsPastEnd () { posición de retorno == ENDPOS ; } public void Print () { foreach ( clave int en la lista ) Consola . WriteLine ( clave ); } Relación pública ( List < int > list ) { this . lista = lista ; } Relación pública () { esto . lista = nueva Lista < int > (); } }