Please enable JavaScript.
Coggle requires JavaScript to display documents.
Procesamiento de Consultas (Operación selección (Implementación de…
Procesamiento de Consultas
Visión general
Pasos básicos
Análisis y traducción
Optimización
Evaluación
La primera acción que el sistema tiene que emprender para procesar una consulta es la traducción de la consulta dada a su formato interno
Luego se construye un árbol para el análisis de la consulta que se transformará en una expresión del álgebra relacional que definen la vista
Las operaciones del álgebra relacional anotadas con instrucciones sobre la evaluación reciben el nombre de primitivas de evaluación
Una secuencia de operaciones primitivas que se pueden utilizar para evaluar una consulta establecen un plan de ejecución de la consulta o plan de evaluación de la consulta
Medidas del coste de una consulta
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
El explorador de archivo es el operador de nivel más bajo para acceder a los datos
Los exploradores de archivo son algoritmos de búsqueda que localizan y recuperan los registros que cumplen una condición de selección
Algoritmos básicos
A1 (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
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
Selecciones con índices
A5 (índice secundario, igualdad)
Las selecciones con una condición de igualdad pueden utilizar un índice secundario
A4 (índice primario, igualdad basada en un atributo no clave)
Se pueden recuperar varios registro 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
A3 (índice primario, igualdad basada en la clave)
Para una condición de igualdad en un atributo clave con índice primario se puede utilizar el índice para recuperar el único registro que satisface la correspondiente condición de igualdad
Selección con condiciones de comparación
A6 (índice primario, comparación)
Se puede utilizar un índice ordenado primario 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
Conjunción
Disyunción
Negación
A8 (selección conjuntiva utilizando un índice)
Hay que determinar si para un atributo hay disponible algún cambio de acceso en alguna de las condiciones simples
A9 (selección conjuntiva utilizando un índice compuesto)
Se podría disponer de un índice compuesto (es decir, un índice sobre varios atributos)
A10 (selección conjuntiva mediante la intersección de identificadores)
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 cambios de acceso en todas las condiciones se la selección disyuntiva, se explora cada índice en busca de punteros cuyas tuplas cumplan una condición individual
Ordenación
En la primera etapa, se crean varias secuencias ordenadas
En la segunda etapa, las secuencias se mezclan
El número total de secuencias N es menor que M, así que se puede asignar un marco de página para cada secuencia y reservar espacio para guardar una página con el resultado
La técnica más utilizada para la ordenación externa es normalmente el algorirmo de ordenación-mezcla externa
La ordenación de relaciones que no caben en memoria se llama ordenación externa
Operación reunión
Reunión en bucle anidado
Consiste en un par de bucles for anidados
La relación r se denomina la relación externa y la s la relación interna de la reunión
Es costoso ya que examina cada pareja de tuplas en las dos relaciones
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 bloque si se procesan las relaciones por bloques en lugar de tuplas
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
En el peor de los casos, cada bloque de la relación interna s se lee solamente una vez por cada bloque de la relación externa, en lugar de una vez por cada tupla de la relación externa
Reunión en bucle anidado indexada
Se puede utilizar cuando existen índices, así como cuando se crean índices temporales con el único propósito de evaluar la reunión
La búsqueda de tuplas en s que cumplan las condiciones de la reunión con una tupla dada t, es esencialmente una selección en s
En el pero de los casos solo hay espacio en la memoria intermedia para una página de r y una página del índice
Reunión por mezcla
Se puede utilizar para calcular reuniones naturales y equirreuniones
Dado que las relaciones están ordenadas, las tuplas con el mismo valor en los atributos de la reunión aparecerán consecutivamente
También es posible realizar una variación de la operación reunión por mezcla en tuplas desordenadas si existen índices secundarios en los dos atributos de la reunión
Reunión por asociación
Se utiliza una función de asociación h para dividir las tuplas de ambas relaciones
Reuniones complejas
Reuniones con condiciones de la reunión más complejas, tales como conjunciones y disyunciones
Otras operaciones
Eliminación de duplicados
Proyección
Operaciones sobre conjuntos
Reunión externa
Agregación
Evaluación de expresiones
Materialización
Los resultados de cada operación intermedia se crea (materializan) para utilizarse a continuación en la evaluación de las operaciones del siguiente nivel
Encauzamiento
La combinación de operaciones en un encauzamiento elimina el coste de leer y escribir relaciones temporales
Implementación del encauzamiento
Bajo demanda
El sistema reitera peticiones de tuplas desde la operación de la cima del encauzamiento
Desde los productores
Los operadores no esperan a que se produzcan peticiones para producir tuplas, en su lugar generan las tuplas impacientemente
Algoritmos de evaluación para el encauzamiento
El uso eficiente del encauzamiento necesita la utlizació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
Casos
Solamente una de las entradas de la reunión está encauzada
Las dos entradas de la reunión están encauzadas