Abrir menú principal

Cuba-Wiki β

Final del 15/06/06 (Bases de Datos)

EnunciadoEditar

Ejercicio 1Editar

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 2Editar

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 3Editar

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 4Editar

  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