Actividad 18

Actividad #18 

Investigar, Analizar y comprobar los algoritmos de control de concurrencia, tales como: los basados en bloqueo,los basados en estampas de tiempo y las pruebas de validación optimistas. Presentando sus resultados en clase y publicados en el blog

Control de concurrencia

El control de concurrencia trata con los problemas de aislamiento y consistencia del procesamiento de transacciones. El control de concurrencia distribuido de una DDBMS asegura que la consistencia de la base de datos se mantiene en un ambiente distribuido multiusuario. Si las transacciones son internamente consistentes, la manera más simple de lograr este objetivo es ejecutar cada transacción sola, una después de otra. Sin embargo, esto puede afectar grandemente el desempeño de un DDBMS dado que el nivel de concurrencia se reduce al mínimo. El nivel de concurrencia, el número de transacciones activas, es probablemente el parámetro más importante en sistemas distribuidos. Por lo tanto, los mecanismos de control de concurrencia buscan encontrar un balance entre el mantenimiento de la consistencia de la base de datos y el mantenimiento de un alto nivel de concurrencia.

Si no se hace un adecuado control de concurrencia, se pueden presentar dos anomalías. En primer lugar, se pueden perder actualizaciones provocando que los efectos de algunas transacciones no se reflejen en la base de datos. En segundo término, pueden presentarse recuperaciones de información inconsistentes.

Algoritmos de control de concurrencia

El criterio de clasificación más común de los algoritmos de control de concurrencia es el tipo de primitiva de sincronización. Esto resulta en dos clases:

- Aquellos algoritmos que están basados en acceso mutuamente exclusivo adatos compartidos (candados o bloqueos).

- Aquellos que intentar ordenar la ejecución de las transacciones de acuerdo a un conjunto de reglas (protocolos).

Basados en estampas de tiempo

Los algoritmos basados en estampas de tiempo no pretenden mantener la seriabilidad por exclusión mutua. En lugar de eso, ellos seleccionan un ordende serialización a prioridad y ejecutan las transacciones, de acuerdo a ellas. Para establecer este ordenamiento, el administrador de transacciones le asigna a cada transacción T1 una estampa de tiempo única t1 (T1) cuando ésta inicia.Una estampa de tiempo es un identificador simple que sirve para identificar cada transacción de manera única.

A diferencia de los algoritmos basados en candados, los algoritmos basados en marcas de tiempono pretenden mantener la seriabilidad por la exclusión mutua. En su lugar eligen un orden deserializacion en primera instancia y ejecutan las transacciones de acuerdo a ese orden. Enestos algoritmos cada transacción lleva asociada una marca de tiempo. Cada dato lleva asociadodos marcas de tiempo: uno de lectura y otro de escritura, que reflejan la marca de tiempo de latransacción que hizo la ultima operación de ese tipo sobre el dato. Para leer la marca de tiempo de escritura del dato, debe ser menor que el de la transacción, si no aborta.Para escribir las marcas de tiempo de escritura y lectura del dato, deben ser menores que el de latransacción, sino se aborta. Estatécnica esta libre de Ínterbloqueos pero puede darse que halla que repetir varias veces latransacción. En los sistemas distribuidos se puede usar un mecanismo como, los relojes deLamport para asignar marcas de tiempo.El conjunto de algoritmos pesimistas esta formado por algoritmos basados en candados,algoritmos basados en ordenamiento por estampas de tiempo y algoritmos híbridos. Los algoritmosoptimistas se componen por los algoritmos basados en candados y algoritmos basados enestampas de tiempo.

De cerradura /Basados en candados

En los algoritmos basados en candados, las transacciones indican sus intenciones solicitando candados al despachador (llamado el administrador de candados) Los candados son de lectura , también llamados compartidos, o de escritura , también llamados exclusivos.

En sistemas basados en candados, el despachador es un administrador de candados . El administrador de transacciones le pasa al administrador de candados la operación sobre la base de datos (lectura o escritura) e información asociada, como por ejemplo el elemento de datos que es accesado y el identificador de la transacción que está enviando la operación a la base de datos. El administrador de candados verifica si el elemento de datos que se quiere accesar ya ha sido bloqueado por un candado. Si el candado solicitado es incompatible con el candado con que el dato está bloqueado, entonces, la transacción solicitante es retrasada. De otra forma, el candado se define sobre el dato en el modo deseado y la operación a la base de datos es transferida al procesador de datos. El administrador de transacciones es informado luego sobre el resultado de la operación. La terminación de una transacción libera todos los candados y se puede iniciar otra transacción que estaba esperando el acceso al mismo dato.

Se usan cerraduras o candados de lectura o escritura sobre los datos. Para asegurar la secuencialidad se usa un protocolo de dos fases, en la fase de crecimiento de la transacción se establecen los cerrojos y en la fase dedecrecimiento se liberan los cerrojos. Hay que tener en cuenta que se pueden producir ínterbloqueos. En los sistemas distribuidos el nodo que mantiene un dato se encarga normalmente de gestionar los cerrojos sobre el mismo.

Candados de dos fases :

En los candados de dos fases una transacción le pone un candado a un objeto antes de usarlo. Cuando un objeto es bloqueado con un candado por otra transacción, la transacción solicitante debe esperar. Cuando una transacción libera un candado, ya no puede solicitar más candados. En la primera fase solicita y adquiere todos los candados sobre los elementos que va a utilizar y en la segunda fase libera los candados obtenidos uno por uno. 

Puede suceder que si una transacción aborta después de liberar un candado, otras transacciones que hayan accesado el mismo elemento de datos aborten también provocando lo que se conoce como abortos en cascada. Para evitar lo anterior, los despachadores para candados de dos fases implementan lo que se conoce como loscandados estrictos de dos fases en los cuales se liberan todos los candados juntos cuando la transacción termina (con compromiso o aborta).

Candados de dos fases centralizados:

 En sistemas distribuidos puede que la administración de los candados se dedique a un solo nodo del sistema, por lo tanto, se tiene un despachador central el cual recibe todas las solicitudes de candados del sistema. La comunicación se presenta entre el administrador de transacciones del nodo en donde se origina la transacción , el administrador de candados en el nodo central y los procesadores de datos de todos los nodos participantes. Los nodos participantes son todos aquellos en donde la operación se va a llevar a cabo.

Candados de dos fases distribuidos:

En los candados de dos fases distribuidos se presentan despachadores en cada nodo del sistema. Cada despachador maneja las solicitudes de candados para los datos en ese nodo. Una transacción puede leer cualquiera de las copias replicada del elemento x, obteniendo un candado de lectura en cualquiera de las copias de x. La escritura sobre x requiere que se obtengan candados para todas las copias de x. Los mensajes de solicitud de candados se envían a todos los administradores de candados que participan en el sistema. Las operaciones son pasadas a los procesadores de datos por los administradores de candados. Los procesadores de datos envían su mensaje de "fin de operación" al administrador de transacciones coordinador.

Control Optimista de la concurrencia

Los algoritmos de control de concurrencia pesimistas asumen que los conflictos entre transacciones son muy frecuentes y no permiten el acceso a un dato si existe una transacción conflictiva que accesa el mismo dato. Así, la ejecución de cualquier operación de una transacción sigue la secuencia de fases: validación , lectura , cómputo y escritura. Los algoritmos optimistas, por otra parte, retrasan la fase de validación justo antes de la fase de escritura. De esta manera, una operación sometida a un despachador optimista nunca es retrasada.

Las operaciones de lectura, cómputo y escritura de cada transacción se procesan libremente sin actualizar la base de datos corriente. Cada transacción inicialmente hace sus cambios en copias locales de los datos. La fase de validación consiste en verificar si esas actualizaciones conservan la consistencia de la base de datos. Si la respuesta es positiva, los cambios se hacen globales (escritos en la base de datos corriente). De otra manera, la transacción es abortada y tiene que reiniciar

Lo que se hace es dejar ejecutar las transacciones y si al terminar se detecta que ha habido conflicto se aborta y se reinicia la transacción. 

Cada transacción tiene tres fases:

Fase de lectura: Cuerpo de la transacción donde se copian datos desde la base de datos, copias que pueden ser actualizadas pero sin copiar a la base de datos

Fase de validación: Se comprueba que no existan conflictos

 Fase de escritura: Si no existen conflictos se instalan lo cambios en la base de datos

Conflictos entre operaciones: Dos operaciones están en conflicto entre si cuando, operan sobre los mismos datos, una de las operaciones es de escritura, o cada operación pertenece a diferentes transacciones

Actividad 18

A) Presentación: https://drive.google.com/drive/folders/0B5A8Qtin-vCUc0E0UFltV0NjcFU/0B5A8Qtin-vCUQXNDcUhGNDVfWGM

B)Resumen:

Una transacción en un Sistema de Gestión de Bases de Datos (SGBD), es un conjunto de órdenes que se ejecutan formando una unidad de trabajo, es decir, en forma indivisible o atómica.

Un SGBD se dice transaccional, si es capaz de mantener la integridad de los datos, haciendo que estas transacciones no puedan finalizar en un estado intermedio. Cuando por alguna causa el sistema debe cancelar la transacción, empieza a deshacer las órdenes ejecutadas hasta dejar la base de datos en su estado inicial (llamado punto de integridad), como si la orden de la transacción nunca se hubiese realizado.

Para esto, el lenguaje de consulta de datos SQL (Structured Query Language), provee los mecanismos para especificar que un conjunto de acciones deben constituir una transacción.

· BEGIN TRAN: Especifica que va a empezar una transacción.

· COMMIT TRAN: Le indica al motor que puede considerar la transacción completada con éxito.

· ROLLBACK TRAN: Indica que se ha alcanzado un fallo y que debe restablecer la base al punto de integridad.

En un sistema ideal, las transacciones deberían garantizar todas las propiedades ACID; en la práctica, a veces alguna de estas propiedades se simplifica o debilita con vistas a obtener un mejor rendimiento.

Un ejemplo de transacción

Un ejemplo habitual de transacción es el traspaso de una cantidad de dinero entre cuentasbancarias. Normalmente se realiza mediante dos operaciones distintas, una en la que se decrementa el saldo de la cuenta origen y otra en la que incrementamos el saldo de la cuenta destino. Para garantizar la atomicidad del sistema (es decir, para que no aparezca o desaparezca dinero), las dos operaciones deben ser atómicas, es decir, el sistema debe garantizar que, bajo cualquier circunstancia (incluso una caída del sistema), el resultado final es que, o bien se han realizado las dos operaciones, o bien no se ha realizado ninguna.

ESTRUCTURA DE LAS TRANSACCIONES

La estructura de una transacción usualmente viene dada según el modelo de la transacción, estas pueden ser planas (simples) o anidadas.

Transacciones planas: Consisten en una secuencia de operaciones primitivas encerradas entre las palabras clave BEGIN y END.

Transacciones Anidadas: Consiste en tener transacciones que dependen de otras, estas transacciones están incluidas dentro de otras de un nivel superior y se las conoce como subtransacciones. La transacción de nivel superior puede producir hijos (subtransacciones) que hagan más fácil la programación del sistema y mejoras del desempeño.

En las transacciones anidadas las operaciones de una transacción pueden ser así mismo otras transacciones.

Fase de preparación

Cuando el administrador de transacciones recibe una solicitud de confirmación, envía un comando de preparación a todos los administradores de recursos implicados en la transacción. Cada administrador de recursos hace lo necesario para que la transacción sea duradera y todos los búferes que contienen imágenes del registro de la transacción se pasan a disco. A medida que cada administrador de recursos completa la fase de preparación, notifica si la preparación ha tenido éxito o no al administrador de transacciones.

Fase de confirmación

Si el administrador de transacciones recibe la notificación de que todas las preparaciones son correctas por parte de todos los administradores de recursos, envía comandos de confirmación a cada administrador de recursos. A continuación, los administradores de recursos pueden completar la confirmación. Si todos los administradores de recursos indican que la confirmación ha sido correcta, el administrador de transacciones envía una notificación de éxito a la aplicación. Si algún administrador de recursos informó de un error al realizar la preparación, el administrador de transacciones envía un comando para revertir la transacción a cada administrador de recursos e indica a la aplicación que se ha producido un error de confirmación.

Recuperación de transacciones distribuidas

· Para realizar la recuperación de transacción distribuida se asume que cada sitio tiene su propio manejador de transacción local (LTM).

· Cada agente utiliza de manera local las primitivas asociadas a sus transacciones. Podemos llamar a los agentes subtransacciones, lo cual origina distinguir las primitivas BEGIN-TRANSACTION, COMMIT Y ROLLBACK asociado a la transacción distribuida de la primitivas locales utilizada por

· cada agente en LTM; para poder distinguir una de las otras, a las ultimas les llamaremos:

· LOCAL-BEGIN, LOCAL-COMMIT Y LOCALROLLBACK.

· Para propósito del manejador de transacciones distribuidas (DTM), requieren que los LTM se conformen de la siguiente manera:

1. Asegurar la atomicidad de su transacción.

2. Grabar en bitácora por órdenes de la transacción distribuida.

Para asegurar que todas las acciones de una transacción distribuida son ejecutadas o no ejecutadas dos condiciones son necesarias:

· En cada sitio todas las acciones son ejecutadas o ninguna es ejecutada.

· Todos los sitios deberán tomar la misma decisión respecto al COMMIT o ROLLBACK de la transición global.

Actividad 17

Jueves, 30 de abril de 2015


Actividad #16 • Investigar estrategias de procesamiento de consulta distribuida y optimización de consultas distribuidas.
Publicar Miércoles 6 de Mayo

Estrategias de procesamiento de consultas

En las BDD se tiene que considerar el procesamiento local de una consulta junto con el costo de transmisión de información al lugar en donde se solicitó la consulta.

El éxito creciente de la tecnología de bases de datos relacionales en el procesamiento de datos se debe, en parte, a la disponibilidad de lenguajes los cuales pueden mejorar significativamente el desarrollo de aplicaciones y la productividad del usuario final

Ocultando los detalles de bajo nivel acerca de la localización física de datos, los lenguajes de bases de datos relacionales permiten la expresión de consultas complejas en una forma concisa y simple. 

Particularmente, para construir la respuesta a una consulta, el usuario no tiene que especificar de manera precisa el procedimiento que se debe seguir. Este procedimiento es llevado a cabo por un módulo del DBMS( Data Base Management System o Sistema Gestor de Base de Datos) llamado el procesador de consultas (query processor).

Dado que la ejecución de consultas es un aspecto crítico en el rendimiento de un DBMS, el procesamiento de consultas ha recibido una gran atención tanto para bases de datos centralizadas como distribuidas.

Sin embargo, el procesamiento de consultas es mucho más difícil en ambientes distribuidos que en centralizados, ya que existe un gran número de parámetros que afectan el rendimiento de las consultas

distribuidas. 

Transformaciones equivalentes

La función principal de un procesador de consultas relacionales es transformar una consulta en una especificación de alto nivel, típicamente en cálculo relacional, a una consulta equivalente en una especificación de bajo nivel, típicamente alguna variación del álgebra relacional

La consulta de bajo nivel implementa de hecho la estrategia de ejecución para la consulta. La transformación debe ser correcta y eficiente. Es correcta si la consulta de bajo nivel tiene la misma semántica que la consulta original, esto es, si ambas consultas producen el mismo resultado.

El mapeo bien definido que se conoce entre el cálculo relacional y el álgebra relacional hace que la correctitud de la transformación sea fácil de verificar. Sin embargo, producir una estrategia de ejecución eficiente es mucho más complicado. Una consulta en el cálculo relacional puede tener muchas transformaciones correctas y equivalentes en el álgebra relacional.

Ya que cada estrategia de ejecución equivalente puede conducir a consumos de recursos de cómputo muy diferentes, la dificultad más importante es seleccionar la estrategia de ejecución que minimiza el consumo de recursos.

Árboles de consultas

Existen distintos métodos para optimizar consultas relacionales, sin embargo el enfoque de optimización basada en costos combinado con heurísticas que permitan reducir el espacio de búsqueda de la solución es el método mayormente utilizado por los motores de base de datos relaciones de la actualidad, en todo caso, independiente del método elegido para optimizar la consulta, la salida de este proceso debe ser un plan de ejecución, el cual comúnmente es representado en su forma de árbol relacional.

 Optimización de consultas distribuidas

El objetivo del procesamiento de consultas en un ambiente distribuido es transformar una consulta sobre una base de datos distribuida en una especificación de alto nivel a una estrategia de ejecución eficiente expresada en un lenguaje de bajo nivel sobre bases de datos locales.

Así, el problema de optimización de consultas es minimizar una función de costo tal que

Función de costo total = costo de I/O + costo de CPU + costo de comunicación

Los diferentes factores pueden tener pesos diferentes dependiendo del ambiente distribuido en el que se trabaje. Por ejemplo, en las redes de área amplia (WAN), normalmente el costo de comunicación domina dado que hay una velocidad de comunicación relativamente baja, los canales están saturados y el trabajo adicional requerido por los protocolos de comunicación es considerable. Así, los algoritmos diseñados para trabajar en una WAN, por lo general, ignoran los costos de CPU y de I/O. En redes de área local (LAN) el costo de comunicación no es tan dominante, así que se consideran los tres factores con pesos variables.

La complejidad de las operaciones del álgebra relacional

La complejidad de las operaciones del álgebra relacional afectan directamente su tiempo de ejecución y establecen algunos principios útiles al procesador de consultas. Esos principios pueden ayudar en elegir la estrategia de ejecución final. La forma más simple de definir la complejidad es en términos de la cardinalidad de las relaciones independientemente de los detalles de implementación tales como fragmentación y estructuras de almacenamiento. La Figura 4.3 presenta la complejidad de las operaciones unarias y binarias en el orden creciente de complejidad.

Operación Complejidad

La complejidad de las operaciones sugiere dos principios:

1. Dado que la complejidad es con base en las cardinalidades de las relaciones, las operaciones más selectivas que reducen las cardinalidades deben ser ejecutadas primero.

2. Las operaciones deben ser ordenadas en el orden de complejidad creciente de manera que el producto Cartesiano puede ser evitado o, al menos, ejecutado al final de la estrategia.

Caracterización de los procesadores de consultas

Es difícil evaluar y comparar procesadores de consultas para sistemas centralizados y distribuidos dado que ellos difieren en muchos aspectos. En esta sección se enumeran algunas características importantes de los procesadores de consultas que pueden ser usados como base para su comparación.

Tipo de optimización

El problema de optimización de consultas es altamente demandante en tiempo de ejecución y, en el caso general, es un problema de la clase NP. Así existen dos estrategias para su solución: Búsqueda exhaustiva o el uso de heurísticas.

• Búsqueda exhaustiva 

Los algoritmos de búsqueda exhaustiva tienen una complejidad combinatorial en el número de relaciones de la consulta. Obtienen la transformación óptima, pero sólo se aplican a consultas simples dado su tiempo de ejecución.

• Uso de Heurísticas

Por otro lado, los algoritmos heurísticos obtienen solo aproximaciones a la transformación óptima pero lo hacen en un tiempo de ejecución razonable. Las heurísticas más directas a aplicar son el agrupamiento de expresiones comunes para evitar el cálculo repetido de las mismas, aplicar primero las operaciones de selección y proyección, reemplazar una junta por una serie de semijuntas y reordenar operaciones para reducir el tamaño de las relaciones intermedias.

Granularidad de la optimización

Existen dos alternativas: considerar sólo una consulta a la vez o tratar de optimizar múltiples consultas. La primera alternativa no considera el uso de resultados comunes intermedios. En el segundo caso puede obtener transformaciones eficientes si las consultas son similares. Sin embargo, el espacio de decisión es mucho más amplio lo que afecta grandemente el tiempo de ejecución de la optimización.

Tiempo de optimización

Una consulta puede ser optimizada en tiempos diferentes con relación a tiempo de ejecución de la consulta. La optimización se puede realizar de manera estática antes de ejecutar la consulta o de forma dinámica durante la ejecución de la consulta. La optimización estática se hace en tiempo de compilación de la consulta. Así, el costo de la optimización puede ser amortizada sobre múltiples ejecuciones de la misma consulta.

Durante la optimización de consultas dinámica la elección de la mejor operación siguiente se puede hacer basado en el conocimiento exacto de los resultados de las operaciones anteriores. Por tanto, se requiere tener estadísticas acerca del tamaño de los resultados intermedios para aplicar esta estrategia.

Un tercer enfoque, conocido como híbrido, utiliza básicamente un enfoque estático, pero se puede aplicar un enfoque dinámico cuando los tamaños de las relaciones estimados están alejados de los tamaños actuales.

Estadísticas

La efectividad de una optimización recae en las estadísticas de la base de datos. La optimización dinámica de consultas requiere de estadísticas para elegir las operaciones que deben realizarse primero. La optimización estática es aún más demandante ya que el tamaño de las relaciones intermedias también debe ser estimado basándose en estadísticas. En bases de datos distribuidas las estadísticas para optimización de consultas típicamente se relacionan a los fragmentos; la cardinalidad y el tamaño de los fragmentos son importantes así como el número de valores diferentes de los atributos. Para minimizar la probabilidad de error, estadísticas más detalladas tales como histogramas de valores de atributos se usan pagando un costo mayor por su manejo.

Nodos de Decisión

Cuando se utiliza la optimización estática, un solo nodo o varios de ellos pueden participar en la selección de la estrategia a ser aplicada para ejecutar la consulta. La mayoría de los sistemas utilizan un enfoque centralizado para la toma de decisiones en el cual un solo lugar decide la estrategia a ejecutar. Sin embargo, el proceso de decisión puede ser distribuido entre varios nodos los cuales participan en la elaboración de la mejor estrategia. El enfoque centralizado es simple, pero requiere tener conocimiento de la base de datos distribuida completa. El enfoque distribuido requiere solo de información local. Existen enfoques híbridos en donde un nodo determina una calendarización global de las operaciones de la estrategia y cada nodo optimiza las subconsultas locales.

Topología de la Red

Como se mencionó al principio, el tipo de red puede impactar severamente la función objetivo a optimizar para elegir la estrategia de ejecución. Por ejemplo, en redes de tipo WAN se sabe que en la función de costo el factor debido a las comunicaciones es dominante. Por lo tanto, se trata de crear una calendarización global basada en el costo de comunicación. A partir de ahí, se generan calendarizaciones locales de acuerdo a una optimización de consultas centralizada. En redes de tipo LAN el costo de comunicación no es tan dominante. Sin embargo, se puede tomar ventaja de la comunicación “broadcast” que existe comúnmente en este tipo de redes para optimizar el procesamiento de las operaciones junta. Por otra parte, se han desarrollado algoritmos especiales para topologías específicas, como por ejemplo, la topología de estrella.

Optimización Global de Consultas: El objetivo de esta capa es hallar una estrategia de ejecución para la consulta cercana a la óptima. La estrategia de ejecución para una consulta distribuida puede ser descrita con los operadores del álgebra relacional y con primitivas de comunicación para transferir datos entre nodos. Para encontrar una buena transformación se consideran las características de los fragmentos, tales como, sus cardinalidades.

Optimización Local de Consultas: El trabajo de la última capa se efectúa en todos los nodos con fragmentos involucrados en la consulta. Cada subconsulta que se ejecuta en un nodo, llamada consulta local, es optimizada usando el esquema local del nodo. Hasta este momento, se pueden eligen los algoritmos para realizar las operaciones relacionales. La optimización local utiliza los algoritmos de sistemas centralizados.

Fuentes de consulta
http://luisantoniosr.webcindario.com/BDD/bdd.html

https://cursos.aiu.edu/Base%20de%20Datos%20Distribuidas/pdf/Tema%203.pdf

Actividad 16

Indicar cuales son los puntos para la optimización de consultas distribuidas, y explicar la optimización global de consultas y la optimización local de consultas.

Introducción

Cambiar el orden de las operaciones dentro de una misma consulta provee diferentes estrategias para su ejecución.

El principal rol de las capa de optimización (u optimizador) es encontrar el ordenamiento 'óptimo' de operaciones para una consulta dada.

¿Es realmente óptimo?

Objetivos: 

• Evitar malas estrategias 
• Acercarse a una estrategia óptima

Encontrar la estrategia "óptima": Requiere la predicción de los costos de ejecución de los distintos candidatos.

Optimización de consultas

I -Es el proceso de producir un QEP (Query Execution Plan) que representa una estrategia de ejecución para la consulta.

II - Es el proceso de selección del plan de evaluación de las consultas mas eficientes de entre las muchas estrategias generalmente disponibles para el procesamiento de una consulta dada, especialmente si la consulta es compleja.

Un optimizador de consultas es usualmente visto como 3 componentes:

1. Un espacio de búsqueda
2. Un modelo de costos
3. Una estrategia de búsqueda

Importancia

Crear un plan de evaluación de consultas que minimice el costo de la evaluación de consultas a través de la optimación de la misma.

Optimizacion global

El compilador de SQL funciona en tres fases, que ayuda a producir una estrategia de acceso optima para evaluar una consulta que hace referencia a una fuente de datos remota. Estas fases son analisis de envio, optimizacion global y generacion de SQL remoto.

El objetivo de la optimizacion global es producir un plan de acceso que optimiza las operaciones de consulta en todas las fuentes de datos globalmente, en todo el sistema federado. un plan de acceso que es optimo globalmente tiene como minimo un coste global de ejecucion en una sistema federado. la fase de generacion de SQL remoto convierte a la inversa el plan optimo globalmente en fragmentos de consulta que se ejecutan como fuentes de datos individuales.

Dada una consulta algebraica sobre fragmentos, el objetivo de esta capa es hallar una estrategia de ejecución para la consulta cercana a la óptima. La estrategia de ejecución para una consulta distribuida puede ser descrita con los operadores del álgebra relacional y con primitivas de comunicación para transferir datos entre nodos. Para encontrar una buena transformación se consideran las características de los fragmentos, tales como, sus cardinalidades. Un aspecto importante de la optimización de consultas es el ordenamiento de juntas, dado que algunas permutaciones de juntas dentro de la consulta pueden conducir a un mejoramiento de varios órdenes de magnitud. La salida de la capa de optimización global es una consulta algebraica optimizada con operación de comunicación incluidas sobre los fragmentos.

Optimización Local de Consultas

El trabajo de la última capa se efectúa en todos los nodos con fragmentos involucrados en la consulta. Cada subconsulta que se ejecuta en un nodo, llamada consulta local, es optimizada usando el esquema local del nodo. Hasta este momento, se pueden eligen los algoritmos para realizar las operaciones relacionales.

Actividad 15 -Exposición

Actividad 15

Actividad #15

Investigar, sobre las diferentes estrategias de procesamiento de consultas distribuidas, tales como: árboles de consultas, transformaciones equivalentes, métodos de ejecución del join.
Preparando la información para exposición en clase en equipos de tres.
Publicación y exposiciones Martes 21 de Abril

Introducción

El procesamiento de consultas es de suma importancia en bases de datos centralizadas. Sin embargo, en BDD éste adquiere una relevancia mayor.

El objetivo es convertir transacciones de usuario en instrucciones para manipulación de datos. No obstante, el orden en que se realizan las transacciones afecta grandemente la velocidad de respuesta del sistema. Así, el procesamiento de consultas presenta un problema de optimización en el cual se determina el orden en el cual se hace la menor cantidad de operaciones. 

El procesamiento de consultas tiene varias etapas a seguir para resolver una consulta SQL, las características del modelo relacional permiten que cada motor de base de datos elija su propia representación que, comúnmente, resulta ser el álgebra relacional. La optimización de consultas es, entonces, una de estas etapas.

Árboles de consultas

Existen distintos métodos para optimizar consultas relacionales, sin embargo el enfoque de optimización basada en costos combinado con heurísticas que permitan reducir el espacio de búsqueda de la solución es el método mayormente utilizado por los motores de base de datos relaciones de la actualidad, en todo caso, independiente del método elegido para optimizar la consulta, la salida de este proceso debe ser un plan de ejecución, el cual comúnmente es representado en su forma de árbol relacional.

Transformaciones equivalentes

1.-el servidor recive una peticion de un nodo
2.-el servidor es atacado por el acceso concurrente a la base de datos cargada localmente
3.-el servidor muestra un resultado y le da un hilo a cada una de las maquinas nodo de la red local.


Una base de datos es accesada 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 de los datos, por lo tanto se respetan las formas normales de la base de datos ok.
Bueno para realizar una transformación en la consulta primero desfragmentamos siguiendo los estandares marcados por las reglas formales y posteriormente realizamos el envio y la maquina que recibe es la que muestra el resultado pertinente para el usuario, de esta se puede producir una copia que sera la equivalente a la original.

Métodos de ejecución del join

La sentencia join en SQL permite combinar registros de dos o más tablas en una base de datos relacional. En el Lenguaje de Consultas Estructurado (SQL), hay tres tipo de JOIN: interno, externo, y cruzado.
En casos especiales una tabla puede unirse a sí misma, produciendo una auto-combinación,SELF-JOIN.
Matemáticamente, JOIN es composición relacional, la operación fundamental en el álgebra relacional, y generalizando es una función de composición.
Existen diferentes algoritmos que pueden obtener transformaciones eficientes 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.

¿Qué se debe de tomar en cuenta en este algoritmo?

•Se tiene que ordenar primero, para después utilizar este método.
•Se tiene que considerar el costo de ordenarlo / las relaciones.
•Es más fácil utilizar pequeñas tuplas.

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.
El número de bloques ocupados por las particiones podría ser ligeramente mayor que.
Debido a que los bloques no están completamente llenos. El acceso a estos bloques puede añadir un gasto adicional de 2·max a lo sumo, ya que cada una de las particiones podría tener un bloque parcialmente ocupado que se tiene que leer y escribir de nuevo.

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.
Cuando r se divide, las tuplas de tampoco se escriben en disco; en su lugar, según se van generando, el sistema las utiliza para examinar el índice asociativo en y así generar las tuplas de salida del join. Después de utilizarlas, estas tuplas se descartan, así que la partición no ocupa espacio en memoria. De este modo se ahorra un acceso de lectura y uno de escritura para cada bloque de y.


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.

El outer join tiene tres formas distintas: por la izquierda, por la derecha y completo. El join por la izquierda ( ) toma todas las tuplas de la relación de la izquierda que no coincidan con ninguna tupla de la relación de la derecha, las rellena con valores nulos en los demás atributos de la relación de la derecha y las añade al resultado del join natural.

Un outer join por la derecha ( ) es análogo al procedimiento anterior y el outer join completo es aquel que efectúa ambas operaciones.
Para el caso de un outer join completo se puede calcular mediante extensiones de los algoritmos de join por mezcla y join por asociación.

http://luisantoniosr.webcindario.com/BDD/bdd_unidad3.html#32

Presentación Algoritmos de distribución de datos no replicados

https://onedrive.live.com/view.aspx?cid=2CE53E163ABD83BE&resid=2CE53E163ABD83BE%21135&app=PowerPoint