Evaluación U4.

http://goanimate.com/videos/0ILLDFx4d16o

Actividad #21

Protocolos REDO/UNDO.

El registro de la base de datos contiene información que es utilizada por el proceso de recuperación para restablecer la base de datos a un estado consistente. Esta información puede incluir entre otras cosas:
el identificador de la transacción,
el tipo de operación realizada,
los datos accesados por la transacción para realizar la acción,
el valor anterior del dato (imagen anterior), y
el valor nuevo del dato (imagen nueva).
Considere el escenario mostrado en la Figura de abajo. El DBMS inicia la ejecución en el tiempo 0 y en el tiempo t se presenta una falla del sistema. Durante el periodo [0, t] ocurren dos transacciones, T1 y T2. T1 ha sido concluida (ha realizado su commit) pero T2 no pudo ser concluida.
La propiedad de durabilidad requiere que los efectos de T1 sean reflejados en la base de datos estable. De forma similar, la propiedad de atomicidad requiere que la base de datos estable no contenga alguno de los efectos de T2.

Ejemplo de una falla del sistema.

A pesar que T1 haya sido terminada, puede suceder que el buffer correspondiente a la página de la base de datos modificada no haya sido escrito a la base de datos estable. Así, para este caso la recuperación tiene que volver a realizar los cambios hechos por T1. A esta operación se le conoce como REDO y se presenta en la Figura de abajo.
La operación de REDO utiliza la información del registro de la base de datos y realiza de nuevo las acciones que pudieron haber sido realizadas antes de la falla. La operación REDO genera una nueva imagen.

Operación REDO.

Por otra parte, es posible que el administrador del buffer haya realizado la escritura en la base de datos estable de algunas de las páginas de la base de datos volátil correspondientes a la transacción T2.
Así, la información de recuperación debe incluir datos suficientes para permitir deshacer ciertas actualizaciones en el nuevo estado de la base de datos y regrasarla al estado anterior. A esta operación se le conoce como UNDO y se muestra en la Figura de abajo. La operación UNDO restablece un dato a su imagen anterior utilizando la información del registro de la base de datos.

Operación UNDO.

De forma similar a la base de datos volátil, el registro de la base de datos se mantiene en memoria principal (llamada los buffers de registro) y se escribe al almacenamiento estable (llamadoregistro estable). Las páginas de registro se pueden escribir en el registro estable de dos formas: síncrona o asíncrona. En forma síncrona, también llamada un registro forzado, la adición de cada dato en el registro requiere que la página del registro correspondiente se mueva al almacenamiento estable. De manera asíncrona, las páginas del registro se mueven en forma periódica o cuando los buffers se llenan.

Puntos de verificación (checkpoints).

Cuando ocurre una falla en el sistema es necesario consultar la bitácora para determinar cuáles son las transacciones que necesitan volver a hacerse y cuando no necesitan hacerse. Estos puntos de verificación nos ayudan para reducir el gasto de tiempo consultando la bitácora. El punto de verificación es un registro que se genera en la bitácora para concluir en todo lo que se encuentra antes de ese punto está correcto y verificado.

Protocolo 2PC de confiabilidad distribuida.

El protocolo 2PC básico un agente (un agente-DTM en el modelo) con un rol especial. Este es llamado el coordinador; todos los demás agentes que deben hacer commit a la vez son llamados participantes.
El coordinador es responsable de tomar la decisión de llevar a cabo un commit o abort finalmente. Cada participante corresponde a una subtransacción la cual ha realizado alguna acción de escritura en su base de datos local.
Se puede asumir que cada participante está en un sitio diferente. Aun si un participante y el coordinador se encuentran en el mismo sitio, se sigue el protocolo como si estuvieran en distintos sitios.
La idea básica del 2PC es determinar una decisión única para todos los participantes con respecto a hacer commit o abort en todas las subtransacciones locales.

El protocolo consiste en dos fases:

La primera fase tiene como objetivo alcanzar una decisión común.
La meta de la segunda fase es implementar esta decisión.
El protocolo procede como sigue:
Fase uno:
El coordinador escribe “prepare” en la bitácora y envía un mensaje donde pregunta a todos los participantes si preparan el commit (PREPARE).
Cada participante escribe “ready” (y registra las subtransacciones) en su propia bitácora si está listo o “abort” de lo contrario.
Cada participante responde con un mensaje READY o ABORT al coordinador.
El coordinador decide el commit o abort en la transacción como un resultado de las respuestas que ha recibido de los participantes. Si todos respondieron READY, decide hacer un commit. Si alguno ha respondido ABORT o no ha respondido en un intervalo de tiempo determinado se aborta la transacción.

Fase dos:
El coordinador registra la decisión tomada en almacenamiento estable; es decir, escribe “global_commit” o “global_abort” en la bitácora.
El coordinador envía mensaje de COMMIT o ABORT según sea el caso para su ejecución.
Todos los participantes escriben un commit o abort en la bitácora basados en el mensaje recibido del coordinador (desde este momento el procedimiento de recuperación es capaz de asegurar que el efecto de la subtransacción no será perdido). Finalmente: Todos los participantes envían un mensaje de acuse de recibo (ACK) al coordinador, y ejecutan las acciones requeridas para terminar (commit) o abortar (abort) la subtransacción. Cuando el coordinador ha recibido un mensaje ACK de todos los participantes, escribe un nuevo tipo de registro en la bitácora, llamado un registro completo.

Actividad #20

Actividad #19

Disciplinas del interbloqueo: prevención, detección, eliminación y recuperación.

Interbloqueo.-
Un esquema para resolver el interbloque en su detención.

Prevención.- 
Las técnicas de interbloqueo utilizan el concepto de marca de tiempo de transacción existen dos esquemas que evitan el interbloqueo.

Recuperación.- 
El objetivo de esta parte de la asignación es conocer y entender las distintas fallas que pueden ocurrir en un BMS y como es posible restaurar el sistema después de dichas fallas este tema se llama recuperación de fallas.

Detención.- 
Existen diversos algoritmos para ello en la detención de ciclos en el grafo de esperas, entre ellos:

• Algoritmo 1. Comprueba la existencia de ciclos mediante la eliminación de nodos terminales.
• Algoritmo 2.- Comprueba posibles ciclos desde la última transacción bloqueada y marcando los nodos por lo que pasa. Si pasa dos veces por el mismo nodo a detectado un ciclo.

#Actividad 18

CONTROL DE CONCURRENCIA
El control de concurrencia trata con los problemas de aislamiento yconsistencia del procesamiento de transacciones.El control de concurrencia distribuido de una DDBMS asegura que laconsistencia de la base de datos se mantiene en un ambiente distribuidomultiusuario.Si las transacciones son internamente consistentes, la manera más simple delograr este objetivo es ejecutar cada transacción sola, una después de otra.

Algoritmos de control de concurrencia
El criterio de clasificación más común de los algoritmos de control deconcurrencia 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.

ALGORITMOS DE CERRADURA O 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.

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 (ver Figura G). Los algoritmos optimistas, por otra parte, retrasan la fase de validación justo antes de la fase de escritura (ver Figura G). 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. 

 

ALGORITMOS BASADOS EN MARCAS DE TIEMPO

A diferencia de los algoritmos basados en candados, los algoritmos basados en marcas de tiempo no pretenden mantener la seriabilidad por la exclusión mutua. En su lugar eligen un orden de serializacion en primera instancia y ejecutan las transacciones de acuerdo a ese orden. En estos algoritmos cada transacción lleva asociada una marca de tiempo. Cada dato lleva asociado dos marcas de tiempo: uno de lectura y otro de escritura, que reflejan la marca de tiempo de la transacció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 la transacción, sino se aborta. Esta técnica esta libre de Ínterbloqueos pero puede darse que halla que repetir varias veces la transacción. En los sistemas distribuidos se puede usar un mecanismo como, los relojes de Lamport para asignar marcas de tiempo.
CONTROL DE CONCURRENCIA EN SISTEMAS DE ARCHIVOS DISTRIBUIDOS

Hasta aquí se a hablado sobre el modelo transaccional haciendo hincapié en lo referido a base de datos distribuidas. En adelante se desarrollara como se emplea el control de concurrencia en sistemas distribuidos de archivos Los sistemas de archivos que forman parte de una red de computadoras tienen múltiples clientes de los que encargarse. Si dos o mas clientes, accidentalmente o no, deciden acceder al mismo archivo al mismo tiempo pueden producirse conflictos. La solución utilizada es permitir a los usuarios el uso de bloqueos sobre los archivos de trabajo. La idea es sencilla, mientras un usuario esta trabajando sobre una parte de los datos, otros no podrán hacerlo de manera que las distintas actualizaciones se efectuaran en forma sucesiva y ordenada sin interferencias. Se utilizan dos clases de bloqueos: Los bloqueos compartidos que por lo general se usan para lectura , y los bloqueos exclusivos que normalmente se usan para escritura. La granularidad del bloqueo es otra consideración importante. Es posible bloquear archivos enteros, pero también es posible bloquear archivos enteros o subárboles, cuanto menor sea la unidad lógica bloqueada mayor será la concurrencia admisible. El concepto de bloqueo introduce varios problemas de contrapartida. Primero, si un cliente necesita acceder a varios archivos, como ocurre de forma común cuando se efectúan transferencias de dinero en aplicaciones bancarias, hay una posibilidad de abrazo mortal.

Actividad #17.

Presentación:
https://drive.google.com/file/d/0B-TlO29GoNtiYm15cWx1bVFqUmM/view?usp=sharing



B)

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 cuentas bancarias. 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.

Exposicion

https://app.emaze.com/@ALOITZCO/bases-de-datos-distribuidas#1

Actividad #16

Estrategias de procesamiento de consultas distribuidas.

Consulta distribuida:
· Las consultas distribuidas tienen acceso a datos de varios orígenes de datos heterogéneos.
· Estos orígenes de datos pueden estar almacenado en el mismo equipo o en equipos diferentes.
· El procesamiento de consultas tiene varias etapas a seguir para resolver una consulta en sql.
· Las características del modelo relacional permiten que cada motor de base de datos elija su propia representación: álgebra relacional.
Existen varios medios para calcular la respuesta a una consulta.
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.

Árboles de consultas:
Son estructuras de datos en forma de árbol, en donde, los datos al estar ordenados en la estructura, hace más ágiles las 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.


Métodos de ejecución del join.
Existen diferentes algoritmos que pueden obtener transformaciones eficientes en el procesamiento de consultas:

Join externo.

Un outer join es una extensión del operador join que se utiliza a menudo para trabajar con la información que falta.

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.

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.

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.

Join por mezcla.

Este algoritmo se puede utilizar para calcular si un Join natural es óptimo en la búsqueda o consulta.

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.

Puntos para la optimización de las consultas distribuidas.

•Identificar sentencias problemáticas 
•Verificar las estadísticas 
•Revisar los planes de ejecución 
•Reestructurar las sentencias SQL
•Reestructurar los índices
•Mantener los planes de ejecución

Para optimizar el uso de la memoria compartida: 

• Escribir código genérico „
• Seguir estándares de codificación „ 
• Usar variables a reemplazar en tiempo de ejecución

Optimización de consulta

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

Es el proceso de selección del plan de evaluación de las consultas más eficiente entre las estrategias disponibles para el procesamiento de una consulta dada.
A través del álgebra relacional intenta hallar una expresión equivalente a la expresión dada ƒ.
Elección de una estrategia detallada para el procesamiento de la consulta:
o Selección del algoritmo que se usará para ejecutar una operación
o Selección de los índices concretos que se van a emplear
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.

Optimización global

El compilador de SQL funciona en tres fases, que ayuda a producir una estrategia de acceso óptima para evaluar una consulta que hace referencia a una fuente de datos remota. Estas fases son análisis de envío, optimización global y generación de SQL remoto.
El objetivo de la optimización 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 óptimo globalmente tiene como mínimo un coste global de ejecución en una sistema federado. la fase de generación 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 cordialidades. 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 incluida 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

Optimización de consulta

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

Es el proceso de selección del plan de evaluación de las consultas más eficiente entre las estrategias disponibles para el procesamiento de una consulta dada.

A través del álgebra relacional intenta hallar una expresión equivalente a la expresión dada ƒ.

Elección de una estrategia detallada para el procesamiento de la consulta: 

o    Selección del algoritmo que se usará para ejecutar una operación

o    Selección de los índices concretos que se van a emplear

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.

Optimización global

El compilador de SQL funciona en  tres fases, que ayuda a producir una estrategia de acceso óptima para evaluar una consulta que hace referencia a una fuente de datos remota. Estas fases son análisis de envío, optimización global y generación de SQL remoto.

El objetivo de la optimización 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 óptimo globalmente tiene como mínimo un coste global de ejecución en una sistema federado. la fase de generación 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 cordialidades. 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 incluida 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.

Estrategias de procesamiento de consultas distribuidas.

Consulta distribuida:

·         Las consultas distribuidas tienen acceso a datos de varios orígenes de datos heterogéneos.

·         Estos orígenes de datos pueden estar almacenado en el mismo equipo o en equipos diferentes.

·         El procesamiento de consultas tiene varias etapas a seguir para resolver una consulta en sql.

·         Las características del modelo relacional permiten que cada motor de base de datos elija su propia representación: álgebra relacional.

Existen varios medios para calcular la respuesta a una consulta.

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.

Árboles de consultas:

Son estructuras de datos en forma de árbol, en donde, los datos al estar ordenados en la estructura, hace más ágiles las 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.

Métodos de ejecución del join.

Existen diferentes algoritmos que pueden obtener transformaciones eficientes en el procesamiento de consultas:

•       Join externo.

Un outer join es una extensión del operador join que se utiliza a menudo para trabajar con la información que falta.

•      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.

•     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.

•          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.

•    Join por mezcla.

Este algoritmo se puede utilizar para calcular si un Join natural es óptimo en la búsqueda o consulta.

•         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.

Exposición-Presentación

Actividad #14

 Algoritmos Distribución Datos No Replicados.

Debido al uso que se da a las redes de computadoras en la actualidad incluyendo Internet, cada vez es más factible implementar Sistemas de Bases de Datos Distribuidas, sin embargo, esta tecnología lleva a los desarrolladores a enfrentar un problema, la carencia de metodologías y herramientas de apoyo para su diseño que permitan decidir la ubicación de los datos en cada uno de los diferentes sitios que componen la red de computadoras.
Este problema se conoce como Diseño de la Distribución y nace de la necesidad de especificar las unidades de almacenamiento adecuadas, ya sea fragmentos verticales, horizontales o mixtos, junto con su ubicación dentro de la aplicación.
El Modelo FURD, ha sido desarrollado para resolver el problema del diseño de las Bases de Datos Distribuidas, el cual está divido en dos etapas o fases: la fragmentación y la ubicación de fragmentos. Estas fases ya se concentran en el Modelo FURD.
 Una vez que se resuelve el Modelo FURD se puede dar solución al problema del diseño. Sin embargo la dificultad radica precisamente en la forma de resolverlo, pues es un problema de optimización muy complejo que a medida que va creciendo su tamaño, se va haciendo más difícil la forma de resolverse.

Actividad #13-Ejercicios

Actividad #13 Resumen.

Resumen.

Sistema de computación distribuido: elementos de procesamiento que cooperan en la ejecución de tareas, interconectadas por una red de ordenadores.

Base de datos distribuida (bdd): son varias bases de datos interrelacionadas lógicamente y situadas en diferentes nodos de una red de ordenadores. Se considera una base de datos distribuida a una colección lógicamente interrelacionada de datos compartidos físicamente distribuida por una red informática.

Sistema gestor de base de datos distribuido: el que gestiona base de datos distribuidas de forma transparente para el usuario. Se considera un sistema gestor de base de datos distribuido a un sistema-software que permite gestionar la base de datos distribuida y hace que dicha distribución sea transparente para los usuarios.

Ventajas de las base de datos distribuidas:

·         Localización transparente de los datos.

·         Transparencia en los nombres.

·         Transparencia de fragmentación.

·         Más fiabilidad y disponibilidad.

·         Mejora del rendimiento.

·         Expansión más sencilla.

Otras funciones de las bases de datos distribuidas.

o   Seguir la pista a los datos.

o   Procesar consultas distribuidas.

o   Gestionar transacciones distribuidas.

o   Gestionar datos replicados.

o   Recuperar bases de datos distribuidas.

o   Seguridad.

o   Gestionar el catálogo distribuido.

Diseño de bases de datos ditribuidas: fragmentación.

1.      Directorio global.

2.      Fragmentar.

·         Fragmentación horizontal.

·         Fragmentación vertical.

3.      Fragmentación mixta.

4.      Esquema de fragmentación.

Base de datos distribuidas: replicación y asignación.

La replicación mejora la disponibilidad de los datos.

Asignación: dónde se sitúan los fragmentos y réplicas.

Descomposición de actualizaciones y consultas.

·         Sistema gestor de base de datos sin transparencia de distribución: hay que indicar el sitio y la tabla sobre la que se realiza la consulta.

·         Sistema gestor de base de datos sin transparencia de replicación: hay que mantener a mano la consistencia de los datos.

·         Sistema gestor de base de datos con transparencia de distribución, replicación y fragmentación: la consulta o actualización se expresan como si se tratase de un sistema gestor de base de datos centralizado.

Base de datos distribuida y cliente-servidor: arquitectura de 2 niveles.

• Los SGBD totalmente distribuidos (transparentes) aun no son viables comercialmente.

• En su lugar se han creado sistemas basados en cliente-servidor.

• La forma habitual de dividir la funcionalidad del SGBD entre cliente y servidor ha sido la arquitectura de 2 niveles:

– Servidor (o servidor SQL): donde se sitúa el SGBD. Una BDD se situaría en varios servidores.

– Clientes:

• Envían consultas/actualizaciones a servidores

• Tienen interfaces SQL, de usuario y funciones de interfaz del lenguaje de programación

• Consultan en el diccionario de datos la información sobre la distribución de la BD entre los servidores. Tienen módulos que descomponen consultas globales en varias locales a cada servidor.

BDD y cliente-servidor: arquitectura de 3 niveles.

• Actualmente es más común utilizar una arquitectura en 3 niveles, sobre todo para aplicaciones web.

• Las 3 capas son:

– Cliente (Presentación):

• Es la interfaz.

• Suelen usar navegadores web y lenguajes como HTML, JavaScript.

• Gestiona las entradas, salidas y la navegación con páginas web estáticas o, cuando accede a BD, con páginas dinámicas.

– Servidor de aplicaciones (SA) (lógica de negocio):

• Incluye, por ejemplo, consultas basadas en datos introducidos por el usuario, o resultados de consultas a los que da formato y envía para su presentación.

• Puede incluir otro tipo de funcionalidad como comprobaciones de seguridad o de la identidad.

• Puede acceder a varias BD conectándose mediante

ODBC, JDBC u otras técnicas.

– Servidor de BD (SBD):

• Procesa consultas y actualizaciones solicitadas por la capa de aplicación.

• Puede devolver los resultados en formato XML.

Estado actual de los SGBDD.

Existen varios productos comerciales con bases de datos distribuidas, como:

• INGRES/STAR de Relational Technology, Inc.

• SQL*STAR, de Oracle Corp.

• DB2 versión 2 Edición 2, de IBM.