Final del 9/3/11 (Bases de Datos)

Problemas

Ejercicio 1

1. Escribir la definición de cubrimiento minimal para un conjunto de dependencias funcionales F. (1 puntos)
2. ¿Puede existir más de un cubrimiento minimal para F? Si la respuesta es afirmativa, ¿Todos estos cubrimientos tienen la misma cardinalidad? Justifiquen sus respuestas. (2 puntos)

Ejercicio 2

Explicar que es un indice denso(1)

Ejercicio 3

1. Enunciar un algoritmo polinomial que dado un esquema de relación R, un conjunto de dependencias funcionales F y un conjunto de atributos X pueda calcular la clausura de X con respecto a F. (1)
2. Probar la correctitud del algoritmo propuesto y determinar la complejidad del algoritmo en funcion de la cantidad de atributos en R y la cantidad de dependencias funcionales en F. (1)

Ejercicio 4

Sea la siguiente base de datos

Alumno(LU, NombreAlu, Edad, Sexo, EstadoCivil)

Carrera(IdCarrera, DescripcionCarrera)

Materia(idMateria, DescripcionMat)

Plan(IdPlan, IdCarrera, AñoComienzoVigencia, AñoFinVigencia, puntos_requerido, FechaComienzoVigencia, FechaFinVigencia)

MatPlan(IdMateria, IdPlan, EsObligatoria, Puntos)

MatAprobadas(LU, IdMateria, FechaAprobacion, Nota)

Dado un registro de MatPlan donde la materia es M y el plan es P quiere decir que M es o bien una optativa o bien una obligatoria de P. Si M es obligatoria entonces tiene 0 punto asignado, en cambio, si M es optativa entonces debe al menos tener un punto asignado. Una materia M sirve para un plan P si solamente su fecha de aprobacion es anterior o igual al fin de vigencia de P. Si la FechaFinVigencia de P es nula significa que P esta vigente.

1. En que forma normal se encuentran los esquemas de esta base?(1)
2. Normalicen estos esquemas lo mas posible(1)
3. Expresar en SQL: los nombres de las licenciadas en "Cs. de la Computacion"(2)

Soluciones

Ejercicio 1

1. Un cubrimiento minimal de DF tiene que tener: a) No mas de un atributo en el lado derecho b) Todos los lados izquierdos son reducidos c) No tener DF que puedan obtenerse derivando de las existentes (por transitividad, por ejemplo)

Ejercicio 2

Un indice denso es aquel que en un bloque tiene tuplas (k,v), donde k es la clave y v es el puntero a la entrada correspondiente. Esta clase de indice existe para facilitar los joins, que se puede iterar secuencialmente para obtener todas las claves y valores correspondientes, a diferencia de indices esparsos que apuntan usualmente al primer elemento de un bloque. Los indices densos sirven además para poder compactar los indices en pocos bloques si los registros apuntados son muy grandes.

Ejercicio 3

La clausura de X se puede obtener asi:

 Mientras X cambie:
   Para toda A->B en F:
     Si A ⊆ X:
        X = X U B

La idea del algoritmo es ir aumentando de una DF a la vez, y llegar a un punto donde, o esten todas las DF de F en X, o no haya ningun otra DF que permita aumentar X. La complejidad del algoritmo depende de la cantidad de DF en F y la cantidad de atributos en R. En el peor caso, por cada iteracion externa se agrega un unico atributo nuevo. Eso quiere decir que se itera |R|*|F| veces. Luego O(R·F).