PDF de programación - BASES DE DATOSDISTRIBUIDAS MIS 515 - 3. PROCESAMIENTO DE CONSULTAS DISTRIBUIDAS

BASES DE DATOSDISTRIBUIDAS MIS 515
1
1
BASES DE DATOS
DISTRIBUIDAS
TEMA 3
PROFESOR: M.C. ALEJANDRO GUTIÉRREZ DÍAZ
2
3. PROCESAMIENTO DE CONSULTAS DISTRIBUIDAS
3.1 Metodología del procesamiento de consultas distribuidas
3.2 Estrategias de procesamiento de consultas distribuidas
3.3 Optimización de consultas distribuidas
3.4 Optimización global
3
El procesamiento de consultas es de suma importancia en bases de
datos centralizadas. Sin embargo, en BDD éste adquiere una relevancia
mayor.
BASES DE DATOSDISTRIBUIDAS MIS 515
2
El objetivo es convertir transacciones de usuario en instrucciones para
manipulación de datos. No obstante, el orden en que se realizan las
transacciones afecta grandemente la velocidad de respuesta del sistema.
Así, el procesamiento de consultas presenta un problema de
optimización en el cual se determina el orden en el cual se hace la menor
cantidad de operaciones. Este problema de optimización es NP-difícil,
por lo que en tiempos razonables solo se pueden obtener soluciones
aproximadas.
4
En BDD se tiene que considerar el procesamiento local de una consulta
junto con el costo de transmisión de información al lugar en donde se
solicitó la consulta.
El éxito creciente de la tecnología de bases de datos relacionales en el
procesamiento de datos se debe, en parte, a la disponibilidad de
lenguajes los cuales pueden mejorar significativamente el desarrollo de
aplicaciones y la productividad del usuario final.

5
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.
Particularmente, 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
BASES DE DATOSDISTRIBUIDAS MIS 515
3
número de parámetros que afectan el rendimiento de las consultas
distribuidas. En este capítulo revisaremos el procesamiento de consultas
para bases de datos distribuidas.
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
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.
6
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. Sin embargo, producir una estrategia de ejecución eficiente
es mucho más complicado. 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.
Ejemplo 4.1. Considere el siguiente subconjunto del esquema de la base
de datos de ingeniería que se presentó en el capítulo 2
E( ENO, ENOMBRE, TITULO )
G( ENO, JNO, RESPONSABLE, JORNADA )

y la siguiente consulta de usuario:
"Encuentre todos los nombres de empleados que manejan un
proyecto"
BASES DE DATOSDISTRIBUIDAS MIS 515
4

7
La expresión de la consulta en SQL se puede ver como
SELECT ENOMBRE
FROM E, G
WHERE E.ENO = G.ENO AND RESPONSABLE =
"ADMINISTRADOR"
Dos consultas equivalentes en el álgebra relacional que son
transformaciones correctas de la consulta en SQL son:

Como es intuitivamente obvio, la segunda estrategia que evita calcular el
producto cartesiano entre E y G, consume mucho menos recursos que la
primera y, por lo tanto, es mejor.
En un contexto centralizado, las estrategias de ejecución de consultas
pueden ser bien expresadas como una extensión del álgebra relacional.
Sin embargo, en sistemas distribuidos, el álgebra relacional no es
suficiente para expresar la ejecución de estrategias. Debe ser
complementada con operaciones para el intercambio de datos entre
nodos diferentes.
Además de elegir el orden de las operaciones del álgebra relacional, el
procesador de consultas distribuidas debe seleccionar también los
mejores sitios para procesar datos y posiblemente la forma en que ellos
tienen que ser transformados.
BASES DE DATOSDISTRIBUIDAS MIS 515
5

8
Ejemplo 4.2. Considere la siguiente consulta del Ejemplo ANTERIOR
Supongamos que las relaciones E y G están fragmentadas horizontalmente como
sigue:
E1 = ó ENO ≤ "E3" (E)
E2 = ó ENO > "E3" (E)

G1 = ó ENO ≤ "E3" (G)
G2 = ó ENO > "E3" (G)
Los fragmentos E1, E2, G1 y G2 están almacenados en los nodos 1, 2, 3 y
4, respectivamente, y el resultado se quiere en el nodo 5. En la Figura
4.2 se presentan dos estrategias distribuidas de ejecución diferentes para
la misma consulta (se ha ignorado el operador de proyección por
simplicidad del ejemplo).
La estrategia A explota el hecho de que las relaciones E y G están
fragmentadas de la misma manera y ejecuta la operación de selección y
junta en paralelo.
La estrategia B centraliza todos los datos en el nodo resultante antes de
procesar la consulta.
Para evaluar el consumo de recursos, se usará un modelo de costo
simple. Suponga que el costo de acceso a un tupla (tupacc) es 1 unidad,
y la transferencia de un tupla (tuptrans) tiene un costo de 10 unidades.
Suponga que las relaciones E y G tienen 400 y 1000 tuplas,
respectivamente, y que existen 20 administradores en la relación G.
También, suponga que los datos están uniformemente distribuidos entre
los nodos.
Finalmente, suponga que las relaciones G y E están agrupadas
localmente en los atributos RESP y ENO, respectivamente, de manera
que, hay un acceso directo a los tuplas de G y E, respectivamente.
BASES DE DATOSDISTRIBUIDAS MIS 515
6

9
El costo de la estrategia A se puede derivar como sigue:

10
El costo de la estrategia B se puede derivar como sigue:
BASES DE DATOSDISTRIBUIDAS MIS 515
7
La estrategia A es mejor por un factor de 37, lo cual es significativo. La
diferencia sería aún mayor si se hubiera asumido un costo de

comunicación mayor y/o un grado de fragmentación mayor.
11
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.
BASES DE DATOSDISTRIBUIDAS MIS 515
8

12
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

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.
BASES DE DATOSDISTRIBUIDAS MIS 515
9

13
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 a