3.2 Modelo de Asignación
El modelo que se presenta a continuación pretende minimizar el
costo total de procesamiento y almacenamiento satisfaciendo
algunas restricciones en el tiempo de respuesta. El modelo tiene
la siguiente forma general:
min(Costo Total)
dadas
restricciones en el tiempo de respuesta
restricciones en las capacidades de almacenamiento
restricciones en el tiempo de procesamiento
A continuación se trataría de ampliar los componentes de este
modelo. Se define la variable de decisión xij de la
siguiente manera:
| xij |
{ |
1, si el fragmento Fi es almacenado en el nodo Sj
0, en otro caso.
|
Costo Total
La función de costo total tiene dos componentes: procesamiento
de consultas y almacenamiento. Así, puede ser expresado de la
siguiente forma:
donde QPCi es el costo de procesamiento de la consulta qi, y
STCjk es el costo de almacenar el fragmento Fj en el nodo
Sk.
El costo de almacenamiento se puede expresar como
donde USCk es el costo de almacenamiento unitario en el nodo
Sk.
El costo de procesamiento de una consulta tiene dos componentes:
el costo de procesamiento y el costo de transmisión. Esto se
puede expresar como
QPCi = PCi + TCi
El componente de procesamiento involucra tres factores: el costo
de acceso (AC), el costo de mantenimiento de la integridad (IE) y
el costo debido al control de concurrencia (CC). Así podemos
expresar
PCi = ACi + IEi + CCi
La especificación detallada de cada uno de estos factores de
costo depende del algoritmo utilizado para realizar estas tareas.
Sin embargo, el costo de acceso se puede especificar con algún
detalle:
donde los primeros dos términos dan el número total de
actualizaciones y lecturas realizadas por la consulta qi en el
fragmento Fj, y LPCk es el costo unitario de procesamiento
local, en Sk, de una unidad de trabajo. Los costos del
mantenimiento de la integridad y del control de concurrencia
pueden ser calculados similarmente al costo de acceso.
Respecto al componente de transmisión, éste puede separarse en
el procesamiento de actualizaciones y de consultas (lecturas),
dado que los tiempos de procesamiento para ellas son completamente
diferentes. En las actualizaciones, es necesario informar a todos
los nodos con réplicas, mientras que en las lecturas o
consultas, es suficiente con acceder sólo a una de las copias.
Más aún, al final de una solicitud de actualización, no
existe una transmisión de datos de regreso, sólo un mensaje de
confirmación, mientras que una consulta (lectura) puede resultar
en una transmisión significativa de datos.
El componente de actualizaciones de la función de transmisión
es
El primer término representa el envío del mensaje de
actualización desde el nodo de origen o(i) de qi a todos
los fragmentos con réplicas que necesitan ser actualizados. El
segundo término es debido al mensaje de confirmación. El
costo correspondiente a las consultas se puede especificar como
El primer término en TCR representa el costo de transmitir la
solicitud de consulta a aquellos nodos que contienen copias de los
fragmentos que necesitan ser accesados. El segundo término toma
en cuenta la transmisión de los resultados de esos nodos al nodo
de origen. La ecuación considera entre los nodos con copias del
mismo fragmento, sólo el nodo que produce el costo mínimo
de transmisión. Ahora, la función del costo de transmisión
para la consulta qi puede ser especificada como
TCi = TCUi + TCRi
Restricciones
La restricción del tiempo de respuesta se debe especificar como:
| tiempo de ejecución de qi < = ; máximo tiempo de respuesta de |
|
La restricción de almacenamiento se puede especificar como:
| Ʃ STCjk < = capacidad de almacenamiento en nodo |
|
La restricción del tiempo de procesamiento es:
 |
carga de procesamiento de qi en el nodo Sk < = capacidad de procesamiento de
|
|
3.4 Métodos de Solucion
La aproximación básica e intuitiva para el problema de
asignación de datos consiste en generar exhaustivamente todas
las posibles asignaciones de datos usando el conjunto de
fragmentos, y calcular el costo de cada posible asignación para
seleccionar la asignación que produzca el costo mínimo.
Esto garantiza que la asignación escogida es el óptimo global,
pero no es factible en la práctica debido a que el número de
posibles asignaciones es sumamente grande (exponencial respecto al
número de sitios y fragmentos).
Han habido varios intentos para reducir la complejidad del
problema. Una estrategia ha sido asumir que todos los
particionamientos posibles han sido determinados junto con sus
costos asociados y sus beneficios en términos del procesamiento
de consultas. El problema entonces, es modelado como la elección
del particionamiento y asignación óptimos para cada
relación. Otra simplificación frecuentemente empleada es
ignorar inicialmente la replicación de datos y encontrar una
solución óptima para el caso no replicado. La replicación se
incorpora en un segundo paso el cual aplica un algoritmo que
inicia a partir de la solución no replicada y trata de mejorarla
iterativamente.
Como puede entenderse, 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, en la siguiente sección 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]
4 Método de dos fases para la asignación de datos
El problema de asignación de datos en una
base de datos distribuida puede ser tratado de una forma elegante
y eficiente mediante una aproximación de dos fases.
Agrupación de Fragmentos
Determina
cómo agrupar fragmentos en clusters basándonos en un conjunto
de consultas dadas y sus frecuencias de accesos.
Asignación de Clusters
Determina cómo
asignar los clusters de fragmentos sobre los nodos de la red, tal
que el costo de procesamiento de todas las consultas (en nuestro
caso, una combinación de costo de transmisión y costo de
procesamiento determinado por un optimizador de consultas
distribuidas) sea minimizado.
Un panorama de esta aproximación se muestra en la
Figura 1.
Fig.1. Esquema de Asignación de Datos en Dos Fases
Una matriz de uso de fragmentos (FUM) indica qué fragmentos son
usados por una determinada consulta, por lo tanto nos brinda
alguna idea de cómo agrupar los fragmentos. En el ejemplo
presentado en el Apéndice A, la consulta Q2
hace uso de los fragmentos F2, F3, F4 y F_5. En este
ejemplo, F2 y F5 son usados siempre en conjunción.
Entonces, si son colocados en el mismo sitio se reducirá el
costo de responder a las consultas que los involucren.
|
