Resumen para el final de Base de Datos

• Modificación
• Inserción (Se solucionan descomponiendo)
• Eliminación

• Descomposición sin pérdida de información
  • El tableau de Chase verifica si una determinada descomposición arbitraria es sin pérdida de información.
• Preservacion de dependencias
  • Algoritmo:

La X⁺(clausura de X) es el conjunto de atributos que dependen de X. Si todos los atributos de una relacion dependen de X, entonces X es superclave. Para que un grupo de dependencias sea equivalente a otro, sus clausuras deben ser equivalentes.

• Algoritmo:

El recubrimiento minimal es un grupo de dependencias equivalente al original, pero lo mas simplificado posible.
Propiedades:

• Todos los lados derechos son unitarios
• Los lados izquierdos no son redundantes
• No hay dependencias funcionales redundantes

1FN ← 2FN ← 3FN ← FNBC ← 4FN ← FNPJ (5FN) Nos orientan a conseguir descomposiciones que cumplan una serie de normas

• 3FN: Para todo X→Y, X es superclave de R o Y es subconjunto de clave de R
  • Existe un algoritmo capaz de obtener una descomposición sin pérdida de información ni dependencias
  • Hay mas redundancia que en FNBC
• FN de Boyce Codd: Toda X→Y es trivial o X es superclave.
  • Menor redundancia que en 3FN
  • No garantiza una completa eliminacion de la redundancia (debido a dfmv)
  • Existe un algoritmo capaz de obtener una descomposición sin pérdida de información, pero no garantiza la preservacion de dependencias funcionales
• 4FN: Toda X →→Y es trivial o X es superclave
  • Satisface FNBC y 3FN (obviamente…)
• 5FN: Toda dj es trivial o es implicada (df) por las claves de R

X multidetermina a Y (X→→Y) cuando para cada valor de X existe un conjunto de valores de Y y ese conjunto es independiente de los restantes atributos (R-XY). Las dependencias funcionales son un caso particular de las dmv's. Condiciones:

• t₁[X] = t₂[X] = t₃[X] = t₄[X]
• t₁[Y] = t₃[Y] ^ t₂[R-XY] = t₃[R-XY]
• t₂[Y] = t₄[Y] ^ t₁[R-XY] = t₄[R-XY]
• X→→Y es trivial si: YcX ó R=XY

NOTA: Encontrar dmv's a un esquema puede generar NUEVAS df's al esquema (ver axioma 5).

1. Complementación: X→→Y => X→→(R-XY)
2. Aumento: V c W ^ X→→Y => XW→→YV
3. Transitividad: X→→Y ^ Y→→Z => X→→(Z-Y)
4. Conversión: X→Y => X→→Y
5. Interacción: X→→Y ^ ∃ W/ WnY=0 ^ ∃ ZcY ^ W→Z => X→Z
6. Unión: X→→Y ^ X→→Z => X→→YZ
7. Pseudo-transitividad: X→→Y ^ YW→→Z => XW→→(Z-YW)
8. Pseudo-transitividad mixta: X→→Y ^ XY→→Z => X→→(Z-Y)
9. Descomposición: ???

Similar al concepto de clausura para un conjunto de atributos.
Si C es un conjunto CERRADO de atributos no vacios, cualquier conjunto de atributos multideterminado por C puede ser obtenido mediante operaciones de conjuntos sobre los subconjuntos de atributos que forman la Base de Dependencias de C

• Base de Dependencias minimal ⇒ minima cantidad de atributos posibles.
• Algoritmo:

Son dmv's que no existen en un esquema original R, pero que son satisfechas en una determinada descomposición del mismo.

Son un caso más general de dependencias. Las dmvs son un caso particular de estas.
Se definen como |x|[R1,….,Rk] como una descomposición de R tal que cualquier instancia r(R) es la junta sin pérdida de sus proyecciones Ri.
Una dmv x→>y sobre R se puede extresar como la dj |x|[XY, X(R-XY)] ya que por una propiedad de las dmvs r(R) satisface la dmv x→>y si y solo si r se puede descomponer sin pérdida de información en los esquemas XY y X(R-XY).
Existe un algoritmo derivado de la tableau de Chase para determinar si una dj (dependencia de junta) es implicada por un conjunto determinado de otras dj.

• Todo en memoria principal, un archivo por tabla, o todas las tablas en un archivo
• los bloques de memoria contienen completar

Se utilizan Buffers en memoria principal debido al costo en tiempos de acceder a memoria estable. Es transparente a los modulos que requieren bloques y utilizan politicas de reemplazo de información en sus buffers debido a que la memoria principal es acotada.

• Indice secuencial, índice denso o su evolucion, el Arbol B
• Hashing estático, Hashing dinámico (por ej. extensible)

El Hashing dinámico es al estático lo que el Arbol B es al índice secuencial. FALTA índices multiples, IMPORTANTE. Revisar el resto del cap por que esto esta muy pobre

• Analizador sintáctico y semántico: Verifica que la consulta este bien escrita y que las tablas y atributos pedidos existan en la BD
• Generacion de codigo intermedio: Expresion de algebra relacional
• Generacion de Arbol de consulta
• Optimización algebraica, Optimización de costos
• Evaluacion → Relacion de respuesta

* Comunicaciones (no tenemos en cuenta BD distribuidas) * Accesos a memoria secundaria * Tiempo de procesador (generalmente desreciado frente al anterior)

Mediante equivalencias algebraicas, transformar las consultas para realizar lo antes posible:

• Selecciones: acotando la cantidad de tuplas de los resultados parciales
• Juntas Naturales en las que participen la menor cantidad de tuplas posibles
• Proyecciones: acotando el tamaño de los resultados parciales
• Operaciones Booleanas

• Sin Indices:
  • Secuencial(el mas lento de todos) Costo = Br + Mr.Bs
  • Por bloques(se utiliza para tablas chicas sin indexar) Costo = Br + Bs
  • Sort-Merge(leo cada bloque solo una vez, sin importar el tamaño de las tablas) Costo = Br + Bs + Bs.Log₂Bs
• Con Indices:
  • Indice normal (Accedo solo a los bloques indicados por el índice) Costo = Mr.Ms/v(A,S) + Br
  • de agrupamiento (Accedo solo a los bloques indicados por el índice, pero ademas las tuplas buscadas se concentran en estos bloques) Costo=Br+Mr.Bs/v(A,S)
• Método simple de Hash
• Método Grace (genera un nuevo archivo ordenando cada tupla por su hash) Costo=3(Br+Bs)
• Método de índice de juntas con mapas de Bits

Comentar algo…

Evitan la necesidad de guardar en memoria secundaria los resultados parciales.

Método: [(T₁,L₁→T₂),L₁→T₃],L₁→T₄ y luego lo mismo con L₂…L_N[T=Tabla, L=Linea]

(propiedades que un SGBD garantiza a las transacciones que ejecuta)

• Atomicidad: Una transacción se ejecuta completamente o no se ejecuta en absoluto.
• Consistencia: Todas las transacciones mantienen a la BD en forma consistente.
• Aislamiento: Ninguna transacción interfiere con otra (por mas que se ejecuten en paralelo)
• Durabilidad: Una vez ejecutado Commit, la actualizacion queda en forma persistente

Cuando la ejecución de un conjunto de transacciones (E) que intercala las operaciones de cada transacción en forma conveniente, es equivalente a alguna ejecución en serie de las transacciones de E, decimos que E es Serializable. Lo importante es que toda ejecución serializable preserva la consistencia de la BD, es decir, las transacciones devolveran resultados validos, mas alla de que el resultado de las transacciones sea distinto segun el orden de ejecución.
Para determinar si un conjunto de transacciones son serializables, generamos un grafo de precedencia, ubicando a las transacciones como nodos y enlazando arcos entre ellas cuando haya conflictos en los protocolos de cierre al intentar acceder a los datos (por ejemplo, cuando se quiera escribir un dato que otra transacción tambien quiere escribir o leer). Si logramos dibujar (de alguna manera) un grafo aciclico, podremos orientar todos los arcos de izquierda a derecha, obteniendo una ejecución serial equivalente.

• Candados simple
  • Un solo tipo de candado para lectura y escritura; no se comparten.
• Candados de lectura y escritura
  • Existen 2 tipos de candados (lectura y escritura) Se permite compartir un cierre para lectura.
  • Se necesita un grafo de precedencia para asegurar la seriabilidad
• Cierre de dos fases
  • Solo se comienzan a liberar los cierres luego de haber obtenido el control de todos los datos necesarios.
  • Si es respetado, nos garantiza que la ejecución sera siempre serializable
• Protocolo de Arbol
  • Cierro en modo inicial un nodo cualquiera del arbol
  • A partir de aca, puedo cerrar un nodo solo si poseo el cierre del nodo padre
  • Libero los nodos padre a medida que dejan de ser necesarios
  • Una vez que comienzo a liberar nodos, no puedo cerrar ningun otro
• Locks de update ???
• Locks de Incremento ???
• Tablas de Locks ???

• Deadlocks (bloqueos) Dos transacciones necesitan mutuamente un dato bajo el control de la otra transacción para poder continuar y liberar los recursos.
• Livelocks (postergacion indefinida) Una transacción necesita modificar un dato que otra transacción cerro para lectura, pero antes de que el dato sea liberado es cerrado para lectura por otra transacción. Si se repite el esquema indefinidamente, tenemos un livelock.

(y los fenomenos que pueden aparecer)

• Lectura Sucia: Lectura de un atributo grabado por una transacción que todavia no hizo Commit
• Lectura no Repetible: Una transacción lee 2 veces un atributo, pero este es modificado entre lecturas
• Fantasma: Una transacción lee una tabla con X elementos, y en una segunda lectura esa cantidad fue cambiada por otra transacción.

• Abort: Restaura los valores de los datos modificados por la transacción abortada
• Commit: Graba a memoria estable los cambios (en el LOG) que hizo la transacción.
• Reiniciar: Aborta todas las transacciones que se estan ejecutando desde la ultima hasta la primera antes del ultimo checkpoint (UNDO) y luego graba a la BD la información actualizada por transacciones que llegaron a ejecutar commit (REDO). Reiniciar es Idempotente ya que debe ser equivalente ejecutarlo una vez, completamente, que varias veces en forma parcial y finalmente una ultima vez en forma completa.

• Write Ahead Log (WAL) Consiste en grabar siempre las actualizaciones primero en el Log y luego en la BD
• Force Log at Commit (FLC) Consiste en grabar al Log las actualizaciones hachas por una transacción antes de concluir el Commit

Se utlizan copias de respaldo en unidades de cinta, pero demanda mucho tiempo. Mas reciente es la utilizacion de RAID replicando discos uno a uno o en conjuntos de mas de 3 utilizando paridad de datos. Si un disco dejara de funcionar, la BD puede seguir funcionando, mientras se le reemplaza el disco dañado por uno nuevo y se reconstruye la paridad en background