Please enable JavaScript.
Coggle requires JavaScript to display documents.
PROCESAMIENTO DE CONSULTAS (13.5. OPERACIÓN REUNIÓN (Reunión por…
PROCESAMIENTO DE CONSULTAS
13.1. VISIÓN GENERAL
Los pasos básicos son:
Análisis y traducción
Optimización
Evaluación
La primera acción que el sistema debe realizar en una consulta es traducirla en su formato interno, que (para sistemas de bases de datos relacionales) está basado normalmente en el álgebra relacional.
En el proceso de generación del formato interno de la consulta, el analizador comprueba la sintaxis, verifica que los nombres de relación que figuran en la consulta son nombres de relaciones de la base de datos, etcétera.
Si la consulta se expresó en términos de una vista, el analizador sustituye todas las referencias al nombre de la vista con su expresión del álgebra relacional para calcularla.
13.2. MEDIDAS DEL COSTE DE UNA CONSULTA
El coste de la evaluación de una consulta se puede expresar en términos de diferentes recursos, incluyendo los accesos a disco, el tiempo de UCP en ejecutar una consulta y, en sistemas de bases de datos distribuidos o paralelos, el coste de la comunicación.
Una medida precisa sería estimar: :
El número de operaciones de búsqueda realizadas.
El número de bloques leídos.
El número de bloques escritos
13.3. OPERACIÓN SELECCIÓN
Algoritmos básicos
• A1 (búsqueda lineal).
En una búsqueda lineal se explora cada bloque del archivo y se comprueban todos los registros para ver si satisfacen la condición de selección. Para una selección sobre un atributo clave, el sistema puede terminar la exploración si se encuentra el registro requerido sin necesidad de examinar los otros registros de la relación.
• A2 (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.
Selecciones con índices
• A3 (í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.
• A4 (índice primario, igualdad basada en un atributo no clave).
Se pueden recuperar 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.
• A5 (í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
• A6 (índice primario, comparación).
Se puede utilizar un índice ordenado primario (por ejemplo, un índice primario de árbol B+) cuando la condición de selección es una comparación.
• A7 (índice secundario, comparación).
Se puede utilizar un índice secundario ordenado para guiar la recuperación bajo condiciones de comparación que contengan <, ≤ , > o ≥.
Implementación de selecciones complejas
• A8 (selección conjuntiva utilizando un índice).
Primero hay que determinar si para un atributo hay disponible algún camino de acceso en alguna de las condiciones simples. Si lo hay, cualquiera de los algoritmos de selección A2 hasta A7 puede recuperar los registros que cumplan esa condición.
• A9 (selección conjuntiva utilizando un índice compuesto).
Se podría disponer de un índice compuesto (es decir, un índice sobre varios atributos) apropiado para algunas 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.
• A10 (selección conjuntiva mediante la intersección de identificadores).
Otra alternativa para implementar la operación selección conjuntiva implica la utilización de punteros a registros o identificadores de registros. Este algoritmo necesita índices con punteros a registros en los campos involucrados por cada condición individual.
• A11 (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.
13.4. ORDENACIÓN
Ordenación externa
Se le llama así a la ordenación de relaciones que no caben en memoria.
La técnica más utilizada para la ordenación externa es normalmente el algoritmo de ordenación-mezcla externa.
En la primera etapa, se crean varias secuencias ordenadas.
En la segunda etapa, las secuencias se mezclan.
El resultado de la etapa de mezcla es la relación ya ordenada. El archivo de salida se almacena en una memoria intermedia para reducir el número de operaciones de escritura en el disco.
13.5. 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, todavía se puede lograr un mayor ahorro en los accesos a los bloques si se procesan las relaciones por bloques en lugar de por tuplas. se empareja cada bloque de la relación interna con cada bloque de la relación externa. En cada par de bloques se empareja cada tupla de un bloque con cada tupla del otro bloque para generar todos los pares de tuplas. Se añaden al resultado todas las parejas de tuplas que satisfacen la condición de la reunión.
Reunión en bucle anidado indexada
En una reunión en bucle anidado, 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. Para cada tupla tr de la relación externa r, se utiliza el índice para buscar tuplas en s que cumplan la condición de reunión con la tupla tr.
• Si hay índices disponibles, se puede utilizar esta.
Reunión por mezcla
Si las relaciones están ordenadas, sería deseable una reunión por mezcla. Además, podría ser útil ordenar una relación antes que calcular una reunión.
Se puede utilizar para calcular reuniones naturales y equirreuniones.
Reunión por asociación
División recursiva
Muchas veces la división de las relaciones no se puede hacer en un solo ciclo por lo que la división se tiene que hacer mediante la repetición de ciclos o recursión
Divide la relación en varias particiones, de tal manera que cada partición de una de las relaciones quepa en memoria. La división se lleva a cabo con una función de asociación en los atributos de la reunión, de tal modo que los pares de particiones correspondientes se puedan reunir independientemente.
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.
Se puede controlar parcialmente el sesgo mediante el incremento del número de particiones de tal manera que el tamaño esperado de cada partición (incluyendo el índice asociativo en la partición) sea algo menor que el tamaño de la memoria.
Coste de una reunión por asociación
Se debe considerar ahora el coste de una reunión por asociación.
4.Reunión por asociación híbrida
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 grandes pero no cabe toda la relación para construir en memoria.
Reuniones complejas
Se pueden implementar reuniones con condiciones de la reunión más complejas, tales como conjunciones y disyunciones.
13.6. OTRAS OPERACIONES
Eliminación de duplicados
Se puede implementar fácilmente la eliminación de duplicados utilizando la ordenación. Las tuplas idénticas aparecerán consecutivas durante la ordenación, pudiéndose eliminar todas las copias menos una.
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
Se pueden implementar las operaciones unión, intersección y diferencia de conjuntos ordenando primero ambas relaciones y examinando después cada relación para producir el resultado.
Reunión externa
Se pueden implementar las operaciones de reunión externa empleando una de las dos estrategias siguientes.
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.
2.Modificar los algoritmos de la reunión. Así, es 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, al igual que se hizo para la supresión de duplicados, pero basándose ahora en la agrupación de atributos.
13.7. EVALUACIÓN DE EXPRESIONES
Materialización
Intuitivamente es fácil de entender cómo evaluar una expresión observando una representación gráfica de la expresión en un árbol de operadores.
Si se aplica el enfoque de la materialización, se comienza por las operaciones de la expresión de nivel más bajo (al fondo del árbol).
Las entradas de las operaciones de nivel más bajo son las relaciones de la base de datos. Se ejecutan estas operaciones utilizando los algoritmos ya estudiados, almacenando sus resultados en relaciones temporales. Luego se utilizan estas relaciones temporales para ejecutar las operaciones del siguiente nivel en el árbol
Encauzamiento
El encauzamiento ayuda a evitar la escritura en disco de los resultados de muchas subexpresiones, usando los resultados de la expresión padre como si se estuviesen generando.
Se puede mejorar la eficiencia de la evaluación de la consulta mediante la reducción del número de archivos temporales que se producen. Se lleva a cabo esta reducción con la combinación de varias operaciones relacionales en un encauzamientode operaciones, en el que se pasan los resultados de una operación a la siguiente operación del encauzamiento.
Implementación del encauzamiento
Se puede implementar el encauzamiento construyendo una única y compleja operación que combine las operaciones que constituyen el encauzamiento
Cada operación del encauzamiento se modela como un proceso aislado o una hebra en el sistema, que toma un flujo de tuplas de sus entradas encauzadas y produce un flujo de tuplas como salida. Para cada pareja de operaciones adyacentes en el encauzamiento se crea una memoria intermedia para guardar las tuplas que se envían de una operación a la siguiente.
Algoritmos de evaluación para el encauzamiento
El uso eficiente del encauzamiento necesita la utilización de algoritmos de evaluación que puedan generar tuplas de salida según se están recibiendo tuplas por las entradas de la operación.