Apunte de Serializabilidad (Bases de Datos)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

ACID[editar]

Son propiedades deseables que garantizan que al ejecutarse una transacción la base de datos quede en un estado consistente (suponiendo que partio de uno).

  • Atomicidad: T se ejecuta completamente o no se ejecuta por completo (todo o nada)
  • Consistencia: T transforma un estado consistente de la BD en otro estado consistente (los programas deben ser correctos)
  • Aislamiento: Las Ti se ejecutan sin interferencias.
  • Durabilidad: Las actualizaciones a la BD serán durables y públicas.


Serializabilidad[editar]

Una historia es serializable sii es equivalente a una historia serial, es decir, una historia en la que cada transacción ocurre completamente luego de la otra (no hay interleaving). Dos historias son equivalentes si estan definidas sobre las mismas transacciones y las operaciones conflictivas tienen el mismo orden.

Un par cualquiera de operaciones es conflictivo si estan definidas sobre el mismo item y alguna de las dos operaciones es un write. Dos reads sobre un mismo item no conflictuan.

Grafo de Precedencia[editar]

Para determinar si una historia es serializable se construye su grafo de precedencias. Si es aciclico, entonces es serializable, y es equivalente a cualquier ordenamiento topologico del grafo.

El digrafo se construye poniendo un nodo por cada transaccion, y un arco de una transaccion Ti a Tj sii alguna operacion de Ti precede y conflictua con otra de Tj. Es decir, dadas dos transacciones que operan sobre un mismo item, si alguna de las dos hace un write, se hace un arco de la primera que accede el item hacia la segunda.


Locking[editar]

Al analizar locking no se consideran las operaciones de read, write, start, commit o abort, sino solamente las operaciones de lock y unlock.

Hay dos tipos de locking. El locking binario utiliza locks exclusivos y tiene dos primitivas: lock y unlock sobre un item. El locking ternario diferencia entre read locks (compartidos para lectura) y write locks (exclusivos y de escritura).

Se supone que para leer o escribir un item se debe lockearlo primero, y para lockear un item es necesario esperar a que la transaccion que lo tenga lockeado lo libere (en caso de que haya un lock exclusivo). Estas son las reglas de legalidad del locking para una historia.

Grafos de Precedencia[editar]

El grafo de precedencia de locking binario se construye teniendo nuevamente un nodo por transaccion, y un arco de Ti a Tj si Ti hace unlock de un recurso y luego Tj hace lock.

Para el caso de ternario, los nodos siguen siendo las transacciones, y los arcos se hacen en dos casos.

  • Si una transaccion Ti hace lock (R o W) de un item X y luego Tj es la proxima en hacer WLock, se hace un arco de Ti a Tj. Notar que el arco solamente vale para la inmediata siguiente en hacer el WLock.
  • Si una transaccion Ti hace WLock de X, luego para todas las Tj que hagan RLock de X antes del proximo WLock se dibuja un arco de Ti a Tj.

Two Phase Locking[editar]

El protocolo 2PL, two phase locking, indica que si todas las transacciones en un conjunto son 2PL entonces toda historia definida sobre ese conjunto será serializable.

Una transacción se define como 2PL sii todos los locks preceden al primer unlock. Es decir, la transacción primero pide todos los recursos (locks) y luego los libera (unlocks).


Criterios de Recuperabilidad[editar]

Los siguientes son los criterios de recuperabilidad; se encuentran ordenados del más débil al más fuerte. Es decir, vale que ST => ACA => RC.

  • RC: H es recuperable (recoverable) si cada transacción commitea después del commitment de todas las transacciones (otras que si misma) de las cuales lee.
  • ACA: H es evita aborts en cascada (avoids cascade aborts) si cada transacción puede leer solamente aquellos valores que fueron escritos por transacciones commiteadas (o por si misma).
  • ST: H es estricta (strict) si ningún ítem X puede ser leído o sobrescrito hasta que la transacción que previamente escribió X finaliza abortando o commiteando.