Final del 19/04/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 19 de Abril de 2006 (Frias)

Ejercicio 1[editar]

Demostrar con la mayor formalidad de que sea capaz:

  1. (20 pts) El poder expresivo del CRD es igual al poder expresivo de CRT
  2. (15 pts) El CRD es al menos tan expresivo como el AR.

Rta

1)

La idea es que, si en CRT se reemplaza cada variable de tupla t(k) por k variables de dominio X1..Xk, y que Xj se use exactamente donde se usa t[j], se consigue una formula en CRD que define la misma relacion. Ademas los existenciales, como ( t(k))F, son reemplazados por ( X1)..( Xk)F', donde F' es la traduccion de F en CRD.

2)

Lo demostraremos por induccion estructural en expresiones de AR, usando que para cada una, existe una en CRT que define la misma relacion (y por el punto anterior, esta puede transformarse en CRD)

  • CB: (sin operadores)
    • Si es rel R => alcanza con: R(m)
    • Si es cte de la forma {m1..mn} => usamos var libre v, y queda: v[1..k]=m1[1..k] o .. o v[1..k]=mn[1..k]
  • PI: E=E1UE2
    • Por HI, formulas F1,F2 para E1,E2. Como E1 y E2 tienen la misma aridad, las var libres de F1 y F2 tambien => se puede renombrar las vars por m. En TRC queda entonces: F1 o F2
  • PI: E=E1\E2
    • Similar al anterior, pero en este caso queda: F1 y ~F2
  • PI: E=πi1..ik(E1)
    • Sea F1 la formula para E1 => tomando la var libre m, queda: ( v) F1(v) y m[1..k]=v[i1..ik]
  • PI: E=E1xE2
    • Sean F1(v(m)) y F1(p(n)) formulas para E1 y E2 => tomando la var libre a(m+n), queda: ( v) ( p) (F1(v) y F2(p) y a[1..m]=v[1..m] y a[m+1..m+n]=p[1..n])
  • PI: E=σAE1
    • Sea F1(m) la formula para E1. A puede ser de 2 formas: ($i θ $j) o ($i θ c), respectivamente queda: (F1(m) y m[i] θ m[j]), o (F1(m) y m[i] θ c)

Ejercicio 2[editar]

Considere las consultas:

  • πC(σA=a(R(A,B) ►◄ S(B,C))) (1), y
  • πC(πB(σA=a R(A,B)) ►◄ S(B,C)) (2)
  1. (10 pts) Demuestre que (1) y (2) son equivalentes.
  2. (20 pts) Hay alguna consulta que se pueda calcular mas eficientemente que la otra? En caso de ser ası, justifique cuidadosamente su respuesta.

Rta

Ver Ejercicio 3 de Final del 15 de Junio de 2006

Ejercicio 3[editar]

  1. (15 pts) Describa el algoritmo que permite testear si una descomposicion no tiene perdidas por junta.
  2. (20 pts) Justifique por que el mismo es correcto.

Rta

1)

Las columnas de la matriz son los atributos de R y las filas son los elementos de la particion. Luego, si el atributo Aj esta en el subesquema Ri, escribo aj en la posicion (i, j) de la matriz. Si no, escribo bij.

Mientras haya cambios en la matriz, para cada dependencia, si la matriz tiene valores similares en el lado izquierdo de la dependencia, igualo los lados derechos:

  • aj gana sobre bij , y reemplazo todas las ocurrencias de bij.
  • Dos elementos del mismo tipo se igualan en algun sentido y se reemplaza en todas las ocurrencias.

mρ(r) = ►◄ i=1..k ΠRi(r)

2)

Supongamos que no hay filas con todas a’s. Podemos ver a la tabla como una relacion r para el esquema R, con tantas tuplas como filas en la matriz. r satisface F porque ası fue construıda. Veremos que r = mρ(r). Claramente a1...an no ∈ r. Sin embargo, si llamamos µi a la i-esima fila, µi[Ri] = ai. Por lo tanto, (a1...an) ∈ mρ(r), QED.