LINK DE VÍDEO

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

Actividad #20

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, T₁ y T₂. T₁ ha sido concluida (ha realizado su commit) pero T₂ no pudo ser concluida.

La propiedad de durabilidad requiere que los efectos de T₁ 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 T₂.

Ejemplo de una falla del sistema.

A pesar que T₁ 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 T₁. 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 T₂.

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.

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 #19

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


Un interbloqueo se produce cuando dos o más tareas se bloquean entre sí permanentemente teniendo cada tarea un bloqueo en un recurso que las otras tareas intentan bloquear.
Un interbloqueo es una condición que se puede dar en cualquier sistema con varios subprocesos, no sólo en un sistema de administración de bases de datos relacionales, y puede producirse para recursos distintos a los bloqueos en objetos de base de datos
Por ejemplo:
La transacción A tiene un bloqueo compartido de la fila 1.
La transacción B tiene un bloqueo compartido de la fila 2.
La transacción A ahora solicita un bloqueo exclusivo de la fila 2 y se bloquea hasta que la transacción B finalice y libere el bloqueo compartido que tiene de la fila 2.
La transacción B ahora solicita un bloqueo exclusivo de la fila 1 y se bloquea hasta que la transacción A finalice y libere el bloqueo compartido que tiene de la fila 1.


Prevención del interbloqueo.
Objetivo: conseguir que sea imposible la aparición de situaciones de interbloqueo.
Impedir que se produzca una de las cuatro condiciones necesarias para producirlo: Exclusión mutua, Retención y espera, No expropiación, y Espera circular.
Condicionar un sistema para quitar cualquier posibilidad de ocurrencia de interbloqueo.
Que no se cumpla una condición necesaria
“Exclusión mutua” y “sin expropiación” no se pueden relajar. Dependen de carácter intrínseco del recurso.
Las otras dos condiciones son más prometedoras.


Recuperación de Interbloqueo.
Limpiar un sistema de interbloqueos, una vez que fueron detectados.
Cuando se ha detectado que existe un interbloqueo, podemos actuar de varias formas. Una posibilidad es informar al operador que ha ocurrido un interbloqueo y dejar que el operador se ocupe de él manualmente. La otra posibilidad es dejar que el sistema se recupere automáticamente del interbloqueo. Dentro de esta recuperación automática tenemos dos opciones para romper el interbloqueo: Una consiste en abortar uno o más procesos hasta romper la espera circular, y la segunda es apropiar algunos recursos de uno o más de los procesos bloqueados.
Eliminar interbloqueos.
Para eliminar interbloqueos abortando un proceso, tenemos dos métodos; en ambos, el sistema recupera todos los recursos asignados a los procesos terminados.
Abortar todos los procesos interbloqueados. Esta es una de las soluciones más comunes, adoptada por Sistemas Operativos. Este método romperá definitivamente el ciclo de interbloqueo pero con un costo muy elevado, ya que estos procesos efectuaron cálculos durante mucho tiempo y habrá que descartar los resultados de estos cálculos parciales, para quizá tener que volver a calcularlos más tarde.
Abortar un proceso en cada ocasión hasta eliminar el ciclo de interbloqueo. El orden en que se seleccionan los procesos para abortarlos debe basarse en algún criterio de costo mínimo. Después de cada aborto, debe solicitarse de nuevo el algoritmo de detección, para ver si todavía existe el interbloqueo. Este método cae en mucho tiempo de procesamiento adicional.


Si éste se encuentra actualizando un archivo, cortarlo a la mitad de la operación puede ocasionar que el archivo quede en un mal estado.
Si se utiliza el método de terminación parcial, entonces, dado un conjunto de procesos bloqueados, debemos determinar cuál proceso o procesos debe terminarse para intentar romper el interbloqueo. Se trata sobre todo de una cuestión económica, debemos abortar los procesos que nos representen el menor costo posible.

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 de lograr 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 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 a datos 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 orden de 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 tiempo no 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. 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. 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 algoritmos optimistas se componen por los algoritmos basados en candados y algoritmos basados en estampas de tiempo.

Basados en bloqueos.

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 (rl), también llamados compartidos, o de escritura (wl), también llamados exclusivos. Como se aprecia en la tabla siguiente, los candados de lectura presentan conflictos con los candados de escritura, dado que las operaciones de lectura y escritura son incompatibles.

En sistemas basados en candados, el despachador es un administrador de candados (LM). 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 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.

Pruebas de validación optimistas

Actividad #17

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 labase 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 #16

PUNTOS PARA LA OPTIMIZACIÓN DE CONSULTAS DISTRIBUIDAS SQL

•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

Procesamiento de consulta distribuidas.

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

Procesamiento de consultas locales.

Para procesar una consulta local solo se hace referencia a tablas y bases de datos locales(no a vistas ni a tablas remotas) , es decir que estén dentro de la misma instancia del manejador de bases de datos, en una única maquina y que nos se tenga que conectar al servidor a otras maquinas para poder efectuar la consulta.

Optimizador de consultas.

El optimizador de consultas es uno de los componentes más importantes de un sistema de base de datos SQL. El optimizador de consultas de SQL Server es un optimizador basado en el costo. El optimizador de consultas debe analizar los planes posibles y elegir el de menor costo estimado. Algunas instrucciones SELECT complejas tienen miles de planes de ejecución posibles. El optimizador de consultas de SQL Server elige, además del plan de ejecución con el costo de recursos mínimo, el plan que devuelve resultados al usuario con un costo razonable de recursos y con la mayor brevedad posible. El optimizador de SQL Server utilizará un plan de ejecución en paralelo para devolver resultados si esto no afecta negativamente a la carga del servidor. Pueden estar seguros de que el optimizador de consultas creará un plan de ejecución eficaz para el estado de la base de datos cada vez que se ejecuta la instrucción.

1.El optimizador de consultas analiza diferentes formas de acceso a las tablas de origen. La versión final y optimizada del árbol de la consulta se denomina plan deejecución.

2.El motor relacional comienza a ejecutar el plan de ejecución. A medida que se procesan los pasos que necesitan datos de las tablas base, el motor relacional solicita al motor de almacenamiento que pase los datos de los conjuntos de filas solicitados desde el motor relacional.

Evidencia de expocisión.

Actividad #15

Puntos para la optimización de consultas distribuidas SQL

•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 global de consultas

 La optimización que se realiza en este apartado ordena la forma en que se van a ejecutar las consultas para que los recursos de computación como discos, comunicaciones, etc. puedan ser utilizados de manera eficiente. Debemos tener en cuenta las cardinalidades de los resultados intermedios, las estadísticas de la base de datos y tener presente el modelo de coste que se expresa de la siguiente forma:
Coste_total=Coste_cpu*#instr+C_I/O*#I/Os+C_mensaje*#mensajes+C_transm*#bytesC_mensaje es el coste de enviar o recibir un mensaje.C_transm es el coste de transmitir unidades de un lugar a otro.
Se aplican varios algoritmos de optimización. Muchos son genéricos de las bases de datos relacionales y otros como INGRES, R*, SSD-1 o AHY son específicos de las bases de datos distribuidas.

Procesamiento de consultas locales.

Para procesar una consulta local solo se hace referencia a tablas y bases de datos locales(no a vistas ni a tablas remotas) , es decir que estén dentro de la misma instancia del manejador de bases de datos, en una única maquina y que nos se tenga que conectar al servidor a otras maquinas para poder efectuar 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 centralizado.

La entrada al optimizador consta de la consulta, el esquema de la base de datos(definiciones de tabla e índice) y las estadísticas de base de datos. Una instrucción SELECT define únicamente los siguientes elementos:

El formato del conjunto de resultados. Las tablas que contienen los datos de origen. Esto se especifica en la cláusula FROM.

Cómo se relacionan lógicamente las tablas para la instrucción SELECT. Esto se define en las especificaciones de combinación, que pueden aparecer en la cláusula WHERE o en una cláusula ONE que sigue a FROM.

Las condiciones que deben cumplir las filas de las tablas de origen para satisfacer los requisitos de la instrucción SELECT. Estas condiciones se especifican en las cláusulas WHERE y HAVING.

Optimizador de consultas.

El optimizador de consultas es uno de los componentes más importantes de un sistema de base de datos SQL. El optimizador de consultas de SQL Server es un optimizador basado en el costo. El optimizador de consultas debe analizar los planes posibles y elegir el de menor costo estimado. Algunas instrucciones SELECT complejas tienen miles de planes de ejecución posibles. El optimizador de consultas de SQL Server elige, además del plan de ejecución con el costo de recursos mínimo, el plan que devuelve resultados al usuario con un costo razonable de recursos y con la mayor brevedad posible. El optimizador de SQL Server utilizará un plan de ejecución en paralelo para devolver resultados si esto no afecta negativamente a la carga del servidor. Pueden estar seguros de que el optimizador de consultas creará un plan de ejecución eficaz para el estado de la base de datos cada vez que se ejecuta la instrucción.

1.El optimizador de consultas analiza diferentes formas de acceso a las tablas de origen. La versión final y optimizada del árbol de la consulta se denomina plan deejecución.

2.El motor relacional comienza a ejecutar el plan de ejecución. A medida que se procesan los pasos que necesitan datos de las tablas base, el motor relacional solicita al motor de almacenamiento que pase los datos de los conjuntos de filas solicitados desde el motor relacional

Referencias:
http://es.scribd.com/doc/23911262/Procesamiento-de-Consultas-Locales#scribd

http://www.econ.uba.ar/www/departamentos/sistemas/plan97/s_datos/waldbott/chinkes/material/Analisis%20y%20Optimizacion%20de%20Consultas_0107_v2.pdf

Actividad #15

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

Si los datos estuvieran ordenados alfabéticamente en una estructura tipo lista, por ejemplo, e hicieras una búsqueda (la cual sería secuencial), tu búsqueda duraría, en el peor de los casos, un tiempo proporcional a la cantidad de registros que tengas. Es decir, tu búsqueda es de órden O(n) [n=número de registros) 

Pero si tus datos están ordenados alfabéticamente en una estructura tipo árbol, e hicieras en el árbol una búsqueda (la cual sería binaria), tu búsqueda se va recortando en tiempo de acuerdo a la cantidad de registros, el algoritmo de búsqueda binaria en árboles es de órden O(log (n+1)) (n=número de registros). Una función de orden logarítmico es más eficiente que una de orden lineal (como la búsqueda secuencial).

Transformaciones equivalentes

Cuando una base de datos se encuentra en múltiples servidores y 

distribuye a un numero determinado de nodos tenemos:

1.-el servidor recibe una petición 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.

Cuando 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 de 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.


¿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://basesdatosdistribuidas.blogspot.mx/2012/10/estrategias-de-procesamiento-de.html

Tema a exponer.

Actividad #14

Una base de datos no replicada guarda una base de datos en un solo sitio por consiguiente, por consiguiente no existe no existen base de datos duplicadas.

Varios factores influyen en la decisión de utilizar replicas de datos.

Tamaño de base de datos.

Frecuencia de usos.

Costos- de desempeño, software,  indirectos y de administración, - asociados con la sincronización de las transacciones y de sus componentes vs beneficios de tolerancias a las fallas asociados con los datos  replicados.

Permite maximizar el costo de comunicación y al mismo tiempo maximizar el tiempo de respuesta. El administrador de bases de datos debe de evaluar el modo de operar de la base de datos, es decir como su nombre lo indica no podemos realizar el algoritmo en aquellas copias, pero debe ser sobre la base de datos original .La fragmentación hibrida es de preferencia lo que debe de llevar este tipo de algoritmos, porque estas utilizan las tres fragmentaciones y las mas aconsejables.

Hablar de algoritmos implica sobre la Programación

Hay gestores que son muy flexibles en cuestiones de programación, mientras que otros ofrecen más rendimiento. Así, al diseñar el algoritmo tendrá que hacer toda la información referente a la vida de la base de datos pero por otro lado deberá buscar siempre de darle soluciones al usuario, pues este será el que al final de cuentas interesa. Existen en la actualidad infinidad de tecnologías en cuanto a los gestores de la base de datos se refiere, el que utilizaremos (el mas actual) será SQL SERVER, este gestor comenzó a crearse por la década de los 90´s, ofrece muchas ventajas sobre otros gestores, la única desventaja que podríamos encontrar en su compatibilidad con los Windows mas comerciales como el 98, XP entre otros. Se preguntaran que tiene que ver el gestor con los algoritmos de datos no replicados, sin embargo la respuesta es muy sencilla, y esta es que este algoritmo es fácil de implantar en SQL SERVER.

Ejercicios

Ejercicio de diseño de base de datos distribuidos: La sociedad médica.

Primero se realiza una proyección de la tabla:

∏código, nombre, dirección, salario, centro (empleado where (centro.código=0))

Fragmentación vertical.

Código

Nombre

Dirección

Salario

Centro

En el resto de centros, los horarios de sus consultas y la información de su personal y de sus especialidades.

Se hace una proyección de en su mayoría los campos de la tabla centro, después también se toman las demás tablas para saber la informacion que se quiere obtener.

∏código, nombre, dirección, teléfono (centro) AND hora (consulta) AND fecha_inic (empleado) AND descripción (especialidad)

Fragmentación vertical.

Código

Nombre

Dirección

Teléfono

Hora

Fecha_inic

Descripción

Ejercicio de diseño de base de datos distribuidoas: servicios informáticos.

Se realiza una fragmentación horizontal (selección) de los atributos de la tabla proyecto.

código, nombre, presupuesto, empresa, jefe, unidad (proyecto)

Fragmentación horizontal.

Código

Nombre

Presupuesto

Empresa

Jefe

Unidad

Así mismo, se realiza también una fragmentación horizontal (selección) con la tabla empleado, arrojando los siguientes datos:

código, nombre, apellidos, dirección, unidad (empleado)

Fragmentación horizontal.

Código

Nombre

Apellidos

Dirección

Unidad

La unidad de recursos humanos realiza la facturación y usa todos los datos de las empresas. El resto de unidades sólo necesita el código y nombre de las empresas con las que trabaja.

Como se desea saber todos los datos de la empresa se hace una selección de todos los atributos de la misma, luego se impone una condición donde solo se necesita el código de las empresas, y los proyectos con los que se esta trabajando.

código, nombre, dirección, correos (empresa where  empresa.código= proyecto.empresa AND (proyecto.unidad=unidad.código AND (unidad.edificio=edificio.código=0)))

Fragmentación horizontal.

Código	Nombre	Dirección	Correos

código, nombre (empresa where (empresa.código=proyecto.empresa AND (proycto.unidad=unidad.código NOT (unidad.edificio=edificio.código=0)))

Fragmentación horizontal.

Código

Nombre

Hay proyectos internos, y por tanto sin factura, que tienen valor nulo en su campo empresa.

código, nombre, presupuesto, jefe, unidad (proyecto)

Fragmentación horizontal.

Código

Nombre

Presupuesto

Jefe

Unidad