Diferencia entre revisiones de «Final del 21/07/06 (Bases de Datos)»
Línea 5: | Línea 5: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
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: | |||
# X(0) = {A/A ∈ X} | |||
# 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 == | == Ejercicio 2 == | ||
Vamos a probar por el absurdo que esta politica de lock previene deadlocks. | Vamos a probar por el absurdo que esta politica de lock previene deadlocks. |
Revisión del 20:14 24 feb 2009
Enunciado
Link: Final del 21 de Julio de 2006 (Frias)
Ejercicio 1
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:
- X(0) = {A/A ∈ X}
- 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
Vamos a probar por el absurdo que esta politica de lock previene deadlocks.
Sean T={T1..Tn} un conjunto de tx que respeten la politica de locks (A1..Am). Sup. que ocurrio un deadlock, luego existe un conjunto de tx T0={T1..Tk}, k>=2, tq: T0 inc T, y i en 1..k, T0i espera a T0j, j= 1 (si i=k), i+1 (sino).
Graficamente: T01->T02->..->T0k->T01
T0i->T0j = T0i espera a T0j lockea un item al que T0i solicito el lock. Ademas, T0j lockea el item de indice Qj, y T0i solicito lock sobre dicho item. Es decir, T0i espera a T0j por el lock del item AQj.
Graficamente: T01->(AQ2)T02->(AQ3)..->T0k->(AQ1)T01
Ejercicio 3
1)
Sea A=XY, B=Y. A%B = ∏X(A) \ ∏X[ (∏X(A) x B) \ A]
2)