Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Procesamiento de consultas distribuidas

Unidad 3 BDD
by

Lucero Zamora

on 23 April 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Procesamiento de consultas distribuidas

Procesamiento de consultas distribuidas Unidad 3 Estrategias de procesamiento de consultas distribuidas Optimización de consultas Métodos de ejecución del join Arboles de consultas Transformaciones equivalentes Ejemplo 1: El problema de procesamiento de consultas El éxito creciente de la tecnología de bases de datos relacionales en el procesamiento de datos se debe, a la disponibilidad de lenguajes no procedurales los cuales puedenmejorar significativamente el desarrollo de aplicaciones y la productividad del usuario final. La función principal de un procesador de consultas relacionales es transformar una consulta en una especificación de alto nivel, típicamente en cálculo relacional, a una consulta equivalente en una especificación de bajo nivel, típicamente alguna variación del álgebra relacional Considere el siguiente subconjunto del esquema de una BD:

Empleado (No_Emp, Nombre_Emp, Titulo)
Proyecto (No_Emp, No_Proy, Nombre_Proy, Responsable)

y la siguiente consulta:

"Encuentre todos los nombres de empleados que manejan un proyecto" Las consultas distribuidas detienen acceso a datos de varios orígenes de datos heterogéneos. Estos orígenes de datos pueden estar almacenados en el mismo equipo o en equipos diferentes. Pasos
– Parsing y traducción de la consulta
– Optimización
– Generación de código
– Ejecución de la consulta Cuando una base de datos se encuentra en múltiples servidores y distribuye a un número determinado de nodos tenemos:
•El servidor recibe una petición de un nodo.
•El servidor es atacado por el acceso concurrente a la base de datos cargada localmente.
•El servidor muestra un resultado y le da un hilo a cada una de las maquinas nodo de la red local. Existen diferentes algoritmos que pueden obtener transformaciones eficientes en el procesamiento de consultas. Una de las funciones más importantes de una BD es su capacidad de hacer que los datos estén disponibles El objetivo de una rutina de optimización de consulta es reducir al mínimo el costo total asociado con la ejecución de una solicitud. Una de las características más importantes de la optimización de consultas en sistemas de BDD, es que debe proporcionar transparencia de distribución así como transparencia de réplica Ing. Lucero Zamora M Ocultando los detalles de bajo nivel acerca de la localización física de datos, los lenguajes de bases de datos relacionales permiten la expresión de consultas complejas en una forma concisa y simple. Para construir la respuesta a una consulta, el usuario no tiene que especificar de manera precisa el procedimiento que se debe seguir.Este procedimiento es llevado a cabo por un módulo del DBMS llamado el procesador de consultas (query processor). Dado que la ejecución de consultas es un aspecto crítica en el rendimiento de un DBMS, el procesamiento de consultas ha recibido una gran atención tanto para bases de datos centralizadas como distribuidas. Sin embargo, el procesamiento de consultas es mucho más difícil en ambientes distribuidos que en centralizados, ya que existe un gran número de parámetros que afectan el rendimiento de las consultas distribuidas. La consulta de bajo nivel implementa de hecho la estrategia de ejecución para la consulta. La transformación debe ser correcta y eficiente. Es correcta si la consulta de bajo nivel tiene la misma semántica que la consulta original, esto es, si ambas consultas producen el mismo resultado. El mapeo bien definido que se conoce entre el cálculo relacional y el álgebra relacional hace que la correctitud de la transformación sea fácil de verificar. Una consulta en el cálculo relacional puede tener muchas transformaciones correctas y equivalentes en el álgebra relacional.
Ya que cada estrategia de ejecución equivalente puede conducir a consumos de recursos de cómputo muy diferentes, la dificultad más importante es seleccionar la estrategia de ejecución que minimiza el consumo de recursos. La expresión de la consulta en SQL se puede ver como:

select Nombre_Emp
from Empleado, Proyecto
where Empleado.No_Emp=Proyecto.No_Emp
and Responsable="Administrador" Tarea:
Encontrar las consultas equivalentes en álgebra relacional que transforman correctamente la consulta de SQL Tarea:
Diferencia entre álgebra relacional y cálculo relacional El procesamiento de consultas tiene varias etapas a seguir para resolver una consulta SQL, las características del modelo relacional permiten que cada motor de base de datos elija su propia representación que,comúnmente, resulta ser el álgebra relacional . Existen varios medios para calcular la respuesta a una consulta. En el caso del sistema centralizado, el criterio principal para determinar el costo de una estrategia específica es el número de acceso al disco. En un sistema distribuido es preciso tener en cuenta otros factores como son:
•El costo de transmisión de datos en la red.
•Repetición y fragmentación.
•Procesamiento de intersección simple. Son estructuras de datos en forma de árbol, en donde, los datos al estar ordenados en la estructura, hace más ágiles las consultas Si los datos estuvieran ordenados alfabéticamente en una estructura tipo lista, por ejemplo, e hicieramos una búsqueda (la cual sería secuencial), la búsqueda duraría, en el peor de los casos, un tiempo proporcional a la cantidad de registros que tengas. Es decir, la búsqueda es de órden O(n) [n=número de registros) Pero si los datos están ordenados alfabéticamente en una estructura tipo árbol, e hiciéramos en el árbol una búsqueda (la cual sería binaria), la búsqueda se va recortando en tiempo de acuerdo a la cantidad de registros, el algoritmo de búsqueda binaria en árboles es de órden O(log (n+1)) (n=número de registros). Una función de orden logarítmico es más eficiente que una de orden lineal (como la búsqueda secuencial). Cuando una base de datos es acezada de esta manera la técnica que se utiliza es la de fragmentación de datos que puede ser híbrida, horizontal y vertical. En esta fragmentación lo que no se quiere es perder la consistencia delos datos, por lo tanto se respetan las formas normales de la base de datos. para realizar una transformación en la consulta primero desfragmentamos siguiendo los estándares marcados por las reglas formales y posteriormente realizamos el envió y la maquina 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. Join en bucles (ciclos) anidados Join en bucles anidados por bloques Join por mezcla Join por asociación Join por asociación híbrida Join Complejos Outer Join (Join externos) En una BD centralizada todos los datos residen en un solo sitio, por tanto el DBMS debe evaluar cada solicitud de datos y encontrar la manera más eficiente de accesar a los datos locales Por el contrario el DDBMS hace posible dividir una BD en varios fragmentos, lo que complica mas las consultas por que el DDBMS debe decidir a qué fragmentos de la BD debe accesar La replicación de los datos complica aún más el problema de acceso, por que ahora la BD debe decidir a qué copia de la BD se debe accesar El DDBMS utiliza técnicas de optimización de consultas para ocuparse de tales problemas y para garantizar un desempeño aceptable de la BD Los costos asociados a una solicitud son una función:
1.- Del costo del tiempo de acceso (E/S) implicado al accesar a los datos físicos guardados en disco
2.- Del costo de comunicación asociado con la transmisión de datos entre nodos en sistemas de BDD
3.- Del costo de tiempo de CPU asociado con la sobrecarga de procesamiento de manejar transacciones distribuidas Para evaluar la optimización de consultas tomamos en cuenta que el procesador de transacciones reciben datos del procesador de datos, los sincroniza, arma la respuesta y la presenta al usuario o a una aplicación. El tiempo de respuesta asociado con sitios remotos, no puede predeterminarse con faciloidad, porque algunos nodos son capaces de completar su parte de la consulta en menos tiempo que otros La transparencia de réplica se refiere a la capacidad del DDBMS de ocultar la existencia de copias múltiples de datos al usuario La mayoría de los algoritmos propuestos para una optimización de consultas se basan en dos principios fundamentales:
1.- La selección del orden de ejecución óptimo
2.- La selección de los sitios a ser accesados para reducir al mínimo los costos de comunicación Con estos dos principios, un algoritmo de optimización de consulta puede ser evaluado con base en su modo de operación o en la temporización de su optimización Tarea:
* Optimización de consultas estáticas
* Optimización de consultas dinámicas
Full transcript