Please enable JavaScript.
Coggle requires JavaScript to display documents.
PROCESAMIENTO DE CONSULTAS (OPERACIÓN REUNIÓN: (Reunión por asociación:…
PROCESAMIENTO DE CONSULTAS
VISIÓN GENERAL
Pasos generales:
Análisis y traducción
Optimización
Evaluación
El sistema traduce la consulta a una forma utilizable para la maquina (traducción
de la consulta dada a su formato interno)
Una consulta se puede traducir en una expresión de álgebra relacional, también se le pueden aplicar operaciones de la álgebra.
primitivas de evaluación: operaciones del álgebra relacional
anotadas con instrucciones sobre la evaluación.
plan de ejecución de la consulta o plan de evaluación de la consulta
El motor de ejecución de consultas toma un plan de evaluación, lo ejecuta y devuelve su respuesta a la consulta
Para optimizar una consulta, el optimizador de consultas
debe conocer el coste de cada operación.
MEDIDAS DEL COSTE DE UNA CONSULTA
se puede expresar en términos de diferentes recursos: accesos a disco (los mas importantes), tiempo de ejecucion en CPU, sistemas de bases de datos distribuidos o paralelos, de comunicacion
número de transferencias de bloques de disco=medida del coste real.
Los numeros de costes precisos los provee: E/S secuencial y E/S aleatoria
Los mas precisos los proporciona: El número de operaciones de búsqueda realizadas.
El número de bloques leídos.
El número de bloques escritos.
OPERACIÓN SELECCIÓN
Algoritmos básicos
búsqueda lineal: explora cada bloque del archivo y se comprueban todos los registros para ver si satisfacen la condición de selección, se termina la consulta si se encuentra el registro requerido.
búsqueda binaria: Si el archivo está ordenado según un atributo y la condición de la selección es una comparación de igualdad en ese atributo, se puede utilizar una búsqueda binaria para localizar los registros que satisfacen la selección. El sistema realiza la búsqueda binaria de los bloques del archivo.
Selecciones con índices
índice primario, igualdad basada en la clave: Para una condición de igualdad en un atributo clave con un índice primario se puede utilizar el índice para recuperar el único registro que satisface la correspondiente condición de igualdad.
índice primario, igualdad basada en un atributo no clave: Se recuperan varios registros mediante el uso de un índice primario cuando la condición de selección especifica una comparación de igualdad en un atributo A que no sea clave.
índice secundario, igualdad: Las selecciones con una condición de igualdad pueden utilizar un índice secundario. Esta estrategia puede recuperar un único registro si la condición de igualdad es sobre una clave; puede que se recuperen varios registros si el campo índice no es clave.
Selecciones con condiciones
de comparación
índice primario, comparación: Se puede utilizar un índice ordenado primario ( árbol B+ ) cuando la condición de selección es una comparación. índice primario se usa para la recuperación de las tuplas.
índice secundario, comparación: Se puede utilizar un índice secundario ordenado para guiar la recuperación de tuplas bajo condiciones de comparación.
Implementación de selecciones
complejas
se usan predicados de disyunción, conjunción y negación.
selección conjuntiva utilizando un índice:determinar si para un atributo hay disponible algún camino de acceso en alguna de las condiciones simples y se utiliza los anteriores algoritmos exceptoel de busqueda lineal. para menores costos se puede seleccionar los algoritmos anteriores menos el de indice secundario, comparacion.
selección conjuntiva utilizando un índice compuesto: Se dispone de un índice compuesto ( índice sobre varios atributos), apropiado para selecciones conjuntivas. Si la selección especifica una condición de igualdad en dos o más atributos y existe un índice compuesto en estos campos con atributos combinados, entonces se podría buscar en el índice directamente.
selección conjuntiva mediante la intersección
de identificadores: la operación de selección conjuntiva implica la utilización de punteros a registros o identificadores de registros, busca de punteros cuyas tuplas cumplan alguna condición indvidual, luego se usa el conjunto de punteros para regresar los regitros reales
selección disyuntiva mediante la unión de identificadores: Si se disponen de caminos de acceso en todas las condiciones de la selección disyuntiva, se explora cada índice en busca de punteros cuyas tuplas cumplan una condición individual.
ORDENACIÓN
solicitar que los resultados sean ordenados.
implementa eficientemente si las relaciones de entrada están ordenadas
La ordenación de relaciones que no caben en memoria
se llama ordenación externa
La técnica más utilizada para la ordenación externa es normalmente el algoritmo de ordenación-mezcla externa.
El resultado de la etapa de mezcla es la relación
ya ordenada
OPERACIÓN REUNIÓN:
Reunión en bucle anidado: consiste en un par de bucles for anidados. Tiene una relación externa y una interna, no necesita índices y se puede utilizar sin importar la condición de la reunión.
Reunión en bucle anidado por bloques: Si la memoria intermedia es demasiado pequeña para contener las dos relaciones por completo en memoria, se lograr un mayor ahorro en los accesos a los bloques si se procesan las relaciones por bloques en lugar de por tuplas
Reunión en bucle anidado indexada: si se
dispone de un índice sobre el atributo de la reunión del bucle interno, se pueden sustituir las exploraciones de
archivo por búsquedas en el índice. Se usa cuando se crean indices temporales que solo evaluan la reunion
Reunión por mezcla: Si las relaciones están ordenadas, es deseable una reunión por mezcla. se debería ordenar una relación antes que calcular una reunión, reuniones naturales y equirreuniones, existe algoritmo híbrido de reunión por mezcla que usa arbol B+.
Reunión por asociación: permite implementar reuniones naturales y equirreuniones, usa una función asociada para dividir tuplas de relaciones
División recursiva: no permite hacer divisiones en un solo ciclo si no en repeticiones de ciclos, se pueden dividir en la misma cantidad de paginas disponibles(division de entrada), la repeticion de la division de entrada se llama división recursiva
Gestión de desbordamientos: El desbordamiento de la tabla de asociación puede ocurrir si hay muchas tuplas en la relación para construir con los mismos valores en los atributos de la reunión, o si la función de asociación no tiene las propiedades de aleatoriedad y uniformidad. El tener mas tuplas que la media, se le dice sesgado. se puede controlar mediante el incremento del numero de particiones. Aparece un nuevo coste de reunion por asociacion. El algoritmo de reunión por asociación híbrida realiza otra optimización; es útil cuando los tamaños de la memoria son relativamente grande
Reuniones complejas: bucle anidado y en bucle anidado por bloques son útiles sean cuales sean las condiciones de la reunión.
OTRAS OPERACIONES
Eliminación de duplicados: elimina las copias de tuplas menos una, reduce el numero de tuplas a procesar, el coste es parecido al de la relación para construir en una reunión por asociación
Proyección: Se puede implementar la proyección fácilmente realizando la proyección de cada tupla, pudiendo originar una relación con registros repetidos y suprimiendo después los registros duplicados.
Operaciones sobre conjuntos: las operaciones unión, intersección y diferencia de conjuntos se aplican y se ordenan, para luego examinar cada relación para producir el resultado.
Reunión externa: Calcular la reunión correspondiente, y luego añadir más tuplas al resultado de la reunión hasta obtener la reunión externa resultado o Modificar los algoritmos de la reunión vuelve fácil extender los algoritmos de reunión en bucle anidado para calcular la reunión externa por la izquierda.
Agregación: se puede implementar de una manera parecida a la eliminación de duplicados. Se utiliza la ordenación o la asociación. Se pueden implementar las funciones de agregación min, max, sum, count y avg sobre la marcha según se construyen los grupos.
EVALUACIÓN DE EXPRESIONES
Materialización
Se comienza por las operaciones de la expresión de nivel más bajo
Se ejecutan estas operaciones utilizando los algoritmos ya estudiados, almacenando sus resultados en relaciones temporales.
Se utilizan estas relaciones temporales para
ejecutar las operaciones del siguiente nivel en el árbol
Al final o se calcula la operación en la raíz del árbol, obteniendo el resultado final de la expresión.
Encauzamiento
reduce del número de archivos temporales que se producen
evaluación encauzada: llevar a cabo la reducción con la combinación de varias operaciones relacionales en un encauzamiento de operaciones.
Implementación del encauzamiento
Se puede implementar el encauzamiento construyendo una única y compleja operación que combine las operaciones que constituyen el encauzamiento.
Los encauzamientos se pueden ejecutar de alguno de los siguientes modos: bajo demanda o desde los productores
El encauzamiento bajo demanda: sistema que reitera peticiones de tuplas desde la operación de la cima del encauzamiento
encauzamiento por los productores: los operadores no esperan a que se produzcan peticiones para producir tuplas. Inserción de datos, extracción de datos, forma perezosa.
Algoritmos de evaluación para
el encauzamiento
uso eficiente del encauzamiento necesita la utilización de algoritmos de evaluación que puedan generar tuplas de salida.