Final del 14/08/19 (Bases de Datos)

Consigna

Se aprueba con 60/100. (10 puntos cada una)

1. Definir dependencia funcional. Dado {idAlumno, nombreAlumno, idCurso, idProfesor} dar un conjunto de dependencias funcionales. Decir en qué forma normal se encuentra.
2. Definir clave candidata y clave primaria. Definir 2FN.
3. Para qué sirve la normalización? Cómo se relaciona con las pautas de diseño de una base de datos? Describir anomalías que puede presentar una base de datos desnormalizada.
4. Qué es una transacción? Dar un ejemplo de algún dominio. Por qué es importante el control de concurrencia?
5. Explicar bases NoSQL por documentos, explicando el concepto de documento. Qué es un DID? Dar un ejemplo de un sistema de base de datos por documentos.
6. Definir base de datos distribuida. Explicar nuevos niveles de transparencia.
7. Explicar fragmentación. Explicar cómo se recupera la tabla original con álgebra relacional.
8. Explicar independencia física.
9. Dar dos ejemplos de optimizaciones algebraicas. Ejemplificar.
10. Diferencia entre administrador de datos y DBA. Relacionar con concepto de independencia física y transparencia.

Respuestas posiblemente incorrectas

Pregunta 1

Una dependencia funcional X -> Y entre dos conjuntos de atributos X e Y de una BD indica que cualquiera dos tuplas t₁ y t₂ en R tal que t₁[X] = t₂[X], se debe cumplir t₁[Y] = t₂[Y].

Las dependencias funcionales dependen de la semántica de la relación, y por tanto vamos a asumir que el conjunto de atributos dado corresponde a un sistema de gestión unviersitaria (e.g Guaraní) para dar sus dependencias funcionales.

1. idAlumno -> nombreAlumno: cada alumno tiene un único id asignado
2. idCurso -> idProfesor: asumiendo que un curso representa una instancia de materia + profesor + cuatrimestre de cursada

Si asumimos que este esquema representa una relación del estilo "inscripción a cursada", podemos considerar que la PK estará compuesta por { idAlumno, idCurso }. En este caso no se llega a 2FN pues los atributos nombreAlumno e idProfesor dependen parcialmente de la PK. El esquema se encuentra en 1FN por no ser 2FN y no tener relaciones dentro de relaciones ni atributos multivaluados.

Pregunta 2

Una clave candidata es una de las posibles claves de una relación. Una clave S es un subconjunto de atributos de R con la propiedad de que no hay dos tuplas t₁, t₂ en un estado legal r(R) que cumplan t₁(S) = t₂(S).

La clave primaria es una clave candidata designada arbitrariamente como tal. Por ejemplo, en una tabla donde se tienen los atributos DNI y Pasaporte de una persona, uno podría elegir tanto DNI como Pasaporte como PK.

2FN es una forma normal que, además de ser 1FN (prohíbe relaciones dentro de relaciones, atributos multivaluados), cumple que todo atributo no primo A de R depende funcionalmente de manera completa de la PK de R. Esto es, que la PK es una DF minimal para todos los atributos que no pertenecen a alguna CK.

Pregunta 3

La normalización es una herramienta que se apoya en las DFs para evaluar y comparar distintas formas de agrupar atributos en un esquema. Al diseñar una base de datos normalizada siguiendo las formas normales, se busca que el resultado sea conceptualmente bueno (e.g entendible) y también físicamente bueno (e.g minimizar duplicación).

Para esto se siguen cuatro pautas fundamentales, que si bien no siempre pueden alcanzarse al mismo tiempo, dan una medida informal de la calidad del diseño:

1. semántica clara
2. reducir información redundante
3. reducir la cantidad de valores NULL
4. no permite generar tuplas espúreas

Una base de datos desnormalizada puede presentar distintos problemas, como por ejemplo:

• Anomalías de modificación: el nombre del departamento 33 es inconsistente (Compras/Adquisiciones):

idEmpleado	idDepartamento	nombreDepartamento
1	33	Compras
2	34	Ventas
3	33	Adquisiciones

• Anomalías de deleción: al borrar el empleado 2 desaparece el departamento Ventas

idEmpleado	idDepartamento	nombreDepartamento
1	33	Compras
3	33	Adquisiciones

• Anomalías de inserción: este esquema no permite agregar información de departamentos que aún no tienen empleados. Lo siguiente es inválido:

idEmpleado	idDepartamento	nombreDepartamento
NULL	35	Ingeniería
NULL	36	Calidad

Pregunta 4

Una transacción es un conjunto de instrucciones que se ejecutan formando una unidad lógica de procesamiento. Una transacción puede incluir uno o más accesos a la BD a través del uso de diversas operaciones (inserción, eliminación, modificación, etc.).

Diversos sistemas como los bancarios, los de reservas de vuelos o del mercado de valores, usan transacciones para garantizar la consistencia de los datos. Por ejemplo, un sistema bancario que usa una transacción para actualizar dos saldos a causa una transferencia evita la pérdida o creación de dinero en caso de fallas. En este caso, la atomicidad de la transacción garantiza que se ejecuta completo o se deshace por completo.

Este tipo de sistemas requieren rápida respuesta y alta disponibilidad para muchos usuarios que acceden de manera concurrente. En este escenario, un motor de base de datos hace uso de la multiprogramación, intercalando operaciones de distintas transacciones que se ejecutan concurrentemente. El control de concurrencia resulta importante pues queremos evitar que una transacción interfiera con otra: para el usuario, las transacciones se comportan como si se hubieran ejecutado una a continuación de la otra. De no manejar la concurrencia, pueden aparecer distintos problemas como:

• Lost update
• Dirty read
• Incorrect summary
• Unrepeatable read

Pregunta 5

Una base de datos NoSQL por documentos es una base no-relacional que almacena los datos como documentos estructurados. El concepto principal es el documento. La BD almacena y recupera documentos. Los documentos pueden ser XML, JSON, BSON, etc.

Cada documento es una colección de pares: nombre de campo y valor. Los valores pueden ser un valor simple, una estructura compleja como una lista, otro documento o listas de documentos hijos.

A la hora de diseñar este tipo de bases de datos hay tres pasos fundamentales:

1. Modelo conceptual de alto nivel, incluyendo patrones de consulta y diagramas de entidad-relación
2. Modelo lógico a través de un diagrama de interrelación de documentos (DID)
3. Modelo físico, incluyendo JSON Schema, estrategias de replicación y distribución, índices

Basándose en el DER, en el DID se especifica la interrelación entre documentos, principalmente si se incrustarán o referenciarán, determinando así el grado de desnormalización de los documentos.

MongoDB es una base de datos de documentos cuya principal ventaja es la capacidad de escalar horizontalmente casi sin configuración. Particionando los datos basándose en sus claves, este motor hace trivial la tarea de sharding. Además, provee otras características como un framework para procesamiento batch y una API de consulta que permite búsquedas por campo, rangos, regex.

Pregunta 6

Una base de datos distribuída (DDB) es una colección de múltiples BD que están lógicamente relacionadas y se encuentran distribuídas en una red de computadoras. Este tipo de DBs presentan características nuevas, para las que los motores proveen transparencia (a costa de flexibilidad) para simplificar el proceso de desarrollo. Estas son:

1. Distribución de los datos: libera al usuario de conocer detalles operativos de la red y ubicación de los datos
2. Replicación: el usuario desconoce la existencia de copias
3. Fragmentación horizontal y vertical: libera al usuario de conocer detalles sobre la fragmentación de los datos
4. Diseño y Ejecución: libera al usuario de conocer cómo está diseñada la DDB y dónde es ejecutada una transacción

A la hora de elegir una DDB, se deberá tener en cuenta la flexibilidad y el grado de control que se requieran para alcanzar la performance, disponibilidad y tolerancia a fallos que se precise (entre otras cosas).

Pregunta 7

La fragmentación consiste en dsitribuir una relación en subrelaciones.

• En el caso de la fragmentación horizontal, estas subrelaciones son subconjuntos de las tuplas de la relación original. En términos de álgebra relacional, estamos hablando de una selección (σ(R)).
• En el caso de la fragmentación vertical, son subconjuntos de columnas de la relación original. En térmnos de AR, es una proyección (π(R)).
• La fragmentación híbrida combina las dos anteriores.

Para recuperar las tablas, debemos pensar en las operaciones "opuestas" a las de fragmentación.

• Para reconstruir una fragmentación horizontal debemos aplicar la operación UNION a todos los fragmentos. Cabe mencionar que nos referimos a la union de conjuntos (sin duplicados) teniendo en cuenta que puede haber replicación.
• Para reconstruir una fragmentación vertical debemos aplicar la operación OUTER UNION. Como es de esperar, esta operación recombina las columnas de cada fila, lo cual es posible solo si cada fragmento contiene al menos una clave candidata (e.g la PK).
• Para reconstruir una híbrida se requiere aplicar UNION y OUTER UNION en el orden apropiado. Ni las slides ni el libro "Introduction to Database Management System" dicen cuál es. Pareciera que a veces es uno y a veces otro, pero no dice bajo qué condiciones.

Pregunta 8

La independencia física es la capacidad de poder cambiar el esquema interno sin tener que cambiar el esquema conceptual (y por lo tanto tampoco los esquemas externos). Algunos potenciales cambios al esquema interno podrían ser la organización de los archivos o el agregado de un índice, usualmente con el fin de mejorar el rendimiento de las operaciones de consulta o de actualización de datos.

Pregunta 9

Las optimizaciones algebraicas son aquellas que buscan mejorar la performance de la consulta independientemente de la organización física. Involucran propiedades algebraicas que permiten construir una consulta equivalente a la original.

Por ejemplo, podemos convertir una selección compleja en una cascada de selecciones simples: σ_{C1∧C2∧...∧Cn}(R) ≡ σ_C1(σ_C2(...σ_Cn(R)))

Otra optimización posible es conmutar selecciones: σ_C1(σ_C2(R)) ≡ σ_C2(σ_C1(R))

Ambas optimizaciones están íntimamente relacionadas, pues descomponer una cascada puede hacerse como primer paso antes de la conmutación.

Esto resulta particularmente performante cuando se dispone de un índice que puede ser aprovechado en una selección (e.g C₂ selecciona los usuarios con apellido que empiece con "J" y se dispone de un índice sobre este atributo)

Pregunta 10

• Administrador de base de datos -> modelo conceptual y lógico
• DBA -> modelo físico, especialista en el motor de base de datos

El administrador de datos es un perfil netamente funcional. Es un especialista en los datos de una organización desde el punto de vista lógico, con funciones como la colección y análisis de requerimientos para el modelado de negocio.

El administrador de datos suele desentenderse de la organización física de los datos, de la cual el DBA es el especialista. Esta persona es quien conoce los detalles de un motor de base de datos, y es asistido por el administrador de datos en la creación de los modelos físicos a partir de los modelos lógicos.