Esquema de fragmentación y Distribucion de BDD

Integrantes: 

Navarrete Marcos

Ibarra Milton

 

Esquema de fragmentación y Distribucion de BDD

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.

Cada relación global puede ser dividida en porciones que no se solapen llamados fragmentos. El mapa resultante se denomina esquema de fragmentación. Una relación global puede dividirse en n fragmentos y un fragmento sólo puede pertenecer a una relación global.

El problema de fragmentación se refiere al particionamiento de la información para distribuir cada parte a los diferentes sitios de la red. 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.

Tipos de fragmentación:
  Vertical

  Horizontal

  Mixta

Fragmentación vertical

Una fragmentación vertical de una relación R produce fragmentos R₁, R₂, ..., R_r, 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:

1. Agrupamiento. Inicia asignando cada atributo a un fragmento, y en cada paso, algunos de los fragmentos satisfaciendo algún criterio se unen para formar un solo fragmento.
2. División. Inicia con una sola relación realizar un particionamiento basado en el comportamiento de acceso de las consultas sobre los atributos.

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 = { q₁, q₂, ..., q_q } que serán aplicadas a la relación R[A₁, A₂, ..., A_n], se define la función

Los vectores use( q_i, · ) son fáciles de definir si el diseñador conoce las aplicaciones que serán ejecutadas en la base de datos.

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( A₁, A₂, …, A_n), donde A_i es un atributo definido sobre el dominio D_i, un predicado simple p_j definido en R tiene la forma

p_j: A_i q Valor

donde q Î { =, <, ¹ , £ , >, ³ } y Valor Î D_i. Para la relación R se define un conjunto de predicados simples como Pr = { p₁, p₂, …, p_m }.

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 = { p₁, p₂, …, p_m }, se define el conjunto de predicados minitérmino como M = { m₁, m₂, …, m_r } como

M = { m_i | m_i = Ù _{pj Î Pr} p_j*}, 1 £ j £ m, 1 £ i £ z

donde, p_j* = p_j o p_j* = Ø (p_j).

Ejemplo 3.8. Los siguientes son minitérminos de la relación J.

m₁: JNOMBRE == "Mantenimiento" Ù Presupuesto £ 200000

m₂: NOT( JNOMBRE == "Mantenimiento") Ù Presupuesto £ 200000

m₃: JNOMBRE == "Mantenimiento" Ù NOT (Presupuesto £ 200000)

m₄: 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:

1. La selectividad de los minitérminos: Denotada como sel( m_i ), se refiere al número de tuplos de la relación que serán accesadas por una consulta de usuario especificada de acuerdo a un predicado minitérmino dado.
2. La frecuencia de acceso: Denotada como acc( q_i ), se refiere a la frecuencia con la cual una consulta de usuario q_i es accesada en un periodo de tiempo. Note que las frecuencias de acceso de minitérminos se pueden determinar a partir de las frecuencias de consultas. La frecuencia de acceso de un minitérmino se denota como acc( m_i ).

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

R_j = s _Fj (R), 1 £ j £ w

donde, F_j es una fórmula de selección, la cual es preferiblemente un predicado minitérmino. Por lo tanto, un fragmento horizontal R_i de una relación R consiste de todos los tuplos de R que satisfacen un predicado minitérmino m_i. 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 = { R₁, R₂, …, R_m } 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 J_i 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.

Fragmentación mixta o híbrida:

En muchos casos la fragmentación vertical u horizontal del esquema de la base de datos no será suficiente para satisfacer los requisitos de las aplicaciones. Como ya se citó al comienzo de este documento podemos combinar ambas, utilizando por ello la denominada fragmentación mixta. Cuando al proceso de fragmentación vertical le sigue una horizontal, es decir, se fragmentan horizontalmente los fragmentos verticales resultantes, se habla de la fragmentación mixta HV. En el caso contrario, estaremos ante una fragmentación VH. Una característica común a ambas es la generación de árboles que representan la estructura de fragmentación (vea la figura 8).

Considere, por ejemplo, la relación PROVINC. Recordará que se le aplicó una fragmentación horizontal de acuerdo al valor del atributo CCODZONA resultando cuatro fragmentos horizontales. Podríamos pensar en aplicarle una nueva fragmentación de carácter vertical. Entonces resultarían cuatro fragmentos horizontales divididos, por ejemplo, en dos fragmentos verticales. En este caso el número total de fragmentos ascendería, lógicamente, a ocho.

Software Utilizado en Base de Datos Distribuidas

Los programas de bases de datos organizan y almacenan los datos de manera tal que las tablas están indexadas y se pueden contestar preguntas. Estas herramientas están disponibles en un número de configuraciones diferentes y escalables para ser usadas por un individuo o una corporación global. Algunos son fáciles de usar, con bases de datos a manera de interfaz visual, mientras que otras, al final del espectro empresarial, requieren entrenamiento y herramientas especializadas para ser útiles.

Access

Access es un sistema de base de datos personal de Microsoft. Se trata de un producto de software orientado hacia lo visual, lo que hace que quienes no sean programadores puedan crear bases de datos útiles con facilidad. Si bien la estructura de base de datos Access puede ampliarse para satisfacer las necesidades empresariales, el uso más común de esta base de datos es para pequeñas bases de datos individuales o en programas multiusuario de uso limitado. Access integra el lenguaje Visual Basic para aplicaciones, por lo que es un entorno de desarrollo completo.

Visual FoxPro

FoxPro es un sistema de base de datos relacional, también producido por Microsoft, que está estrechamente unido a su lenguaje de programación. FoxPro es menos amigable que las bases de datos de usuario final, lo que requiere más conocimientos técnicos que Access. Este sistema de base de datos es conocido por su motor de procesamiento rápido y la capacidad de manejar numerosas transacciones simultáneas.

MySQL Database

MySQL es una base de datos basada en servidor que permite a varios usuarios acceder a múltiples bases de datos. El software funciona en múltiples plataformas, incluyendo la mayoría de las variedades de UNIX y Windows. Ofrece usabilidad de primer plano limitada y está diseñado como un servidor de base de datos back-end. MySQL se diferencia de otros productos de base de datos por sus costos, la versión no empresarial se distribuye de forma gratuita.

SQL Server

SQL Server es un servidor de base de datos a nivel empresarial escalable. Este producto se diferencia de la base de datos personal al no proporcionar las herramientas para el usuario que proporciona un producto de base de datos individual. El motor de base de datos se centra en responder rápidamente a las solicitudes del cliente en el formulario de consultas SQL. Estas consultas se pueden generar directamente en SQL Server, o por medio de una interfaz de usuario independiente desarrollada en una variedad de lenguajes de programación. SQL Server está diseñado para manejar bases de datos con millones de registros.

Oracle

La base de datos Oracle es otra base de datos escalable a nivel empresarial. La base de datos de SQL soporta bases de datos corporativas distribuidas, que permiten al usuario acceder a los datos de forma local o desde bases de datos remotas en una transacción transparente. Las bases de datos distribuidas ayudan a superar las limitaciones físicas de un entorno informático físico. El tamaño máximo de base de datos para una base de datos Oracle es de 8 millones de terabytes, lo que requiere un almacenamiento físico más allá de la capacidad de la mayoría de las instalaciones individuales.

Aplicaciones de bases de datos distribuidas

Los ambientes en los que se encuentra el uso de las BDD son:

·        Cualquier organización que tiene una estructura descentralizada: organismos gubernamentales y de servicios públicos.

·        La industria de la manufactura, particularmente aquella con plantas múltiples, y la industria automotriz.

·        Aplicaciones de control y comando militar.

·        Cadenas hoteleras.

·        Líneas de transportación aérea.

·        Servicios bancarios y financieros.

Ejemplos de algunos DDBMS:

Prototipos

•       SDD-1, que fue construido en la división de investigación de Computer Corporation of America.

–       Finales de los años 70 y principios de los 80.

•       R*, una versión distribuida del prototipo System R, construida en IBM Research

–       Principios de los años 80

•       Distributed Ingres, una versión distribuida del prototipo Ingres, construida en la Universidad de California en Berkeley

–       Principios de los 80

Implementaciones comerciales:

•       La mayoría de los productos SQL actuales proporcionan algún tipo de soporte de BDD (con diversos grados de funcionalidad).

–       Ingres/Star, el componente de BDD de Ingres

–       La opción de BDD de Oracle

–       La propiedad de datos distribuidos de DB2

•       Tanto los DDBMS prototipos como los productos, son relacionales (al menos todos soportan SQL).

•       Además, hay varias razones por las cuales, para que un sistema distribuido sea exitoso, debe ser relacional.

• La tecnología relacional es un requisito previo para tecnología distribuida.