En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos




descargar 0.75 Mb.
títuloEn años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos
página17/36
fecha de publicación02.02.2016
tamaño0.75 Mb.
tipoDocumentos
b.se-todo.com > Economía > Documentos
1   ...   13   14   15   16   17   18   19   20   ...   36

4.2 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.

4.3 La complejidad de las operaciones del álgebra relacional



La complejidad de las operaciones del álgebra relacional afectan directamente su tiempo de ejecución y establecen algunos principios útiles al procesador de consultas. Esos principios pueden ayudar en elegir la estrategia de ejecución final. La forma más simple de definir la complejidad es en términos de la cardinalidad de las relaciones independientemente de los detalles de implementación tales como fragmentación y estructuras de almacenamiento. La Figura 4.3 presenta la complejidad de las operaciones unarias y binarias en el orden creciente de complejidad.


Operación

Complejidad

Selección
Proyección
(sin eliminación de duplicados)

O(n)

Proyección
(con eliminación de duplicados)
Agrupación

O(n*log n)

Junta
Semijunta
División
Operadores sobre conjuntos

O(n*log n)

Producto Cartesiano

O(n2)

Figura 4.3. Complejidad de las operaciones del álgebra relacional.
Esta simple mirada a la complejidad de las operaciones sugiere dos principios:


  1. Dado que la complejidad es con base en las cardinalidades de las relaciones, las operaciones más selectivas que reducen las cardinalidades deben ser ejecutadas primero.

  2. Las operaciones deben ser ordenadas en el orden de complejidad creciente de manera que el producto Cartesiano puede ser evitado o, al menos, ejecutado al final de la estrategia.



4.4 Caracterización de los procesadores de consultas



Es difícil evaluar y comparar procesadores de consultas para sistemas centralizados y distribuidos dado que ellos difieren en muchos aspectos. En esta sección se enumeran algunas características importantes de los procesadores de consultas que pueden ser usados como base para su comparación.

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 o el 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.

Estadísticas



La efectividad de una optimización recae en las estadísticas de la base de datos. La optimización dinámica de consultas requiere de estadísticas para elegir las operaciones que deben realizarse primero. La optimización estática es aún más demandante ya que el tamaño de las relaciones intermedias también debe ser estimado basándose en estadísticas. En bases de datos distribuidas las estadísticas para optimización de consultas típicamente se relacionan a los fragmentos; la cardinalidad y el tamaño de los fragmentos son importantes así como el número de valores diferentes de los atributos. Para minimizar la probabilidad de error, estadísticas más detalladas tales como histogramas de valores de atributos se usan pagando un costo mayor por su manejo.

Nodos de Decisión



Cuando se utiliza la optimización estática, un solo nodo o varios de ellos pueden participar en la selección de la estrategia a ser aplicada para ejecutar la consulta. La mayoría de los sistemas utilizan un enfoque centralizado para la toma de decisiones en el cual un solo lugar decide la estrategia a ejecutar. Sin embargo, el proceso de decisión puede ser distribuido entre varios nodos los cuales participan en la elaboración de la mejor estrategia. El enfoque centralizado es simple, pero requiere tener conocimiento de la base de datos distribuida completa. El enfoque distribuido requiere solo de información local. Existen enfoques híbridos en donde un nodo determina una calendarización global de las operaciones de la estrategia y cada nodo optimiza las subconsultas locales.

Topología de la Red



Como se mencionó al principio, el tipo de red puede impactar severamente la función objetivo a optimizar para elegir la estrategia de ejecución. Por ejemplo, en redes de tipo WAN se sabe que en la función de costo el factor debido a las comunicaciones es dominante. Por lo tanto, se trata de crear una calendarización global basada en el costo de comunicación. A partir de ahí, se generan calendarizaciones locales de acuerdo a una optimización de consultas centralizada. En redes de tipo LAN el costo de comunicación no es tan dominante. Sin embargo, se puede tomar ventaja de la comunicación "broadcast" que existe comúnmente en este tipo de redes para optimizar el procesamiento de las operaciones junta. Por otra parte, se han desarrollado algoritmos especiales para topologías específicas, como por ejemplo, la topología de estrella.

1   ...   13   14   15   16   17   18   19   20   ...   36

similar:

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases de datos de secuencias de adn y proteínas

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconUna red de comunicaciones es la combinación de hardware, software...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconResumen a lo largo de los años, la agricultura se ha mantenido como...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconResumen El presente trabajo de investigación bibliográfica trata...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconCientífico británico que sentó las bases de la moderna teoría evolutiva,...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconRecibimos de las distintas sucursales de la empresa los datos correspondientes a las ventas en

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconEntre las herramientas utilizadas en la minería de datos (Data Mining)...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconMinería de Datos aplicados a las ventas con Tarjeta de Crédito realizados...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases moleculares de las acciones de la insulina

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases moleculares de las acciones de la insulina




Todos los derechos reservados. Copyright © 2015
contactos
b.se-todo.com