Description

Normativa
Límite de entrega: Domingo 22 de septiembre, 23:59hs. Enviar el zip al mail: algo2.dc+TP1@gmail.com Normas de entrega: Ver “Información sobre la cursada” en el sitio Web de la materia.
Enunciado
Una base de datos es un sistema para el almacenamiento de información. Se caracteriza por mantener la información de forma estructurada y en un solo lugar. Además están preparadas para guardar grandes volúmenes de información. La estructura de los datos permite hacer consultas sofisticadas, que incluyen filtrar datos, transformarlos y contabilizarlos. Una de las principales utilidades de las bases de datos es la de guardar información de elementos que se encuentran relacionados y poder acceder a estas relaciones de forma muy eficiente. Un ejemplo de elementos relacionados sería guardar información de Proveedores y Productos, donde los Proveedores venden distintos Productos. Las bases de datos permiten hacer consultas del tipo ¿Cuales son los productos que vende el proveedor X? de forma muy rápida, incluso con una cantidad enorme de datos. El objetivo de este TP es diseñar la interfaz de una base de datos.
Una base de datos tiene tablas. Cada tabla suele representar un concepto. Las tablas se identifica con un nombre único.
Por ejemplo, una base de datos podría contar con tres tablas: Empleados, Proveedores y Productos.
Cada tabla tiene campos o “columnas” que se identifican con un nombre. Cada tabla tiene exactamente un campo que se declara como la clave de la tabla. (En los ejemplos de abajo la clave se subraya).
Por ejemplo, la base de datos podría tener las siguientes tres tablas:
Empleados campos: {nombre, apellido, cuit} la clave es el cuit. Proveedores campos: {razón_social, cuit} la clave es el cuit.
Productos campos: {nombre, precio} la clave es el nombre.
Un registro es una asociación entre nombres de campos y valores. Los valores son siempre cadenas de caracteres (strings).
Por ejemplo, {nombre: “Mona”, apellido: “Lisa”, cuit: “12345678”} es un registro.
Cada tabla tiene varios registros o “filas”. Por ejemplo, las tablas de la base de datos podrían tener los siguientes registros:
Empleados
nombre apellido cuit
Mona Lisa 12345678
Papá Noel 12345679
Mona Simpson 12345680
King Kong 12345681
King King 12345682
Mona Jiménez 12345683
King Lear 12345684
nombre precio
caramelo 1
chocolatín 1
paleta 2
alfajor 2
alfajor triple 3
razón_social cuit
Acme 98765432
Xanadu 98765431
Productos Proveedores
Una tabla no puede tener dos registros que coincidan en el valor del campo clave. Por ejemplo, en la tabla Productos puede haber dos registros con el mismo precio, pero no puede haber dos registros con el mismo nombre.
Se deben permitir las siguientes operaciones sobre la base de datos:
1. Agregar una tabla, indicando cuáles son sus campos y cuál es el campo clave.
2. Eliminar una tabla.
3. Agregar un registro a una tabla, dándole valor a todos (y solamente a) los campos de la tabla.
4. Eliminar un registro de una tabla, identificándolo por su clave.
5. Realizar una consulta. Las consultas se describen a continuación.
Consultas
Las consultas están basadas en un formalismo conocido como álgebra relacional . El resultado de hacer una consulta sobre una base de datos es un conjunto de registros. Las consultas se construyen recursivamente de la siguiente manera:
1. Tabla completa. Si t es el nombre de una tabla, FROM(t) es la consulta que devuelve todos los registros de la tabla t. Nota: si t no es el nombre de una tabla definida en la base de datos, la consulta deberá comportarse de alguna manera que ustedes deben especificar.
2. Filtrar por valor de un campo. Si q es una consulta, c es el nombre de un campo y v es un valor, SELECT(q,c,v) es una nueva consulta que devuelve los registros de la consulta q tales que el campo c tiene valor v.
Por ejemplo, SELECT(FROM(Empleados),nombre,“Mona”) devuelve el conjunto:
{nombre: “Mona”, apellido: “Lisa”, cuit: “12345678”}
{nombre: “Mona”, apellido: “Simpson”, cuit: “12345680”}
{nombre: “Mona”, apellido: “Jiménez”, cuit: “12345683”}
Nota: si hay registros que no tienen el campo c, la consulta deberá comportarse de alguna manera que ustedes deben especificar.
3. Filtrar por coincidencia de campos. Si q es una consulta y c1 y c2 son nombres de campos, MATCH(q,c1,c2) es una nueva consulta que devuelve los registros de la consulta q tales que los campos c1 y c2 tienen el mismo valor.
Por ejemplo, MATCH(FROM(Empleados),nombre,apellido) devuelve el conjunto:
{nombre: “King”, apellido: “King”, cuit: “12345682”}
Nota: si hay registros que no tienen el campo c1 o que no tienen el campo c2, la consulta deberá comportarse de alguna manera que ustedes deben especificar.
4. Proyección. Si q es una consulta y C es un conjunto de campos PROJ(q,C) es una nueva consulta que devuelve los mismos registros que la consulta q, pero que incluyen solamente los campos del conjunto C.
Por ejemplo, PROJ(SELECT(FROM(Empleados),nombre,“Mona”),{apellido,cuit}) devuelve el conjunto:
{apellido: “Lisa”, cuit: “12345678”}
{apellido: “Simpson”, cuit: “12345680”}
{apellido: “Jiménez”, cuit: “12345683”}
5. Renombre. Si q y es una consulta y c1 y c2 son nombres de campos, RENAME(q,c1,c2) renombra el campo c1 en el resultado de la consulta q para que pase a llamarse c2.
Por ejemplo RENAME(FROM(Proveedores),razón_social,nombre_proveedor) devuelve el conjunto:
{nombre_proveedor: “Acme”, cuit: “98765432”}
{nombre_proveedor: “Xanadu”, cuit: “98765431”}
Nota: si hay registros que no tienen definido el campo c1 o que ya tienen definido el campo c2, la consulta deberá comportarse de alguna manera que ustedes deben especificar.
6. Intersección. Si q1 y q2 son consultas, INTER(q1,q2) es una nueva consulta que devuelve la intersección entre los registros de las consultas q1 y q2.
Por ejemplo la consulta:
INTER(SELECT(FROM(Empleados),nombre,“Mona”),SELECT(FROM(Empleados),apellido,“Lisa”)) devuelve el conjunto:
{nombre: “Mona”, apellido: “Lisa”, cuit: “12345678”}
7. Unión. Si q1 y q2 son consultas, UNION(q1,q2) es una nueva consulta que devuelve la unión entre los registros de las consultas q1 y q2.
Por ejemplo, la consulta:
UNION(SELECT(FROM(Empleados),nombre,“Papá”),SELECT(FROM(Productos),precio,3)) devuelve el conjunto:
{nombre: “Papá”, apellido: “Noel”, cuit: “12345679”}
{nombre: “alfajor triple”, precio: “3”}
Nota: observar que el resultado de una consulta puede mezclar diferentes “tipos” de registros.
8. Producto cartesiano. Si q1 y q2 son consultas, PRODUCT(q1,q2) es una nueva consulta que devuelve el producto cartesiano entre los registros de las consultas q1 y q2.
Por ejemplo, la consulta:
PRODUCT(FROM(Proveedores),SELECT(FROM(Productos),precio,2))
devuelve el conjunto:
{razón_social: “Acme”, cuit: “98765432”, nombre: “paleta”, precio: “2”}
{razón_social: “Acme”, cuit: “98765432”, nombre: “alfajor”, precio: “2”}
{razón_social: “Xanadu”, cuit: “98765431”, nombre: “paleta”, precio: “2”}
{razón_social: “Xanadu”, cuit: “98765431”, nombre: “alfajor”, precio: “2”}
Nota: si hay registros provenientes de la consulta q1 que tienen campos en común con registros provenientes de la consulta q2, la consulta deberá comportarse de alguna manera que ustedes deben especificar.
Entrega
La entrega consistirá de un único documento digital con la descripción de todos los módulos y sus interfaces. Se debe diseñar el módulo principal (BaseDeDatos) y todos los módulos auxiliares. De definirse módulos que no pueden ser apropiadamente explicados por un TAD existente, deberá desarrollarse un TAD para describir el comportamiento del mismo. Esto aplica principalmente para el módulo BaseDeDatos. La única excepción son los módulos disponibles en el Apunte de Módulos Básicos, que se pueden utilizar sin diseñarlos: lista enlazada, pila, cola, vector, diccionario lineal, conjunto lineal y conjunto acotado de naturales.
En este TP se debe diseñar únicamente la interfaz de los módulos, que constará de las siguientes partes:
1. Descripción. Descripción del papel que cumple el módulo en la solución del problema, cuáles son sus principales utilidades, qué información almacena y cómo se espera que sea usado.
2. Tipo abstracto (“se explica con …”). Género (TAD) que sirve para explicar las instancias del módulo, escrito en el lenguaje de especificación formal de la materia. Pueden utilizar la especificación que se incluye en el apéndice.
3. Signatura. Listado de todas las operaciones públicas que provee el módulo, escrita con la notación de módulos de la materia, por ejemplo:
apilar(in/out pila : Pila, in x : Elemento)
4. Contrato. Precondición y postcondición de todas las operaciones públicas. Las precondiciones de las operaciones deben estar expresadas formalmente en lógica de primer orden.
La corrección se realizará con los siguientes criterios en mente:
Completitud. Los módulos deben tener operaciones en la interfaz que permitan operar con ellos de las formas esperadas.
Correctitud. Las precondiciones y postcondiciones de las operaciones deben dar buenas descripciones de los requisitos y efectos de las operaciones. En relación a esto, se debe contar con las funciones y TADs de forma que puedan describirse las operaciones correctamente.
Interpretabilidad. Es fundamental para que un módulo sea usable que su interfaz sea entendible, por lo que se espera que la selección de operaciones permita comprender cómo y porqué se utiliza el módulo.
Se recomienda el uso de los paquetes de LATEX de la cátedra para lograr una mejor visualización del informe.
La entrega se realizará por mail a la dirección algo2.dc+tp1@gmail.com. El documento desarrollado se entregará como un archivo en formato pdf hasta el día 22 de septiembre a las 23:59hs. El mail deberá tener como Asunto los números de libreta separados por punto y coma (;). Por ejemplo:
To: algo2.dc+tp1@gmail.com
From: alumno-algo2@dc.uba.ar
Subject: 123/45; 67/8; 910/11; 12/13
Adjunto: tp1.pdf
Sobre el recuperatorio: dado que el TP2 consistirá en extender el TP1, agregando las estructuras de datos y

algoritmos necesarios para implementar los módulos diseñados, el recuperatorio del TP1 se entregará como parte del informe del TP2.
A. Tipos abstractos de datos
Para escribir formalmente las precondiciones y postcondiciones de las operaciones, pueden utilizar los siguientes tipos abstractos de datos. Si es necesario, pueden extender estos tipos de datos con más operaciones, o definir nuevos tipos abstractos de datos (p.ej. pueden definir el TAD BaseDeDatos si lo necesitan).
Usaremos los siguientes tipos auxiliares. El tipo String es un arreglo dimensionable de caracteres, extendido con una operación • = • : string × string → bool para compararlas por igualdad. Cada caracter es un número entre 0 y 255.
TAD Char es Enum(0, 1, .., 255)
TAD String es Arreglo dimensionable(Char)
TAD NombreCampo es String
TAD NombreTabla es String
TAD Valor es String
A.1. Registro
TAD Registro géneros registro exporta observadores, generadores
usa NombreCampo, Valor, Conjunto
igualdad observacional
  campos(r) =obs campos(r0)∧L 
(∀r,r0 : registro) r =obs r0 ⇐⇒ (∀c : nombre_campo)(c ∈ campos(r) ⇒L 
r[c] =obs r0[c])
observadores básicos
campos : registro −→ conj(nombre_campo)
•[•] : registro r × nombre_campo c −→ valor {c ∈ campos(r)}
generadores
nuevo : −→ registro definir : registro × nombre_campo × valor −→ registro axiomas ∀r : registro,∀c,c0 : nombre_campo,∀v : valor campos(nuevo) ≡ ∅
campos(definir(r,c,v)) ≡ Ag(c,campos(r)) definir(r,c,v)[c0] ≡ if c = c0 then v else r[c0] fi
Fin TAD
A.2. Tabla
TAD Tabla géneros tabla
exporta observadores, generadores
usa NombreCampo, Valor, Conjunto, Registro
igualdad observacional
(∀t,t0 : tabla) obs 0 registroscampos(t() =t) =obsobs campos(t0)0)∧ clave(t) =obs clave(t0) ∧ registros(t
observadores básicos
campos : tabla −→ conj(nombre_campo) clave : tabla −→ nombre_campo registros : tabla −→ conj(registro)
generadores
nueva : conj(nombre_campo) cs × nombre_campo k −→ tabla {k ∈ cs}
insertar : tabla t × registro r −→ tabla {campos(t) =obs campos(r)}
borrar : tabla × valor otras operaciones −→ tabla
insertarRegistro : nombre_campo k × registro r × conj(registro) rs −→ conj(registro)
{k ∈ campos(r) ∧ (∀r0 : registro)(r0 ∈ rs ⇒ k ∈ campos(r0))}
borrarRegistro : nombre_campo k × valor v × conj(registro) rs −→ conj(registro)
{(∀r : registro)(r ∈ rs ⇒ k ∈ campos(r))}
axiomas ∀t : tabla,k : nombre_campo,cs : conj(nombre_campo),r : registro,rs : conj(registro),v : valor
campos(nueva(cs,k)) ≡ cs campos(insertar(t,r)) ≡ campos(t) campos(borrar(t,v)) ≡ campos(t)
clave(nueva(cs,k)) ≡ k clave(insertar(t,r)) ≡ clave(t) clave(borrar(t,v)) ≡ clave(t)
registros(nueva(cs,k)) ≡ ∅ registros(insertar(t,r)) ≡ insertarRegistro(clave(t),r,registros(t)) registros(borrar(t,v)) ≡ borrarRegistro(clave(t),v,registros(t))
insertarRegistro(k,r,rs) ≡ if ∅?(rs) then Ag(r,∅) else if dameUno(rs)[k] = r[k] then
Ag(r,sinUno(rs)) else
Ag(dameUno(rs),insertarRegistro(k,r,sinUno(rs))) fi
fi
borrarRegistro(k,v,rs) ≡ if ∅?(rs) then ∅ else
if dameUno(rs)[k] = v then sinUno(rs)
else
Ag(dameUno(rs),borrarRegistro(k,v,sinUno(rs))) fi
fi
Fin TAD
A.3. Consulta
TAD TipoConsulta es Enum(FROM, SELECT, MATCH, PROJ, RENAME, INTER, UNION, PRODUCT)
TAD Consulta géneros consulta exporta observadores, generadores
usa NombreCampo, NombreTabla, Valor, Conjunto
igualdad observacional
(∀q,q0 : consulta)q =obs q0 ⇐⇒ tipo_consulta(q) =obs tipo_consulta(q0)∧L
(tipo_consulta(q) ∈{FROM} ⇒L nombre_tabla(q) =obs nombre_tabla
(tipo_consulta(q) ∈{SELECT,MATCH,RENAME} ⇒L campo1(q) =obs campo1(q0)) tipo_consulta(q) ∈{MATCH,RENAME} ⇒L campo2(q) =obs campo2(q0)) tipo_consulta(q) ∈{SELECT} ⇒L valor(q) =obs valor(q0))
(tipo_consulta(q) ∈{PROJ} ⇒L conj_campos(q) =obs conj_campos tipo_consulta(q) ∈{SELECT,MATCH,PROJ,RENAME,INTER,UNION,PRODUCT}
 ⇒L subconsulta1(q) =obs subconsulta
∧ (tipo_consulta(q) ∈{INTER,UNION,PROJ} ⇒L subconsulta2(q) =obs subconsulta
generadores
FROM : nombre_tabla −→ consulta
SELECT : consulta × nombre_campo × valor −→ consulta
MATCH : consulta × nombre_campo × nombre_campo −→ consulta
PROJ : consulta × conj(nombre_campo) −→ consulta
RENAME : consulta × nombre_campo × nombre_campo −→ consulta
INTER : consulta × consulta −→ consulta
UNION : consulta × consulta −→ consulta
PRODUCT : consulta × consulta observadores básicos tipo_consulta : consulta −→ tipo_consulta −→ consulta
nombre_tabla : consulta q −→ nombre_tabla {tipo_consulta(q) ∈{FROM}}
campo1 : consulta q −→ nombre_campo {tipo_consulta(q) ∈{SELECT,MATCH,RENAME}} campo2 : consulta q −→ nombre_campo {tipo_consulta(q) ∈{MATCH,RENAME}} valor : consulta q −→ valor {tipo_consulta(q) ∈{SELECT}} conj_campos : consulta q −→ conj(nombre_campo) {tipo_consulta(q) ∈{PROJ}} subconsulta1 : consulta q −→ consulta
{tipo_consulta(q) ∈{SELECT,MATCH,PROJ,RENAME,INTER,UNION,PRODUCT}}
subconsulta2 : consulta q −→ consulta {tipo_consulta(q) ∈{INTER,UNION,PRODUCT}}
axiomas ∀r : registro,∀c,c0 : nombre_campo,∀v : valor
tipo_consulta(FROM(t)) ≡ FROM
tipo_consulta(SELECT(q,c,v)) ≡ SELECT
tipo_consulta(MATCH(q,c1,c2)) ≡ MATCH
tipo_consulta(PROJ(q,cs)) ≡ PROJ
tipo_consulta(RENAME(q,c1,c2)) ≡ RENAME
tipo_consulta(INTER(q1,q2)) ≡ INTER
tipo_consulta(UNION(q1,q2)) ≡ UNION
tipo_consulta(PRODUCT(q1,q2)) ≡ PRODUCT
nombre_tabla(FROM(t)) ≡ t
campo1(SELECT(q,c,v)) ≡ c
campo1(MATCH(q,c1,c2)) ≡ c1
campo1(RENAME(q,c1,c2)) ≡ c1
campo2(MATCH(q,c1,c2)) ≡ c2
campo2(RENAME(q,c1,c2)) ≡ c2
valor(SELECT(q,c,v)) ≡ v
conj_campos(PROJ(q,cs)) ≡ cs
subconsulta1(SELECT(q,c,v)) ≡ q
subconsulta1(MATCH(q,c1,c2)) ≡ q
subconsulta1(PROJ(q,cs)) ≡ q
subconsulta1(RENAME(q,c1,c2)) ≡ q
subconsulta1(INTER(q1,q2)) ≡ q1
subconsulta1(UNION(q1,q2)) ≡ q1
subconsulta1(PRODUCT(q1,q2)) ≡ q1
subconsulta2(INTER(q1,q2)) ≡ q2
subconsulta2(UNION(q1,q2)) ≡ q2
subconsulta2(PRODUCT(q1,q2)) ≡ q2
Fin TAD