Fragmentación
El
problema de fragmentación se refiere al particionamiento de
la información para
distribuir cada parte a los diferentes sitios de la red
Objetivos
de la fragmentación
El objetivo
de la fragmentación consiste
en la relación en un de relaciones más
pequeñas tal que algunas de las aplicaciones de usuario sólo hagan
uso de un fragmento.
Sobre
este marco, una fragmentación óptima es aquella que produce un
esquema de división que minimiza el tiempo de
ejecución de las aplicaciones que emplean esos fragmentos.
La
unidad de fragmentación no es la tabla sino una
subdivisión de ésta.
Esto
es debido a:
- Las aplicaciones usan vistas definidas sobre varias relaciones, es decir, se forman a partir de "trozos" de varias tablas. Si conseguimos que cada una de las vistas esté definida sobre subtablas locales (o en su defecto lo mas "cerca" posible) a cada aplicación, es de esperar un incremento en el rendimiento.
- Si múltiples vistas de diferentes aplicaciones están definidas sobre una tabla no fragmentada, se tiene :
- Si la tabla no está replicada entonces se produce generación de por accesos remotos.
- Si la tabla está replicada en todos o algunos de los sitios donde residen cada una de las aplicaciones entonces la generación de trafico innecesario es producida por la necesidad de la actualización de las copias.
Al
descomponer una relación en fragmentos (unidades de distribución) :
- Permitimos el procesamiento concurrente de transacciones ya que no se bloquean tablas enteras sino subtablas, por lo que dos consultas pueden acceder a la misma tabla a fragmentos distintos.
- Permitimos la paralelización de consultas al poder descomponerlas en subconsultas, cada una de la cuales trabajará con un fragmento diferente incrementándose así el rendimiento.
Desventajas
- Degradación del rendimiento en vistas definidas sobre varios fragmentos ubicados en sitios distintos (es necesario realizar operaciones con esos trozos lo cual es costoso)
- El control semántico se dificulta y el rendimiento se degrada debido que la verificación de restricciones de integridad (claves ajenas, uniques, etc) implican buscar fragmentos en múltiples localizaciones.
Por
lo tanto división y ubicación de los fragmentos no es trivial.
Tipos
de fragmentación de datos
Existen
tres tipos de fragmentación:
- Fragmentación horizontal
- Fragmentación vertical
- Fragmentación híbrida
Para
que una la fragmentación de una relación sea correcta debe
satisfacer las siguientes condiciones:
- Condición de completitud.
La
descomposición de una relación R en
los fragmentos R1, R2, ..., Rn es
completa si y solamente si cada elemento de datos en R se
encuentra en alguno de los fragmentos Ri.
- Condición de Reconstrucción.
La
descomposición de una relación R en
los fragmentos R1, R2, ..., Rn es
completa si y solamente si cada elemento de datos en R se
encuentra en alguno de los fragmentos Ri.
- Condición de Fragmentos Disjuntos.
Si
la relación R se
descompone en los fragmentos R1, R2, ..., Rn,
y el dato di está
en Rj,
entonces, no debe estar en ningún otro fragmento Rk (k?j).
Fragmentación
horizontal
La fragmentación
horizontal de
una relación R produce
una serie de fragmentos R1,
R2, ..., Rr,
cada uno de los cuales contiene un subconjunto de las tuplas de R que
cumplen determinadas propiedades (predicados)
Fragmentación
horizontal primaria y derivada
La Fragmentación
Horizontal Primaria (FHP) de
una relación se obtiene usando predicados que están definidos en
esa relación.
La Fragmentación
Horizontal Derivada (FHD)
por otra parte, es el particionamiento de una relación como
resultado de predicados que se definen en otra relación.
Fragmentación
vertical
La
fragmentación vertical de una relación R produce
una serie de fragmentos R1,
R2, ..., Rr cada
uno de los cuales contiene un subconjunto de los atributos de R así
como la clave primaria de R.
Complejidad
de la fragmentación Vertical
La
fragmentación vertical resulta más complicada que la horizontal. En
el caso vertical, si una relación tiene m atributos
clave no primarios, el número de posibles fragmentos es igual
a B(m),
es decir el m-ésimo número de Bell [3]. Para valores grandes
de m, B(m)(mm;
por ejemplo, para m =
10, B(m)
( 115.000, para m =
15, B(m)
( 109, para m =
30, B(m)
= 1023.
Estos
valores indican que la obtención de una solución óptima de la
fragmentación vertical resultará una tarea imposible, sino nos
apoyamos en el uso de heurísticas.
El
problema de la asignación de fragmentos
Asumamos
que hay un conjunto de fragmentos F =
{ F1, F2, ..., Fn }
y una
red que
consiste de los sitios S =
{ S1, S2, ..., Sm }
en los cuales un conjunto Q =
{ q1, q2, ..., qq }
de consultas se van a ejecutar.
El
problema de asignación consiste en determinar la
distribución "óptima" de F en S.
La
optimalidad puede ser definida de acuerdo a dos medidas:
- Costo mínimo. Consiste del costo de comunicación de datos, del costo de almacenamiento, y del costo procesamiento (lecturas y actualizaciones a cada fragmento). El problema de la asignación, es encontrar un esquema de asignación o ubicación que minimiza la función de costo combinada.
- Rendimiento: La estrategia de asignación se diseña para mantener una métrica de rendimiento. Las dos métricas más utilizadas son el tiempo de respuesta y el "throughput" (número de trabajos procesados por unidad de tiempo).
Asignación
de fragmentos
Asignación
Proceso
mediante el cual se decide donde se ubicaran los fragmentos de la
etapa anterior y si se harán replicas de los mismos.
Hacer
replicas tiene sentido por :
- Confiabilidad : Mayor seguridad ante perdida de datos
- Disponibilidad : Mayor tolerancia a fallos ante caídas de los computadores
- Aumento del paralelismo : Mayor eficiencia en las consultas de lectura al posibilitarse su descomposición en subconsultas y la paralelización de éstas.
Pero
presenta el inconvenientes de las consultas de escritura,
que conllevan las actualización de todas las copias de la red.
En
la práctica : Sopesar lecturas vs escrituras
- Mas lecturas que escrituras : Replicación es buena idea
- Mas escrituras que lecturas : No replicamos.
Según
el grado de replicación, distinguimos entre :
- BD fragmentada : Fragmentos disjuntos, cada uno en un nodo (no hay replicas)
- BD totalmente replicada : Se encuentra una copia de toda la BD en cada nodo
- BD parcialmente replicada : Mezcla las anteriores. Algunos fragmentos están replicados.
Como
se ve las técnicas de
fragmentación y replicación se combinan en la práctica.
Replicación
de fragmentos
El
problema de la replicación de segmentos asignación consiste en la
determinación de que fragmentos se replicarán en diferentes sitios
a pesar de los problemas que acarrea la actualización.
No hay comentarios:
Publicar un comentario