Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico Matemáticas y Naturales
Departamento: Informatica
Área: Area I: Datos
(Programa del año 2011)
(Programa en trámite de aprobación)
(Programa presentado el 23/05/2011 10:28:12)
I - Oferta Académica
Materia Carrera Plan Año Periodo
ORGANIZACION DE ARCHIVOS Y BASES DE DATOS I PROF.CS.COMPUT. 06/08 2011 1° cuatrimestre
ORGANIZACION DE ARCHIVOS Y BASES DE DATOS I LIC.CS.COMP. 32/12 2011 1° cuatrimestre
II - Equipo Docente
Docente Función Cargo Dedicación
HERRERA, NORMA EDITH Prof. Responsable P.Adj Exc 40 Hs
RUANO, CARINA MABEL Responsable de Práctico JTP Exc 40 Hs
TARANILLA, MARIA TERESA Responsable de Práctico JTP Exc 40 Hs
RUANO, DARIO MARTIN Auxiliar de Práctico A.1ra Semi 20 Hs
VILLEGAS AGUILERA, ANA VALERIA Auxiliar de Práctico A.1ra Simp 10 Hs
III - Características del Curso
Credito Horario Semanal Tipificación Duración
Teórico/Práctico Teóricas Prácticas de Aula Práct. de lab/ camp/ Resid/ PIP, etc. Total B - Teoria con prácticas de aula y laboratorio Desde Hasta Cantidad de Semanas Cantidad en Horas
Periodo
 Hs. 4 Hs. 3 Hs. 2 Hs. 9 Hs. 1º Cuatrimestre 16/03/2011 24/06/2011 15 135
IV - Fundamentación
Se inicia el estudio de la disciplina Base de Datos, introduciéndose la teoría de diseño de Bases de Datos Relacionales, como así también el lenguaje de consulta Algebra Relacional. Se estudia también la temática de indexación en bases de datos relacionales. Para ello, se retoma lo visto en Estructuras de Datos y Algoritmos, para introducir al alumno en el diseño de índices considerando ahora otros tipos de parámetros: evocaciones de respuesta múltiples, múltiples evocaciones sobre una relación e índices en memoria secundaria.

De esta manera el alumno adquiere una base sólida en las disciplinas Estructuras de Datos y Base de Datos, de forma tal que si opta por obtener sólo el título intermedio tiene la idoneidad suficiente en la temática contando con los conceptos, principios y teorías que constituyen el ámbito de competencia. En caso de que el alumno persiga obtener el título de licenciado, tiene una formación sólida como para encarar un estudio teórico mas fuerte de esta temática, que será desarrollado en la asignatura Base de Datos II.
V - Objetivos / Resultados de Aprendizaje
Al finalizar el curso, se pretende que el alumno sea capaz de:

- Manejar con idoneidad los conceptos que involucran el diseño de estructuras de datos en disco.

- Comprender y aplicar adecuadamente la teoría de diseño de bases de datos relacionales.

- Expresar consultas en Algebra Relacional.

- Desarrollar una actitud crítica frente al uso de las herramientas enseñadas.

- Frente a un problema en particular, ser capaz de brindar una solución eficiente utilizando los conceptos vistos sobre diseño de estructuras de datos y diseño de bases de datos relacionales.
VI - Contenidos
1. Introducción
Dato e Información. Definición de Bases de Datos. Propiedades. Modelos de Datos. El concepto de esquema e instancia. Sistemas de Gestión de Bases de Datos (SGBD). Arquitectura de 3 esquemas de un SGBD. El concepto de independencia de datos.

2. Teoría de Diseño de Base de Datos Relacionales
Objetivos. Antecedentes formales. Esquema e instancia de una relación. Estudio de dependencias funcionales. Definiciones. Claves. Implicación lógica y clausura de conjuntos de dependencias funcionales. Clausura de conjuntos de atributos. Axiomas de Armstrong. Consistencia y completitud de los axiomas. Derivación. Conjuntos equivalentes de dependencias funcionales. Coberturas equivalentes minimales. Descomposiciones de esquemas de relación. Propiedades de las descomposiciones: descomposición sin pérdida de información (Lossless Join) y descomposición con preservación de dependencias. Algoritmos de verificación de las propiedades.
Formas normales: 1NF, 2NF, 3NF y BCNF. Algoritmos para hallar descomposición en 3NF, sin pérdida de información y/o que preserve dependencias Algoritmo para hallar descomposición en BCNF sin pérdida de información.

3. Algebra relacional
Definición formal. Expresión relacional. Operadores primitivos: Unión, Diferencia, Producto Cartesiano (extendido), Selección y Proyección. Operadores no primitivos: Intersección, Ensamble con fórmula, Ensamble Natural y División. Expresividad del lenguaje: consultas a bases de datos relacionales no expresables en Álgebra Relacional.

4. SQL (Structure Query Language)
Estudio de SQL. El lenguaje de consultas SQL. Consultas simples. Conjunto de instrucciones básicas del SQL: select, insert, update, delete, create, drop. Operaciones de conjunto: union, intersect, difference. Subconsultas.

5. Evocaciones asociativas de respuesta múltiple
Estructura general del programa invocante. Rutinas para su resolución. Su posible conversión a problemas de respuesta única.

6. Múltiples servicios sobre una relación
Unicidad de la imagen de la información. Criterios primarios y secundarios. Diferencias en los parámetros entre técnicas usadas como criterio primario y como criterio secundario (índices).

7. Estructuras de Datos en Memoria Secundaria
Descripción del hardware de los dispositivos de disco. Tiempo de acceso a una página de disco. El problema del manejo de estructuras de datos en disco. Árbol B: Operaciones básicas: creación, localización, altas y bajas. Deducción de esfuerzos máximos.Variaciones de Árbol-B: Árbol B*, Árbol B+. Rebalses en disco. Rebalse extensible.

8. Otros tipos de evocaciones
Secuenciales. Evocaciones por rango: unidimensional y multidimensional. El KD-tree. Búsqueda de patrones en texto: árboles y arreglos de sufijos.

9. Filtros
Filtro de igualdad. Su aplicación a servicios secundarios. Deducción del error.
Filtro de pertenencia: determinación del número óptimo de marcas por elemento. Su aplicación a Archivos Diferenciales.

10. Ordenamientos
Cota inferior de la complejidad. Estudios de los algoritmos: inserción, selección, burbujas, heapsort,rápido, shell. Análisis de esfuerzos de algunos algoritmos

11. Estudio de un SGBD: ORACLE
Instancia Oracle: Procesos en memoria principal y área global de sistema (SGA). Descripción de estructuras de datos en memoria principal que forman la SGA: database cache (archivos diferenciales), redo log buffer y shared pool. Estructuras de datos en disco: tablas simples(relación almacenada en espacio común de nuplas), tablas basadas en índices(relación almacenada en servicio primario), índices de única columna o columnas concatenadas (servicios con uno o más dominios aportados), índices únicos o no únicos (servicios con o sin dependencia fucional), estructuras de almacenamiento utilizadas para índices (Árbol B, Filtro de Pertenencia). Definiendo el tamaño del cluster para transferencia entre disco y memoria principal.

VII - Plan de Trabajos Prácticos
PRÁCTICOS DE AULA
1. Resolución de consultas en bases de datos en Algebra Relacional.

2. Manejo de dependencias funcionales: implicaciones lógicas, derivaciones, cálculo de clausuras F+ y X+, obtención de coberturas minimales. Obtención del conjunto de dependencias para distintas realidades.

3. Descomposición de esquemas en 3NF y BCNF. Análisis de PD y LLJ.

4. Implementación de servicios asociativos de respuesta múltiple. Análisis de casos de alta y baja.

5. Implementación de múltiples servicios sobre una relación. Filtros de igualdad. Indices en memoria secundaria. Diseño completo de una solución: obtención del conjunto de dependencias, descomposición en 3NF y BCNF, planteo de los servicios necesarios sobre cada esquema resultante de la descomposición, diseño de las estructuras de almacenamiento

6. Hashing extensible, Árbol B. Filtros de pertenencia. Deducciones de error, cantidad de marcas y tamaño del vector. Diseño de soluciones usando archivos diferenciales y filtros de pertenencia.

7. Ordenamientos. Detalle de implementación de los algoritmos y deducciones de esfuerzos.

8. Resolución de búsquedas por rango y de búsquedas de patrones en texto.

PRÁCTICOS DE MÁQUINA
1. Implementación de rebalse abierto lineal en memoria principal, para un servicio de evocación asociativa con dependencia funcional.
2. Resolución de consultas en SQL Server 7.0
3. Implementación de rebalse abierto lineal en memoria principal, para un servicio de evocación asociativa sin dependencia funcional.
4. Análisis e implementación de una realidad a informatizar, que involucre estructuras de datos en memoria principal y en disco.
VIII - Regimen de Aprobación
La materia se aprueba por medio de regularización más examen final.

Condiciones de regularización: para regularizar la materia el alumno deberá:
- Aprobar los parciales (dos en total) o sus respectivas recuperaciones con una nota mínima de 7 puntos. Para los alumnos que trabajan existirá una recuperación adicional que sólo pueden utilizar para recuperar uno de los dos parciales.
- Aprobar los trabajos en máquina que se realicen.
- Tener un 70 % de asistencia a clases teóricas.
- Tener un 70 % de asistencia a clases prácticas.


Modalidad de examen final
El examen final podrá ser oral y/o escrito.

Examen Libre
No se admiten alumnos libres.
IX - Bibliografía Básica
[1] FUNDAMENTOS DE SISTEMAS DE BASES DE DATOS Autores: Elmasri, Ramez; Navathe, Shamkant. Editorial Addison Wesley, 5ta edición, 2006.
[2] PRINCIPLES OF DATABASE AND KNOWLEDGE - BASE SYSTEMS (VOL I)Autor: Ullman, Jeffrey D. Ubicación en biblioteca: 519.683.5 U42. Computer Science Press, 1ra edición, 1990.
[3] DATABASE SYSTEMS: THE COMPLETE BOOK. Autores: Hector Garcia, Molina; Jeffrey D. Ullman; Jennifer Widom. Editorial Prentice Hall, 2da edición, 2008.
[4] DISEÑO DE BASE DE DATOS RELACIONALES Autores: De Miguel, A.; Piattini, M.; Marcos, E.Editorial Alfaomega, 2000.
[5] FILE STRUCTURES Autores: Folk, Michael J.; Zoellick,Bill.Ubicación en biblioteca: 519.683.2 F666f2. Editorial Addison-Wesley; 2 edición; 1991.
[6] FILE ORGANIZATION AND PROCESSING Autor: Tharp, Alan L. Ubicación en biblioteca: 519.683.2 T367. Editorial Wiley, 1 edición, 1988.
[7] THE ART OF COMPUTER PROGRAMMING (VOL I Y III)Autor: Knuth, Donald E.Ubicación en biblioteca: 681.3.06 K74. Addison-Wesley, 3ra edición, 1997.
[8] AN INTRODUCTION TO DATABASE SYSTEMS Autor: Date, C.J.ISBN: 0-201-82458-2 Ubicación en biblioteca: 519.683.5 D232i6. Eidtorial Addison-Wesley, 6ta edición, 1994.
[9] THE THEORY OF RELATIONAL DATABASE Autor: Maier, David. Computer Science Press, 1ra edición, 1983.
X - Bibliografia Complementaria
[1] DATA STRUCTURES AND PROGRAM DESIGN IN C Autores: Kruse, Robert L.; Leung, Bruce P.; Tondo, Clovis L. Ubicación en biblioteca: 519.682.2681.3.06 K94. Editorial Pearson, 2da edición, 1997.
[2] DATA STRUCTURES AND ALGORITHMS Autores: Aho, Alfred V; Hopcroft, John E.; Ullman, Jeffrey D. Ubicación en biblioteca: 519.683.2 A286. Addison Wesley, 1ra edición, 1983.
[3] HANDBOOK OF ALGORITHMS AND DATA STRUCTURES Autores: Gonnet G.;Baeza Yates, R. ISBN: 0-201-41607-7. Editorial Addison-Wesley, 2da edición, 1991.
[4] A FIRST COURSE IN A DATABASE SYSTEMS Autor: Ullman, Jeffrey D.; Widom Jenifer. Ubicación en biblioteca: 519.683.5 U41. Prentice Hall, 3ra edición, 2007.
[5] THE DESING AND ANALYSIS OF COMPUTER ALGORITHMS Autores: Aho, fred V.; Hopcroft, John E.; Ullman, Jeffrey D. Ubicación en biblioteca:519.683.2 A286. Editorial Addison-Wesley, 1ra edición, 1974.
XI - Resumen de Objetivos
Al finalizar el curso, se pretende que el alumno sea capaz de:

- Manejar con idoneidad los conceptos que involucran el diseño de estructuras de datos.

- Comprender y aplicar adecuadamente la teoría de diseño de bases de datos relacionales.

- Expresar consultas en Algebra Relacional.

- Desarrollar una actitud crítica frente al uso de las herramientas enseñadas.

- Frente a un problema en particular, ser capaz de brindar una solución eficiente utilizando los conceptos vistos sobre diseño de estructuras de datos y diseño de bases de datos relacionales.
XII - Resumen del Programa
Teoría de diseño de Bases de Datos Relacionales. Dependencias funcionales. Descomposiciones: 1NF, 2NF, 3NF, y BCNF

Álgebra Relacional. Operadores primitivos y no primitivos.
Expresividad: consultas no expresables en álgebra relacional.

SQL: El lenguaje de consultas SQL. Conjunto de instrucciones básicas de SQL.

Estructuras de datos en memoria secundaria: Arbol B, Árbol B+, Árbol B*, Hashing extensible.

Evocaciones asociativas de respuesta múltiple.

Múltiples servicios sobre una relación. Diferencias en los parámetros entre técnicas usadas como criterio primario y como criterio secundario. Recodificaciones.

Filtros: de igualdad, de pertenencia. Archivos diferenciales.

Evocaciones por rango: KD-tree. Búsqueda de patrones en texto: árbol y arreglo de sufijo.

Algoritmos de ordenamiento: inserción, selección, burbujas , heapsort, quick, shell.

Estudio del SGBD ORACLE.
XIII - Imprevistos
 
XIV - Otros