REPORTE UNIDAD lll

Instituto Tecnologico de Ciudad Juarez

 

BASES DE DATOS DISTRIBUIDAS  

Reporte de Actividades

UNIDAD III

3.1. Metodología del procesamiento de consultas distribuidas

                             3.2. Estrategias de procesamiento de consultas distribuidas

                             3.3. Optimización de consultas

 

Alumna: Gomez Rodriguez Veronica

titular: Angelica C. Martinez Q. 

 

Estrategias de procesamiento de consultas distribuidas

Contamos con la estrategia de Reformulación de consultas, que nos sirve para  encontrar que la información que nos va a proveer sea solo la que se le pidió por la  fuente. También se cuenta con la estrategia de descomposición de las fuentes, que consiste  en que según las fuentes que pidan cierto tipo de datos sean las atentidas con mayor  velocidad.

 Árboles de consultas

Es una estructura de árbol que corresponde a una  expresión del álgebra relacional en el que las tablas se representan como  nodos hojas y las operaciones del álgebra relacional como nodos  intermedios. 

Transformaciones equivalentes

Cuando una base de datos se encuentra en múltiples servidores y distribuye a un  número determinado de nodos tenemos:

1.-el servidor recibe una petición de un nodo

2.-el servidor es atacado por el acceso concurrente a la base de datos cargada  localmente

3.-el servidor muestra un resultado y le da un hilo a cada una de las maquinas  nodo de la red local.

Cuando una base de datos es accesada de esta manera la técnica que se utiliza  es la de fragmentación de datos que puede ser hibrida, horizontal y vertical. En esta fragmentación lo que no se quiere es perder la consistencia de los datos,  por lo tanto se respetan las formas normales de la base de datos.

Para realizar una transformación en la consulta primero se desfragmenta  siguiendo los estándares marcados por las reglas formales y posteriormente se  realiza él envió y la máquina que recibe es la que muestra el resultado pertinente para el usuario, de esta se puede producir una copia que será la equivalente a la  original.

 Métodos de ejecución del Join

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 r para 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.

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.

Optimización de consultas

Para poder optimizar una consulta necesitamos tener claras las propiedades del algebra relacional para asegurar la reformulación de la consulta, al optimizar una consulta obtenemos los siguientes beneficios:

°minimizar costos

°Reducir espacios de comunicaciones-Seguridad en envíos de información

Objetivos de la optimización de consultas

Como se estableció antes, el objetivo del procesamiento de consultas en un ambiente distribuido es transformar una consulta sobre una base de datos distribuida en una especificación de alto nivel a una estrategia de ejecución eficiente expresada en un lenguaje de bajo nivel sobre bases de datos locales.

Así, el problema de optimización de consultas es minimizar una función de costo tal que función de costo total = costo de I/O + costo de CPU + costo de comunicación.

Los diferentes factores pueden tener pesos diferentes dependiendo del ambiente distribuido en el que se trabaje. Por ejemplo, en las redes de área amplia (WAN), normalmente el costo de comunicación domina dado que hay una velocidad de comunicación relativamente baja, los canales están saturados y el trabajo adicional requerido por los protocolos de comunicación es considerable.

Así, los algoritmos diseñados para trabajar en una WAN, por lo general, ignoran los costos de CPU y de I/O. En redes de área local (LAN) el costo de comunicación no es tan dominante, así que se consideran los tres factores con pesos variables.

Tipo de optimización

El problema de optimización de consultas es altamente demandante en tiempo de ejecución y, en el caso general, es un problema de la clase NP. Así existen dos estrategias para su solución: búsqueda exhaustiva oel uso de heurísticas. Los algoritmos de búsqueda exhaustiva tienen una complejidad combinatorial en el número de relaciones de la consulta.

Obtienen la transformación óptima, pero sólo se aplican a consultas simples dado su tiempo de ejecución.

Por otro lado, los algoritmos heurísticos obtienen solo aproximaciones a la transformación óptima pero lo hacen en un tiempo de ejecución razonable. Las heurísticas más directas a aplicar son el agrupamiento de expresiones comunes para evitar el cálculo repetido de las mismas, aplicar primero las operaciones de selección y proyección, reemplazar una junta por una serie de semijuntas y reordenar operaciones para reducir el tamaño de las relaciones intermedias.

Granularidad de la optimización

Existen dos alternativas: considerar sólo una consulta a la vez o tratar de optimizar múltiples consultas. La primera alternativa no considera el uso de resultados comunes intermedios. En el segundo caso puede obtener transformaciones eficientes si las consultas son similares. Sin embargo, el espacio de decisión es mucho más amplio lo que afecta grandemente el tiempo de ejecución de la optimización.

Tiempo de optimización

Una consulta puede ser optimizada en tiempos diferentes con relación a tiempo de ejecución de la consulta. La optimización se puede realizar de manera estática antes de ejecutar la consulta o de forma dinámica durante la ejecución de la consulta. La optimización estática se hace en tiempo de compilación de la consulta. Así, el costo de la optimización puede ser amortizada sobre múltiples ejecuciones de la misma consulta. Durante la optimización de consultas dinámica la elección de la mejor operación siguiente se puede hacer basado en el conocimiento exacto de los resultados de las operaciones anteriores. Por tanto, se requiere tener estadísticas acerca del tamaño de los resultados intermedios para aplicar esta estrategia.

Un tercer enfoque, conocido como híbrido, utiliza básicamente un enfoque estático, pero se puede aplicar un enfoque dinámico cuando los tamaños de las relaciones estimados están alejados de los tamaños actuales.

 Optimización global de consultas

Cuando hablamos de optimización de consultas nos referimos a mejorar los tiempos de respuesta en un sistema de gestión de bases de datos relacional, pues la optimización es el proceso de modificar un sistema para mejorar su eficiencia o también el uso de los recursos disponibles.

En bases de datos relacionales el lenguaje de consultas SQL es el más utilizado por el común de los programadores y desarrolladores para obtener información desde la base de datos. La complejidad que pueden alcanzar algunas consultas puede ser tal, que el diseño de una consulta puede tomar un tiempo considerable, obteniendo no siempre una respuesta óptima.

Optimización local de consultas

Para procesar una consulta local solo se hace referencia a tablas y bases de datos locales(no a vistas ni a tablas remotas) , es decir que estén dentro de la misma instancia del manejador de bases de datos, en una única máquina y que no se tenga que conectar al servidor a otras máquinas para poder efectuar la consulta. Cada subconsulta que se ejecuta en un nodo, llamada consulta local, es optimizada usando el esquema local del nodo. Hasta este momento, se pueden eligen los algoritmos para realizar las operaciones relacionales. La optimización local utiliza los algoritmos de sistemas centralizados.