Final del 17/05/07 (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 15 de Mayo de 2007 (Frias)

Ejercicio 1[editar]

  1. De una traduccion T correcta de expresiones de AR a CRT.
  2. Demuestre que si M=<R1..Rk> es un modelo en el cual todas las relaciones son finitas, [T(E)] es una relacion finita.

Rta

1)
Sea la traduccion T(E)={t|T't(E)} donde T't(E) es:

  • T't(R)=t Є R
  • T't(RUS)=T't(R) o T't(S)
  • T't(R\S)=T't(R) y ~T't(S)
  • T't(RxS)=( t1)(T't1(R) ^ t[1..n]=t1[1..n]) ^( t2)(T't2(S) ^ t[n+1..n+m]=t2[1..m])
  • T't(πi1..in(R))=( t1)(T't1(R) ^ t[1..n]=t1[i1..in])
  • T't(σiθc(R))=T't(R) ^ t[i] θ c
  • T't(σiθj(R))=T't(R) ^ t[i] θ t[j]

2)
Sea M={R1..Rn} -modelo- y v:variables->tuplas -funcion- => [{t|E}]M={v(t)|M |= E[v]}, donde M |= E[v] es:

  • M |= (t Є Ri)[v] <=> v(t) Є Ri
  • M |= (E1 y E2)[v] <=> M |= E1[v] y M |= E2[v]
  • M |= (E1 o E2)[v] <=> M |= E1[v] o M |= E2[v]
  • M |= (~E1)[v] <=> no M |= E1[v]
  • M |= ( t)(E1)[v] <=> ( a)(M |= E1[v[a]])
  • (x)[v[a=t]] <=> { v(x) si x!=t | a si x=t }

Propiedades:

  • P(a) <=> a Є {b|P(b)}
  • E <=> a Є {b|E[b/a]}

Ahora qvq para toda expresion valida de AR, [T(E)]M es una relacion finita. Voy a demostrarlo por induccion sobre la estructura de las expresiones de AR.

  • Para R:
    • [T(R)]M =TRAD [{t|t Є Ri}]M =SEM {v(t)|v(t) Є Ri}=Ren {a|a Є Ri} =CONJ Ri
    • en M todas las relaciones son finitas, por lo cual Ri es finita.
  • Para R U S:
    • [T(R U S)]M =TRAD [{t|T't (R) U T't (S)}]M =SEM {v(t)|M |= T't (R)[v] o M |= T't (S)[v]} =CONJ {v(t)|M |= T't (R)[v]} U {v(t)|M |= T't (S)[v]} =SEM [{t|T't (R)]M U [{t|T't (S)}]M =TRAD [T(R)]M U [T(S)]M
    • Por HI, [T(R)]M y [T(S)]M son ambas finitas => su union lo es tambien.
  • Para R\S:
    • [T(R\S)]M =TRAD [{t|T't (R) y no T't (S)}]M =SEM {v(t)|M |= T't (R)[v] y no M |= T't (S)[v]}=CONJ{v(t)|M |= T't (R)[v]}\{v(t)|M |= T't (S)[v]} =SEM [{t|T't (R)]M\[{t|T't (S)}]M =TRAD [T(R)]M\[T(S)]M
    • Por HI, [T(R)]M y [T(S)]M son ambas finitas => su resta lo es tambien.
  • Para RxS:
    • [T(RxS)]M =TRAD [{t|( t1)(T't1(R) ^ t[1..n]=t1[1..n]) ^ ( t2)(T't2(S) ^ t[n+1..n+m]=t2[1..m])}]M =SEM {v(t)|( a1)(M |= T't1(R)[v[a1=t1]] y v(t)[1..n]=a1[1..n]) y ( a2)(M |= T't2 (S)[v[a2=t2]] y v(t)[n+1..n+m]=a2[1..m])} =PROP1{v(t)|( a1; a2)(a1 Є {v(t1)|M |= T't1(R)[v]} y a2 Є {v(t2)|M |= T't2(S)[v]} y v(t) es a1 `concatenado' con b)} =CONJ {v(t1)|M |= T't1 (R)[v]} x {v(t2)|M |= T't2(S)[v]} =SEM [{t1|T't1(R)]M x [{t2|T't2(S)}]M =TRAD [T(R)]M x [T(S)]M
    • Por HI, [T(R)]M y [T(S)]M son ambas finitas => su join lo es tambien.
  • Para πi1..in(R): (*)
    • [T(πi1..in(R))]M =TRAD [{t|( t1)(T't1(R) ^ t[1..n]=t1[i1..in])}]M =SEM {v(t)|( a)(M |= T't1(R)[v[a=t1]] y v(t)[1..n]=a[i1..in])} =PROP2 {v(t)|( a)(a Є {v(t1)|M |= T't1(R)[v]} y v(t)[1..n]=a[i1..in])} =JUSTIF. {v(t)|( a)(a Є {v(t1)|M |= T't1(R)[v]} y v(t)[1..n]=a[1..n])} =JUSTIF. {v(t)|M |= T't (R)[v]} =SEM [{t|T't (R)}]M =TRAD [T(R)]M
    • Por HI, [T(R)]M es finita.
  • Para σiθc(R)
    • [T(σiθc(R))]M =TRAD [{t|T't (R) ^ t[i] θc}]M =SEM {v(t)|M |= T't (R)[v] y v(t)[i] θc} =CONJ {v(t)|M |= T't (R)[v]} ∩ {v(t)|v(t)[i] θc} =REESCR {v(t)|M |= T't (R)[v]} ∩ {b|b[i] θc} =CONJ [{t|T't (R)}]M ∩ {b|b[i] θc} =TRAD [T(R)]M ∩ {b|b[i] θc}
    • Por HI, [T(R)]M es finita, y por lo tanto su interseccion con otro conjunto lo es tambien.
  • Para σiθj(R)
    • [T(σiθj(R))]M =TRAD [{t|T't (R) ^ t[i] θ t[j]}]M =SEM {v(t)|M |= T't (R)[v] y v(t)[i] θ v(t)[j]} =CONJ {v(t)|M |= T't (R)[v]} ∩ {v(t)|v(t)[i] θ v(t)[j]} =REESCR {v(t)|M |= T't (R)[v]} ∩ {b|b[i] θ b[j]} =CONJ [{t|T't (R)}]M ∩ {b|b[i] θ b[j]} =TRAD [T(R)]M ∩ {b|b[i] θ b[j]}
    • Por HI, [T(R)]M es finita, y por lo tanto su interseccion con otro conjunto lo es tambien.

(*)Justificacion:

  • Podemos ver que el dominio de los atributos de v(t) depende de los de a (por v(t)[1]=a[1] y..y v(t)[n]=a[n]) y que a pertenece a {v(t1)|M |= T't1(R)[v]}. Pero v(t) solo `toma' algunos atributos de a (al menos uno), por lo cual la cantidad de tuplas va a ser siempre menor a que las que hay en el conjunto al que pertenece a. El unico caso en que serian iguales de da todos los atributos de v(t) son iguales a los de a (v(t)=a). Si demostramos que este es finito, cualquier otro caso tambien lo sera.

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

Ver Ejercicio 2 de Final del 21 de Julio de 2006

Ejercicio 3[editar]

Sea F U {X->Y} un conjunto de dependencias funcionales.

  • a) Demuestre que la relacion r (abajo) satisface F+
(Atribs de X+) (Otros Atribs)
    1...1          1...1
    1...1          0...0
  • b) Demuestre que si no F+ |- X->Y => no r |= X->Y
  • c) Deduzca de a) y b) que los axiomas de Armstrong son completos

Rta

Definicion: X+ (clausura de X respecto de un conjunto de dep. func) = {A / F |- X->Y}

1)


Lema: F |- X->Y <=> Y ⊆ X+
=>) Por descomposición F |- X->A para cada A Є Y. Luego, Y ⊆ X+
<=) Por definición, para cada atributo A Є Y , A Є X+. Por regla de unión (varias aplicaciones), F |- X->A => F |- X->Y

Sup. que V->W Є F+ y r Є V->W. Como r Є V->W, tiene que suceder que V ⊆ X+ y ex. A Є W(A no Є X+), pues:

  • Si W ⊆ X+ => r no violaría V->W
  • Si ex. B Є V (B no Є X+) => r no violaría V->W

Como V ⊆ X+ => X->V. Por transitividad, X->W (pues V->W Є F+). Por reflexibidad, W->A Є F+. Por transitividad, X->A Є F+ => A ⊆ X+ => ABS (de suponer que no r |= F+)

2)

Sup. que no F |- X->Y. qvq X->Y no vale en r. Sup. que r |= X->Y => X ⊆ X+, y Y ⊆ X+, pues X->Y ( sino t1[X]=t2[X] y t1[Y]=t2[Y] => no valdría X->Y ). Luego (por lema) F |- X->Y (se demuestra con Armstrong) => ABS (de suponer que r |= X->Y)

3)

Para demostrar la completitud de los axiomas de Armstrong, tengo que ver que F |= X->Y => F |- X->Y , es decir, todo lo que se sigue lógicamente de un conjunto de dep. func. se puede demostrar usando axiomas de Armstrong.

Por contrarecíproco, qvq no F |- X->Y => no F |= X->Y. Tengo que ver que ex. relación r / r |= F y no r |= X->Y.

Sea r la relación del enunciado. r |= F (punto 1) y no F+ |- X->Y => no r |= X->Y (punto 2). Luego, r |= F y no r |= X->Y => X->Y no se sigue logicamente de F.

=> los axiomas son completos