Bases Distribuidas

8/6/2019 Bases Distribuidas

1/43

Bases de Datos II

INDICE:

I NDICE:................................................................................................................................................CONSIDERACIONESGENERALES...................................................................................................................ESTRUCTURA DE BASE DE DATOS DISTRIBUIDAS...........................................................................................3CONSIDERACIONES AL DISTRIBUIR LA BASE DE DATOS.....................................................................................5

Ventajas de la distribucin de datos...........................................................................................Utilizacin compartida de los datos y distribucin del control..................................................5

Fiabilidad y disponibilidad........................................................................................................5

Agilizacin del procesamiento de consultas..............................................................................6

Desventajas de la distribucin de los datos................................................................................TRANSPARENCIA Y AUTONOMA..................................................................................................................

Asignacin de nombres y autonoma local.................................................................................Transparencia de la repeticin y la fragmentacin.....................................................................Transparencia de localizacin....................................................................................................Esquema completo de asignacin de nombres...........................................................................Transparencia y actualizaciones...............................................................................................

DISEO DE LA DISTRIBUCIN:...................................................................................................................1Introduccin..............................................................................................................................Diseo.......................................................................................................................................

TIPOS DE FRAGMENTACIN:......................................................................................................................1Grado de Fragmentacin...........................................................................................................Reglas de correccin de la fragmentacin.................................................................................Alternativas de asignacin........................................................................................................Informacin necesaria...............................................................................................................

Bases de Datos Distribuidas Pgina 1 de 43


2/43

Bases de Datos II

FRAGMENTACINHORIZONTAL:................................................................................................................2Informacin necesaria para la fragmentacin horizontal............................................................

Informacin sobre la base de datos. ........................................................................................27

Informacin sobre la aplicacin....................................................................................... .......27

Fragmentacin horizontal primaria............................................................................................Fragmentacin horizontal derivada...........................................................................................

FRAGMENTACINVERTICAL:....................................................................................................................3Introduccin..............................................................................................................................

Informacin necesaria para la fragmentacin vertical................................................................FRAGMENTACIN MIXTA O HBRIDA:..........................................................................................................36

Informacin necesaria...............................................................................................................PROCESAMIENTO DISTRIBUIDO DE CONSULTAS..............................................................................................39

Repeticin y fragmentacin.............................................................................................. ........Procesamiento de interseccin simple.......................................................................................Estrategias de interseccin utilizando el paralelismo.................................................................Estrategia de seminterseccin...................................................................................................

CONCLUSIONES Y CONSIDERACIONES:.........................................................................................................42



3/43

Bases de Datos II

CONSIDERACIONESGENERALES

En un sistema de base de datos distribuida, los datos se almacenan en varios computadores. Lcomputadores de un sistema distribuido se comunican entre s a travs de diversos medios comunicacin, tales como cables de alta velocidad o lneas telefnicas. No comparten la memo principal ni el reloj.

Los procesadores de un sistema distribuido pueden variar en cuanto su tamao y funcin. Puedincluir microcomputadores pequeos, estaciones de trabajo y sistemas de computadores grandesaplicacin general. Estos procesadores reciben diferentes nombres, tales como localidades, nodocomputadores.

Un sistema distribuido de bases de datos consiste en un conjunto de localidades, cada uno de cuales puede participar en la ejecucin de transacciones que accedan a datos de una o varias localidaLa diferencia principal entre los sistemas de base de datos centralizados y distribuidos es que, en

primeros, los datos residen en una sola localidad, mientras que, en los ltimos, se encuentran en valocalidades.

ESTRUCTURA DE BASE DE DATOS DISTRIBUIDAS

Un sistema distribuido de base de datos consiste en un conjunto de localidades, cada una de

cuales mantiene un sistema de base de datos local. Cada localidad puede procesar transacciones locao bien transacciones globales entre varias localidades, requiriendo para ello comunicacin entre ellas.

Las localidades pueden conectarse fsicamente de diversas formas, las principales son:



4/43

Bases de Datos II

Red totalmente conectada

Red prcticamente conectada

Red con estructura de rbol

Red de estrella

Red de anillo

Las diferencias principales entre estas configuraciones son:

Coste de instalacin: El coste de conectar fsicamente las localidades desistema

Coste de comunicacin: El coste en tiempo y dinero que implica enviar umensaje desde la localidad A a la B.

Fiabilidad: La frecuencia con que falla una lnea de comunicacin o unlocalidad.

Disponibilidad: La posibilidad de acceder a informacin a pesar de falloen algunas localidades o lneas de comunicacin.

Las localidades pueden estar dispersas, ya sea por un rea geogrfica extensa (a lo largo de pas), llamadas redes de larga distancia; o en un rea reducida (en un mismo edificio), llamadas redesrea local. Para las primeras se utilizan en la comunicacin lneas telefnicas, conexiones de microony canales de satlites; mientras que para las segundas se utiliza cables coaxiales de banda base o ba

ancha y fibra ptica.



5/43

Bases de Datos II

CONSIDERACIONES AL DISTRIBUIR LA BASE DE DATOS

Existen varias razones para construir sistemas distribuidos de bases de datos que incluycompartir la informacin, fiabilidad y disponibilidad y agilizar el procesamiento de las consultas. Ptambin tiene sus desventajas, como desarrollos de software ms costosos, mayor posibilidad de errorcostos extras de procesamiento.

Ventajas de la distribucin de datos

La principal ventaja de los sistemas distribuidos es la capacidad de compartir y acceder a informacin de una forma fiable y eficaz.

Utilizacin compartida de los datos y distribucin del control

La ventaja principal de compartir los datos por medio de la distribucin es que cada localid

pueda controlar hasta cierto punto los datos almacenados localmente. En un sistema centralizadoadministrador de base de datos de la localidad central controla la base de datos. En un sistema distribuexiste un administrador global de la base de datos que se encarga de todo el sistema. Parte de eresponsabilidad se delega al administrador de base de datos de cada localidad. Dependiendo del disdel sistema distribuido, cada administrador local podr tener un grado de autonoma diferente, queconoce como autonoma local. La posibilidad de contar con autonoma local es en muchos casos uventaja importante de las bases de datos distribuidas.

Fiabilidad y disponibilidad



6/43

Bases de Datos II

Si se produce un fallo en una localidad de un sistema distribuido, es posible que las demlocalidades puedan seguir trabajando. En particular, si los datos se repiten en varias localidades, utransaccin que requiere un dato especfico puede encontrarlo en ms de una localidad. As, el fallouna localidad no implica necesariamente la desactivacin del sistema.

El sistema debe detectar cuando falla una localidad y tomar las medidas necesarias para recuperadel fallo. El sistema no debe seguir utilizando la localidad que fall. Por ltimo, cuando se recuperrepare esta localidad, debe contarse con mecanismos para reintegrarla al sistema con el mnimo

complicaciones.

La disponibilidad es fundamental para los sistemas de bases de datos que se utilizan eaplicaciones de tiempo real. Por ejemplo, si una lnea area no puede tener acceso a la informacin posible que pierda clientes a favor de la competencia.

Agilizacin del procesamiento de consultas

Si una consulta comprende datos de varias localidades, puede ser posible dividir la consulta varias subconsultas que se ejecuten en paralelo en distintas localidades. Sin embargo, en un sistedistribuido no se comparte la memoria principal, as que no todas las estrategias de interseccin se pueaplicar en estos sistemas. En los casos en que hay repeticin de los datos, el sistema puede pasaconsulta a las localidades ms ligeras de carga.

Desventajas de la distribucin de los datos

La desventaja principal de los sistemas distribuidos es la mayor complejidad que se requiere pgarantizar una coordinacin adecuada entre localidades.

El aumento de la complejidad se refleja en:



7/43

Bases de Datos II

Coste del desarrollo de software: es ms difcil estructura un sistema d bases de datos distribuidos y por tanto su coste es menor

Mayor posibilidad de errores: puesto que las localidades del sistemdistribuido operan en paralelo, es ms difcil garantizar que los algoritmos seacorrectos.

Mayor tiempo extra de procesamiento: el intercambio de mensajes y loclculos adicionales son una forma de tiempo extra que no existe en los sistem

centralizados.

TRANSPARENCIA Y AUTONOMA

En la seccin anterior se vio que una relacin r puede almacenarse de varias formas en un sistede base de datos distribuida. Es esencial que el sistema reduzca al mnimo la necesidad de que el usua

se d cuenta de cmo est almacenada una relacin. Como veremos. un sistema puede ocultar los detade la distribucin de la informacin en la red. Esto se denomina transparencia de la red. La transparende la red se relaciona, en algn modo, a la autonoma local. La transparencia de la red es el grado hastcual los usuarios del sistema pueden ignorar los detalles del diseo distribuido. La autonoma local egrado hasta el cual el diseador o administrador de una localidad pueden ser independientes del restosistema distribuido . Los temas de transparencia y autonoma sern considerados desde los siguien puntos de vista:

Nombre de los datos.

Repeticin de los datos.Fragmentacin de los datos.

Localizacin de los fragmentos y copias.



8/43

Bases de Datos II

Asignacin de nombres y autonoma local

Todo elemento de informacin de una base de datos debe tener un nombre nico. Esta propiedadasegura fcilmente en una base de datos que no est distribuida. Sin embargo, en una base de dadistribuida, las distintas localidades deben asegurarse no utilizar el mismo nombre para dos dadiferentes.

Una solucin para este problema es requerir que se registren todos los nombres en unasignador central de nombres . Sin embargo, este enfoque tiene varias desventajas:

Es posible que el asignador de nombres se convierta en un cuello de botella..

Si el asignador de nombres se cae, es posible que ninguna de las localidades desistema distribuido pueda seguir trabajando.

Se reduce la autonoma local, ya que la asignacin de nombres se controla deforma centralizada.

Un enfoque diferente que origina una mayor autonoma local es exigir que cada localidad poncomo prefijo un identificador de localidad a cualquier nombre que genere. Esto garantiza que dlocalidades nunca generarn el mismo nombre (ya que cada localidad tiene un identificador nicAdems, no se requiere un control central.

Esta solucin al problema de asignacin de nombres, logra autonoma local, pero no transparende la red, ya que se agregan identificadores de localidad a los nombres. As, la relacin depsito pollamarse localidad17.depsito en vez de depsito simplemente.

Cada copia y fragmento de un elemento de informacin deben tener un nombre nico. E



9/43

Bases de Datos II

importante que el sistema pueda determinar qu copias son copias del mismo elemento de informaciqu fragmentos son fragmentos del mismo elemento de informacin.

Transparencia de la repeticin y la fragmentacin

No es conveniente requerir que los usuarios hagan referencia a una copia especfica de uelemento de informacin. El sistema debe ser el que determine a qu copia debe acceder cuando se solicite su lectura, y debe modificar todas las copias cuando se produzca una peticin de escritura.

Cuando se solicita un dato, no es necesario especificar la copia. El sistema utiliza una tablacatlogo para determinar cules son todas las copias de ese dato.

De manera similar, no debe exigirse a los usuarios que sepan cmo est fragmentado un elemende informacin. Es posible que los fragmentos verticales contengan id-tuplas, que representadirecciones de tuplas. Los fragmentos horizontales pueden haberse obtenido por predicados de seleccicomplejos. Por tanto, un sistema de bases de datos distribuido debe permitir las consultas que se haga

en trminos de elementos de informacin sin fragmentar. Esto no presenta problemas graves, ya qusiempre es posible reconstruir el elemento de informacin original a partir de sus fragmentos. Sembargo, este proceso puede ser ineficiente.

Transparencia de localizacin

Si el sistema es transparente en cuanto a repeticin y fragmentacin, se ocultar al usuario gr parte del esquema de la base de datos distribuida. Sin embargo, el componente de los nombres identifican a la localidad obliga al usuario a darse cuenta del hecho de que cl sistema est distribuido.



10/43

Bases de Datos II

La transparencia de localizacin se logra creando un conjunto de seudnimos o alias para causuario. As, el usuario puede referirse a los datos usando nombres sencillos que el sistema traducnombres completos.

Con el uso de seudnimos, no ser necesario que el usuario conozca la localizacin fsica de dato. Adems, el administrador de la base de datos puede cambiar un dato de una localidad a otra afectar a los usuarios.

Esquema completo de asignacin de nombres

Ya vimos que un nombre proporcionado por el usuario debe pasar por varios pasos de traducciantes de que pueda servir como referencia a una copia especfica de un fragmento determinado en localidad especfica.

Para ilustrar cmo funciona el esquema, consideramos un usuario que se encuentra en la sucur1 (L1). Este usuario emplea el seudnimo depsito-local para el fragmento local depsito-F1 de

relacin deposito. Cuando este usuario hace referencia a depsito-local, el subsistema de procesamiede consultas busca depsito-local en la tabla de seudnimos y la sustituye por Ll.depsito.F1. posible que L1.depsito.Fl est repetido. Si es as, debe consultarse la tabla de copias para elegir copia. Esta copia podra tambin estar fragmentada, lo que hara necesario consultar la tabla fragmentacin. En la mayor parte de los casos, slo es preciso consultar una o dos tablas.

Transparencia y actualizaciones

De alguna forma es ms difcil hacer transparente la base de datos para usuarios que laactualizan que para aquellos que slo leen datos. El problema principal es asegurarse de que seactualizan todas las copias de un dato y tambin los fragmentos afectados.



11/43


12/43

Bases de Datos II

en tal caso existe una rplica de las aplicaciones en cada mquina y los datos viajan por la red; y,reparten datos y programas, dado un programa ubicado en un determinado sitio, ste puede solicitar un

Figura 1. Enfoque de la distribucin.

servicio a otro programa localizado en un segundo lugar, el cual podr acceder a los datos situados entercer emplazamiento. Como se coment lneas atrs, en este caso se optar por el punto intermediocomparticin.

Respecto a las caractersticas de acceso a los datos existen dos alternativas principalmente: el m

de acceso a los datos que solicitan los usuarios puede ser esttico, es decir, no cambiar a lo largo tiempo, o bien, dinmico. El lector podr comprender fcilmente la dificultad de encontrar sistemdistribuidos reales que puedan clasificarse como estticos. Sin embargo, lo realmente importante radestableciendo el dinamismo como base, cmo de dinmico es, cuntas variaciones sufre a lo largo tiempo. Esta dimensin establece la relacin entre el diseo de bases de datos distribuidas y procesamiento de consultas.

La tercera clasificacin es el nivel de conocimiento de las caractersticas de acceso. Una posibili

es, evidentemente, que los diseadores carezcan de informacin alguna sobre cmo los usuarios accea la base de datos. Es una posibilidad terica, pero sera muy laborioso abordar el diseo de la basedatos con tal ausencia de informacin. Lo ms prctico sera conocer con detenimiento la forma de accde los usuarios o, en el caso de su imposibilidad, conformarnos con una informacin parcial de sta.



13/43

Bases de Datos II

El problema del diseo de bases de datos distribuidas podra enfocarse a travs de esta trama opciones. En todos los casos, excepto aquel en el que no existe comparticin, aparecern una serienuevos problemas que son irrelevantes en el caso centralizado.

A la hora de abordar el diseo de una base de datos distribuida podremos optar principalmente pdos tipos de estrategias: la estrategia ascendente y la estrategia descendente. Ambos tipos no sexcluyentes, y no resultara extrao a la hora de abordar un trabajo real de diseo de una base de da

que se pudiesen emplear en diferentes etapas del proyecto una u otra estrategia. La estrategia ascende podra aplicarse en aquel caso donde haya que proceder a un diseo a partir de un nmero de peque bases de datos existentes, con el fin de integrarlas en una sola. En este caso se partira de los esqueconceptuales locales y se trabajara para llegar a conseguir el esquema conceptual global. Aunque ecaso se pueda presentar con facilidad en la vida real, se prefiere pensar en el caso donde se parte de cese avanza en el desarrollo del trabajo siguiendo la estrategia descendente. La estrategia descendente (la figura 2) debera resultar familiar a la persona que posea conocimientos sobre el diseo de basesdatos, exceptuando la fase del diseo de la distribucin. Pese a todo, se resumirn brevemente las eta

por las que se transcurre.



14/43

Bases de Datos II



15/43

Bases de Datos II

Figura 2. Estrategia descendente.



16/43

Bases de Datos II

Todo comienza con un anlisis de los requisitos que definirn el entorno del sistema en arasobtener tanto los datos como las necesidades de procesamiento de todos los posibles usuarios del bade datos. Igualmente, se debern fijar los requisitos del sistema, los objetivos que debe cumplir respecunos grados de rendimiento, seguridad, disponibilidad y flexibilidad, sin olvidar el importante aspeeconmico. Como puede observarse, los resultados de este ltimo paso sirven de entrada para dactividades que se realizan de forma paralela. El diseo de las vistas trata de definir las interfaces parusuario final y, por otro lado, el diseo conceptual se encarga de examinar la empresa para determinartipos de entidades y establecer la relacin entre ellas. Existe un vnculo entre el diseo de las vistas

diseo conceptual. El diseo conceptual puede interpretarse como la integracin de las vistas del usuaeste aspecto es de vital importancia ya que el modelo conceptual debera soportar no slo las aplicacioexistentes, sino que debera estar preparado para futuras aplicaciones. En el diseo conceptual y devistas del usuario se especificarn las entidades de datos y se determinarn las aplicaciones qfuncionarn sobre la base de datos, as mismo, se recopilarn datos estadsticos o estimaciones sobractividad de estas aplicaciones. Dichas estimaciones deberan girar en torno a la frecuencia de acceso, parte de una aplicacin, a las distintas relaciones de las que hace uso, podra afinarse ms anotandoatributos de la relacin a la que accede. Desarrollado el trabajo hasta aqu, se puede abordar la confec

del esquema conceptual global. Este esquema y la informacin relativa al acceso a los datos sirvenentrada al paso distintivo: el diseo de la distribucin. El objetivo de esta etapa consiste en disear esquemas conceptuales locales que se distribuirn a lo largo de todos los puestos del sistema distribuiSera posible tratar cada entidad como una unidad de distribucin; en el caso del modelo relacional, centidad se corresponde con una relacin. Resulta bastante frecuente dividir cada relacin en subrelaciomenores denominadas fragmentos que luego se ubican en uno u otro sitio. De ah, que el proceso diseo de la distribucin conste de dos actividades fundamentales: la fragmentacin y la asignacinltimo paso del diseo de la distribucin es el diseo fsico, el cual proyecta los esquemas conceptu

locales sobre los dispositivos de almacenamiento fsico disponibles en los distintos sitios. Las entra para este paso son los esquemas conceptuales locales y la informacin de acceso a los fragmentos. ltimo, se sabe que la actividad de desarrollo y diseo es un tipo de proceso que necesita de u



17/43

Bases de Datos II

monitorizacin y un ajuste peridicos, para que si se llegan a producir desviaciones, se pueda retornalguna de las fases anteriores.

Diseo

Existen diversas formas de afrontar el problema del diseo de la distribucin. Las ms usualesmuestran en la figura 3. En el primer caso, caso A, los dos procesos fundamentales, la fragmentacin

asignacin, se abordan de forma simultnea. Esta metodologa se encuentra en desuso, sustituida poenfoque en dos fases, caso B: la realizacin primeramente de la particin para luego asignar lfragmentos generados. El resto de los casos se comentan en la seccin referente a los distintos tipos dfragmentacin.



18/43

Bases de Datos II

Figura 3. Enfoques para realizar el diseo distributivo.

Antes de exponer las alternativas existentes de fragmentacin, se desean presentar las ventajainconvenientes de esta tcnica. Se ha comentado en la introduccin la conveniencia de descomponerrelaciones de la base de datos en pequeos fragmentos, pero no se ha justificado el hecho ni se haportado razones para efectuarlo. Por ello, desde este punto se va a intentar aportar las razones necesa para llevar a cabo esa descomposicin, esa fragmentacin.

El principal problema de la fragmentacin radica en encontrar la unidad apropiada de distribuciUna relacin no es una buena unidad por muchas razones. Primero, las vistas de la aplicacinormalmente son subconjuntos de relaciones. Adems, la localidad de los accesos de las aplicacionesest definida sobre relaciones enteras pero s sobre subconjuntos de las mismas. Por ello, sera normconsiderar como unidad de distribucin a estos subconjuntos de relaciones.

Segundo, si las aplicaciones tienen vistas definidas sobre una determinada relacin (considerndahora una unidad de distribucin) que reside en varios sitios de la red, se puede optar por dos alternati

Por un lado, la relacin no estar replicada y se almacena en un nico sitio, o existe rplica en todoalgunos de los sitios en los cuales reside la aplicacin. Las consecuencias de esta estrategia songeneracin de un volumen de accesos remotos innecesario. Adems, se pueden realizar rpliinnecesarias que causen problemas en la ejecucin de las actualizaciones y puede no ser deseable sespacio de almacenamiento est limitado.

Tercero, la descomposicin de una relacin en fragmentos, tratados cada uno de ellos como uunidad de distribucin, permite el proceso concurrente de las transacciones. Tambin la relacin de erelaciones, normalmente, provocar la ejecucin paralela de una consulta al dividirla en una seriesubconsultas que operar sobre los fragmentos.



19/43

Bases de Datos II

Pero la fragmentacin tambin acarrea inconvenientes. Si las aplicaciones tienen requisitos taque prevengan la descomposicin de la relacin en fragmentos mutuamente exclusivos, estas aplicaciocuyas vistas estn definidas sobre ms de un fragmento pueden sufrir una degradacin en el rendimiePor tanto, puede ser necesario recuperar los datos de dos fragmentos y llevar a cabo sobre ellos operacde unin y yunto , lo cual es costoso.

Un segundo problema se refiere al control semntico. Como resultado de la fragmentacin atributos implicados en una dependencia se descomponen en diferentes fragmentos los cuales pue

destinarse a sitios diferentes. En este caso, la sencilla tarea de verificar las dependencias puede resuuna tarea de bsqueda de los datos implicados en un gran nmero de sitios.

TIPOS DE FRAGMENTACIN:

Dado que una relacin se corresponde esencialmente con una tabla y la cuestin consiste dividirla en fragmentos menores, inmediatamente surgen dos alternativas lgicas para llevar a cabo proceso: la divisin horizontal y la divisin vertical. La divisin o fragmentacin horizontal trabaja solas tuplas, dividiendo la relacin en subrelaciones que contienen un subconjunto de las tuplas que albela primera. La fragmentacin vertical, en cambio, se basa en los atributos de la relacin para efectuadivisin. Estos dos tipos de particin podran considerarse los fundamentales y bsicos. Sin embarexisten otras alternativas. Fundamentalmente, se habla de fragmentacin mixta o hbrida cuando proceso de particin hace uso de los dos tipos anteriores. La fragmentacin mixta puede llevarse a cde tres formas diferentes: desarrollando primero la fragmentacin vertical y, posteriormente, aplicand particin horizontal sobre los fragmentos verticales (denominada particin VH), o aplicando primero divisin horizontal para luego, sobre los fragmentos generados, desarrollar una fragmentacin vert(llamada particin HV), o bien, de forma directa considerando la semntica de las transacciones. Oenfoque distinto y relativamente nuevo, consiste en aplicar sobre una relacin, de forma simultnea y



20/43


21/43


22/43

Bases de Datos II

Figura 3. Enfoques para realizar el diseo distributivo.

Grado de fragmentacin. Cuando se va a fragmentar una base de datos deberamos sopesar qgrado de fragmentacin va a alcanzar, ya que ste ser un factor que influir notablemente endesarrollo de la ejecucin de las consultas. El grado de fragmentacin puede variar desde una ausencila divisin, considerando a las relaciones unidades de fragmentacin; o bien, fragmentar a un grado ecada tupla o atributo forme un fragmento. Ante estos dos casos extremos, evidentemente se ha de busun compromiso intermedio, el cual debera establecerse sobre las caractersticas de las aplicaciones

hacen uso de la base de datos. Dichas caractersticas se podrn formalizar en una serie de parmetrosacuerdo con sus valores, se podr establecer el grado de fragmentacin del banco de datos.



23/43

Bases de Datos II

Figura 4. Distintos tipos de fragmentacin.

Grado de Fragmentacin

Cuando se va a fragmentar una base de datos deberamos sopesar qu grado de fragmentacin valcanzar, ya que ste ser un factor que influir notablemente en el desarrollo de la ejecucin de consultas. El grado de fragmentacin puede variar desde una ausencia de la divisin, considerando arelaciones unidades de fragmentacin; o bien, fragmentar a un grado en el cada tupla o atributo formefragmento. Ante estos dos casos extremos, evidentemente se ha de buscar un compromiso intermedio

cual debera establecerse sobre las caractersticas de las aplicaciones que hacen uso de la base de daDichas caractersticas se podrn formalizar en una serie de parmetros. De acuerdo con sus valores podr establecer el grado de fragmentacin del banco de datos.



24/43

Bases de Datos II

Reglas de correccin de la fragmentacin

A continuacin se enuncian las tres reglas que se han de cumplir durante el proceso fragmentacin, las cuales asegurarn la ausencia de cambios semnticos en la base de datos durant proceso.

1. Complecin. Si una relacinR se descompone en una serie de fragmentosR 1,R 2 , ..., R n, cada elemento de datos que pueda encontrarse enR deber poder encontrarse enuno o varios fragmentosR i . Esta propiedad extremadamente importante asegura que los datosde la relacin global se proyectan sobre los fragmentos sin prdida alguna. Tenga en cuenta qen el caso horizontal el elemento de datos, normalmente, es una tupla, mientras que en el cavertical es un atributo.

2. Reconstruccin. Si una relacinR se descompone en una serie de fragmentosR 1, R 2 , ..., R n, puede definirse una operador relacional tal que el operador ser diferentedependiendo de las diferentes formas de fragmentacin. La reconstruccin de la relacin partir de sus fragmentos asegura la preservacin de las restricciones definidas sobre los daen forma de dependencias.

3. Disyuncin. Si una relacinR se descompone horizontalmente en una serie defragmentosR 1, R 2 , ..., R n, y un elemento de datos di se encuentra en algn fragmentoR j ,entonces no se encuentra en otro fragmentoR k (k j ). Esta regla asegura que los fragmentoshorizontales sean disjuntos. Si una relacinR se descompone verticalmente, sus atributos primarios clave normalmente se repiten en todos sus fragmentos.

Alternativas de asignacin



25/43

Bases de Datos II

Partiendo del supuesto que el banco de datos se haya fragmentado correctamente, habr que decsobre la manera de asignar los fragmentos a los distintos sitios de la red. Cuando una serie de datoasignan, stos pueden replicarse para mantener una copia. Las razones para la rplica giran en torno seguridad y a la eficiencia de las consultas de lectura. Si existen muchas reproducciones de un elemede datos, en caso de fallo en el sistema se podra acceder a esos datos ubicados en sitios distintAdems, las consultas que acceden a los mismos datos pueden ejecutarse en paralelo, ya que habr coen diferentes sitios. Por otra parte, la ejecucin de consultas de actualizacin, de escritura, implicaractualizacin de todas las copias que existan en la red, cuyo proceso puede resultar problemtico

complicado. Por tanto, un buen parmetro para afrontar el grado de rplica consistira en sopesarcantidad de consultas de lectura que se efectuarn, as como el nmero de consultas de escritura quellevarn a cabo. En una red donde las consultas que se procesen sean mayoritariamente de lectura podra alcanzar un alto grado de rplica, no as en el caso contrario. Una base de datos fragmentadaquella donde no existe rplica alguna. Los fragmentos se alojan en sitios donde nicamente existe copia de cada uno de ellos a lo largo de toda la red. En caso de rplica, podemos considerar una basedatos totalmente replicada, donde existe una copia de todo el banco de datos en cada sitio, o consideuna base de datos parcialmente replicada donde existan copias de los fragmentos ubicados en diferen

sitios. El nmero de copias de un fragmento ser una de las posibles entradas a los algoritmos asignacin, o una variable de decisin cuyo valor lo determine el algoritmo. La figura 5 compara las alternativas de rplica con respecto a distintas funciones de un sistema de base de datos distribuido.

Rplica totalRplica

parcialParticin



26/43

Bases de Datos II

Procesamiento de consultas fcil dificultad similar Gestin del directorio fcil o inexistente dificultad similar Control de concurrencia moderado difcil fcilSeguridad muy alta alta baja \Realidad posible aplicacin realista posible aplicacin

Informacin necesaria

Un aspecto importante en el diseo de la distribucin es la cantidad de factores que contribuyeun diseo ptimo. La organizacin lgica de la base de datos, la localizacin de las aplicaciones, caractersticas de acceso de las aplicaciones a la base de datos y las caractersticas del sistema en csitio, tienen una decisiva influencia sobre la distribucin. La informacin necesaria para el diseo ddistribucin puede dividirse en cuatro categoras: la informacin del banco de datos, la informacin daplicacin, la informacin sobre la red de ordenadores y la informacin sobre los ordenadores en s. dos ltimas son de carcter cuantitativo y servirn, principalmente, para desarrollar el proceso asignacin. Se entrar en detalle sobre la informacin empleada cuando se aborden los distinalgoritmos de fragmentacin y asignacin.

FRAGMENTACINHORIZONTAL:

Como se ha explicada anteriormente, la fragmentacin horizontal se realiza sobre las tuplas derelacin. Cada fragmento ser un subconjunto de las tuplas de la relacin. Existen dos variantes dfragmentacin horizontal: la primaria y la derivada. La fragmentacin horizontal primaria de una relacse desarrolla empleando los predicados definidos en esa relacin. Por el contrario, la fragmentac



27/43

Bases de Datos II

horizontal derivada consiste en dividir una relacin partiendo de los predicados definidos sobre algotra.

Informacin necesaria para la fragmentacin horizontal

Informacin sobre la base de datos.

Esta informacin implica al esquema conceptual global. Es importante sealar cmo las relaciode la base de datos se conectan con otras. En una conexin de relaciones normalmente se denomrelacin propietaria a aquella situada en la cola del enlace, mientras que se llama relacin miembro ubicada en la cabecera del vnculo. Dicho de otra forma podemos pensar en relaciones de origen cuanos refiramos a las propietarias y relaciones destino cuando lo hagamos con las miembro. Definiremdos funciones: propietaria y miembro, las cuales proyectarn un conjunto de enlaces sobre un conjuntrelaciones. Adems, dado un enlace, devolvern el miembro y el propietario de la relacirespectivamente. La informacin cuantitativa necesaria gira en torno a la cardinalidad de cada relac

notada comocard (R ).

Informacin sobre la aplicacin.

Necesitaremos tanto informacin cualitativa como cuantitativa. La informacin cualitativa guiarfragmentacin, mientras que la cuantitativa se necesitar en los modelos de asignacin. La princiinformacin de carcter cualitativo son los predicados empleados en las consultas de usuario. Si no fu posible investigar todas las aplicaciones para determinar estos predicados, al menos se deberan invest

las ms importantes. Podemos pensar en la regla "80/20" para guiarnos en nuestro anlisis, esta regla que el 20% de las consultas existentes acceden al 80% de los datos. Llegados a este punto, seinteresante determinar los predicados simples.



28/43

Bases de Datos II

A parte de los predicados simples, las consultas emplean predicados ms complejos resultado combinaciones lgicas de los simples. Una combinacin especialmente interesante es la conjuncin predicados simples, al predicado resultante se le denomina predicado mintrmino. Partiendo de siempre es posible transformar una expresin lgica en su forma normal conjuntiva, usaremos predicados mintrmino en los algoritmos para no causar ninguna prdida de generalidad.

Sobre la informacin cuantitativa necesaria relativa a las aplicaciones, necesitaremos definir dconjuntos de datos.

1. Selectividad mintrmino. Es el nmero de tuplas de una relacin a las que accede una consultaacuerdo a un predicado mintrmino dado. Por ejemplo, en el ejemplo anterior, la selectividad de 6 es 0 ya que no existe ninguna tupla que satisfaga las condiciones; en cambio, la selectividad dem1 es2. Notaremos la selectividad de un mintrmino mi comosel (m i ).

2. Frecuencia de acceso. Es la frecuencia con la que un usuario accede a los datos. SiQ = {q1 , q 2 , ...,qq} es un conjunto de consultas de usuario,acc (q i ) indica la frecuencia de acceso a la consultaqi enun periodo dado.

Fragmentacin horizontal primaria

Antes de presentar un algoritmo formal que lleve a cabo la fragmentacin horizontal, intentaremexplicar de manera intuitiva los procesos de fragmentacin horizontal primaria y derivada. fragmentacin horizontal primaria se define como una operacin de seleccin de las relacion propietarias del esquema de la base de datos

Ahora definiremos la fragmentacin horizontal ms formalmente. Un fragmento horizontalR i deuna relacinR contiene todas las tuplas deR que satisfacen un predicado mintrminom i . Por tanto, dadoun conjunto de predicados mintrminoM , existen tantos fragmentos horizontales de la relacinR como



29/43

Bases de Datos II

predicados mintrmino. Este conjunto de fragmentos horizontales tambin se conocen como conjuntofragmentos mintrmino. En los prrafos siguientes se asumir que la definicin de fragmenhorizontales se basa en los predicados mintrmino. Adems, el primer paso para el algoritmo fragmentacin consiste en establecer un conjunto de predicados con ciertas propiedades.

Un aspecto importante de los predicados simples es su complecin, as como su minimalidad. conjunto de predicados simplesPr se dice que es completo si y solo si existe una probabilidad idntica deacceder por cada aplicacin a cualquier par de tuplas pertenecientes a cualquier fragmento mintrm

que se define de acuerdo conPr . Se puede apreciar como la definicin de complecin de un conjunto de predicados simples difiere de la regla de complecin de la fragmentacin.

El segundo paso en el proceso de fragmentacin primaria consiste en derivar el conjunto predicados mintrmino que pueden definirse sobre los predicados del conjuntoPr' . Estos predicadosmintrmino establecen los fragmentos candidatos para el proceso de asignacin. El establecimiento de predicados mintrmino es trivial; la dificultad radica en el tamao del conjunto de predicados mintrmque puede ser muy grande (de hecho, exponencial respecto al nmero de predicados simples). En el p

siguiente se presentarn formas de reducir el nmero de predicados mintrmino necesarios parafragmentacin.

El tercer paso aborda, como ya se ha citado, la eliminacin de algunos fragmentos mintrmino q puedan ser redundantes. Esta eliminacin se desarrolla identificando aquellos mintrminos que pueresultar contradictorios sobre un conjunto de implicaciones.

Fragmentacin horizontal derivada

Una fragmentacin horizontal derivada se define sobre una relacin miembro de acuerdo a uoperacin de seleccin especificada sobre su propietaria. Se deben dejar claros dos puntos. Primero



30/43

Bases de Datos II

enlace entre las relaciones propietaria y miembro se define como un equi-yunto. Segundo, un equi-yu puede desarrollarse a travs de semiyuntos. Este segundo punto es especialmente importante pnuestros propsitos, ya que deseamos fraccionar una relacin miembro segn la fragmentacin de propietaria, adems es necesario que el fragmento resultante se defina nicamente sobre los atributosla relacin miembro.

Las tres entradas necesarias para desarrollar la fragmentacin horizontal derivada son lsiguientes: el conjunto de particiones de la relacin propietaria, la relacin miembro y el conjunto

predicados resultados de aplicar el semi-yunto entre la propietaria y la miembro. El algoritmofragmentacin resulta tan trivial que no se ve la necesidad de entrar en detalles.

Existe una posible complicacin que necesita nuestro estudio. En un esquema de base de datresulta frecuente que existan ms de dos enlaces sobre una relacin R. En este caso, aparecen ms de posibilidad de fragmentacin horizontal derivada. La decisin para elegir una u otra se basa en criterios: Uno, la fragmentacin con mejores caractersticas de yunto. Dos, la fragmentacin empleadams aplicaciones.

Discutamos el segundo criterio primero. Resulta sencillo de establecer si tomamos econsideracin la frecuencia con la que cada aplicacin accede a los datos. Si es posible, deberamintentar facilitar el acceso a los usuarios que hagan mayor uso de los datos para, de esta maneminimizar el impacto total del rendimiento del sistema.

Figura 5. Grafo de yuntos entre fragmentos.



31/43

Bases de Datos II

El primer criterio, sin embargo, no es tan sencillo. Considere, por ejemplo, la fragmentaciexpuesta en el ejemplo 8. El objetivo de esta fragmentacin consiste en beneficiar a la consulta que huso de las dos relaciones al poder realizarse el yunto de CLIENTES y PROVINC sobre relaciones m pequeas (es decir, fragmentos), y posibilitar la confeccin de yuntos de manera distribuida. El priaspecto resulta obvio. Los fragmentos de CLIENTES son ms pequeos que la propia relaciCLIENTES. Por tanto, resultar ms rpido llevar a cabo el yunto de un fragmento de PROVINC con de CLIENTES que trabajar con las propias relaciones. El segundo punto, sin embargo, es ms importaya que es la esencia de las bases de datos distribuidas. Si, adems de estar ejecutando un nmeroconsultas en diferentes sitios, podemos ejecutar una consulta en paralelo, se espera que el tiemporespuesta del sistema aumente. En el caso de yuntos, esto es posible bajo ciertas circunstanciConsidere, por ejemplo, el grafo de yunto (los enlaces) entre los fragmentos de CLIENTES y la derivPROVINC. Hay nicamente un enlace entrando o saliendo de un fragmento. De ah, que se denomineste grafo, grafo simple. La ventaja de este diseo donde la relacin de yunto entre los fragmentossimple, radica en la asignacin a un sitio tanto de la propietaria como de la miembro y los yuntos e pares diferentes de fragmentos pueden realizarse independientemente y en paralelo. Desgraciadament

obtencin de grafos de yunto simples no siempre es posible. En tal caso, la mejor alternativa sera realun diseo que provoque un grafo de yuntos fragmentados. Un grafo fragmentado consiste en dos o msubgrafos que no estn enlazados entre ellos. Por tanto, los fragmentos que se obtengan no se distribu para ejecuciones paralelas de un modo tan fcil como aquellos obtenidos a travs de grafos simples, psu asignacin an ser posible.

Procederemos ahora a probar la correccin de los algoritmos presentados con respecto a los trcriterios enunciados pginas atrs.

1. Complecin . La complecin de una fragmentacin horizontal primaria se basa en la seleccin de lo predicados a usar. En la medida que los predicados seleccionados sean completos, se garantizar q



32/43

Bases de Datos II

el resultado de la fragmentacin tambin lo ser. Partiendo de la base que el algoritmo fragmentacin es un conjunto de predicados completos y mnimosPr' , se garantiza la complecinsiempre que no aparezcan errores al realizar la definicin dePr' . La complecin de una fragmentacinhorizontal derivada es algo ms difcil de definir. La dificultad viene dada por el hecho de que predicados que intervienen en la fragmentacin forman parte de dos relaciones. Definamos la reglacomplecin formalmente. SeaR la relacin miembro de un enlace cuya propietaria es la relacinS , lacual est fragmentada comoF S = {S 1 , S 2 , ..., S w }. Adems, sea A el atributo de yunto entreR y S .Entonces para cada tuplat de R , existir una tuplat' de S tal quet [ A] = t' [ A].

2. Reconstruccin . La reconstruccin de una relacin global a partir de sus fragmentos se desarrollcon el operador de unin tanto para la fragmentacin horizontal primaria como para la derivada.

3. Disyuncin . Resulta sencillo establecer la disyuncin de la fragmentacin tanto para la primaricomo para la derivada. En el primer caso, la disyuncin se garantiza en la medida en que l predicados mintrmino que determinan la fragmentacin son mutuamente exclusivos. En fragmentacin derivada, sin embargo, implica un semi-yunto que aade complejidad al asunto. disyuncin puede garantizarse si el grafo de yunto es simple. Si no es simple, ser necesarinvestigar los valores de las tuplas. En general, no se desea juntar una tupla de una relacin miem

con dos o ms tuplas de una relacin propietaria cuando estas tuplas se encuentran en fragmendiferentes a los de la propietaria. Esto no es fcil de establecer, e ilustra por qu los esquemas defragmentacin derivada que generan un grafo de yunto simple son siempre ms atractivos.

FRAGMENTACINVERTICAL:

Introduccin



33/43

Bases de Datos II

Recurdese que la fragmentacin vertical de una relacinR produce una serie de fragmentosR 1,R 2 , ..., R r , cada uno de los cuales contiene un subconjunto de los atributos deR as como la clave primaria deR . El objetivo de la fragmentacin vertical consiste en dividir la relacin en un conjunto drelaciones ms pequeas tal que algunas de las aplicaciones de usuario slo hagan uso de un fragmenSobre este marco, una fragmentacin ptima es aquella que produce un esquema de divisin qminimiza el tiempo de ejecucin de las aplicaciones que emplean esos fragmentos.

La particin vertical resulta ms complicada que la horizontal. Esto se debe al aumento del nm

total de alternativas que tenemos disponibles. Por ejemplo, en la particin horizontal, si el nmero tota predicados simples dePr es n, existen 2n predicados mintrminos posibles que puedan definirse. Adems,sabemos que algunos de estos predicados resultarn contradictorios con algunas de las aplicacionexistentes, por lo que podremos reducir el nmero inicial. En el caso vertical, si una relacin tienematributos clave no primarios, el nmero de posibles fragmentos es igual aB(m), es decir el m-simonmero de Bell [3]. Para valores grandes dem, B(m) mm; por ejemplo, param = 10,B(m) 115.000, param= 15,B(m) 109, param = 30,B(m) = 1023.

Estos valores indican que la obtencin de una solucin ptima de la fragmentacin verticresultar una tarea intil, sino nos apoyamos en el uso de heursticos. Existen dos enfoques heursti para la fragmentacin vertical de relaciones:

1. Agrupacin . Comienza asignando cada atributo a un fragmento, y en cada paso, junta algunos de lfragmentos hasta que satisface un determinado criterio. La agrupacin sugiri en principio para bade datos centralizadas y se us posteriormente para las bases de datos distribuidas.

2. Escisin . A partir de la relacin se deciden que fragmentos resultan mejores, basndose en la

caractersticas de acceso de las aplicaciones a los atributos. Esta tcnica se present, tambin, p bases de datos centralizadas. Posteriormente, se extendi al entorno distribuido.



34/43

Bases de Datos II

En este documento se tratar nicamente la tcnica de escisin, ya que es ms apropiada paraestrategia descendente y porque resulta ms probable encontrar la solucin para la relacin entera qu partir de un conjunto de fragmentos con un nico atributo. Adems, la escisin genera fragmentossolapados mientras que la agrupacin normalmente produce fragmentos solapados. Dentro del contede los sistemas de bases de datos distribuidos, son preferibles los fragmentos no solapados por razoobvias. Evidentemente, los fragmentos no solapados se refieren nicamente a atributos clave primarios.

Antes de comenzar, vamos a aclarar un problema: la rplica de las claves de la relacin en lfragmentos. Esta es una caracterstica de la fragmentacin vertical que permite la reconstruccin drelacin global. Por tanto, la escisin considera nicamente aquellos atributos que no son parte de la c primaria.

La rplica de los atributos clave supone una gran ventaja, a pesar de los problemas que puecausar. La ventaja est relacionada con el esfuerzo para mantener la integridad semntica. Tengacuenta que cada dependencia (funcional, multivaluada ...) es, de hecho, una restriccin que influye so

el valor de los atributos de las respectivas relaciones en todo momento. Tambin muchas de esdependencias implican a los atributos clave de una relacin. Si queremos disear una base de datosque los atributos clave sean parte de una fragmento que est ubicado en un sitio, y los atributrelacionados sean parte de otro fragmento asignado a un segundo sitio, cada peticin de actualizac provocar la verificacin de integridad que necesitar de una comunicacin entre esos sitios. La rpliclos atributos clave de cada fragmento reduce esta problemtica, pero no elimina toda su complejidadque la comunicacin puede ser necesaria para las restricciones de integridad que implican a las cla primarias, as como para el control de concurrencia.

Una posible alternativa a la rplica de los atributos clave es el empleo de identificadores de tuplque son valores nicos asignados por el sistema a las tuplas de una relacin. Mientras el sistemmantenga los identificadores, los fragmentos permanecern disjuntos.



35/43

Bases de Datos II

Informacin necesaria para la fragmentacin vertical

La principal informacin que necesitaremos se referir a las aplicaciones. Por tanto, este puntratar de especificar la informacin que de una aplicacin que funciona sobre la base de datos podamextraer. Teniendo en cuenta que la fragmentacin vertical coloca en un fragmento aquellos atributos aque se accede de manera simultnea, necesitaremos alguna medida que defina con ms precisinconcepto de simultaneidad. Esta medida es la afinidad de los atributos, que indica la relacin estre

existente entre los atributos. Desgraciadamente, no es muy realista esperar que el diseador o los usua puedan especificar estos valores. Por ello, presentaremos una forma por la cual obtengamos esos valo partiendo de datos ms bsicos.

El principal dato necesario relativo a las aplicaciones es la frecuencia de acceso. SeaQ = {q1,q2 , ..., q q} el conjunto de consultas de usuario (aplicaciones) que funcionan sobre una relacinR(A1,

A2 , ..., A n).

Los vectores uso(qi,) pueden definirse muy fcilmente para cada aplicacin siempre que diseador conozca las aplicaciones existentes en el sistema. La regla 80/20 expuesta pginas atrs poresultar til para el desarrollo de esta tarea.

Los valores del uso de los atributos en general no son suficientes para desarrollar la base deescisin y la fragmentacin de los atributos, ya que estos valores no representan el peso de las frecuende la aplicacin. La dimensin de esta frecuencia puede incluirse en la definicin de la medida de atributos afinesafd ( A i , A j ), la cual mide el lmite entre dos atributos de una relacin de acuerdo a cmo la

aplicaciones acceden a ellos.



36/43

Bases de Datos II

FRAGMENTACIN MIXTA O HBRIDA:

En muchos casos la fragmentacin vertical u horizontal del esquema de la base de datos no ssuficiente para satisfacer los requisitos de las aplicaciones. Como ya se cit al comienzo de edocumento podemos combinar ambas, utilizando por ello la denominada fragmentacin mixta. Cuand proceso de fragmentacin vertical le sigue una horizontal, es decir, se fragmentan horizontalmentefragmentos verticales resultantes, se habla de la fragmentacin mixta HV. En el caso contrario, estaremante una fragmentacin VH. Una caracterstica comn a ambas es la generacin de rboles qrepresentan la estructura de fragmentacin (vea la figura 8).

Considere, por ejemplo, la relacin PROVINC. Recordar que se le aplic una fragmentacihorizontal de acuerdo al valor del atributo CCODZONA resultando cuatro fragmentos horizontalPodramos pensar en aplicarle una nueva fragmentacin de carcter vertical. Entonces resultaran cufragmentos horizontales divididos, por ejemplo, en dos fragmentos verticales. En este caso el nmtotal de fragmentos ascendera, lgicamente, a ocho.



37/43

Bases de Datos II

Figura 8. Estructura arbrea de fragmentacin mixta.

No se desea entrar en excesivos detalles sobre las reglas y condiciones para efectuar fragmentacin mixta. Entre otras razones porque, tanto a la fragmentacin HV como la fragmentacVH, se le pueden aplicar los mismos criterios y reglas que a la fragmentacin horizontal y verticaldecir, volviendo al ejemplo anterior, al cual le practicamos la fragmentacin HV, al realizar fragmentacin horizontal tal como se ha expuesto, lo que se obtienen no son ms que subrelacionesunin de las cuales da lugar a la relacin PROVINC. Por tanto, para fragmentar cada subrelacin s perfectamente viable aplicarle el mtodo de fragmentacin vertical que se ha desarrollado. Como, en caso, se han querido generar dos fragmentos verticales por cada uno horizontal, simplemente deberamconfeccionar la matriz de grupos afines (a travs del algoritmoBEA) para cada fragmento horizontal yaplicarle, posteriormente, el algoritmo de fragmentacin binaria PARTICIN.

Tambin debe tenerse en cuenta el nmero de niveles arbreos que se generen, es decir, nadimpide que tras realizar una fragmentacin VH, podamos aplicar a los fragmentos resultantes una nufragmentacin vertical, y a estos ltimos una nueva fragmentacin horizontal, etc. Dicho nmero puser grande, pero tambin ser ciertamente finito. En el caso horizontal, el nivel mximo de profundidaalcanzar cuando cada fragmento albergue una nica tupla, mientras que en el caso vertical el final llecuando cada fragmento contenga un nico atributo. Sin embargo, aunque no deba tomarse como dogel nmero de niveles no debera superar el par (VH y HV). El porqu de esta afirmacin es bien senci piense, por ejemplo, en el coste que supondra realizar la unin o el yunto de una relacin cfragmentacin nivel 7. Evidentemente, el coste sera muy elevado y ese aumento de rendimiento que persigue al aplicar estas tcnicas, quizs, no se produzca.

Antes de pasar a estudiar el problema de la asignacin se desea comentar la tcnica dfragmentacin mixta basada en celdas [2]. Esta tcnica se basa en la generacin de celdas de rejilla. Qes una celda de rejilla, podramos definirla como un fragmento horizontal y vertical simultneo.



38/43

Bases de Datos II

tcnica aplica un algoritmo de fragmentacin vertical y otro horizontal de manera concurrente sobrrelacin. Los algoritmos realizan una fragmentacin mxima, es decir, se persigue que en cada cenicamente haya un atributo y una tupla. Quiz el lector pueda encontrar el mtodo contradictorio cocitado anteriormente respecto a la eficiencia, dada la gran cantidad de fragmentos generados, el nmes, efectivamente, el mximo. Sin embargo, este slo es el primer paso del proceso. Una vez generalas celdas se aplica un mtodo para optimizar la rejilla mediante fusin o desfragmentacin, de acuerfundamentalmente, a las aplicaciones que acten sobre esos fragmentos. El mtodo, por tanto, persiuna fragmentacin los ms especfica posible acorde con las aplicaciones y los sitios existentes en la re

Informacin necesaria

En esta etapa de la asignacin, necesitaremos datos cuantitativos sobre la base de datos, laplicaciones que funcionan sobre ella, la red de comunicaciones, las caractersticas de proceso, y el lmde almacenamiento de cada sitio de la red. Procederemos a discutirlos en detalle.

Informacin de la base de datos . Para desarrollar la fragmentacin horizontal, definimos la

selectividad de los mintrminos. Ahora, necesitamos extender esta definicin a los fragmentos y definselectividad de un fragmentoF j con respecto a una consultaq i . Es el nmero de tuplas deF j a las que senecesita acceder para procesar q i . Este valor lo notaremos comosel i (F j ). Otro elemento informativo de losfragmentos de la base de datos es su tamao. El tamao de un fragmentoF j viene dado por tamao (F j ) =card (F j )*long (F j ), donde long(Fj) es la longitud (en octetos) de una tupla del fragmento Fj.

Informacin de los sitios . Sobre cada ordenador necesitamos conocer sus capacidades de procesamiento y almacenamiento. Obviamente, estos valores pueden calcularse a travs de funcio

elaboradas o por simples estimaciones. La unidad de coste de almacenar datos en el sitioS k ser denotadacomoUCAk . As mismo, especificaremos como medida de costeUPT k al coste de procesar una unidad de



39/43

Bases de Datos II

trabajo en el sitioS k . La unidad de trabajo debera ser idntica a aquella utilizada en las medidasRR yUR .

Informacin sobre la red. En nuestro modelo asumiremos la existencia de una red simple dondeel coste de comunicaciones se define respecto a una trama de datos. Entoncesg ij nota el coste decomunicacin por trama entre los sitiosS i y S j . Para permitir el clculo del nmero de mensajes,usaremosf tamao como el tamao (en octetos) de una trama. Es evidente que existen modelos de remucho ms elaborados que toman en cuenta las capacidades del canal, las distancias entre sitios,

caractersticas del protocolo, etc. Sin embargo, se cree que la derivacin de estas ecuaciones se sale fude este documento.

PROCESAMIENTO DISTRIBUIDO DE CONSULTAS

Existen varios medios para calcular la respuesta a una consulta. En el caso de sistemcentralizado, el criterio principal para determinar el costo de una estrategia especifica es el nmeroaccesos al disco. En un sistema distribuido es preciso tener en cuenta otros factores, como son:

El costo de transmisin de datos en la red. El beneficio potencial que supondra en la ejecucin el que varias localidades procesaran en paral

partes de la consulta.

El costo relativo de la transferencia de datos en la red y la transferencia de datos entre la memoy el disco varia en forma considerable, dependiendo del tipo de red y de la velocidad de los discos. tanto, en un caso general, no podemos tener en cuenta solo los costos del disco o los de la red. necesario llegar a un equilibrio adecuado entre los dos.



40/43

Bases de Datos II

Repeticin y fragmentacin

Considere una consulta muy sencilla: encontrar todas las tuplas de la relacin depsito. Aunqueconsulta es muy simple, de hecho es trivial; su procesamiento no es trivial, ya que es posible querelacin depsito est fragmentada, repetido o las dos cosas, como ya se vio. Si la relacin deposito repetida, es preciso decidir qu copia se va a utilizar. Si ninguna de las copias est fragmentada, se ela copia que implique costos de transmisin ms reducidos. Pero si una copia est fragmentada,eleccin no se tan sencilla, ya que es preciso calcular varios productos o uniones para reconstruir

relacin depsito. En tal caso, el nmero de estrategias para este ejemplo sencillo puede ser grande.hecho, la eleccin de una estrategia puede ser una tarea tan compleja como hacer una consulta arbitrar

Procesamiento de interseccin simple

Considere la expresin en lgebra relacional:

cliente x deposito x sucursal

Suponemos que ninguna de las tres relaciones est repetida o fragmentada y que cliente esalmacenada en la localidad Lc, deposito en la Ld y sucursal en la L b. Sea Li la localidad donde se origin laconsulta. El sistema debe producir el resultado en la localidad Li. Entre las posibles estrategias para procesar esta consulta se encuentran las siguientes:

Enviar copias de las tres relaciones a la localidad Li. Al emplear las tcnicas de procesamiento deconsulta, escoger una estrategia para procesar en forma local la consulta completa en Li.

Enviar una copia de la relacin cliente a la localidad Li y calcular cliente x depsito de Ld. Enviar cliente x depsito de Ld a L b, donde se calcula (cliente x depsito) x sucursal. El resultado de estaoperacin es enviado a Li.



41/43

Bases de Datos II

Pueden elaborarse estrategias similares a la anterior al intercambiar los papeles de Lc, Ld y L b.

No puede garantizarse que una estrategia sea la mejor en todos los casos. entre los factores qdeben tomarse en cuenta estn la cantidad de datos que debe transmitirse, el costo de transmitir un blode datos entre dos localidades determinadas y la velocidad de procesamiento relativa en cada localidad

Estrategias de interseccin utilizando el paralelismo

Considere un producto de cuatro relaciones:

r1 x r2 r3 r4

donde la relacin r1 est almacenada en la localidad Li. Suponemos que el resultado ha de presentarse en la localidad Li. Existen, por supuesto muchas estrategias que se pueden considerar. Unmtodo atractivo sera utilizar la estrategia de interseccin encauzada. Por ejemplo, se puede enviar rL2 y calcular r 1 x r 2 en L2. al mismo tiempo se puede enviar r 3 a L4 y calcular r 3 x r 4 en L4.

La localidad L2 puede enviar tuplas de (r 1 x r 2) a Li conforme se vayan produciendo, en vez deesperar a que se calcule el producto completo. De forma similar, L4 pude enviar tuplas de (r 3 x r 4) a Li.Una vez que las tuplas de (r 1 x r 2) y (r 3 x r 4) lleguen a Li, esta localidad podr empezar el clculo de (r 1x r 2) x (r 3 x r 4) en paralelo con el clculo de (r 1 x r 2) en L2 y de (r 3 x r 4) en L4.

Estrategia de seminterseccin

Suponer que deseamos calcular la expresin r 1 x r 2, donde r 1 y r 2 estn almacenados en laslocalidades L1 y L2 respectivamente. Sean R 1 y R 2 los esquemas de r 1 y r 2. Suponer que queremos obtener el resultado en L1. Si hay muchas tuplas de r 2 que no interseccionan con ninguna de r 1, entonces el envo



42/43

Bases de Datos II

de r 2 a S1 requiere el envo de tuplas que no contribuyen al resultado. Es conveniente borrar tales tupantes de enviar los datos a L1, particularmente si los costos de la red son muy elevados.

Para hacerlo vemos la siguiente estrategia:

1. Calcular temp1 r1 r2 (r1) en L1.2. enviar temp1 de L1 a L2.3. Calcular temp2 r2 x temp1 en L2.

4. Enviar temp2 de L2 a L1.5. Calcular r 1 x temp2 en L1.

La estrategia anterior es ventajosa particularmente cuando en el producto participan relativame pocas tuplas de r 2. Es probable que suceda esta situacin si r 1 es el resultado de una expresin de lgebrarelacional que contenga la seleccin.

Esta estrategia es conocida como una estrategia de semiproducto, despus del operador

semiproducto, indicado por x, de lgebra relacional.

CONCLUSIONES Y CONSIDERACIONES:

A lo largo de este documento se ha intentado dar una visin global y genrica de los problemacaractersticas que contiene el diseo de una base de datos distribuida. Se ha hecho especial hincapilas tcnicas de fragmentacin horizontal y vertical a travs de mtodos y algoritmos muy frecuentes eliteratura referida al tema. Se espera que el lector no haya tenido demasiados problemas para



43/43

Bases de Datos II

comprensin, las tcnicas son sencillas y se ha procurado incluir distintos ejemplos para facilitarentendimiento. Igualmente, la puesta en prctica de los algoritmos, es decir, su codificacin, no es proceso complicado si se poseen nociones en el desarrollo de algoritmos. Piense, por ejemplo, que losalgoritmos de particin vertical presentados, no hacen ms que manipular matrices.

Tambin debera tenerse presente la existencia de enfoques de fragmentacin distintos posiblemente, ms complejos, pero se debe pensar que ms eficientes. Sean, por ejemplo, las tcnicafragmentacin vertical basadas en grafos, como el algoritmo de Navathe y Ra que genera en un solo p

fragmentos verticales. Adems, estn apareciendo mtodos de fragmentacin mixta como el que secomentado. Si bien, estos mtodos son enfoques formales ms que prcticos, desarrollados por insiginvestigadores en universidades, por tanto, lejos todava de su desarrollo comercial.

Pese a la aparicin de los mtodos de bases de datos distribuidas hace ya aos, parece que el sade lo centralizado a lo distribuido a escala comercial est por venir. Todava no se ha extendisuficientemente el esquema distribuido, pero se espera que prximamente se produzca el avandefinitivo. Considere los dos componentes bsicos de los sistemas de bases de datos distribuidos

propia base de datos y la red de ordenadores) y piense en la situacin actual de la informtica. Si las bde datos es una de las ramas ms antiguas e importantes de la informtica, muchas empresas compordenadores para dedicarlos exclusivamente a la gestin de sus datos (pienso que, prcticamente, en100% de las PYMES se produce este hecho) y, como parece ser que se ha asumido por parte de todo tde empresarios los beneficios que acarrea la conexin de los ordenadores, la instalacin de una red puede concluir diciendo que el terreno ya est abonado para su extensin comercial. Slo falta qdeterminadas multinacionales decidan apostar ms fuerte por este enfoque a travs de sus famosistemas gestores de bases de datos y que se produzca la consolidacin de la resolucin de los problem

que el enfoque distribuido acarrea.

Documents

Bases Distribuidas