Procesamiento de la Fragmentación de Datos
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 y Fragmentación Vertical
Reglas a Cumplir por Fragmentación
En el ejemplo la calificación de la fragmetación hecha a S, 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
Si todas las calificaciones de los fragmentos son mutuamente exclusivas, es decir, si al aplicar las calificaciones se producen fragmentos que al intersectarlos generan un conjunto vacio.
F = F1 INTERSECT F2 INTERSECT ..
INTESECT Fn
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).
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.
Fragmentación Híbrida: Consiste en aplicar las operaciones de fragmentación vistas anteriormente de manera recursiva, satisfaciendo las condiciones de correctés 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:
E1 = Ex[Emp#, Nombre, #Jefe,Dept#] Where Dept# <10
E2 = Ex[Emp#, Nombre, #Jefe,Dept#] Where Dept# >=10 And Dept# <=20
E3 = Ex[Emp#, Nombre, #Jefe,Dept#] Where Dept# >20
E4 = E[Emp#, Salario, Impto]
La fragmentación básicamente se puede hacer de dos formas: Fragmentación Horizontal y Fragmentación Vertical
Reglas a Cumplir por Fragmentación
- Condición de Completés.
- Todos los datos de la relación global deberán ser mapeados a algún fragmento.
- Condición de Reconstrucción.
- Deberá ser siempre posible reconstruir la relación global a partir de sus fragmentos.
- Condición de Conjuntos Disjuntos.
- Es conveniente que los fragmentos sean disjuntos.
En el ejemplo la calificación de la fragmetación hecha a S, 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
Si todas las calificaciones de los fragmentos son mutuamente exclusivas, es decir, si al aplicar las calificaciones se producen fragmentos que al intersectarlos generan un conjunto vacio.
F = F1 INTERSECT F2 INTERSECT ..
INTESECT Fn
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).
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.
Fragmentación Híbrida: Consiste en aplicar las operaciones de fragmentación vistas anteriormente de manera recursiva, satisfaciendo las condiciones de correctés 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:
E1 = Ex[Emp#, Nombre, #Jefe,Dept#] Where Dept# <10
E2 = Ex[Emp#, Nombre, #Jefe,Dept#] Where Dept# >=10 And Dept# <=20
E3 = Ex[Emp#, Nombre, #Jefe,Dept#] Where Dept# >20
E4 = E[Emp#, Salario, Impto]
Procesamiento de Consulta Distribuida
Las consultas distribuidas detienen acceso a datos de varios orígenes de datos heterogéneos. Estos orígenes de datos pueden estar almacenados en el mismo equipo o en equipos diferentes.
El procesamiento de consultas tiene varias etapas a seguir para resolver una consulta SQL, las características del modelo relacional permiten quecada motor de base de datos elija su propia representación que,comúnmente, resulta ser el álgebra relacional .Existen varios medios para calcular la respuesta a una consulta. En el caso del sistema centralizado, el criterio principal para determinar el costo de una estrategia específica es el número de acceso al disco. En un sistema distribuido es preciso tener en cuenta otros factores como son:
- El costo de transmisión de datos en la red.
- Repetición y fragmentación.
- Procesamiento de intersección simple.
Características de los procesadores de consultas
Comparar un sistema centralizado con uno distribuido es una tarea complicada ya que ambos difieren en una gran cantidad de aspectos, desde su arquitectura hasta la forma de tratar una consulta. Vamos a enumerar las principales características de los procesadores de consultas distribuidas y que los diferencias de los procesadores de los sistemas centralizados:
- Tipo de optimización.
- Granularidad de la optimización.
- Tiempo de optimización
- Estadísticas
- Nodos de decisión.
- Topología de la red
Arquitectura del procesamiento de consultas
El procesamiento de consultas distribuidas podemos separarlo en cuatro fases o niveles, desde que la consulta llega hasta que se optimiza al máximo posible:
- Descomposición de consultas.
- Localización de datos.
- Optimización global de consultas.
- Optimización local de consultas.
ARBOLES DE CONSULTAS
Pasos:
- Parsing y traducción de la consulta
- Optimización
- Generación de código
- Ejecución de la consulta
TRANSFORMACIONES EQUIVALENTES
Cuando una base de datos se encuentra en múltiples servidores y distribuye a un número determinado de nodos tenemos:
- El servidor recibe una petición de un nodo.
- El servidor es atacado por el acceso concurrente a la base de datos cargada localmente.
- El servidor muestra un resultado y le da un hilo a cada una de las maquinas nodo de la red local.
Cuando una base de datos es acezada de esta manera la técnica que se utiliza es la de fragmentación de datos que puede ser hibrida, horizontal y vertical. En esta fragmentación lo que no se quiere es perder la consistencia delos datos, por lo tanto se respetan las formas normales de la base de datos.
Para realizar una transformación en la consulta primero desfragmentamos siguiendo los estándares marcados por las reglas formales y posteriormente realizamos el envió y la maquina que recibe es la que muestra el resultado pertinente para el usuario, de esta se puede producir una copia que será la equivalente a la original.
Métodos de ejecución del join
- join: Existen diferentes algoritmos que pueden obtener transformacioneseficientes en el procesamiento de consultas.
- Join en bucles (ciclos) anidados: Si z = r s, r recibirá el nombre de relación externa y s se llamará relación interna, el algoritmo de bucles anidados se puede presentar como sigue: Para cada tupla tr en s si (tr,ts) si satisface la condición, entonces añadir tr * ts al resultado Donde tr * ts será la concatenación de las tuplas tr y ts. Como para cada registro de r se tiene que realizar una exploración completa de ts, y suponiendo el peor caso, en el cual la memoria intermedia sólo puede concatenar un bloque de cada relación, entonces el número de bloques a acceder es de sr bn b. Por otro lado, en el mejor de los casos si se pueden contener ambas relaciones en la memoria intermedia entonces sólo se necesitarían accesos a bloques.
- Join en bucles anidados por bloques: Una variante del algoritmo anterior puede lograr un ahorro en el acceso a bloques, si se procesan las relaciones por bloques en vez de por tuplas. Para cada bloque Br dar a igual para cada bloque Bs de s, para cada tupla tr en Br. La diferencia principal en costos de este algoritmo con el anterior es que en el peor de los casos cada bloque de la relación interna s se lee una vez por cada bloque de dr y no por cada tupla de la relación externa.
- Join por mezcla: Este algoritmo se puede utilizar para calcular si un Join natural es óptimo en la búsqueda o consulta. Para tales efectos, ambas relaciones deben estar ordenadas para los atributos en común es decir se asocia un puntero a cada relación, al principio estos punteros apuntan al inicio de cada una de las relaciones. Según avance el algoritmo el puntero se mueve a través de la relación. De este modo se leen en memoria un grupo de tuplas de una relación con el mismo valor en los atributos de las relaciones.
- Join por asociación:Al igual que el algoritmo de join por mezcla, el algoritmo de join por asociación se puede utilizar para un Join natural o un equi-join. Este algoritmo utiliza una función de asociación h para dividir las tuplas de ambas relaciones. La idea fundamental es dividir las tuplas de cada relación en conjuntos con el mismo valor de la función de asociación en los atributos de join.
- Join por asociación híbrida: El algoritmo de join por asociación híbrida realiza otra optimización; es útil cuando el tamaño de la memoria es relativamente grande paro aún así, no cabe toda la relación s en memoria. Dado que el algoritmo de join por asociación necesita max +1 bloques de memoria para dividir ambas relaciones se puede utilizar el resto de la memoria (M – max – 1 bloques)para guardar en la memoria intermedia la primera partición de la relación s, esto es, así no es necesaria leerla ni escribirla nuevamente y se puede construir un índice asociativo.
- Join Complejos:Los join en bucle anidado y en bucle anidado por bloques son útiles siempre, sin embargo, las otras técnicas de join son más eficientes que estas, pero sólo se pueden utilizar en condiciones particulares tales como join natural o equi-join. Se pueden implementar join con condiciones más complejas tales como conjunción o disyunción Dado un join de las forma se pueden aplicar una o más de las técnicas de join descritas anteriormente en cada condición individual, el resultado total consiste en las tuplas del resultado intermedio que satisfacen el resto de las condiciones. Estas condiciones se pueden ir comprobado según se generen las tuplas. La implementación de la disyunción es homóloga a la conjunción.
- Outer Join (Join externos): Un outer join es una extensión del operador join que se utiliza a menudo para trabajar con la información que falta.
Por ejemplo:Suponiendo que se desea generar una lista con todos los choferes y los autos que manejan (si manejan alguno) entonces se debe cruzar la relación Chofer con la relación Móvil. Si se efectúa un join corriente se perderán todas aquellas tuplas que pertenecen a los choferes, en cambio con un outer join se pueden desplegar las tuplas resultado incluyendo a aquellos choferes que no tengan a cargo un auto.
A continuación se presenta un video del tema:
Conclusión.
Nos va ayudar a no solo conocer las características, si no a una mejor toma de decisiones y organización de los datos, tanto a la hora del diseño como cuando se muestra a los usuarios finales.
Comentarios
Publicar un comentario