Final del 21/07/06 (Bases de Datos)

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

Enunciado[editar]

Link: Final del 21 de Julio de 2006 (Frias)

Ejercicio 1[editar]

Provea un algoritmo eficiente para computar la clausura de un conjunto de dependencias funcionales F.

Rta

Entrada: Un conjunto de atributos R, un conjunto de dependencias funcionales F, y un conjunto X ⊆ R.

Salida: X+, la clausura de X con respecto a F.

Metodo: Computaremos una secuencia de conjuntos X(0),X(1), ... segun las siguientes reglas:

  1. X(0) = {A/A ∈ X}
  2. X(i+1) = X(i) ∪ {A/ existe Y → Z ∈ F : A ∈ Z ∧ Y ⊆ X(i)}

Dado que X = X(0) ⊆ ··· ⊆ X(i) ⊆ ··· ⊆ R, y R es finito entonces existira i tal queX(i) = X(i+1). Como X(i+1) se calcula solo en terminos de X(i), se sigue que X(i) = X(i+1) = X(i+2) = ···. En consecuencia, el algoritmo finaliza cuando X(i) = X(i+1).

Ejercicio 2[editar]

Considere la siguiente politica de administracion de locks:

  1. Asigne un orden lineal a los items
  2. Cada transaccion debe solicitar los locks en ese orden.

Demuestre que esta politica previene los deadlocks.

Rta

Por el absurdo.

Sea S un conjunto de tx tal que c/u espera un lock de un item que está actualmente lockeado por otra tx en S. Se puede asumir que todas las tx en S tienen un lock de un ítem que otra tx en S esta esperando (Si no es así, se puede eliminar la transacción del conjunto y seguir manteniendo la situación de deadlock).

Sea Ak el primer item de los Ai en el orden asumido. Luego, Tk, que espera el item Ak, no puede tener ninguno de los Ai, pues los Ai son menores que Ak, para i = k, lo que es una contradicción.

Ejercicio 3[editar]

Sean A y B relaciones.

  1. Provea una expresion en el algebra relacional que defina el cociente de A y B.
  2. Demuestre que la expresion es correcta.

Rta

1)

La division puede escribirse asi:
Sea A=XY, B=Y => A%B = ∏X(A) \ ∏X[ (∏X(A) x B) \ A]

2)

Esta expresion hace lo siguiente: primero toma los atributos en X⊆A y los relaciona con todos los de B, restando las tuplas que aparecen en A. Esto hara que solo queden las relaciones que "falten" para los atributos de X que no se relacionaban con todos los de B. Con lo cual, se toman los atributos de X de esas "faltantes", y se restan de los atributos de X en A, finalmente obteniendo el resultado buscado.

Ejercicio 4[editar]

Se desea almacenar una relacion R(abcd) con un indice clustered sobre a. Analice las posibilidades de hacerlo utilizando

  1. Sequencias
  2. Tablas de hash
  3. B-trees.

Rta

Creo que apunta a .. Hash bueno para igualdad, B-trees buenos para rangos, etc etc