• Author / Uploaded
• Elliot Leon Galicia

Citation preview

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

BASES DE DATOS DISTRIBUIDAS (BDD)

Fragmentación Fragmentación es la descomposición o partición de una tabla en pedazos llamados fragmentos. La fragmentación básicamente se puede hacer de dos formas: Fragmentación Horizontal. Selecciona registros completos de una relación Fragmentación Vertical. Selecciona columnas completas de una relación

Reglas a Cumplir por Fragmentación Condición de Completes o Todos los datos de la relación global deberán ser mapeados a algún fragmento Condición de Reconstrucción. o Deberá ser siempre posible reconstruir la relación global a partir de sus fragmentos. Condición de Conjuntos Disjuntos. o Es conveniente que los fragmentos sean disjuntos.

Fragmentación Horizontal Definir fragmentos horizontales se hace a través del operador de selección del algebra relacional operando sobre una relación global. Supplier SNUM S1 S2 S3 S4 S5

NOM X Y Z A B

FH1

CD L L P P L

Una posible fragmentación horizontal de esta tabla sería: FH1 = P WHERE CD=’L’ FH2 = P WHERE CD=’P’

SNUM S1 S2 S5

FH2

NOM X Y B

CD L L L

SNUM NOM CD S3 Z P S4 A P

Los predicados que permiten definir una fragmentación de una relación son llamados la calificación de la fragmentación. En el ejemplo la calificación de la fragmentación hecha a Supplier, son: q1 : CD = ‘L’ q2 : CD = ‘P’ En general una fragmentación horizontal es correcta, si cumple que: El conjunto de calificaciones mapea todo el dominio del atributo(s) bajo el cual se hace la calificación. Si siempre es posible reconstruir la tabla global por medio del operador UNION del algebra relaciónal: R = F1 UNION F2 UNION …UNION Fn Ejemplo > Create table emp_f select * from empleado where sexo="f"; > Create table emp_m select * from empleado where sexo="m"; > select * from emp_f union select * from emp_m; Si todas las calificaciones de los fragmentos son mutuamente exclusivas, es decir, si al aplicar las calificaciones se producen fragmentos que al intersecarse generan un conjunto vacio.

1

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

0 = F1 INTERSECT F2 INTERSECT .. INTESECT Fn > select * from emp_f a,emp_m b where a.id_emp=b.id_emp; Empty set (0.00 sec)

Fragmentación Horizontal Derivada Este tipo de fragmentación particiona una tabla en base a un atributo(s) que esta presente en otra tabla(s). SP

Id_S Id_P Id_DEPT CANT

Ejemplo: Fragmentar a SP de acuerdo a la ciudad del proveedor Pero ciudad no está en SP, como le hacemos ? Debemos hacer un JOIN de SP y Supplier y proceder a realizar la fragmentación horizontal. Los fragmentos se definirán de la sig. manera: FDH1 = ((Supplier JOIN SP) Where CD = ‘L’) FDH2 = ((Supplier JOIN SP) Where CD = ‘P’) SP

Supplier

Id_S S1 S1 S2 S2 S3 S4 S4 S4

Id_P P1 P3 P1 P2 P3 P4 P5 P6

Id_DEPT D1 D1 D2 D2 D1 D2 D3 D1

CANT 100 100 50 200 100 50 100 50

Id_s S1 S2 S3 S4 S5

NOMBRE X Y Z A B

FDH1 CD L L P P L

Id_S S1 S1 S2 S2

FDH2 Id_P P1 P3 P1 P2

Id_DEPT D1 D1 D2 D2

CANT 100 100 50 200

Id_S S3 S4 S4 S4

Id_P P3 P4 P5 P6

Id_DEPT D1 D2 D3 D1

CANT 100 50 100 50

Fragmentación Vertical Definir fragmentos verticales se hace a través del operador de proyección del algebra relacional operando sobre una relación global. E ID_EMP E1 E2 E3 E4 E5

NOMBRE X Y Z A B

SALARIO 1000 1500 500 4000 2000

IMPTO 100 300 20 1000 350

ND D1 D1 D2 D3 D2

FV1 = E [ID_EMP, NOMBRE, ND] ID_EMP E1 E2 E3 E4 E5

NOMBRE X Y Z A B

DEPT# D1 D1 D2 D3 D2

FV2 = E [ID_EMP, SALARIO, IMPTO] ID_EMP E1 E2 E3 E4 E5

SALARIO 1000 1500 500 4000 2000

IMPTO 100 300 20 1000 350

Una característica importante de la fragmentación vertical, es que todos los fragmentos deben incluir la llave primaria de la relación global. La razón es que si no incluimos la llave primaria no es posible reconstruir la relación original. Para reconstruir la relación original debemos realizar un JOIN de todos los fragmentos. R = F1 JOIN F2 JOIN … JOIN F3

2

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

En la fragmentación vertical no se cumple que los fragmentos sean disjuntos (la llave está repetida en todos los fragmentos). Ejemplo > Create table emp_v_sal select id_emp, nombre, apellido,sal from empleado; > Create table emp_v_nd select id_emp, nombre, apellido,nd from empleado; > select a.id_emp,a.nombre,a.apellido,a.sal,b.nd from emp_v_sal a, emp_v_nd b where a.id_emp=b.id_emp; Fragmentación Híbrida Consiste en aplicar las operaciones de fragmentación vistas anteriormente de manera recursiva, satisfaciendo las condiciones de correctes cada vez que se realiza la fragmentación. La reconstrucción puede ser obtenida aplicando las reglas de reconstrucción en orden inverso. De esta forma podemos fragmentar nuestra tabla global en los pedazos que queramos y como queramos. Ejemplo: Considere la relación de empleado (E). Una posible fragmentación híbrida sería: E E E4

E1

E2

E3

E1 = E[id_emp, Nombre, nd] Where nd =10 And nd20 E4 = E[id_emp, Salario, Impto

> Create table emp_v_nd select id_emp, nombre, apellido,nd from empleado; > Create table emp_v_nd_rango select id_emp, nombre, apellido,nd from empleado where id_emp >200;

3

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

Replicación de datos Se refiere al almacenamiento de copias de datos en sitios múltiples servidos por una red de computadoras. Pueden guardarse copias de fragmentos en varios sitios para satisfacer requerimientos de información específicos. Como la existencia de copias de fragmentos puede mejorar la disponibilidad de los datos y el tiempo de respuesta, estas copias reducen los costos de comunicación y consulta totales Ejemplo: Suponga que la BD A esta dividida en dos fragmentos: A1 y A2 Dentro de una BDD es posible el escenario: el fragmento A1 se guarda en los sitios S1 y S2 el fragmento A2 se guarda en los sitios S2 y S3 Los datos replicados se someten a la regla de consistencia mutua La regla de consistencia mutua requiere que todas las copias de fragmentos sean idénticas Por consiguiente, para mantener la consistencia de los datos entre las replicas, el SGBDD debe garantizar que se realice una actualización de la BD en todos los sitios donde existan replicas Aunque la replicación tiene algunos beneficios, también exige más complejidad de procesamiento del SGBDD, porque cada copia de datos debe ser mantenida por el sistema. Procesos que el SGBDD debe realizar para utilizar la BD: Si la BD esta fragmentada, el SGBDD debe decidir que copia acceder Una operación Read selecciona la copia más cercana para satisfacer la transacción Una operación Write requiere que todas las copias se seleccionen y actualicen para la regla de consistencia mutua El procesador de transacciones envía una solicitud de datos a cada procesador de datos para su ejecución El procesador de datos recibe y ejecuta cada solicitud y envía los datos de vuelta al procesador de transacciones El procesador de transacciones arma las respuestas del procesador de datos El problema se complica más cuando se consideran factores adicionales tales como la topología de la red y procesos de comunicación Existen tres escenarios de replicación 1) 2) 3)

Una BD totalmente replicada. Guarda varias copias de cada fragmento de la BD en varios sitios. En este caso, los fragmentos de la BD están replicados. Una BD totalmente replicada puede no ser practica debido a la cantidad de carga impuesta al sistema Una BD parcialmente replicada. Guarda múltiples copias de algunos fragmentos de la BD en múltiples sitios. La mayoría de los SGBDD son capaces de manejar bien la BD parcialmente replicada Una BD no replicada. Guarda cada fragmento de BD en un solo sitio. Por consiguiente, no existen fragmentos de BD duplicados

4

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

Factores que influyen en la decisión de utilizar replicación de datos Tamaño de la BD Frecuencia de uso Costos de desempeño, Software, indirectos y de administración, asociados con la sincronización de las transacciones

Colocación de datos La colocación de los datos describe el proceso de decidir donde localizarlos. Las estrategias de colocación de los datos son las siguientes: Colocación particionada de los datos. La base de datos se divide en varias partes desarticuladas (fragmentos) y se guardan en varios sitios Colocación replicada de los datos. Se guardan copias de uno o más fragmentos de la BD en varios sitios La distribución de los datos a través de la una red de computadoras, se logra mediante la partición de los datos, replicación de los datos o mediante una combinación de ambas La colocación de los datos esta estrechamente relacionada con la manera en que una BD se divide o fragmenta. La mayoría de los estudios de colocación de los datos se enfocan en un tema: QUE datos localizar y en DONDE Los algoritmos de colocación de los datos consideran varios factores: Objetivos de desempeño y disponibilidad de los datos Tamaño, numero de tuplas y el número de relaciones (vínculos) que una entidad mantiene con otras entidades Tipos de transacciones a ser aplicadas a la BD, los atributos accedidos por cada una de las transacciones, entre otros

5

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

Practica. Fragmentación, distribución y replicación Fragmentar y distribuir la BD Compania Supongamos que la Compañía tiene 3 nodos de servidor, uno para cada uno de los departamentos actuales. 1.

2.

Los nodos 2 y 3 son para los departamentos 5 y 4 respectivamente. a)

En cada uno de estos nodos esperamos que haya un acceso frecuente a la información de EMPLEADO y PROYECTO de los empleados que trabajan en ese departamento y los proyectos controlados por ese departamento ( se deduce la información de lugar_dept y trabaja_en)

b)

Además, supongamos que en estos nodos se tiene acceso principalmente a los atributos ID_EMP, NOMBRE, APELLIDO, SALARIO y NO_SUPERV de empleado.

El nodo 1 usa la oficina central de la compañía y tiene acceso con regularidad a toda la información de empleados y proyectos, además de utilizar la información de DEPENDIENTE para cuestiones de seguros

De acuerdo con estos requerimientos, la base de datos completa se puede almacenar en el nodo 1. Determinar los fragmentos que deben replicarse en los nodos 2 y 3.

6

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

Nodo 2

id_emp nombre apellido fecnac direccion sexo sal no_superv nd 123 luis Viades 1960-01-09 Paris 5 m 30000 333 5 666 Mario Alberto Luque 1958-09-15 Madrid 43 m 38000 333 5 453 Lucia Aldana 1962-04-12 Budapest 300 f 20000 333 5 EMPD5 id_emp nombre apellido sal no_superv nd 123 luis Viades 30000 333 5 666 Mario Alberto Luque 38000 333 5 453 Lucia Aldana 20000 333 5

Select id_emp, nombre, apellido,sal, no_superv, id from empleado where nd=5

DEPTO5 Numdept nomdept nssgte fecinigte 5 Ingenieria 333 1980-10-07 LUGAR_D5 numdept lugard 5 Altavista 5 Buenavista 5 CIVAC PROY5 no_proy nomproy lugarp numd 1 EnsamblajeA Altavista 5 2 ProcecosABC CIVAC 5 3 Calidad Total Buenavista 5

Fragmentar TRABAJA_EN y decidir cuáles fragmentos almacenar en los nodos 2 y 3.

Problema Ningún atributo de trabaja_en indica directamente el departamento al que pertenece cada tupla Cada tupla de trabaja_en relaciona un empleado e con un proyecto p Podríamos fragmentar TRABAJA_EN según el departamento d al que e pertenece o bien según el departamento d’ que controla p La fragmentación se facilita si tenemos una restricción que especifique que d=d’ para todas las tuplas TRABAJA_EN; esto es, si los empleados solo pueden trabajar en los proyectos controlados por el departamento al que pertenecen. Sin embargo, no hay tal restricción en la BD, por ejemplo, la tupla TRABAJA_EN (333, 3, 20) relaciona un empleado que pertenece al departamento 4 con un proyecto que está bajo el control del departamento 5. En este caso podríamos fragmentar TRABAJA_EN con base tanto en el departamento al que pertenece el empleado como en el departamento que controla el proyecto

7

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

A. ND=5 X1 > select * from trabaja_en where no_emp in (select id_emp from empleado where nd=5) and numproy in (select no_proy from proyecto where numd=5); > select no_emp, numproy, horas from empleado, proyecto, trabaja_en where id_emp=no_emp and numproy=no_proy and nd=5 and numd=5 no_emp numproy Horas 123 1 32.5 123 2 40 666 3 20 453 1 10 453 2 30 X2

nd=5 and numd=4

X3

nd=5 and numd=2

X4

nd=5 and numd=1

B. ND=4 X5

c)

>select no_emp, numproy, horas from empleado, proyecto, trabaja_en where id_emp=no_emp and numproy=no_proy and nd=4 and numd=5 no_emp numproy Horas 333 2 35 333 3 20 nd=4 and numd=4 no_emp numproy Horas 333 10 0 nd=4 and numd=2 nd=4 and numd=1 no_emp numproy horas 333 20 10 ND=2

X9 X10 X11 X12

nd=2 and numd=5 nd=2 and numd=4 nd=2 and numd=2 nd=2 and numd=1

d)

ND=1

X13 X14 X15 X16

nd=1 and numd=5 nd=1 and numd=4 nd=1 and numd=2 nd=1 and numd=1

X6

X7 X8

La unión de los fragmentos X1, X2, X3 y X4 produce todas las tuplas TRABAJA_EN de los empleados que pertenecen al departamento 5

8

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

La unión de los fragmentos X5, X6, X7 y X8 produce todas las tuplas TRABAJA_EN de los empleados que pertenecen al departamento 4 La unión de los fragmentos X1, X5, X9 y X13 produce todas las tuplas TRABAJA_EN de los proyectos controlados por el departamento 5 En nuestra distribución incluimos todos los fragmentos que se pueden reunir para dar una tupla EMPLEADO o bien una tupla PROYECTO en los nodos 2 y 3 Nodo 2 Colocamos la union de los fragmentos X1, X2, X3, X4, X5, X9 y X13 en el nodo 2 TRABAJA_EN no_emp numproy Horas 123 1 32.5 123 2 40 666 3 20 453 1 10 453 2 30 333 333

2 3

35 20

Nodo 3 Colocamos la union de los fragmentos X5, X6, X7, X8, X2, X10 y X14 en el nodo 2 no_emp numproy Horas 333 2 35 333 3 20 333 10 0 333 20 10

Los fragmentos X2 y X5 se replican en ambos nodos

9

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

Procesamiento de consultas en bases de datos distribuidas Cómo un SGBDD procesa y optimiza una consulta Costos de la transferencia de datos en el procesamiento de consultas distribuidas En un sistema distribuido varios factores complican el procesamiento de consultas El primero es el costo de transferir datos por la red. Estos datos incluyen los archivos intermedios que se transfieren a otros nodos para continuar su procesamiento, así como los archivos de resultado final que tal vez deban transferirse al nodo donde se necesita el resultado de la consulta Los algoritmos de optimización de los SGBDD consideran el objetivo de reducir la cantidad de transferencia de datos como criterio de optimización al elegir una estrategia de ejecución de una consulta distribuida Ejemplos Supongamos que las tablas EMPLEADO Y DEPTO están distribuidas de la siguiente forma (supondremos que ninguna de las tablas está fragmentada): Nodo 1 EMPLEADO id_emp nombre apellido fecnac direccion sexo sal no_superv nd 10 000 registros Cada registro tiene 100 bytes de longitud Id_emp tiene 9 bytes nombre 15 bytes

apellido 15 bytes

nd 4 bytes

Nodo 2 DEPTO Numdept nomdept nssgte fecinigte 100 registros Cada registro tiene 35 bytes de longitud Numdept tiene 4 bytes

nomdept 10 bytes

Con base en la información: El tamaño de EMPLEADO es 100 * 10 000 El tamaño de DEPTO es 35 * 100

nssgte 9 bytes

= 1 000 000 bytes = 3 500 bytes

Consideremos la consulta A: Para cada empleado, obtener su nombre y apellido y el nombre del departamento al que pertenece

A

NOMBRE, APELLIDO, NOMDEPT (EMPLEADO

>< ND=NUMDEPT DEPTO)

El resultado de esta consulta incluirá 10 000 registros, si todo empleado está relacionado con un departamento: Cada registro del resultado de la consulta tiene 40 bytes de longitud (15 + 15 + 10) La consulta se introduce en un nodo 3 distinto que es donde se requiere el resultado de la consulta Ninguna de las dos tablas EMPLEADO ni DEPTO reside en el nodo 3.

10

Base de Datos Distribuidas Prof. Sergio Ortiz Gama

Hay tres estrategias simples para ejecutar esta consulta distribuida 1.

Transferir EMPLEADO y DEPTO al nodo 3 y efectuar la reunión. Requerimos transferir un total de 1 000 000 + 3500 = 1 003 500 bytes

2.

Transferir EMPLEADO al nodo 2, ejecutar la reunión en ese nodo y enviar el resultado al nodo 3. El tamaño del resultado de la consulta es 40 * 10 000 = 400 000 bytes, de modo que debemos transferir 400 000 + 1 000 000 = 1 400 000 bytes

3.

Transferir DEPTO al nodo 1, ejecutar la reunión en ese nodo y enviar el resultado al nodo 3. En este caso tenemos que transferir 400 000 + 3500 = 403 500 bytes

Si minimizar la cantidad de transferencia de datos es el criterio de optimización, debemos elegir la estrategia 3

11