En el presente capítulo se mostrará los aspectos importantes referentes al diseño de una base de datos distribuida. Se revisará el problema de fragmentación de los datos así como la transparencia que un sistema de datos distribuidos debe guardar respecto a la vista del usuario. Se presentarán los algoritmos para fragmentación horizontal, fragmentación horizontal derivada y fragmentación vertical. En la parte final de este capítulo se discute el problema de asignamiento de fragmentos. 3.1 El problema de diseño El problema de diseño de bases de datos distribuidos se refiere, en general, a hacer decisiones acerca de la ubicación de datos y programas a través de los diferentes sitios de una red de computadoras. Este problema debería estar relacionado al diseño de la misma red de computadoras. Sin embargo, en estas notas únicamente el diseño de la base de datos se toma en cuenta. La decisión de donde colocar a las aplicaciones tiene que ver tanto con el software del SMBDD como con las aplicaciones que se van a ejecutar sobre la base de datos. El diseño de las bases de datos centralizadas contempla los dos puntos siguientes: 1. Diseño del "esquema conceptual" el cual describe la base de datos integrada (esto es, todos los datos que son utilizados por las aplicaciones que tienen acceso a las bases de datos). 2. Diseño "físico de la base de datos", esto es, mapear el esquema conceptual a las áreas de almacenamiento y determinar los métodos de acceso a las bases de datos. En el caso de las bases de datos distribuidas se tienen que considerar los dos problemas siguientes: 3. Diseño de la fragmentación, este se determina por la forma en que las relaciones globales se subdividen en fragmentos horizontales, verticales o mixtos. 4. Diseño de la asignación de los fragmentos, esto se determina en la forma en que los fragmentos se mapean a las imágenes físicas, en esta forma, también se determina la solicitud de fragmentos.
Objetivos del Diseño de la Distribución de los Datos. En el diseño de la distribución de los datos, se deben de tomar en cuenta los siguientes objetivos:
3.2 Enfoques al problema de diseño de bases de datos
distribuidas
Figura 3.1. El enfoque top-down para el diseño de bases de datos distribuidas. El diseño de una base de datos distribuida, cualquiera sea el enfoque que se siga, debe responder satisfactoriamente las siguientes preguntas:
Figura 3.2. El problema de fragmentación de relaciones. 3.3 El problema de 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, como se observa en la Figura 3.2. Inmediatamente aparece la siguiente pregunta: ¿cuál es la unidad razonable de distribución?. Se puede considerar que una relación completa es lo adecuado ya que las vistas de usuario son subconjuntos de las relaciones. Sin embargo, el uso completo de relaciones no favorece las cuestiones de eficiencia sobre todo aquellas relacionadas con el procesamiento de consultas. La otra posibilidad es usar fragmentos de relaciones (sub-relaciones) lo cual favorece la ejecución concurrente de varias transacciones que accesan porciones diferentes de una relación. Sin embargo, el uso de sub-relaciones también presenta inconvenientes. Por ejemplo, las vistas de usuario que no se pueden definir sobre un solo fragmento necesitarán un procesamiento adicional a fin de localizar todos los fragmentos de una vista. Aunado a esto, el control semántico de datos es mucho más complejo ya que, por ejemplo, el manejo de llaves únicas requiere considerar todos los fragmentos en los que se distribuyen todos los registros de la relación. En resumen, el objetivo de la fragmentación es encontrar un nivel de particionamiento adecuado en el rango que va desde tuplas o atributos hasta relaciones completas (ver Figura 3.3). Ejemplo 3.1. Considere la relación J del ejemplo visto en el capítulo 2. J:
La relación J se puede fragmentar horizontalmente produciendo los siguientes fragmentos. J1: proyectos con presupuesto menor que $200,000
J2: proyectos con presupuesto mayor que o igual a $200,000
¨ Ejemplo 3.2. La relación J del ejemplo anterior se puede fragmentar verticalmente produciendo los siguientes fragmentos: J1: información acerca de presupuestos de proyectos
J2: información acerca de los nombres y ubicaciones de proyectos
¨ Figura 3.3. El grado de fragmentación. Correctitud de una fragmentaciónAl realizar la fragmentación de una relación se deben satisfacer las siguientes condiciones para garantizar la correctitud de la misma:
Alternativas sobre replicación para el asignamiento de fragmentos La replicación de información es de utilidad para obtener un mejor rendimiento y para ofrecer un mayor grado de confiabilidad (tolerancia a fallas). La replicación se complica cuando es necesario hacer actualizaciones a las copias múltiples de un dato. Por tanto, respecto a la replicación, en el asignamiento de fragmentos se tienen tres estrategias:
Como regla general se debe considerar que la replicación de fragmentos es de utilidad cuando el número de consultas de solo lectura es (mucho) mayor que el número de consultas para actualizaciones. En la Tabla 3.1 se comparan la complejidad de implementar o tomar ventaja de las diferentes alternativas de replicación, respecto de los diferentes aspectos importantes en bases de datos distribuidas.
Tabla 3.1. Comparación de las estrategias de replicación de fragmentos.
Requerimientos de información Con el fin de realizar una fragmentación adecuada es necesario proporcionar información que ayude a realizarla. Esta información normalmente debe ser proporcionada por el usuario y tiene que ver con cuatro tipos:
3.4. Tipos de fragmentación de datos Existen tres tipos de fragmentación:
En las siguientes secciones revisaremos de manera informal cada uno de los tipos mencionados. Más adelante, se presentará de manera más formal la construcción de los diferentes tipos de fragmentación.
3.4.1 Fragmentación horizontal primaria Consiste del particionamiento en tuplas de una relación global en subconjuntos, donde cada subconjunto puede contener datos que tienen propiedades comunes y se puede definir expresando cada fragmento como una operación de selección sobre la relación global. Ejemplo 3.3. Considere la relación global SUPPLIER( SNUM, NAME, CITY ) entonces, la fragmentación horizontal puede ser definida como: SUPPLIER1 = SLcity == "SF"SUPPLIER SUPPLIER1 = SLcity == "LA"SUPPLIER
2. La condición de reconstrucción se logra con: SUPPLIER = SUPPLIER1 union SUPPLIER2 3. La condición de disjuntos se cumple claramente en este ejemplo. ¨ 3.4.2 Fragmentación horizontal derivada La fragmentación derivada horizontal se define partiendo de una fragmentación horizontal. En esta operación se requiere de Semi-junta (Semi-Join) el cual nos sirve para derivar las tuplas o registros de dos relaciones. Ejemplo 3.4. Las siguientes relaciones definen una fragmentación horizontal derivada de la relación SUPPLY. SUPPLY1 = SUPPLYSJsnum == snumSUPPLIER1 SUPPLY2 = SUPPLYSJsnum == snumSUPPLIER2 ¨ 3.4.3 Fragmentación vertical La fragmentación vertical es la subdivisión de atributos en grupos. Los fragmentos se obtienen proyectando la relación global sobre cada grupo. La fragmentación es correcta si cada atributo se mapea en al menos un atributo del fragmento. Ejemplo 3.5. Considere la siguiente relación global: EMP( empnum, name, sal, tax, mgrnum, depnum ) una fragmentación vertical de esta relación puede ser definida como: EMP1 = PJempnum, name, mgrnum, depnum EMP EMP2 = PJempnum, sal, tax EMP la reconstrucción de la relación EMP puede ser obtenida como: EMP = EMP1 (JN empnum) EMP2 porque empnum es una clave de EMP ¨ 3.4.4 Fragmentación híbrida En la que respecto a la fragmentación híbrida, esta consiste en aplicar la fragmentación vertical seguida de la fragmentación horizontal o viceversa. Ejemplo 3.6. Considere la relación global EMP( empnum, name, sal, tax, mrgnum, depnum ) Las siguientes son para obtener una fragmentación mixta, aplicando la vertical seguida de la horizontal: EMP1 = SL depnum <= 10 PJempnum, name, mgrnum, depnum EMP EMP2 = SL 10 < depnum <= 20 PJempnum, name, mgrnum, depnum EMP EMP3 = SL depnum > 20 PJempnum, name, mgrnum, depnum EMP EMP4 = PJ empnum, name, sal, tax EMP La reconstrucción de la relación EMP es definida por la siguiente expresión: EMP = UN(EMP1, EMP2, EMP3)JNempnum = empnumPJempnum, sal, tax EMP4 Finalmente, como otro ejemplo considere el siguiente esquema global EMP(EMPNUM, NAME, SAL, TAX, MGRNUM, DEPNUM) DEP(DEPNUM, NAME, AREA, MGRNUM) SUPPLIER(SNUM, NAME, CITY) SUPPLY(SNUM, PNUM, DEPNUM, QUAN) Después de aplicar una fragmentación mixta se obtiene el siguiente esquema fragmentado EMP1 = Sldepnum <= 10 PJempnum, name, mgrnum, depnum (EMP) EMP2 = SL 10 < depnum <= 20 PJempnum, name, mgrnum, depnum (EMP) EMP3 = SL depnum > 20 PJempnum, name, mgrnum, depnum (EMP) EMP4 = PJ empnum, name, sal, tax (EMP) DEP1 = SL depnum <= 10 (DEP) DEP2 = SL 10 < depnum <= 20 (DEP) DEP3 = SL depnum > 20 (DEP) SUPPLIER1 = SL city == "SF" (SUPPLIER) SUPPLIER2 = SL city == "LA" (SUPPLIER) SUPPLY1 = SUPPLYSJsnum == snumSUPPLIER1 SUPPLY2 = SUPPLYSJsnum == snumSUPPLIER2 ¨ 3.5 Fragmentación horizontal En las siguientes secciones revisaremos de manera más formal la forma de construir los diferentes tipos de fragmentación. La fragmentación horizontal primaria de una relación se obtiene usando predicados que están definidos en esa relación. La fragmentación horizontal derivada, por otra parte, es el particionamiento de una relación como resultado de predicados que se definen en otra relación. Para poder construir una fragmentación, es necesario proporcionar información acerca de la base de datos y acerca de las aplicaciones que las utilizan. En primer término, es necesario proporcionar la información acerca del esquema conceptual global. En este sentido es importante dar información acerca de las relaciones que componen a la base de datos, la cardinalidad de cada relación y las dependencias entre relaciones. Por ejemplo, en la Figura 3.4 se presenta un diagrama mostrando el esquema conceptual de la base de datos de ejemplo del capítulo 2. En segundo lugar se debe proporcionar información acerca de la aplicación que utiliza la base de datos. Este tipo de información es cuantitativa y consiste de los predicados usados en las consultas de usuario. Figura 3.4. Esquema conceptual de la base de datos de ejemplo del capítulo 2.
Dada una relación R( A1, A2, …, An), donde Ai es un atributo definido sobre el dominio Di, un predicado simple pj definido en R tiene la forma pj: Ai q Valor donde q Î { =, <, ¹ , £ , >, ³ } y Valor Î Di. Para la relación R se define un conjunto de predicados simples como Pr = { p1, p2, …, pm }. Ejemplo 3.7. Las siguientes expresiones se consideran como predicados simples. JNOMBRE = "Mantenimiento" PRESUPUESO < 200000 ¨ Dado la relación R y el conjunto de predicados simples Pr = { p1, p2, …, pm }, se define el conjunto de predicados minitérmino como M = { m1, m2, …, mr } como M = { mi | mi = Ù pj Î Pr pj*}, 1 £ j £ m, 1 £ i £ z donde, pj* = pj o pj* = Ø (pj). Ejemplo 3.8. Los siguientes son minitérminos de la relación J. m1: JNOMBRE == "Mantenimiento" Ù Presupuesto £ 200000 m2: NOT( JNOMBRE == "Mantenimiento") Ù Presupuesto £ 200000 m3: JNOMBRE == "Mantenimiento" Ù NOT (Presupuesto £ 200000) m4: NOT( JNOMBRE == "Mantenimiento") Ù NOT(Presupuesto £ 200000) ¨ En términos de la información cuantitativa acerca de las aplicaciones de usuario, se necesita tener dos conjuntos de datos:
Una fragmentación horizontal primaria se define por una operación de selección en las relaciones propietarias de un esquema de la base de datos. Por tanto, dada una relación R, su fragmentación horizontal está dada por Rj = s Fj (R), 1 £ j £ w donde, Fj es una fórmula de selección, la cual es preferiblemente un predicado minitérmino. Por lo tanto, un fragmento horizontal Ri de una relación R consiste de todos los tuplos de R que satisfacen un predicado minitérmino mi. Lo anterior implica que dado un conjunto de predicados minitérmino M, existen tantos fragmentos horizontales de R como minitérminos existan. El conjunto de fragmentos horizontales también se entiende como los fragmentos minitérminos. Es necesario desarrollar un algoritmo que tome como entrada una relación R y el conjunto de predicados simples Pr y proporcione como resultado el conjunto de fragmentos de R = { R1, R2, …, Rm } el cual obedece las reglas de fragmentación. Un aspecto importante del conjunto de predicados es que debe ser completo y minimal. Un conjunto de predicados simples Pr se dice que es completo si y solo si los accesos a los tuplos de los fragmentos minitérminos definidos en Pr requieren que dos tuplos del mismo fragmento tengan la misma probabilidad de ser accesados por cualquier aplicación. Ejemplo 3.9 Considere que la relación J[JNO, JNOMBRE, PRESUPUESTO, LUGAR] tiene dos consultas definidas en ella: Encontrar todos los presupuestos de los proyectos en cada lugar (1) Encontrar proyectos con presupuestos menores a $200000. (2) De acuerdo a (1), Pr = { LUGAR = "México", LUGAR = "Puebla", LUGAR = "Guadalajara", LUGAR = "Monterrrey" } no es completa con respecto a (2) dado que algunos de los tuplos dentro de cada Ji tienen una probabilidad mayor de ser accesados por la segunda consulta. Si se modifica Pr como Pr = { LUGAR = "México", LUGAR = "Puebla", LUGAR = "Guadalajara", LUGAR = "Monterrrey", PRESUPUESTO £ 2000000, PRESUPUESTO > 200000 } entonces, Pr es completo. ¨ De manera intuitiva se puede ver que si un predicado influye en la fragmentación, esto es, causa que un fragmento f se fragmente aún más digamos en fi y fj, entonces habría una consulta que accese fi y fj de manera diferente. En otras palabras, un predicado debe ser relevante en determinar una fragmentación. Si todos los predicados de un conjunto Pr son relevantes, entonces Pr es mínimo. La definición formal de relevancia es la siguiente. Sean mi y mj dos predicados minitérminos definidos exactamente igual excepto que mi contiene a pi y mj contiene a pj. También, sean fi y fj los dos fragmentos definidos de acuerdo a mi y mj, respectivamente. Entonces, pi es relevante si y solo si acc(mi)/card(fi) ¹ acc(mj)/card(fj) Por ejemplo, el conjunto Pr definido arriba es mínimo y completo. Sin embargo, si se le agrega el predicado JNOMBRE = "Instrumentación", entonces, Pr no es mínimo. El algoritmo siguiente llamado COM_MIN genera un conjunto completo y mínimo de predicados Pr’ dado un conjunto de predicados simple Pr. Por brevedad durante el algoritmo se utiliza la siguiente regla: Regla 1: regla fundamental de completes y minimalidad, la cual afirma que una relación o fragmento es particionado en al menos dos partes las cuales se accesan en forma diferente por al menos una consulta de usuario.
Algoritmo 3.1 COM_MIN Entrada: una relación R y un conjunto de predicados simples Pr Salida: un conjunto completo y mínimo de predicados simples Pr’ para Pr.
Hacer Pr’ = Pr’ - pk; F ¬ F - fk El algoritmo empieza encontrando un predicado que es relevante y que particiona la relación de entrada. Después, agrega de manera iterativa predicados a este conjunto, asegurando minimalidad en cada paso. Por lo tanto, al final el conjunto Pr’ es tanto completo como mínimo. El segundo paso en el proceso de diseño de fragmentación horizontal primaria es derivar el conjunto de predicados minitérminos que pueden ser definidos en los predicados del conjunto Pr’. Esos minitérminos definen los fragmentos que serán usados como candidatos en el paso de asignamiento. El algoritmo de fragmentación horizontal primaria, llamado PHORIZONTAL, se presenta a continuación. La entrada al algoritmo es una relación Ri la cual es sometida a fragmentación horizontal primaria, y Pri, el cual es el conjunto de predicados simples que han sido determinados de acuerdo a las consultas definidas en la relación Ri. Algoritmo 3.2 PHORIZONTAL Entrada: Una relación R y un conjunto de predicados simples Pr. Salida: Un conjunto de predicados minitérminos, M, de acuerdo a los cuales la relación R será fragmentada.
Ejemplo 3.10. Para la relación S la consulta o aplicación es verificar la información del salario y determinar incrementos. Suponga además que los registros de empleados se mantienen en dos lugares y, por tanto, la aplicación o consulta se ejecuta en dos lugares. Los predicados simples que serían usados para particionar la relación S son: p1 : SAL £ 30000 p2 : SAL > 30000 Al aplicar el algoritmo COM_MIN se verifica que Pr = { P1, P2 } se completo y minimal, Pr’ = Pr. Se pueden formar los siguientes predicados minitérminos como miembros de M: m1: (SAL £ 30000) Ù (SAL > 30000) m2: (SAL £ 30000) Ù NOT (SAL > 30000) m3: NOT (SAL £ 30000) Ù (SAL > 30000) m4: NOT (SAL £ 30000) Ù NOT (SAL > 30000) Asumiendo que el dominio de SALARIO se puede partir en dos, como se sugiere Pr p1 y p2, las siguientes implicaciones son obvias: i1: (SAL £ 30000) Þ NOT (SAL > 30000) i2: NOT (SAL £ 30000) Þ (SAL > 30000) i3: (SAL > 30000) Þ NOT (SAL £ 30000) i4: NOT (SAL > 30000) Þ (SAL £ 30000) De acuerdo a i1, m1 es contradictorio; de acuerdo a i2, m4 es contradictorio. Por lo tanto, nos quedamos con M = { m2, m3 }. Por tanto, se definen los dos fragmentos Fs = { S1, S2 } de acuerdo a M. S1
S1
¨ Ejemplo 3.11. Para la relación J la consulta es encontrar el nombre y presupuesto de proyectos dados por su número. Esta consulta es realizada en tres lugares. El acceso a la información de proyecto se realiza de acuerdo a su presupuesto; un lugar accesa presupuesto £ 200000 y el otro accesa presupuesto > 200000. Los predicados simples para la primera consulta serían: p1 : LUGAR = "México" p2 : LUGAR = "Monterrey" p3 : LUGAR = "Puebla" Los predicados simples para la segunda consulta serían: p4 : PRESUPUESTO £ 200000 p5 : PRESUPUESTO > 200000 Si el algoritmo COM_MIN es seguido, el conjunto Pr’ = {p1, p2, p3, p4, p5} es obviamente completo y mínimo. Basado en Pr’, los siguientes seis minitérminos que forman a M se pueden definir como: m1: (LUGAR = "México") Ù (PRESUPUESTO £ 200000) m2: (LUGAR = "México") Ù (PRESUPUESTO > 200000) m3: (LUGAR = "Monterrey") Ù (PRESUPUESTO £ 200000) m4: (LUGAR = "Monterrey") Ù (PRESUPUESTO > 200000) m5: (LUGAR = "Puebla") Ù (PRESUPUESTO £ 200000) m6: (LUGAR = "Puebla") Ù (PRESUPUESTO > 200000) Estos no son los únicos minitérminos que se pueden generar. Por ejemplo, es posible especificar predicados de la forma: p1 Ù p2 Ù p3 Ù p4 Ù p5 Sin embargo, las implicaciones obvias: i1: p1 Þ Ø p2 Ù Ø p3 i2: p2 Þ Ø p1 Ù Ø p3 i3: p3 Þ Ø p1 Ù Ø p2 i4: p4 Þ Ø p5 i5: p5 Þ Ø p4 i6: Ø p4 Þ p5 i7: Ø p5 Þ p4 eliminan esos minitérminos y nos quedamos con m1 hasta m6. Observando la instancia de la base de datos del ejemplo, podríamos decir que las siguientes implicaciones se mantienen: i1: (LUGAR = "México") Ù NOT (PRESUPUESTO > 200000) i2: (LUGAR = "Monterrey") Ù NOT (PRESUPUESTO £ 200000) i3: NOT (LUGAR = "México") Ù (PRESUPUESTO £ 200000) i4: NOT (LUGAR = "Monterrey") Ù (PRESUPUESTO > 200000) Sin embargo, recuerde que las implicaciones deben ser definidas de acuerdo a la semántica de la base de datos, no de acuerdo a los valores actuales. Algunos de los fragmentos definidos por M = { m1, m2, m3, m4, m5, m6 } pueden estar vacíos, pero ellos son, no obstante, fragmentos. No existe nada en la semántica de la base de datos que sugiera que las implicaciones i8 hasta i11 se satisfagan. Los resultados de la fragmentación horizontal primaria de J forman seis fragmentos FJ = { J1, J2, J3, J4, J5, J6 } de acuerdo a los minitérminos de M. Algunos de esos están vacíos y por lo tanto no se presentan aquí. J1
J3
J4
J6
¨ Correctitud de la Fragmentación Horizontal Primaria
R = U " Ri Î FR Ri
3.6 Fragmentación horizontal derivada Una fragmentación horizontal derivada se define en la relación miembro de una liga de acuerdo a la operación de selección especificada en la relación propietaria. La liga entre las relaciones propietaria y miembro se define como una equi-junta. Una equi-junta se puede implementar por semi-juntas. Esto es importante, ya que se quiere particionar una relación miembro de acuerdo a la fragmentación de su propietario, pero se quiere que los fragmentos resultantes queden definidos únicamente en los atributos de la relación miembro. Dada una liga L donde owner( L ) = S y member( L ) = R, las fragmentos horizontal derivados de R se definen como: Ri = R> p F Si, 1 £ i £ w donde w es el número máximo de fragmentos que serán definidos en R y Si = s Fi ( S ) donde Fi es la fórmula de acuerdo a la cual la fragmentación horizontal primaria Si se define. Ejemplo 3.12. Dada la liga L1 donde owner( L1 ) = S y member( L1 ) = E. Se pueden agrupar a los ingenieros en dos grupos con base en su salario; aquellos que perciben menos de 30000 y aquellos que ganan mas de 30000. Los fragmentos E1 y E2 se definen como sigue E1 = E > p S1 E2 = E > p S2 donde S1 = s SAL £ 30000 (S) S2 = s SAL > 30000 (S) Así, el resultado de la fragmentación se presenta en las siguientes tablas
E1
E2
¨ Para llevar a cabo una fragmentación horizontal derivada se requieren tres entradas: el conjunto de particiones de la relación propietaria, la relación miembro, y el conjunto de predicados semi-junta entre el propietario y el miembro. El algoritmo de fragmentación es trivial y no será presentado aquí. Correctitud de la Fragmentación Horizontal Derivada
La completitud de una fragmentación horizontal derivada es un poco más difícil de definir. La dificultad se debe al hecho de que los predicados que determinan la fragmentación involucran a dos relaciones. Sea R la relación miembro de una liga cuyo propietario es la relación S, la cual es fragmentada por FS = { S1, S2, ..., Sw }. Además, sea A el atributo de junta entre R y S. Entonces, por cada tupo t en R, debe haber un tuplo t’ en S tal que t[A] = t’[A] A esta regla se le conoce como integridad referencial y asegura que los tuplos de cualquier fragmento de la relación miembro están también en la relación propietaria.
R = U Ri " Ri Î FR
Ejemplo 3.13. En el ejemplo anterior los minitérminos predicados son m1: (SAL £ 30000) m2: (SAL > 30000) Ya que m1 y m2 son mutuamente exclusivos, la fragmentación de S es disjunta. Para la relación E, sin embargo, se requiere que
Puesto que esas dos reglas se siguen de la semántica de la base de datos, la fragmentación de E con respecto a S es disjunta. ¨ 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:
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) = S las consultas que accesan Ai y Aj S 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:
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:
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
A = TA U TB la completitud de la fragmentación vertical se asegura.
R = > < K Ri " Ri Î FR 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).
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:
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.
size(Fj ) = card( Fj ) * length( Fj )
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:
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, " qi Î Q 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. 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:
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.
size(Fj ) = card( Fj ) * length( Fj )
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:
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, " qi Î Q 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. |