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

3.7 FRAGMENTACION VERTICAL



Una fragmentación vertical de una relación R produce fragmentos R1, R2, ..., Rr, cada uno de los cuales contiene un subconjunto de los atributos de R así como la llave primaria de R. El objetivo de la fragmentación vertical es particionar una relación en un conjunto de relaciones más pequeñas de manera que varias de las aplicaciones de usuario se ejecutarán sobre un fragmento. En este contexto, una fragmentación "óptima" es aquella que produce un esquema de fragmentación que minimiza el tiempo de ejecución de las consultas de usuario.
La fragmentación vertical ha sido estudiada principalmente dentro del contexto de los sistemas de manejo de bases de datos centralizados como una herramienta de diseño, la cual permite que las consultas de usuario traten con relaciones más pequeñas haciendo, por tanto, un número menor de accesos a páginas.
La fragmentación vertical es inherentemente más complicada que particionamiento horizontal ya que existe un gran número de alternativas para realizarla. Por lo tanto, se utilizan heurísticas para hacer el particionamiento. Los dos enfoques básicos son:


  1. Agrupamiento. Inicia asignando cada atributo a un fragmento, y en cada paso, algunos de los fragmentos satisfaciendo algún criterio se unen para formar un solo fragmento.

  2. División. Inicia con una sola relación realizar un particionamiento basado en el comportamiento de acceso de las consultas sobre los atributos.


Nos concentraremos aquí al estudio del enfoque divisional ya que, por un lado, su aplicación es más natural al enfoque de diseño "top-down". Además, el enfoque divisional genera fragmentos que no se traslapan mientras que el agrupamiento típicamente resulta en fragmentos traslapados. Por supuesto, la no traslapación no incluye a las llaves primarias.

 

Requerimientos de información para la fragmentación vertical



Como en el caso de la fragmentación horizontal, es necesario proporcionar información para poder realizar una adecuada fragmentación vertical. Ya que el particionamiento vertical coloca en un fragmento aquellos atributos que se accesan juntos, se presenta la necesidad de una medida que relacione la afinidad de los atributos, la cual indica qué tan relacionados están los atributos. Esta medida se obtiene por datos primitivos.
Dado un conjunto de consultas Q = { q1, q2, ..., qq } que serán aplicadas a la relación R[A1, A2, ..., An], se define la función

Los vectores use( qi, ) son fáciles de definir si el diseñador conoce las aplicaciones que serán ejecutadas en la base de datos.

Ejemplo 3.14. Considere la relación J de la Figura 3.4. Suponga que las siguientes consultas se definen sobre esta relación:
q1: Encuentre el presupuesto de un proyecto dado su número de identificación.
SELECT PRESUPUESTO

FROM J

WHERE JNO=valor
q2: Encuentre los nombres y presupuestos de todos los proyectos.
SELECT JNOMBRE, PRESUPUESTO

FROM J
q3: Encuentre los nombres de los proyectos en una ciudad dada.
SELECT JNOMBRE

FROM J

WHERE LUGAR=valor
q4: Encuentre el presupuesto total de los proyectos en cada ciudad.
SELECT SUM(PRESUPUESTO)

FROM J

WHERE LUGAR=valor
Sean A1=JNO, A2=JNOMBRE, A3=PRESUPUESTO, A4=LUGAR. La función use se puede representar por la siguiente matriz:




La medida de afinidad entre dos atributos Ai y Aj de una relación R[A1, A2, ..., An] con respecto al conjunto de consultas Q = { q1, q2, ..., qq } se define como sigue:
aff(Ai,Aj) =  las consultas que accesan Ai y A Sl (refl(qk) accl(qk))
donde, refl(qk) es el número de accesos a los atributos (Ai, Aj) para cada ejecución de la consulta qk en el sitio Sl y accl(qk) es la frecuencia de acceso de la consulta previamente definida y modificada para incluir las frecuencias en sitios diferentes.

Ejemplo 3.15. Continuando con el ejemplo 3.14, suponga que cada consulta en dicho ejemplo accesa los atributos una vez durante cada ejecución (refl(qk) = 1):
Las frecuencias de acceso de las consultas están dadas por:

La afinidad de los atributos A1 y A3 se puede medir como

ya que la única aplicación que accesa ambos atributos es q1. La matriz de afinidades entre atributos, AA, es




Algoritmo de Agrupamiento (Clustering)



La tarea fundamental en el diseño de una fragmentación vertical es encontrar algún medio para agrupar los atributos de una relación basándose en los valores de afinidad entre atributos. La idea del algoritmo de agrupamiento es tomar la matriz de afinidades entre atributos (AA) y reorganizar el orden de los atributos para formar grupos en donde los atributos dentro de cada grupo presentan alta afinidad uno con otro.
El algoritmo de energía acotada (BEA por sus siglas en inglés) encuentra un ordenamiento de los atributos, de tal manera, que se maximiza la siguiente medida de afinidad global (AM):

donde,

Algoritmo 3.3 BEA
Entrada: La matriz de afinidades entre atributos AA.

Salida: La matriz de afinidades agrupada, CA, la cual es una perturbación de AA.

Iniciación: Coloque y fije una de las columnas de AA en CA.

Iteración: Coloque las restantes n-i columnas en las restantes i+1 posiciones en la matriz CA. Para cada columna, elija la ubicación que causa la mayor contribución a la medida de afinidad global.

Ordenamiento de renglones: Ordene los renglones de acuerdo al ordenamiento de columnas.
Para definir la mejor ubicación se define la contribución de una ubicación.

donde,



Ejemplo 3.16. Considere la siguiente matriz AA y la matriz correspondiente CA en donde A1 y A2 han sido colocados.

Al colocar A3 existen tres posibilidades:


  • Ordenamiento(0-3-1):





  • Ordenamiento(1-3-2):





  • Ordenamiento(2-3-4):



Por lo tanto, la matriz CA tiene la forma:

Cuando A4 es colocado, se obtiene la forma final de la matriz CA (después de la reorganización entre renglones):



Algoritmo de Particionamiento
El objetivo del particionamiento es encontrar conjuntos de atributos que son accesados de manera única, o a lo más, por conjuntos disjuntos de consultas. Considere la matriz de atributos agrupada de la Figura 3.5. Si se fija un punto a lo largo de la diagonal, se identifican dos conjuntos de atributos. Un conjunto es {A1, …, Ai} está en la esquina superior izquierda y el segundo conjunto {Ai+1, …, An} está en la esquina inferior derecha. Al primer conjunto se le llama arriba y al segundo conjunto se le denomina abajo.
Considere ahora el conjunto de consultas Q = { q1, q2, ..., qq } y defina el conjunto de aplicaciones que accesan únicamente a TA, a BA, o ambas. Defina


Figura 3.5. Localización del punto de división.

Considere ahora el conjunto de consultas Q = { q1, q2, ..., qq } y defina el conjunto de aplicaciones que accesan únicamente a TA, a BA, o ambas. Defina
TQ = conjunto de aplicaciones que accesan únicamente a TA

BQ = conjunto de aplicaciones que accesan únicamente a BA

OQ = conjunto de aplicaciones que accesan tanto a TA como a BA

CTQ = número total de accesos a atributos por aplicaciones que accesan únicamente a TA

CBQ = número total de accesos a atributos por aplicaciones que accesan únicamente a BA

COQ = número total de accesos a atributos por aplicaciones que accesan únicamente tanto a TA como a BA
El problema es encontrar el punto a lo largo de la diagonal que maximiza la función objetivo
z = CTQ * CBQ - COQ2
La característica importante de esta expresión es que define dos fragmentos tales que los valores de CTQ y CBQ son tan similares como sea posible. Esto nos permite balancear las cargas de procesamiento cuando los fragmentos están distribuidos en varios sitios.
Existen dos complicaciones que tienen que ser consideradas:


  1. El particionamiento puede ser formado en la parte media de la matriz CA. Aquí se debe aplicar un corrimiento circular de un renglón hacia arriba y una columna hacia la izquierda para encontrar el mejor punto de particionamiento. Si esto se realiza para todos los posibles corrimientos el algoritmo tomaría O(n2) pasos.

  2. Es posible que se formen más de dos grupos. Aquí la estrategia sería tratan con 1, 2, …, n-1 puntos a lo largo de la diagonal y tratar de hallar el mejor punto de particionamiento para cada uno de ellos. Claramente, este algoritmo tomaría entonces O(2n) pasos.

 

Ejemplo 3.17. Cuando el algoritmo de particionamiento se aplica a la matriz CA para la relación J, el resultado es la definición de los fragmentos FJ = { J1, J2 }, donde J1 = {A1, A3} y J2 = {A1, A2, A4}. Así
J1 = { JNO, PRESUPUESTO }

J2 = { JNO, JNOMBRE, LUGAR }



Correctitud de la Fragmentación Vertical





  • Completitud. La completitud de una fragmentación vertical es garantizada por el algoritmo de particionamiento. Ya que cada atributo de la relación global se asigna a uno de los fragmentos. Siempre y cuando el conjunto de atributos A sobre los cuales se define una relación R consiste de

A = TA  TB

la completitud de la fragmentación vertical se asegura.

  • Reconstrucción. La reconstrucción de la relación global original se hace por medio de la operación de junta. Así, para una relación R con fragmentación vertical FR = { R1, R2, ..., Rr } y llave K

R =  K Ri RiFR

Por lo tanto, siempre que Ri sea completo, la operación de junto reconstruirá adecuadamente R. Otro punto importante es que o cada Ri debe contener a la llave de R, o debe contener los identificadores de tuplo asignados por el sistema (TID).

  • Fragmentos Disjuntos. Existen dos casos:

  1. Los TID no se considera que se traslapan ya que ellos son mantenidos por el sistema.

  2. Las llaves duplicadas no se considera que se traslapan.

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