Confiabilidad:
En cualquier sistema de bases de datos, centralizado o distribuido, se debe ofrecer garantías de que la información es confiable. Así cada consulta o actualización de la información se hace mediante transacciones, las cuales tiene un inicio y un fin. En sistemas distribuidos el manejo de la durabilidad de las transacciones es aun más complejo, ya que una sola transacción puede involucrar 2 o más sitios de la red. Entonces el control de recuperación en sistemas distribuidos debe asegurar que el conjunto de agentes que participan en una transacción realicen todo un compromiso (commit)) de que toso al mismo tiempo restablezcan la información anterior (roll-back).
domingo, 18 de noviembre de 2012
Algoritmos de Control de Concurrencia
Basados en Bloqueos
Basados en estampas de tiempo
Pruebas de validación optimistas
Fuentes: http://es.scribd.com/doc/80796514/Ensayo-Base-de-Datos-Distribuidos-Leonel
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.
|
rl
|
wl
|
rl
|
Si
|
No
|
Wl
|
No
|
No
|
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.
Basados en estampas de tiempo
A diferencia de los algoritmos basados en candados, 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 priori y ejecutan las transacciones de acuerdo a ellas. Para
establecer este ordenamiento, el administrador de transacciones le asigna a
cada transacción Ti una estampa de tiempo única ts (Ti ) cuando
ésta inicia. Una estampa de tiempo es un identificador simple que
sirve para identificar cada transacción de manera única. Otra propiedad de las
estampas de tiempo es la monoticidad , esto es, dos estampas de tiempo
generadas por el mismo administrador de transacciones deben ser monotonicamente
crecientes. Así, las estampas de tiempo son valores derivados de un dominio
totalmente ordenado.
Existen varias formas en que las estampas de tiempo se
pueden asignar. Un método es usar un contador global monotonicamente creciente.
Sin embargo, el mantenimiento de contadores globales es un problema en sistemas
distribuidos. Por lo tanto, es preferible que cada nodo asigne de manera autónoma
las estampas de tiempos basándose en un contador local. Para obtener la
unicidad, cada nodo le agrega al contador su propio identificador. Así, la
estampa de tiempo es un par de la forma
<contador local ,identificador de nodo >
Note que el identificador de nodo se agrega en la posición
menos significativa, de manera que, éste sirve solo en el caso en que dos nodos
diferentes le asignen el mismo contador local a dos transacciones diferentes.
El administrador de transacciones asigna también una estampa de tiempo a todas
las operaciones solicitadas por una transacción. Más aún, a cada elemento de
datos x se le asigna una estampa de tiempo de escritura, wts (x ),
y una estampa de tiempo de lectura ,rts (x ); sus valores
indican la estampa de tiempo más grande para cualquier lectura y escritura
de x , respectivamente.
Pruebas de validación optimistas
Fuentes: http://es.scribd.com/doc/80796514/Ensayo-Base-de-Datos-Distribuidos-Leonel
Actividad
Responda lo siguiente:
¿Que es álgebra relacional?
El álgebra relacional es un conjunto de operaciones que describen paso a paso como computar una respuesta sobre las relaciones, tal y como éstas son definidas en el modelo relacional.
Describe el aspecto de la manipulación de datos. Estas operaciones se usan como una representación intermedia de una consulta a una base de datos y, debido a sus propiedades algebraicas, sirven para obtener una versión más optimizada y eficiente de dicha consulta.
¿Como se aplica el algebra relacional a la optimizacion de consultas en Mysql?
¿Como se representa la proyección y la selección relacionado con las consultas a bases de datos?
¿Para que nos sirve la división (hablando de álgebra relacional) en las consultas?
presente 2 ejemplos que incluyan la utilización de el álgebra relacional
Estas operaciones son fundamentales en el sentido en que (1) todas las demás operaciones pueden ser expresadas como una combinación de éstas y (2) ninguna de estas operaciones pueden ser omitidas sin que con ello se pierda información.
Una reunión theta ( θ-Join) de dos relaciones es equivalente a:
Fuente de información : http://es.wikipedia.org/wiki/%C3%81lgebra_relacional#Proyecci.C3.B3n_.28.CE.A0.29
RESUELVA:
¿Que es álgebra relacional?
El álgebra relacional es un conjunto de operaciones que describen paso a paso como computar una respuesta sobre las relaciones, tal y como éstas son definidas en el modelo relacional.
Describe el aspecto de la manipulación de datos. Estas operaciones se usan como una representación intermedia de una consulta a una base de datos y, debido a sus propiedades algebraicas, sirven para obtener una versión más optimizada y eficiente de dicha consulta.
¿Como se aplica el algebra relacional a la optimizacion de consultas en Mysql?
¿Como se representa la proyección y la selección relacionado con las consultas a bases de datos?
¿Para que nos sirve la división (hablando de álgebra relacional) en las consultas?
presente 2 ejemplos que incluyan la utilización de el álgebra relacional
Las operaciones
Básicas
Cada operador del álgebra acepta una o dos relaciones y retorna una relación como resultado. σ y Π son operadores unarios, el resto de los operadores son binarios. Las operaciones básicas del álgebra relacional son:
Seleccióna (σ)
Permite seleccionar un subconjunto de tuplas de una relación (R), todas aquellas que cumplan la(s) condición(es) P, esto es:
Ejemplo:
Selecciona todas las tuplas que contengan Gómez como apellido en la relación Alumnos.
Una condición puede ser una combinación booleana, donde se pueden usar operadores como: , , combinándolos con operadores .
Proyección (Π)
Permite extraer columnas (atributos) de una relación, dando como resultado un subconjunto vertical de atributos de la relación, esto es:
donde son atributos de la relación R .
Ejemplo:
Selecciona los atributos Apellido, Semestre y NumeroControl de la relación Alumnos, mostrados como un subconjunto de la relación Alumnos
Producto cartesiano (x)
El producto cartesiano de dos relaciones se escribe como:
y entrega una relación, cuyo esquema corresponde a una combinación de todas las tuplas de R con cada una de las tuplas de S, y sus atributos corresponden a los de Rseguidos por los de S.
Ejemplo:
Muestra una nueva relación, cuyo esquema contiene cada una de las tuplas de la relación Alumnos junto con las tuplas de la relación Maestros, mostrando primero los atributos de la relación Alumnos seguidos por las tuplas de la relación Maestros.
Unión (∪)
La operación
retorna el conjunto de tuplas que están en R, o en S, o en ambas. R y S deben ser uniones compatibles.
Diferencia (-)
La diferencia de dos relaciones, R y S denotada por:
entrega todas aquellas tuplas que están en R, pero no en S. R y S deben ser uniones compatibles.
Estas operaciones son fundamentales en el sentido en que (1) todas las demás operaciones pueden ser expresadas como una combinación de éstas y (2) ninguna de estas operaciones pueden ser omitidas sin que con ello se pierda información.
No básicas o Derivadas
Entre los operadores no básicos tenemos:
Intersección (∩)
La intersección de dos relaciones se puede especificar en función de otros operadores básicos:
La intersección, como en Teoría de conjuntos, corresponde al conjunto de todas las tuplas que están en R y en S, siendo R y S uniones compatibles.
Unión natural () (Natural Join)
La operación unión natural en el álgebra relacional es la que permite reconstruir las tablas originales previas al proceso de normalización. Consiste en combinar las proyección, selección y producto cartesiano en una sola operación, donde la condición es la igualdad Clave Primaria = Clave Externa (o Foranea), y la proyección elimina la columna duplicada (clave externa).
Expresada en las operaciones básicas, queda
Una reunión theta ( θ-Join) de dos relaciones es equivalente a:
donde la condición es libre.
Si la condición es una igualdad se denomina EquiJoin.
División (/)
Supongamos que tenemos dos relaciones A(x, y) y B(y) donde el dominio de y en A y B, es el mismo.
El operador división A / B retorna todos los distintos valores de x tales que para todo valor y en B existe una tupla en A.
Agrupación (Ģ)
Permite agrupar conjuntos de valores en función de un campo determinado y hacer operaciones con otros campos.
Por ejemplo: Ģ sum(puntos) as Total Equipo (PARTIDOS).
Fuente de información : http://es.wikipedia.org/wiki/%C3%81lgebra_relacional#Proyecci.C3.B3n_.28.CE.A0.29
RESUELVA:
[2] Π código , descripción
(σ código= descripción P)
[3] Π nombre C, U , Π Id
Venta V (σ cantidad >500 V)
[4] Π nombre C
- V
[5] Π nombre C = V
[6] Π Id Venta (cantidad > cantidad(Id Venta =18)V)
[7] Π P – (σ población = “Palencia” C)
[8] Π P(V=(σ población = “Palencia, Valladolid” C ))
miércoles, 7 de noviembre de 2012
Cierre unidad III
Álgebra relacional aplicada a bases de datos distribuidas ( definición y ejemplos)
Definir fragmentos verticales se hace a través del operador de proyección del álgebra relacional operando sobre una relación global.
Analizar
Heurísticas
Es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas (tiempo, espacio, etc.), o cuando no existe del todo.
Acceso concurrente
Un sistema que permite a varias estaciones de trabajo modificar en forma simultánea una misma base de datos.
Fuentes de información:
http://isisabcd.pbworks.com/w/page/33368354/Acceso%20concurrente%20a%20bases%20de%20datos
http://es.wikipedia.org/wiki/Heur%C3%ADstica_(inform%C3%A1tica)
http://definicion.dictionarist.com/parsing
http://www.carlosproal.com/bda/bda05.html
jueves, 1 de noviembre de 2012
Optimización de consultas distribuidas
Optimización de consultas distribuidas
El objetivo del procesamiento
de consultas en un ambiente distribuido es transformar una consulta sobre
una base de datos distribuida en una especificación de alto nivel a una estrategia de ejecución eficiente
expresada en un lenguaje de bajo nivel sobre bases de datos locales.
El problema de optimización de consultas es minimizar una
función de costo tal que función de costo total = costo de I/O + costo de CPU +costo
de comunicación.
Por ejemplo:
En las redes de área amplia (WAN), normalmente el costo de comunicación domina dado que hay una velocidad de comunicación relativamente
baja, los canales están saturados y el trabajo adición al requerido por los
protocolos de comunicación es considerable.
Así, los algoritmos diseñados para trabajar en una WAN, por
lo general, ignoran los costos de CPU y de I/O. En redes de área local (LAN) el
costo de comunicación no es tan dominante, así que se consideran los tres factores
con pesos variables.
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.
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 consulta que se ejecuta en un nodo,
llamada consulta local, es optimizada usando el esquema local del nodo. Hasta
este momento, se eligen los algoritmos para realizar las operaciones
relacionales. La optimización local utiliza los algoritmos de sistemas
centralizados.
Fuente de informacion: http://es.scribd.com/doc/44436671/Unidad-III
Suscribirse a:
Entradas (Atom)