Algoritmo de partición.

El objetivo de la escisión consiste en encontrar conjuntos de atributos a los que se acceda conjuntamente, o a un gran número de ellos, por los distintos grupos de aplicaciones. Por ejemplo, si es posible identificar dos atributos, A1 y A2, a los que accede únicamente la aplicación q1, y unos atributos A3 y A4, a los que acceden dos aplicaciones q2 y q3, sería muy sencillo decidir qué fragmentos establecer. Por ello, es necesario encontrar un algoritmo que identifique estos grupos.

Considere la matriz de grupos afines de la figura 6. Si se fija un punto a lo largo de la diagonal, se pueden establecer dos conjuntos de atributos. Un conjunto {A1, A2, ..., Ai} situado en la esquina superior izquierda y un segundo conjunto {Ai+1, ..., An} en la parte inferior derecha de este punto. Denominaremos al primero de ellos el conjunto superior y al segundo el conjunto inferior y notaremos sus conjuntos de atributos como AS y AI, respectivamente.

Figura 6. Escisión de la matriz.

Detengámonos ahora en el conjunto de aplicaciones Q = {q1, q2, ..., qq} y definamos los conjuntos de aplicaciones que acceden solamente a AS o a AI, o a ambas. Estos conjuntos se definen como sigue:

La primera de estas ecuaciones define el conjunto de atributos a los que accede la aplicación qi; SQ e IQ son el conjunto de aplicaciones que sólo acceden a los conjuntos AS y AI, respectivamente, y XQ es el conjunto de aplicaciones que accede a ambos.

Nos encontramos ante un problema de optimización. Si hay n atributos en una relación, existen n - 1 posibles posiciones en las que situar el punto de división a lo largo de la diagonal, para producir los conjuntos SQ e IQ, tal que el acceso total a un único fragmento se maximice mientras que el acceso por las aplicaciones a varios fragmentos se minimice. Definiremos, por ello, las siguientes ecuaciones de coste:

Cada una de las ecuaciones cuenta el número total de accesos a los atributos por parte de cada aplicación para sus respectivas clases. Basándonos en esta medida, el problema de optimización se define encontrando el punto x (1 x n) tal que la expresión siguiente sea máxima:

La característica fundamental de esta expresión es que define dos fragmentos tales que los valores de CSQ y CIQ son tan próximos como sea posible. Esto permite el equilibrio de la carga de procesamiento cuando los fragmentos estén distribuidos entre varios sitios. Está claro que el algoritmo de partición tiene complejidad lineal con respecto al número de atributos de la relación, que es O(n).

Existen dos complicaciones que necesitan apuntarse. La primera es relativa a la escisión. Como el lector habrá podido percatarse, el procedimiento de escisión únicamente divide el conjunto de atributos de dos formas: generando el conjunto AS y el conjunto AI. En el caso que el conjunto de atributos sea grande, seguramente será necesario un método de partición que soporte n-formas de división. El diseño de este algoritmo es posible, pero computacionalmente costoso. A lo largo de la diagonal de la matriz MGA es necesario probar 1, 2, ..., n - 1 puntos de división y para cada uno de estos verificar el lugar que maximice a z. Por tanto, la complejidad del algoritmo alcanzaría un valor de O(2ⁿ). Sin embargo, puede llevarse a cabo una solución alternativa consistente en una llamada iterativa al algoritmo de fragmentación binaria para cada uno de los fragmentos obtenidos en la iteración previa. Esta solución cuyo coste computacional es de O(n³) se presenta más adelante.

La segunda complicación se refiere a la localización de un bloque de atributos que debería formar un fragmento. Nuestra discusión no va más allá de considerar que el punto de escisión es único y simple, y que divide a la matriz MGA en una partición superior izquierda y en una partición con el resto de los atributos. La partición, sin embargo, podría formarse en el medio de la matriz. En este caso, necesitamos modificar el algoritmo levemente. La columna más a la izquierda de la matriz MGA se desplaza para convertirse en la columna más a la derecha y la fila superior se desplaza para pasar a ser la inferior. A la operación de desplazamiento le sigue la verificación de las n - 1 posiciones de la diagonal para encontrar el máximo de z. La idea que esconde el desplazamiento consiste en mover el bloque de atributos que debería formar un grupo a la esquina superior izquierda, donde se identificará más fácilmente. Con el añadido de la operación de desplazamiento, la complejidad del algoritmo de partición se eleva en un factor n convirtiéndose en O(n²).

Asumiendo que el procedimiento de desplazamiento, denominado DESPLAZAR, ya se ha desarrollado, el algoritmo se presenta a continuación. La entrada del algoritmo PARTICIÓN[1] es la matriz de grupos afines y la relación R a fragmentar. La salida es el conjunto de fragmentos FR = {R1, R2}, donde Ri {A1, A2, ..., An} y R1 R2 = los atributos clave de R. Tenga en cuenta, que para el algoritmo de n-formas esta rutina debería invocarse iterativamente, o desarrollarse como procedimiento recursivo.

Ejemplo 14. Al aplicar el algoritmo PARTICIÓN sobre la matriz MGA obtenida para la relación CLIENTES se obtiene el grupo de fragmentos FCLIENTES = {CLIENTES1, CLIENTES2} donde CLIENTES1 = {A7, A5, A1} y CLIENTES2 = {A1, A2, A3, A8, A4, A6} teniendo en cuenta que se considera clave primaria a A1. Por lo tanto,

CLIENTES1 = {CPTLCLI, CPOBCLI, CLIENTES}
CLIENTES2 = {CLIENTES, CCODCLI, CNOMCLI, CDNICIF, CDIRCLI, NCODPROV}

Fragmentando relaciones grandes.

Se ha citado anteriormente la necesidad existente en muchos casos de fragmentar una relación en más de dos partes, especialmente si ésta es grande, contiene un número considerable de atributos. Existen dos alternativas para desarrollar el algoritmo de n-formas que haga esto posible. Por un lado podríamos modificar el algoritmo de partición para que llevase a cabo esta tarea, lo cual resultaría bastante complicado y, por otra, hacer uso de éste tal cual pero siendo la base del nuevo algoritmo, es decir, lo utilizaríamos iterativamente para fragmentar binariamente cada uno de los fragmentos que se generen en el paso anterior. La opción elegida es esta última.

El algoritmo [7] mostrado a continuación es bastante sencillo, sólo hay que tener en cuenta el número de grupos de fragmentación que se van generando.

Evidentemente el coste computacional de todo el proceso aumenta. Partiendo de que el coste del algoritmo PARTICIÓN es de O(n²), el coste añadido es el siguiente. En los pasos 2, 4, 5 y 6 es de O(1). En el paso 3 se necesita buscar el esquema de grupo de atributos actual para TF, es decir, el conjunto de fragmentos que representa la actual MGA. En otras palabras, TF = FS FI. Esta búsqueda puede llevar consigo como mucho n iteraciones dado que el tamaño del grupo de fragmentos actual no puede ser mayor que n, es decir, cada grupo en el grupo de fragmentos actual sólo puede contener un fragmento en él. Los pasos 7 y 8 se ejecutan como máximo n veces. Por todo ello, la complejidad del algoritmo n-formas se incrementa en un factor n a partir de la complejidad temporal de PARTICIÓN, entonces el coste total alcanza un valor de O(n³).

Ejemplo 15. Al emplear el algoritmo N-FORMAS sobre la relación clientes, se obtienen los siguientes esquemas de fragmentación . Observe como en cada paso se produce un fragmento más respecto al inmediato anterior. Debido a esta característica se dice que los esquemas de fragmentación generados son jerárquicos.

Dado que el método n-formas para una relación R que se desee fragmentar y que consta de m atributos, puede generar desde 2 hasta m fragmentos diferentes, es fácil preguntarse cuál de todos los esquemas generados es el mejor. Para responder a esto se va a proceder a estudiar en detalle el Examinador de Particiones (EP) [8], que no es más que una función de coste que determina el mejor esquema. Este punto muy relacionada con la fase de asignación se expone en siguientes apartados. Pero antes de ello, resulta necesario verificar la corrección del algoritmo de partición.

Comprobación de la corrección.

Emplearemos argumentos similares a los de la fragmentación horizontal para probar que el algoritmo de fragmentación vertital es correcto.

1. Compleción. La compleción se garantiza ya que cada atributo de la relación global se asigna a uno de los fragmentos. Independientemente del tamaño del conjunto de atributos A sobre el que se define la relación R, este está formado por A = AS AI, por lo que la compleción está asegurada.
2. Reconstrucción. Ya se ha mencionado que la reconstrucción de la relación es posible si se hace uso de la operación de yunto. Entonces, para una relación R con un conjunto de fragmentos verticales FR = {R1, R2, ..., Rr} y el atributo o los atributos clave K,

   

   Por tanto, dado que cada Ri es completo, la operación de yunto podrá reconstruir adecuadamente R. Otro punto importante es que cada Ri debería contener el o los atributos claves de R, o bien, albergar el identificador de tupla asignado por el sistema.

3. Disyunción. La disyunción de los fragmentos no es tan importante en la fragmentación vertical como en la horizontal. Existen dos casos:

1. Se usan identificadores de tuplas, en este caso los fragmentos son disjuntos ya que los identificadores que se replican en cada fragmento se asignan por el sistema y son totalmente invisibles al usuario.
2. Los atributos clave se replican en cada fragmento, en este caso no se puede decir que sean disjuntos en un sentido estricto. Sin embargo, es importante que esta duplicación de los atributos clave se conozca y gestione por el sistema. Resumiendo, los fragmentos son disjuntos excepto para los atributos clave.