Final del 15/06/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 15 de Junio de 2006 (Frias)

Ejercicio 1[editar]

Sea R un esquema relacional. Sea p=(R1,R2) una descomposicion, y sea F un conjunto de dependencias funcionales. Demuestre que R1 ∩ R2 -> R1 − R2 <=> la descomposicion es sin perdida por junta.

Rta

<=)

Corriendo el algoritmo de Tableaux, inicialmente:

   R1∩R2 R1-R2 R2-R1          R1∩R2 R1-R2 R2-R1
R1 a..a  a..a  b..b  ...   R1 a..a  a..a  b..b
R2 a..a  b..b  a..a        R2 a..a  a..a  a..a

Finalizando, queda una fila de a's (si esa fila es la 1ra, intercambiamos R1 y R2). Sea A Є (R1-R2). La fila R2 columna A, inicialmente vale b, y luego de j iteraciones pasa a a. Luego, X->Y tq: X ⊆ R1∩R2 y A ⊆ Y => A Є X+ ⊆ (R1∩R2)+. Como A es atributo de R1-R2 => R1∩R2->R1-R2

=>)

Lema: Si X=a en las 2 filas y |- X->Y => el alg. eventualmente pone Y=a en las 2 filas.
Dem: por induccion en long dem. de X->Y por Armstrong.

  • CB: P(1)
    • X->Y Є F => en una iteracion el alg. iguala las 2 filas con a
    • no Y ⊆ X (reflex) => el alg. inicializa las 2 filas con a
  • PI: P(<n) -> P(n)
    • Trans => .. i) X->Z .. j) Z->Y .. n) X->Y (trans i y j). Como X=a en las 2 filas =>(HI) el alg pone Z=a en las 2 filas. Como Z=a en las 2 filas =>(HI) el alg pone Y=a en las 2 filas.
    • Aumento => .. i) V->W .. n) VZ->WZ (uso X=VZ y Y=WZ). V->W y V=a en las 2 filas =>(HI) el alg. pone W=a. Si X=a en las 2 filas, como Z ⊆ X ya tiene sus atributos en a. Luego WZ=Y=a en las 2 filas.

Como R1∩R2 vale a en las 2 filas y R1∩R2->R1-R2 =>(lema) pone a en R1-R2 => queda una fila de a's y la descomp. es SPPJ.

Ejercicio 2[editar]

Sea R un esquema relacional. Sea p=(R1,R2) una descomposicion, y sea F un conjunto de dependencias funcionales. Es cierto que si R1 ∩ R2 -> R1 − R2 => la descomposicion es sin perdida de dependencias?

Rta

Es falso. Veamos un contraejemplo:

Sea el esquema R=(CEP)(C=ciudad,E=estado, P=cod.postal), F={CE->P,P->C}, p=(R1,R2) con R1=EP y R2=CP.

Veamos que vale R1∩R2->R2-R1: R1∩R2=EP∩CP=P; R2-R1=C; Claramente F|=P->C.

Veamos ahora que p NO es SPDF, usando lo siguiente:

  • Una descomposicion p=(R1,R2) es SPDF <=> ∏R1(F)U∏R2(F) |= F
  • La proyeccion de F sobre R es ∏F(R) = {X->Y | X->Y Є F+ y XY inc R}

Como ∏F(EP)=dep.triviales y ∏F(CP)=P->C mas dep.triviales => no vale ∏F(R1)U∏F(R2)|=CE->P => ∏F(R1)U∏F(R2)|=F -> p NO es SPDF.

Ejercicio 3[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

1)

Semantica AR:

  • <Ri> = Ri
  • <M x N> = <M> x <N>
  • <σiθc(M)> = { <x1..xk> Є <M> | xiθc }
  • <σiθj(M)> = { <x1..xk> Є <M> | xiθxj }
  • <πi1..in(M)> = { <xi1..xin> Є <M> | EX xj1..xj(k-n), {i1..in,j1..j(k-n)} = {1..k} <x1..xk> Є <M> }

2)

Ejercicio 4[editar]

  1. (5 pts) Enuncie la regla de transitividad para dependencias multivaluadas.
  2. (15 pts.) Demuestre que la regla es correcta.

Rta

1)

La regla de transitividad para DFM es {X->>Y,Y->>Z} |= X->>Z-Y.

2)

La demostraremos por absurdo. Sup r rel. / r|={X->>Y,Y->>Z} pero no r|={X->>Z-Y}.

  • Como no r |={X->>Z-Y} => t1,t2 / t1[X]=t2[X]
  • v ademas => u / u[X]=t1[X]=t2[X], u[Z-Y]=t1[Z-Y], u[U-X-(Z-Y)]=t2[U-X-(Z-Y)]
  • Como r|=X->>Y => v / v[X]=t1[X]=t2[X], v[Y]=t2[Y], t1[U-X-Y]=t2[U-X-Y]
  • Como r|=Y->>Z => w / w[Y]=v[Y]=t2[Y], w[Z]=v[Z], w[U-Y-Z]=t2[U-Y-Z]

El abs entonces proviene de ver que w=u.

  • Veamos w[X]=u[X]:
    • Por teoria de conj => X=(XnZ)U(X-Z).
      • v[Z]=w[Z],v[X]=t1[X] => w[XnZ]=t1[XnZ]
      • t2[X-Z]=w[X-Z],t2[X]=t1[X] => w[X-Z]=t1[X-Z]
    • Luego w[X]=t1[X]=u[X]
  • Veamos w[Z-Y]=u[Z-Y]:
    • v[Z]=w[Z],v[Z-Y]=t1[Z-Y].
    • Luego w[Z-Y]=t1[Z-Y]=u[Z-Y]
  • Veamos w[U-X-(Z-Y)]=u[U-X-(Z-Y)]:
    • Es decir, w[U-X-(Z-Y)]=t2[U-X-(Z-Y)]. Sea V=U-X-(Z-Y). Por teoria de conj => V=(VnZ)U(V-Z)
      • (VnZ)=(YnZ)-X. w[Z]=v[Z],v[Y]=t2[Y] => w[VnZ]=t2[VnZ]
      • w[U-Z]=t2[U-Z] => w[V-Z]=t2[V-Z]
    • Luego w[V]=t2[V]=u[V]

=> w=u => ABS