Resumen.
Dentro del diseño de una base de datos distribuida, el diseño
de la distribución de los datos fragmentación y asignación
es un aspecto crítico y es lo que marca la diferencia del
diseño de una base de datos no distribuida. Este trabajo está
enfocado a la asignación de los datos, mas no a la
fragmentación de los mismos, para lo cual se presenta el modelo
matemático general de este problema.
El problema de la asignación de los datos no es un problema
sencillo de resolver algorítmicamente, por lo que es
necesario buscar métodos de solución heurísticos que
permitan obtener una buena solución. En este sentido, se
describe el método de dos fases para el problema de asignación
óptima de datos (fragmentos) sobre una red en un sistema de base
de datos distribuida [4].
En la primera fase se realiza la agrupación de fragmentos, en la
que se forman grupos de fragmentos que tienden a ser accesados por
una misma consulta en el sistema de base de datos distribuida. En
la segunda fase se usa la técnica de búsqueda Divide y
Conquista para asignar clusters a los nodos en la red (sitios).
Para cada una de las fases, se van presentando los resultados con
un ejemplo práctico.
1 Introducción:
La asignación de datos es un aspecto crítico en el diseño
de un sistema de base de datos distribuida. Una asignación de
datos pobremente diseñada puede permitir cálculos
ineficientes, altos costos de acceso, y sobrecarga en la red,
mientras que una asignación de datos bien diseñaada puede
mejorar la disponibilidad de los datos, disminuir el tiempo de
acceso y optimizar el uso de los recursos. Por lo tanto, es muy
importante brindar sistemas de base de datos distribuida con una
forma eficiente de conseguir una asignación de datos efectiva.
Este documento está orientado a determinar dónde ubicar un
conjunto de datos dado (fragmentos) sobre los nodos de una red de
computadoras (sitios) para minimizar el costo de respuesta a un
conjunto de consultas Q. Asumimos que la fragmentación de las
tablas originales de la base de datos se ha llevado a cabo antes
de la fase de asignación de datos. La fragmentación puede
estar basada en intereses pragmáticos de la empresa a la que
corresponde la base de datos, la semántica de la misma base de
datos, o en algún criterio de desempeño. Aunque la
fragmentación es un tema importante, nuestro principal interés
aquí es cómo deberían ser asignados los datos
alrededor de la red una vez que han sido particionados de acuerdo
a algún criterio.
Hay dos aspectos importantes en una buena solución para el
problema de la asignación de datos. Primero, ésta debería
generar asignaciones efectivas (esto es, asignaciones que
minimicen el costo de respuesta a las consultas establecidas).
Segundo, el proceso de asignación debe ser eficiente (es decir,
debe encontrar una buena solución en un tiempo razonable).
En este documento, se presenta una aproximación para el problema
de asignación de datos que comprende dos fases: en la primera
fase, se desarrolla la agrupación de fragmentos y en la segunda
se determina una ubicación eficiente para estos grupos de
fragmentos o clusters en la red. El fundamento de esta
aproximación radica en que, los fragmentos que son usados para
responder a cierta consulta deberían estar ubicados en el
mismo sitio, y debido a que los fragmentos son agrupados en
clusters antes de la asignación y considerando los clusters como
la unidad movible durante la asignación, se reduce
considerablemente el espacio de búsqueda para el problema de la
asignación.
El problema de agrupamiento de fragmentos (clustering) involucra
ubicar un conjunto de objetos en grupos de acuerdo a alguna medida
(usualmente heurística) de su "relatividad". En este caso, la
"relatividad" que ncesitamos medir es la tendencia de los
fragmentos a ser usados juntos en responder a un conjunto dado de
consultas. Esta noción ya ha sido utilizada como la base de un
algoritmo de agrupamiento para bases de datos distribuidas : el
Algoritmo de Particionamiento Vertical Binario (BVP)
[9]. Aunque este método fue desarrollado
originalmente para determinar grupos de atributos dentro de una
relación con el propósito de fragmentarla verticalmente, puede
ser f\'acilmente adaptado para determinar grupos de fragmentos. En
concordancia con su nuevo uso, se ha renombrado este algoritmo
como Algoritmo de Agrupamiento Binario de Fragmentos (BFC)
[4]. Según este esquema, se invoca al algoritmo BFC
recursivamente para generar una serie de n esquemas de
agrupamiento (donde n es el número total de fragmentos). El
primer esquema tiene un grupo conteniendo todos los fragmentos, el
segundo esquema tiene dos grupos, y, así sucesivamente, hasta
el nth esquema que contiene n grupos, cada uno conteniendo un
único fragmento.
Como se mencionó anteriormente, el problema de asignación de
datos involucra determinar dónde ubicar un conjunto de datos de
tal forma que se minimice el costo de responder a un conjunto de
consultas establecidas. Éste es un problema complejo de
optimización para el cual todavía no se ha encontrado una
solución analítica eficiente. Sin embargo, se han sugerido
muchas soluciones heurísticas. En el método presentado en
este documento, los grupos de fragmentos producidos por el
algoritmo BFC sirven como entrada al algoritmo de asignación de
datos [4]. Se usa una técnica de búsqueda conocida
como divide y conquista, que hace uso de las propiedades de
los esquemas de agrupamiento generados en la primera fase, para
determinar eficientemente una ubicación cercana a la óptima
para cada uno de los grupos de fragmentos sobre los sitios de la
red. Debido a que la técnica de búsqueda trabaja sobre grupos
de fragmentos en lugar de fragmentos individuales, el espacio de
búsqueda se reduce considerablemente.
En la sección 2 se presentan algunos
conceptos básicos e introductorios definiendo una base de datos
distribuida y especialmente enfocándose en el diseño de la
distribución de los datos. Un punto importante tratado en esta
sección se refiere a la fragmentación, sobre el cual sólo se
da un alcance panorámico.
La sección 3 muestra en qué consiste el problema
de asignación de datos en una base de datos distribuida. Dentro
de esta sección se presenta el modelo matemático del problema
de asignación. El método de dos fases para la asignación de
datos se presenta en la sección 4. La
sección 5 presenta las conclusiones.
2 Preliminares
El diseño de una base de datos distribuida implica la toma de
decisiones sobre la ubicación de los programas que accederán a
la base de datos y sobre los propios datos que constituyen esta
última, a lo largo de los diferentes nodos que configuren una
red de computadoras. La ubicación de los programas, a priori, no
debería suponer un excesivo problema dado que se puede tener
una copia de ellos en cada máquina de la red (de hecho, en este
documento se asumirá que así es). Sin embargo, cuál es la
mejor opción para colocar los datos: en una gran máquina que
albergue a todos ellos, encargada de responder a todas las
peticiones del resto de las estaciones (sistema de base de datos
centralizado), o podríamos pensar en repartir las tablas, por
toda la red. En el supuesto caso que nos decidamos por esta
segunda opción, ¿qué criterios se deberían seguir para
llevar a cabo tal distribución? ¿Realmente este enfoque
ofrecería un mayor rendimiento que el caso centralizado?
¿Podría optarse por alguna otra alternativa? En los
párrafos siguientes se tratar\'a de responder a estas preguntas.
Dentro del diseño de una base de datos distribuida, el diseño
de la distribución constituye el paso distintivo del diseño de
una base de datos centralizada. El objetivo de esta etapa consiste
en diseñar los esquemas conceptuales locales que se
distribuirán a lo largo de todos los nodos del sistema
distribuido. Sería posible tratar cada entidad como una
unidad de distribución; en el caso del modelo relacional, cada
entidad se corresponde con una relación. Resulta bastante
frecuente dividir cada relación en subrelaciones menores
denominadas fragmentos que luego se ubican en uno u otro sitio. De
ahí, que el proceso del diseño de la distribución conste
de dos actividades fundamentales: la fragmentación y la
asignación.
El principal problema de la fragmentación radica en encontrar la
unidad apropiada de distribución. Una relación no es una buena
unidad, por ello, sería normal considerar como unidad de
distribución a subconjuntos de relaciones. Dado que una
relación se corresponde esencialmente con una tabla y la
cuestión consiste en dividirla en fragmentos menores,
inmediatamente surgen dos alternativas lógicas para llevar a
cabo el proceso: la división horizontal y la división
vertical. La división o fragmentación horizontal trabaja sobre
las tuplas, dividiendo la relación en subrelaciones que
contienen un subconjunto de las tuplas que alberga la primera. La
fragmentación vertical, en cambio, se basa en los atributos de
la relación para efectuar la división.
Partiendo del supuesto que la base de datos se haya fragmentado
correctamente, habrá que decidir sobre la manera de asignar los
fragmentos a los distintos sitios de la red.
3 El Problema de Asignación de Datos en una Base de Datos Distribuida
3.1 El Problema de Asignación
Sean un conjunto de fragmentos F={F1, F2, ..., Fn} y una
red formada por el conjunto de sitios S={S1, S2, ..., Sm}
en la cual se ejecutan un conjunto de consultas (o aplicaciones)
Q={q1, q2, ..., qq}. El problema de asignación implica
encontrar la distribución óptima de F sobre S.
Uno de los problemas más importantes que necesita discusión es
el significado de distribución óptima. La distribución
óptima puede definirse respecto a dos medidas:
Costo mínimo : La función de costo consiste en el
costo de almacenamiento de cada Fi en un sitio Sj, el costo
de practicar una consulta en Fi en el sitio Sj, el costo de
actualizar Fi en todos los sitios donde se almacene y el costo
de las comunicaciones de datos. El problema de la asignación,
entonces, intenta encontrar un esquema de asignación tal que
minimice esta función de costo combinado.
Rendimiento : La estrategia de asignación se diseña para
mantener una medida del rendimiento. Dos medidas habituales de
este rendimiento son el tiempo de respuesta y throughput del
sistema en cada sitio. Evidentemente, se debe intentar minimizar
la primera y maximizar la segunda.
En cualquier problema de optimización existen restricciones que
se deben satisfacer. En el caso de distribución de fragmentos,
las restricciones se establecen sobre las capacidades de
almacenamiento y procesamiento de cada nodo en la red.
3.2 Requerimientos de Información
En la fase de asignación se necesita conocer información
cuantitativa relativa a la base de datos, las aplicaciones que se
utilizarán, la red de comunicaciones, las capacidades de
procesamiento y de almacenamiento de cada nodo en la red.
Información sobre la base de datos : Es necesario conocer
la selectividad de un fragmento Fj respecto a una consulta
qi, esto es, el número de tuplas de Fj que sería
necesario accesar para procesar qi. Este valor se denota como
sel(Fj). Así también, es necesario conocer el tamaño
de cada fragmento, el cual está dado por
tamaño(Fj) = card(Fj)long(Fj)
Información sobre las aplicaciones : Es necesario
distinguir el número de lecturas que una consulta qj hace a
un fragmento Fj durante su ejecución, del número de
escrituras. Se requiere de una matriz que indique qué consultas
actualizan cuáles fragmentos. Una matriz similar se necesita
para indicar las lecturas de consultas a fragmentos. Finalmente,
se necesita saber cuál es el nodo de la red que origina cada
consulta.
Información sobre cada nodo de la red : Las medidas
utilizadas son el costo unitario de almacenamiento de datos en un
nodo y el costo unitario de procesamiento de datos en un nodo.
Información sobre la red de comunicaciones : Las medidas a
considerar son el costo por trama de comunicación entre dos
sitios y el tamaño de la trama.
|
