Fragmentacion Vertical

Fragmentación Vertical usando el Algoritmo de Clustering (CA) y el Algoritmo de Energía Límite (Bond Energy Algorithm – BEA)
El objetivo de estos algoritmos es encontrar un término medio de agrupación de los atributos de una relación basándose en los valores de afinidad de los atributos contenidos en la Matriz de Afinidad. El algoritmo BEA se considera adecuado por varias razones:

• Sediseñó específicamente para determinar grupos de elementos similares frente a una ordenación lineal de los elementos (es decir, grupos de atributos con gran afinidad frente a grupos de atributos con valores pequeños de la misma)
• Los grupos resultantes no eran sensibles al orden en el cual los elementos se dispusieran por el algoritmo.
• El tiempo de cálculo del algoritmo es razonable,O (n2), donde n es el número de atributos.
• La interrelación secundaria entre grupos de atributos es identificable.

El algoritmo de energía límite toma como entrada la Matriz de Afinidad, intercambia columnas y genera una Matriz de Grupos Afines. La permutación o intercambio se hace de manera que se maximice la afinidad global.

En la matriz de grupos afines existen 2 columnasimaginarias: A0 y A(n+1), donde n es el número de atributos, llenas de ceros.

El proceso es el siguiente (partiendo de la Matriz de Afinidad):
1. Se colocan las 2 primeras columnas en la Matriz de Grupos Afines.
2. La tercer columna se puede colocar en diferentes ubicaciones:
a) A0 – A3 – A1 b) A1 – A3 – A2 c) A1 – A3 – A5

Considere:
o A3 siempre debe estar en medio de lasubicaciones posibles.
o No se considera A4 dado que aún no se ha colocado.

3. Se calculará la contribución cont (Ai, Ak, Aj), que es un valor para que 3 atributos vayan juntos. Si el valor es grande, los atributos deben ir juntos; si el valor es pequeño, los atributos deben ir separados. La contribución se calcula usando la siguiente fórmula:


cont (Ai, Ak, Aj) = 2 bond (Ai, Ak)+ 2 bond (Ak, Aj) – 2 bond (Ai, Aj) , donde
[pic]
si debe calcularse el bond de la columna 0 o n + 1, el bond del par vale 0.

bond(Ax, Ay) significa multiplicar las afinidades del mismo renglón entre las columnas x e y, y sumar los productos al final.

Para nuestro caso particular hay que considerar 3 contribuciones:

cont (A0, A3, A1) = 2 bond (A0,A3) + 2 bond (A3, A1) – 2 bond (A0, A1)
cont (A1, A3, A2) = 2 bond (A1, A3) + 2 bond (A3, A2) – 2 bond (A1, A2)
cont (A1, A3, A5) = 2 bond (A1, A3) + 2 bond (A3, A5) – 2 bond (A1, A5)
4. Se elige la contribución de mayor valor, la cual indicará el orden correcto de las columnas.


5. Se repiten los pasos 2 al 4 para las siguientes columnas hasta terminar de vaciar todas enla matriz global de agrupación.



6. Los fragmentos se realizarán tomando las columnas donde, al ir avanzando, no se encuentren ceros.

Ejercicio:

Se tiene la siguiente definición de tabla:
Proyecto (numProy, nombreProy, presupuesto, ubicacion)

Las siguientes aplicaciones:
q1 = Elegir el presupuesto de un proyecto conociendo su número.
q2 = Elegir el nombre ypresupuesto de todos los proyectos.
q3 = Elegir el nombre de un proyecto conociendo la ubicación.
q4 = Conocer el total de presupuestos de los proyectos de una ubicación específica.

Y la matriz de frecuencias de acceso:
| |S1 |S2 |S3 |Total de accesos |
|q1 |15 |20 |10 | |
|q2 |5 |0 |0 ||
|q3 |25 |25 |25 | |
|q4 |3 |0 |0 | |

Utilizar el CA y BEA para determinar de forma heurística los grupos de la fragmentación vertical.

Solución
Paso 1: Realizamos las consultas respectivas a cada aplicación
q1: Select presupuesto From Proyecto Where numProy = X
q2: Select nombreProy,...