Actividad #16

PROCESAMIENTO DE CONSULTAS 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.

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.

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.

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 

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.

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.

Objetivos de la optimización de consultas

Como se estableció antes, 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.

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 oel uso de heurísticas. 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. 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.

Localización de Datos

La entrada a esta capa es una consulta algebraica definida sobre relaciones distribuidas. El objetivo de esta capa es localizar los datos de la consulta usando la información sobre la distribución de datos. Esta capa determina cuales fragmentos están involucrados en la consulta y transforma la consulta distribuida en una consulta sobre fragmentos.

Optimización Global de Consultas

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. La optimización local utiliza los

algoritmos de sistemas centralizados.

Actividad #15

Consultas Distribuidas

• Las consultas distribuidas detienen acceso a datos de varios orígenes de datos heterogéneos.
• Estos orígenes de datos pueden estar almacenados en el mismo equipo o en equipos diferentes.

Optimización de consulta

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.

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

1. A través del álgebra relacional intenta hallar una expresión equivalente a la expresión dada ƒ 
2. Elección de una estrategia detallada para el procesamiento de la consulta: 

• Selección del algoritmo que se usará para ejecutar una operación
• 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.

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

Procesamiento de consultas distribuidas

Arboles de consultas

Son estructuras de datos en forma de árbol, en donde, los datos al estar ordenados en la estructura, hace mas ágiles las consultas.

Pasos para el arboles de 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 de JOIN

• Join – Reunión
• Todas las tuplas que estén en ambas tablas
• Símbolo ∞

Tipos de Join:

Reunion natural

• reunion de tablas con todos los atributos del mismo nombre de ambas tablas.

Semireunion

• solo las tuplas que cumplan las condiciones

Left outer join

• reuniom externa por la izquierda
• todas las tuplas de R aunque no esten en S
• Los campos donde no hay correspondencia se asocian a NULL

Rigth outer join

• reuniom externa por la derecha
• todas las tuplas de S aunque no esten en R
• Los campos donde no hay correspondencia se asocian a NULL

Evidencia de la expocision:

Actividad #13

Esquema de framentación y distribución de una BDD

El objetivo de la fragmentación es encontrar un nivel de particionamiento adecuado en el rango que va desde tuplas o atributos hasta relaciones completas.Cada relación global puede ser dividida en porciones que no se solapen llamados fragmentos. 
El mapa resultante se denomina esquema de fragmentación. Una relación global puede dividirse en n fragmentos y un fragmento sólo puede pertenecer a una relación global.

Los fragmentos son porciones lógicas de relaciones globales que pueden estar físicamente ubicadas en uno o varios nodos de la red. 

El esquema de ubicación define en qué nodos un fragmento va a ser almacenado. El tipo de mapa definido en el esquema de ubicación determina si la BDD es redundante o no. Todos los fragmentos que corresponden a la misma relación global R y están ubicados en el mismo nodo constituyen la imagen física de una relación global R en el nodo. Las imágenes físicas se pueden referenciar por el nombre de la relación global R y un superíndice; por ejemplo, Rj indica la imagen física de la relación global R en el nodo j.

se denomina copia de fragmento a la información de un fragmento en un nodo determinado en un nodo dado, y se denota usando el nombre de la relación global, un subíndice y un superíndice. Por ejemplo, R3 2 indica copia del fragmento R2 que está ubicado en el nodo 3. Dos imágenes físicas pueden ser idénticas; se dice entonces que una imagen física es copia de otra imagen física.

Esquema de fragmentacion:

Es el conjunto de fragmentación que:

• fragmentación completa: todos los atributos y tuplas están en algún fragmento.
• permite reconstruir la BD original

Presentación:

Actividad #12

Sistema de Gestión de Base de Datos Distribuida

Un sistema de gestión de bases de datos distribuidas (SGBDD) es un Sistema de Gestión de bases de datos que gestiona la BD distribuida

Funcionalidades adicionales de un SGBDD

• Accede a sitios remotos y transmite consultas y datos a través de varios sitios mediante una red de comunicación.
• Almacena el esquema de distribución y replicación de los datos en el catalogo del sistema.
• Establece las estrategias de ejecución de las consultas y las transacciones que acceden a los datos en más de un sitio.
• Decide sobre cual copia de los datos replicados acceder.
• Mantiene la consistencia de las copias de los datos replicados.
• Realiza la recuperación ante los fallos.

Oracle
es una potente herramienta cliente/servidor para la gestión de Bases de Datos. Explicamos la herramienta y las ayudas que ofrece al desarrollador.

Oracle es básicamente una herramienta cliente/servidor para la gestión de Bases de Datos. Es un producto vendido a nivel mundial, aunque la gran potencia que tiene y su elevado precio hace que sólo se vea en empresas muy grandes y multinacionales, por norma general. En el desarrollo de páginas web pasa lo mismo: como es un sistema muy caro no está tan extendido como otras bases de datos, por ejemplo, Access, MySQL, SQL Server, etc.

Microsoft SQL Server 

es un sistema para la gestión de bases de datos producido por Microsoft basado en el modelo relacional. Sus lenguajes para consultas son T-SQL y ANSI SQL. Microsoft SQL Server constituye la alternativa de Microsoft a otros potentes sistemas gestores de bases de datos como son Oracle, PostgreSQL o MySQL.

PostgreSQL

es un Sistema de gestión de bases de datos relacional orientado a objetos y libre, publicado bajo la licencia BSD. Como muchos otros proyectos de código abierto, el desarrollo de PostgreSQL no es manejado por una empresa y/o persona, sino que es dirigido por una comunidad de desarrolladores que trabajan de forma desinteresada, altruista, libre y/o apoyados por organizaciones comerciales. Dicha comunidad es denominada el PGDG (PostgreSQL Global Development Group).

MySQL 

es un sistema de gestión de bases de datos relacional, multihilo y multiusuario con más de seis millones de instalaciones. MySQL AB—desde enero de 2008 una subsidiaria de Sun Microsystems y ésta a su vez de Oracle Corporation desde abril de 2009— desarrolla MySQL como software libre en un esquema de licenciamiento dual.

Resumen 1: Bases de datos Distribuidas(BDD)

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

– No han de ser homogéneos

– Dividen un problema en otros más manejables y los resuelven de modo coordinado

• BD distribuida (BDD): son varias BD interrelacionadas lógicamente y situadas en diferentes nodos de una red de ordenadores.

• SGBD distribuido: el que gestiona BD distribuidas de forma transparente para el usuario (éste ve las BD como si fueran una sola BD centralizada)

• Ventajas de las BDD:

– Localización transparente de los datos: las instrucciones no dependen de dónde se ejecutan ni de dónde se sitúan los datos

– Transparencia en los nombres: un objeto se accede por su nombre, sin ambigüedad y sin especificar nada más.

– Transparencia de fragmentación: fragmentación horizontal es distribuir una tabla en varios conjuntos de tuplas (cada uno en un ordenador). La vertical en distribuir la tabla en conjuntos de atributos. La consulta sobre la tabla se transforma de modo automático en varias consultas sobre sus fragmentos

Fragmentar: decidir dónde situar las partes de la BDD 

– Se puede plantear top-down (como aquí) o bottom-up 

• Idea simple: situar cada tabla en un ordenador distinto

La replicación mejora la disponibilidad de los datos

• Caso extremo: tener una réplica de la BD completa en cada sitio (ordenador):

– Ventajas: mejora el rendimiento local y global además de la disponibilidad (con un sitio activo se accede a toda la BD) 

– Inconvenientes: actualizaciones más costosas (se deben realizar en todas las réplicas para mantener la coherencia). El control de concurrencia y recuperación es también más costoso.

• Esquema de replicación: describe qué se replica

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

– La elección del lugar y el grado de replicación depende de los objetivos de rendimiento y disponibilidad. También del tipo de transacciones y su frecuencia.

– Encontrar una solución óptima o incluso una buena es un problema complejo

Resumen 2: Diseño de un sistema gestor de base de datos distribuida basado en Oracle9i

Una BDD (base de datos distribuida) a “una colección lógicamente interrelacionada de datos compartidos (junto con una descripción de estos datos) físicamente distribuidas por una red informática”

Un SGBDD se compone de una única base  de datos lógica, que físicamente está dividida en fragmentos ubicados en nodos distintos e interconectados mediante una red de comunicaciones.

La diferencia entre SGBD distribuido y SGBD paralelo definido como “un SGBD  que se ejecuta sobre múltiples procesadores y utilizando múltiples discos y que está diseñado para ejecutar las operaciones en paralelo”

El factor más importante que diferencia a  unos SGBDD de otros es la transparencia.

Esto supone que no se requiere soporte para la manipulación de datos (transparente para el usuario) pero si se requieren operaciones de definición de datos (FRAGMENT, REPLICATE).

Desde el punto de vista académico los dos tipos de software conocidos son:

•  Microsoft Access, con un SGBD muy sencillo porque da soporte a una base de datos de oficina muy poco sofisticada. No proporciona funcionalidad de BDD, pero se pueden implementar módulos que simulen la fragmentación, replicación y consultas distribuidas. Sin embargo, no se garantiza la fiabilidad del SGBDD desarrollado.

•  MySQL, no proporciona actualmente soporte alguno para los BDD verdaderos.

•  Oracle9i, (KOCH, G., 2003); no ofrece utilidades para fragmentar, replicar y realizar consultas optimizadas, pero se  la ha elegido como plataforma para desarrollar la transparencia debido a sus prestaciones como SGBD.

El catálogo en una base de datos centralizada proporciona la información relativa a las relaciones, vistas e índices se almacena en un CATALOGO o DICCIONARIO DE DATOS.

Fragmentación de la base de datos original: La fragmentación debe poder ser mixta y derivada con asignación de los fragmentos a distintos nodos. La fragmentación mixta es una combinación de horizontal y vertical. La fragmentación horizontal se aplica cuando se extraen fragmentos por selección de tuplas que cumplan una determinada condición.  La fragmentación vertical se aplica cuando se extraen fragmentos por selección de atributos de todas las tuplas. Por tanto, la fragmentación mixta se aplica a la selección de varios  atributos de las tuplas que cumplan una determinada condición. La fragmentación derivada es aquella que afecta a más de una tabla porque el criterio de fragmentación de una tabla afecta a atributo(s) que actúa(n) como clave extranjera en otra(s).

Actividad #11

Tipos de Fragmentación

Existen  tres  tipos  de  fragmentación:

1.  Fragmentación horizontal

2. Fragmentación vertical

3. Fragmentación mixta o híbrida.

Dado que una relación se corresponde esencialmente con una tabla y la cuestión consiste en dividirla en fragmentos menores, inmediatamente surgen dos alternativas lógicas para llevar a cabo el proceso: la división horizontal y la división vertical. Estos  dos  tipos  de  partición  podrían  considerarse  los fundamentales y básicos. Sin embargo, existen otras alternativas. Fundamentalmente, se habla de fragmentación mixta o híbrida cuando el proceso de partición hace uso de los dos tipos anteriores.

En algunos lenguajes y especialmente en la teoría de bases de datos, una tupla se define como una función finita que mapea (asocia unívocamente) los nombres con algunos valores.

FRAGMENTACIÓN HORIZONTAL (HF):
La fragmentación horizontal se realiza sobre las tuplas de la relación. Cada fragmento será un subconjunto de las tuplas de la relación. Existen dos variantes de la fragmentación horizontal: la primaria y la derivada. La fragmentación horizontal primaria de una relación se desarrolla empleando los predicados definidos en esa relación. Por el contrario, la fragmentación horizontal derivada consiste en dividir una relación partiendo de los predicados definidos sobre alguna otra.

Fragmentación Vertical:
El objetivo de la fragmentación vertical consiste en dividir la relación en un conjunto de relaciones más pequeñas tal que algunas de las aplicaciones de usuario sólo hagan uso de un fragmento. Sobre este marco, una fragmentación óptima es aquella que produce un esquema de división que minimiza el tiempo de ejecución de las aplicaciones que emplean esos fragmentos.

Fragmentación mixta o híbrida:
En muchos casos la fragmentación vertical u horizontal del esquema de la base de datos no será suficiente para satisfacer los requisitos de las aplicaciones. Como ya se citó al comienzo de este documento podemos combinar ambas, utilizando por ello la denominada fragmentación mixta. Cuando al proceso de fragmentación vertical le sigue una horizontal, es decir, se fragmentan horizontalmente los fragmentos verticales resultantes, se habla de la fragmentación mixta HV

Presentación

Actividad #10

¿Qué es una transacción?

Es una unidad de la ejecución de un programa que accede y posiblemente actualiza varios elementos de datos.

¿Qué significa ACID?  y defina cada una de las palabras que forman las sigla

ACID: Atomicity, Consistency, Isolation y Durability

• La atomicidad asegura que, o bien todos los efectos de la transacción se reflejan en la base de datos, o bien ninguno de ellos; un fallo no puede dejar a la base de datos en un estado en el cual una transacción se haya ejecutado parcialmente.
•  La consistencia asegura que si la base de datos es consistente inicialmente, la ejecución de la transacción (debido a la misma) deja la base de datos en un estado consistente.
• El aislamiento asegura que en la ejecución concurrente de transacciones, están aisladas entre sí, de tal manera que cada una tiene la impresión de que ninguna otra transacción se ejecuta concurrentemente con ella.
• La durabilidad asegura que, una vez que la transacción se ha comprometido, las actualizaciones hechas por la transacción no se pierden incluso si hay un fallo del sistema. 

¿Qué significa Tx?

Tx significa Transmisión o Transmisor (en este caso Transacción).

¿Para que nos sirve el Rollback?

En tecnologías de base de datos, un rollback es una operación que devuelve a la base de datos a algún estado previo.

Defina Integridad de datos

Integridad de datos en general: hace referencia a que todas las características de los datos (reglas, definiciones, fechas, etc) deben ser correctos para que los datos estén completos.

Integridad de datos en bases de datos: Integridad de datos se refiere al estado de corrección y completitud de los datos ingresados en una base de datos.

Defina concurrencia

La concurrencia es la propiedad de los sistemas que permiten que múltiples procesossean ejecutados al mismo tiempo, y que potencialmente puedan interactuar entre sí.

Defina Grado de consistencia

Podría definirse como la coherencia entre todos los datos de la base de datos.

Mencione aspectos relacionados al procesamiento de transacciones

• Modelo de estructura de transacciones: Es importante considerar si las transacciones son planas o pueden estar anidadas.
• Consistencia de la base de datos interna: Los algoritmos de control de datos semántico tienen que satisfacer siempre las restricciones de integridad cuando una transacción pretende hacer un commit.
• Protocolos de confiabilidad: En transacciones distribuidas es necesario introducir medios de comunicación entre los diferentes nodos de una red para garantizar la atomicidad y durabilidad de las transacciones. Así también, se requieren protocolos para la recuperación local y para efectuar los compromisos (commit) globales.
• Algoritmos de control de concurrencia: Los algoritmos de control de concurrencia deben sincronizar la ejecución de transacciones concurrentes bajo el criterio de correctitud. La consistencia entre transacciones se garantiza mediante el aislamiento de las mismas.
• Protocolos de control de réplicas: El control de réplicas se refiere a cómo garantizar la consistencia mutua de datos replicados. Por ejemplo se puede seguir la estrategia read-one-write-all (ROWA).

Defina los estados de una transacción:

• Activa: el estado inicial; la transacción permanece en este estado durante su ejecución.
• Parcialmente comprometida, después de ejecutarse la última instrucción.
• Fallida, tras descubrir que no puede continuar la ejecución normal.
• Abortada, después de haber retrocedido la transacción y restablecido la base de datos a su estado anterior al comienzo de la transacción.
• Comprometida, tras completarse con éxito.