JOIN. Estimación del tamaño.
Sean r® y s(S) dos relaciones:
Si R S= entonces r s es lo mismo que r x s, y por lo tanto se puede utilizar la estimación del producto cartesiano.
Si R S es una clave de R entonces el número de tuplas en r s no es mayor que el número de tuplas en S. Si R S es una clave externa de R entonces el número de tuplas de r s es exactamente el número de tuplas de S.
Si R S no es clave de R ni de S entonces se supone que cada valor aparece con la misma probabilidad , por lo tanto, sea t una tupla de r y sea R S=Ā, entonces se estima que la tupla t produce :
tuplas en s, por lo tanto se estima el tamaño de r s = (a) al cambiar los papeles de r y s se tiene (b)
Estos valores serán distintos si y sólo si V(A,r) V(A,s), si este es el caso, la más baja estimación de ambas será la más conveniente.
Join en bucles anidados.
Si z = r s, r recibirá el nombre de relación externa y s se llamará relación interna, el algoritmo de bucles anidados se puede presentar como sigue. para cada tupla tr en rpara cada tupla ts en ssi (tr,ts) satisface la condición entonces añadir tr ts al resultado Algoritmo 5–1 - Join en bucles anidados.
Donde tr ts será la concatenación de las tuplas tr y ts .
Como para cada registro de r se tiene que realizar una exploración completa de s, y suponiendo el peor caso, en el cual la memoria intermedia sólo puede concatenar un bloque de cada relación, entonces el número de bloques a acceder es de . Por otro lado, en el mejor de los casos si se pueden contener ambas relaciones en la memoria intermedia entonces sólo se necesitarían accesos a bloques.
Ahora bien, si la más pequeña de ambas relaciones cabe completamente en la memoria, es conveniente utilizar esta relación como la relación interna, utilizando así sólo accesos a bloques. Join en bucles anidados por bloques.
Una variante del algoritmo anterior puede lograr un ahorro en el acceso a bloques si se procesan las relaciones por bloques en vez de por tuplas. para cada bloque Br de rpara cada bloque Bs de spara cada tupla tr en Brpara cada tupla ts en Bssi (tr,ts) satisface la condición entonces añadir tr ts al resultado Algoritmo 5–2 - Join en bucles anidados por bloques.
La diferencia principal en costos de este algoritmo con el anterior es que en el peor de los casos cada bloque de la relación interna s se lee una vez por cada bloque de r y no por cada tupla de la relación externa, de este modo el número de bloques a acceder es de donde además resulta más conveniente utilizar la relación más pequeña como la relación externa. Join en bucles anidados por índices.
Este algoritmo simplemente sustituye las búsquedas en tablas por búsquedas en índices, esto puede ocurrir siempre y cuando exista un índice en el atributo de join de la relación interna. Este método se utiliza cuando existen índices así como cuando se crean índices temporales con el único propósito de evaluar la reunión.
El costo de este algoritmo se puede calcular como sigue: para cada tupla de la relación externa r se realiza una búsqueda en el índice de s para recuperar las tuplas apropiadas, sea c = costo de la búsqueda en el índice, el cual se puede calcular con cualquiera de los algoritmos A3, A4 o A5. Entonces el costo del join es ; si hay índices disponibles para el atributo de join en ambas relaciones, es conveniente utilizar la relación con menos tuplas. Join por mezcla.
El algoritmo de Join por mezcla se pude utilizar para calcular un Join natural o un equi-join. Para tales efectos ambas relaciones deben estar ordenadas por los atributos en común.
Este algoritmo asocia un puntero a cada relación, al principio estos punteros apuntan al inicio de cada una de la relaciones. Según avanza el algoritmo, el puntero se mueve a través de la relación. De este modo se leen en memoria un grupo de tuplas de una relación con el mismo valor en los atributos de la reunión. Pr = dirección de la primera tupla de r;ps = dirección de la primera tupla de s;mientras (ps <> nulo y pr <> nulo)iniciots = tupla a la que apunta ps;S = {ts};ps = puntero a la siguiente tupla de s;hecho = falso;mientras (not hecho y ps <> nulo)iniciots’ = tupla a la que apunta ps;si (ts’[Atribs Reunión?] = ts[Atribs Reunión]) S = S union {ts’};ps = puntero a la siguiente tupla de s;sino hecho = verdadero;fin mientras;tr = tupla a la que apunta pr;mientras (pr <> nulo y tr[Atribs Reunión] < ts[Atribs Reunión])iniciopr = puntero a la siguiente tupla de r;tr = tupla a la que apunta pr;fin mientras;mientras (pr <> nulo y tr[Atribs Reunión] = ts[Atribs Reunión])iniciopara cada ts en Sañadir ts x tr al resultadopr = puntero a la siguiente tupla de r;tr = tupla a la que apunta pr;fin mientrasfin mientras
Dado que las relaciones están ordenadas, las tuplas con el mismo valor en los atributos de la reunión aparecerán consecutivamente. De este modo solamente es necesario leer cada tupla en el orden una sola vez. Puesto que sólo se hace un ciclo en ambas tablas, este método resulta eficiente; el número de accesos a bloques de disco es igual a la suma de los bloques de las dos tablas . Si una de las relaciones no está ordenada según los atributos comunes del join, se puede ordenar primero para luego utilizar el algoritmo de join por mezcla. En este caso hay que considerar también el costo de ordenar la o las relaciones y sumarlo al costo de este algoritmo. Como se menciono anteriormente este algoritmo necesita que el conjunto S de tuplas quepa completamente en la memoria principal, este requisito se puede alcanzar normalmente, incluso si la relación s es grande. De no poder cumplirse este requisito se deberá efectuar un join en bucle anidado por bloques entre {S} y r con los mismos valores en los atributos del join, con lo que el costo del join aumenta.
Una variación de este algoritmo se puede realizar aún en tuplas desordenadas si existen índices secundarios en los atributos de join de cada una de las relaciones, sin embargo, dada la naturaleza de este tipo de caminos de acceso existe una alta probabilidad de que se necesite un acceso a bloque de disco por cada tupla, lo que lo hace sustancialmente más costoso. Para evitar este costo se puede utilizar un algoritmo de join por mezcla híbrido, que combina índices con un join por mezcla. Si sólo una de las relaciones está desordenada pero existe un índice secundario en el atributo de join, el algoritmo de join por mezcla híbrido combina la relación ordenada con las entradas hojas del índice secundario. El resultado de esta operación se debe ordenar según las direcciones del índice secundario permitiendo así una recuperación eficiente de las tuplas, según el orden físico de almacenamiento. Join por asociación.
Al igual que el algoritmo de join por mezcla, el algoritmo de join por asociación se puede utilizar para un Join natural o un equi-join. Este algoritmo utiliza una función de asociación h para dividir las tuplas de ambas relaciones. La idea fundamental es dividir las tuplas de cada relación en conjuntos con el mismo valor de la función de asociación en los atributos de join.
Se supone que: h es una función de asociación que asigna a los atributos de join los valores {0,1,…max}
• denotan las particiones de las tuplas de r, inicialmente todas vacías. Cada tupla se pone en la partición donde
• denotan las particiones de las tuplas de s, inicialmente todas vacías. Cada tupla se pone en la partición donde
La idea detrás del algoritmo es la siguiente, supóngase que una tupla de r y una tupla de s satisfacen la condición de join y por lo tanto tienen los mismos valores en los atributos de join. Si estos valores se asocian con algún valor i, entonces la tupla de r tiene que estar en y la tupla de s tiene que estar en , de este modo sólo será necesario comparar las tuplas de r en con las tuplas de s en y no con las tuplas de s de otra partición.
El algoritmo es el siguiente. para cada tupla en s ; ;fin para;para cada tupla en r ; ;fin para;para i = 1 hasta maxleer y construir un índice asociativo en memoria sobre él;para cada tupla en explorar el índice asociativo en para localizar todas las tuplastales que = ;para cada tupla que concuerde en añadir x al resultado;fin para;fin para;fin para; Algoritmo 5–4 - Join por asociación.
El índice asociativo en se construye en memoria por lo que no se hace necesario acceder al disco para recuperar las tuplas, la función de asociación utilizada para construir este índice es distinta a la función h utilizada para construir las particiones. Después de la división de las relaciones el resto del código realiza un join en bucle anidado por índices en cada una de las particiones. Para lograr esto primero se construye un índice asociativo en cada y luego se prueba (se busca en ) con las tuplas de .
Se tiene que elegir el valor de max lo suficientemente grande como para que, para cada i, las tuplas de la partición junto con el índice asociativo de la relación quepan completamente en la memoria. Claramente será más conveniente utilizar la relación más pequeña como la relación s. Si el tamaño de la relación s es bloques, entonces para que cada una de las max particiones tengan un tamaño menor o igual a M, max debe ser al menos más el espacio adicional ocupado por el índice asociativo. Una consideración a seguir para que las divisiones de las relaciones se efectúe en un solo paso es que M>max+1 o equivalentemente si M>( /M)+1 que de manera aproximada se simplifica a . Por ejemplo, si una relación contiene 440 bloques de 2KB cada uno, entonces , osea M > 20. De tal manera sólo se necesitarán 40 Kb. de espacio de memoria (más el espacio requerido por el índice asociativo) para el particionamiento de la relación.
El cálculo del costo de un join por asociación tiene la siguiente lógica: el particionamiento de ambas relaciones reclama una lectura completa de cada relación, como también su posterior escritura, esta operación necesita accesos a bloques. Las fases de construcción y prueba (como se le denomina al join en bucle anidado por índices) lee cada una de las particiones una vez empleando accesos adicionales. El número de bloques ocupados por las particiones podría ser ligeramente mayor que . Debido a que los bloques no están completamente llenos,. El acceso a estos bloques puede añadir un gasto adicional de 2·max a lo sumo, ya que cada una de las particiones podría tener un bloque parcialmente ocupado que se tiene que leer y escribir de nuevo. Así el costo estimado para un join por asociación es :
Join por asociación híbrida.
El algoritmo de join por asociación híbrida realiza otra optimización; es útil cuando el tamaño de la memoria es relativamente grande paro aún así, no cabe toda la relación s en memoria. Dado que el algoritmo de join por asociación necesita max +1 bloques de memoria para dividir ambas relaciones se puede utilizar el resto de la memoria (M – max – 1 bloques) para guardar en la memoria intermedia la primera partición de la relación s, esto es , así no es necesaria leerla ni escribirla nuevamente y se puede construir un índice asociativo en .
Cuando r se divide, las tuplas de tampoco se escriben en disco; en su lugar, según se van generando, el sistema las utiliza para examinar el índice asociativo en y así generar las tuplas de salida del join. Después de utilizarlas, estas tuplas se descartan, así que la partición no ocupa espacio en memoria. De este modo se ahorra un acceso de lectura y uno de escritura para cada bloque de y . Las tuplas de otras particiones se escriben de la manera usual para reunirlas más tarde.
Join Complejos.
Los join en bucle anidado y en bucle anidado por bloques son útiles siempre, sin embargo, las otras técnicas de join son más eficientes que estas, pero sólo se pueden utilizar en condiciones particulares tales como join natural o equi-join. Se pueden implementar join con condiciones más complejas tales como conjunción o disyunción Dado un join de las forma se pueden aplicar una o más de las técnicas de join descritas anteriormente en cada condición individual , el resultado total consiste en las tuplas del resultado intermedio que satisfacen el resto de las condiciones. Estas condiciones se pueden ir comprobado según se generen las tuplas de . La implementación de la disyunción es homóloga a la conjunción.
Outer Join (Join externos)
Un outer join es una extensión del operador join que se utiliza a menudo para trabajar con la información que falta. Por ejemplo, suponiendo que se desea generar una lista con todos los choferes y los autos que manejan (si manejan alguno) entonces se debe cruzar la relación Chofer con la relación Movil. Si se efectúa un join corriente se perderán todas aquellas tuplas que pertenecen a los choferes, en cambio con un outer join se pueden desplegar las tuplas resultado incluyendo a aquellos choferes que no tengan a cargo un auto. El outer join tiene tres formas distintas: por la izquierda, por la derecha y completo. El join por la izquierda ( )toma todas las tuplas de la relación de la izquierda que no coincidan con ninguna tupla de la relación de la derecha , las rellena con valores nulos en los demás atributos de la relación de la derecha y las añade al resultado del join natural. Un outer join por la derecha ( ) es análogo al procedimiento anterior y el outer join completo es aquel que efectúa ambas operaciones.
Se puede implementar un outer join empleando una de las dos estrategias siguientes. La primera efectúa un join natural y luego añade más tuplas al resultado hasta obtener el join externo. Sea r® y s(S) , para evaluar se calcula primero r s y se guarda este resultado en la relación temporal q1, a continuación se calcula que produce las tuplas de r que no participan del join, estas tuplas se rellenan con valores nulos en los atributos de s y se añaden a q1 para obtener el resultado deseado. El procedimiento es homólogo para los outer join por la derecha o completo.
La segunda estrategia significa modificar el algoritmo de join. Se pude extender el algoritmo de join en bucles anidados para calcular el outer join por la izquierda. Las tuplas de la relación externa que no concuerden con ninguna tupla de la relación interna se completan con valores nulos y se escriben en la salida.
Para el caso de un outer join completo se puede calcular mediante extensiones de los algoritmos de join por mezcla y join por asociación. En el caso del algoritmo de join por mezcla, cuando se está produciendo la mezcla de ambas relaciones, las tuplas de la relación que no encajan con ninguna tupla de la otra relación se rellenan con valores nulos y se escriben en la salida. Puesto que las relaciones están ordenadas, es fácil detectar si una tupla coincide o no con alguna tupla de la otra relación. El costo estimado para realizar un outer join utilizando el algoritmo de join por mezcla es el mismo que si fuera un join normal, la única diferencia es el tamaño del resultado, por lo tanto el número de bloques a escribir en el resultado puede aumentar. Agregación.
La agregación es otra de las características del álgebra de relaciones extendida. La idea de este tipo de funciones es que tomen un conjunto de valores y que retornen un solo valor. se utilizan comúnmente para información agregada (de ahí su nombre), analizan una agrupación de registros y rescatan el valor solicitado, se aplican sobre un atributo o sobre una composición de atributos, el valor retornado puede ser min, max, count, sum, avg, que corresponden respectivamente a el mínimo valor del subconjunto; el máximo valor; una cuenta de valores; la suma sobre algún atributo o composición de atributos y el promedio.
Para la implementación de la operación de agregación se puede utilizar un algoritmo de ordenación o uno de asociación, para el caso de la asociación, lo que se hace es agrupar las tuplas que tengan el mismo valor en los atributos de la agregación y luego se aplica la función de agregación en cada uno de los grupos para obtener el resultado.
El tamaño de la agregación sobre A es simplemente V(A,r). El costo estimado de la implementación de la agregación es el mismo de una ordenación (cualquiera sea el algoritmo).
En lugar de reunir todas las tuplas en grupos y aplicar entonces las funciones de agregación, se pueden implementar sobre la marcha según se construyen los grupos. Si las V(A,r) tuplas del resultado caben en memoria, las implementaciones basadas en ordenación y las basadas en asociación no requieren escribir bloques adicionales a disco, según se leen las tuplas se pueden ir insertando en una estructura ordenada de árbol o en un índice asociativo, de esta manera sólo se necesitan transferencias de bloques.
