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ágina15/36
fecha de publicación02.02.2016
tamaño0.75 Mb.
tipoDocumentos
b.se-todo.com > Economía > Documentos
1   ...   11   12   13   14   15   16   17   18   ...   36

3.8 FRAGMENTACION HIBRIDA



En muchos casos una fragmentación horizontal o vertical de un esquema de una base de datos no será suficiente para satisfacer los requerimientos de aplicaciones de usuario. En este caso, una fragmentación vertical puede ser seguida de uno horizontal, o viceversa, produciendo un árbol de particionamiento estructurado, como se muestra en la Figura 3.6. Ya que los dos tipos de particionamiento se aplican uno después del otro, esta alternativa se le conoce como fragmentación híbrida.


Figura 3.6. Fragmentación híbrida.

Un buen ejemplo de la necesidad de la fragmentación híbrida es la relación J, con la cual se ha trabajado. En la Figura 3.7 se muestra el árbol de reconstrucción de la fragmentación híbrida de J. Inicialmente se aplica una fragmentación horizontal y posteriormente una fragmentación vertical.


Figura 3.7. Fragmentación híbrida de la relación J.

 

3.9 ASIGNAMIENTO DE FRAGMENTOS



El asignamiento de recursos entre los nodos de una red de computadoras es un problema que se ha estudiado de manera extensa. Sin embargo, la mayoría de este trabajo no considera el problema de diseño de bases de datos distribuidas, en lugar de eso considera el problema de ubicar archivos individuales en redes de computadoras.

 

El problema de asignamiento



Suponga 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 de consultas Q = { q1, q2, ..., qq } se van a ejecutar. El problema de asignamiento determina la distribución "óptima" de F en S. La optimalidad puede ser definida de acuerdo a dos medidas:


  1. 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 asignamiento, entonces, pretende encontrar un esquema de asignmiento que minimiza una función de costo combinada.

  2. Rendimiento. La estrategia de asignamiento 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).

 

En cualquier problema de optimización existen restricciones que se deben satisfacer. El caso de distribución de fragmentos, las restricciones se establecen sobre las capacidades de almacenamiento y procesamiento de cada nodo en la red.

 

Requerimientos de información



En la fase de asignamiento 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 con respecto a una consulta qi, esto es, el número de tuplos de Fj que será 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:

size(Fj ) = card( Fj ) * length( 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 que consultas actualizan cuales fragmentos. Una matriz similar se necesita para indicar las lecturas de consultas a fragmentos. Finalmente, se necesita saber cual 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: la velocidad de comunicación, el tiempo de latencia en la comunicación y la cantidad de trabajo adicional a realizar para una comunicación.



Asignamiento de archivos vs. Asignamiento de fragmentos



En el diseño de bases de datos distribuidas no se puede considerar similar al problema de distribución de archivos por las siguientes razones:


  1. Los fragmentos no son archivos individuales. La colocación de un fragmento usualmente tiene un impacto en la colocación de otros fragmentos. Por lo tanto, es necesario mantener las relaciones entre fragmentos.

  2. El acceso a las bases de datos es más complicado que a archivos. Los modelos de acceso remoto a archivos no se aplican. Es necesario considerar las relaciones entre el asignamiento de fragmentos y el procesamiento de consultas.

  3. El costo que incurre el mantenimiento de la integridad de la información debe ser considerado en las bases de datos distribuidas.

  4. El costo que incurre el control de concurrencia a una base de datos distribuida también debe ser considerado.

 

Modelo de Asignamiento



Se discute ahora un modelo de asignamiento que 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á de ampliar las componentes de este modelo. Se define la variable de decisión xij de la siguiente manera:

 

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
STCjk = USCk * size( Fj ) * xjk
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
La componente de procesamiento involucra tres factores: el costo 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 esos 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. Sin embargo, éstos no se discutirán sino en los capítulos siguientes.
Respecto a la componente de transmisión, ésta 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 accesar solo 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 mas que un mensaje de confirmación, mientras que una consulta puede resultar una transmisión significativa de datos.
La componente de actualizaciones de la función de transmisión es

El primer término es por 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 confirmación. El costo de consulta 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 sólo considera de entre los nodos con copias del mismo fragmento, solo 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



Las funciones de restricción se pueden especificar con un detalle similar a la función de costo total. Sin embargo, en lugar de describir tales funciones con profundidad, se indicará simplemente cual es su forma general. La restricción del tiempo de respuesta se debe especificar como:
tiempo de ejecución de qi  máximo tiempo de respuesta de qi,  qiQ
La restricción de almacenamiento se puede especificar como:

La restricción del tiempo de procesamiento es:

 

Métodos de solución



Es sabido que el problema de asignamiento establecido como en el modelo discutido pertenece a la clase de problemas NP-completos. Por lo tanto, es necesario buscar métodos heurísticos que produzcan soluciones aproximadas. Diferentes heurísticas se han usado a la solución del modelo de asignamiento entre las cuales se pueden mencionar: la solución al problema de la valija (knapsack), técnicas tipo "branch-and-bound" y algoritmos para el flujo de redes.
Ha 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 asignamiento óptimos para cada relación. Otra simplificación frecuentemente empleada es ignorar inicialmente la replicación de datos y enconcontrar una solución óptima para el caso no replicado. La replicación se incorpora en un segundo paso el cual aplica un algoritmo ávido que inicia a partir de la solución no replicada y trata de mejorarla iterativamente.

CAPITULO 4

PROCESAMIENTO DE CONSULTAS DISTRIBUIDAS

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 no procedurales los cuales pueden mejorar significativamente el desarrollo de aplicaciones y la productividad del usuario final. 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 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.

1   ...   11   12   13   14   15   16   17   18   ...   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