| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| == Problemas == | | == Final del 9/3/2011 == |
| | |
| ====Ejercicio 1====
| |
| | |
| #Escribir la definición de cubrimiento minimal para un conjunto de dependencias funcionales F. (1 puntos)
| |
| #¿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====
| |
| #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)
| |
| #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(<u>LU</u>, NombreAlu, Edad, Sexo, EstadoCivil)
| |
| | |
| Carrera(<u>IdCarrera</u>, DescripcionCarrera)
| |
| | |
| Materia(<u>idMateria</u>, DescripcionMat)
| |
| | |
| Plan(<u>IdPlan</u>, IdCarrera, AñoComienzoVigencia, AñoFinVigencia, puntos_requerido, FechaComienzoVigencia, FechaFinVigencia)
| |
| | |
| MatPlan(<u>IdMateria, IdPlan</u>, EsObligatoria, Puntos)
| |
| | |
| MatAprobadas(<u>LU, IdMateria</u>, 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.
| |
| | |
| #En que forma normal se encuentran los esquemas de esta base?(1)
| |
| #Normalicen estos esquemas lo mas posible(1)
| |
| #Expresar en SQL: los nombres de las licenciadas en "Cs. de la Computacion"(2)
| |
| | |
| | |
| == Soluciones ==
| |
| | |
| ====Ejercicio 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).
| |
| | |
| ====Ejercicio 4====
| |
