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 2008)
(Programa en trámite de aprobación)
(Programa presentado el 12/03/2008 09:57:31)
I - Oferta Académica
Materia Carrera Plan Año Periodo
ORGANIZACION DE ARCHIVOS Y BASES DE DATOS I LIC.EN CS.DE LA COMPUTACION 2008 1° cuatrimestre
ORGANIZACION DE ARCHIVOS Y BASES DE DATOS I PROF.EN CS.DE LA COMPUTACION 2008 1° cuatrimestre
II - Equipo Docente
Docente Función Cargo Dedicación
HERRERA, NORMA EDITH Prof. Responsable P.Adj Exc 40 Hs
RUANO, CARINA MABEL Auxiliar de Práctico A.1ra Exc 40 Hs
RUANO, DARIO MARTIN Auxiliar de Práctico A.1ra Semi 20 Hs
TARANILLA, MARIA TERESA Auxiliar de Práctico A.1ra Exc 40 Hs
VILLEGAS AGUILERA, ANA VALERIA Auxiliar de Práctico A.1ra Exc 40 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 10/03/2008 20/06/2008 15 135
IV - Fundamentación
Considerando como punto de partida lo visto en Estructuras de Datos y Algoritmos, se retoma en este curso el diseño de estructuras de datos, considerando ahora otros tipos parámetros en el diseño: evocaciones de respuesta múltiples, evocaciones por rango y estructuras en disco.

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.

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

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. 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.

2. Evocaciones asociativas sin unicidad de respuesta
Estructura general del programa invocante.
Su posible conversión a problemas de respuesta única.

3. Organización para múltiples criterios de búsqueda
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).

4. Recodificación de dominios
Planteo general del problema. Diccionarios.
Condiciones bajo las cuales conviene una recodificación.
Enumeración por medio de una recodificación.

5. Estructuras de Datos en Memoria Secundaria
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 Arbol-B: árbol B*, árbol B+.
Rebalses en disco. Rebalse extensible.

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

7. 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.

8. Estructura de la Información
¿Qué es información? ¿Qué es estructura de la información?
Estudio de la estructura de la información a ser procesada.
Su incidencia en las estructuras de almacenamiento.

9. 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.
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)
- 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.

10. Algebra relacional
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.

11. 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.

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

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

3. 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.

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

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

6. Implementación de múltiples servicios sobre una relación. Casos de uso de recodificaciones y filtros de igualdad.

7. 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.

8. Diseño completo de una solución. Para distintas realidades: 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


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.

VIII - Regimen de Aprobación
Condiciones de regularización
- Aprobar los parciales(dos en total) o sus respectivas recuperaciones. 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.
- 70 % de asistencia a clases teóricas.
- 70 % de asistencia a clases prácticas.


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

Examen Libre
Sólo podrán rendir el examen final en la condición de libre, aquellos alumnos que, habiendo aprobado todos los prácticos de máquina, queden libres por parciales. El plazo máximo para aprobar la materia en condición de libre es la fecha de inicio de la próxima cursada. No podrán rendir como libres los alumnos que queden libres por faltas.

El exámen constará de dos partes. La primera parte será escrita y de carácter práctico. La segunda, será oral y/o escrita, y de carácter teórico.

IX - Bibliografía Básica
[1] DATA STRUCTURES & PROGRAM DESIGN Autor: Kruse, Robert Ubicación en biblioteca: 681.3.06 K94D2
[2] FILE STRUCTURES Autores: Folk, Michael J.; Zoellick, Bill ISBN: 0-201-55713-4 Ubicación en biblioteca: 519.683.2 F666f2
[3] FILE ORGANIZATION AND PROCESSING Autor: Tharp, Alan L.
[4] ISBN: 0-471-61766-0Ubicación en biblioteca: 519.683.2 T367
[5] COMPUTER ALGORITHMS: KEY SEARCH STRATEGIES IEEE Computer Society Technology Series Ubicación en biblioteca:519.681.5519.878681.3.06 A638
[6] THE ART OF COMPUTER PROGRAMMING (VOL I Y III)Autor: Knuth, Donald E.Ubicación en biblioteca: 681.3.06 K74
[7] FUNDAMENTALS OF DATA STRUCTURES IN PASCAL Autores: Horowitz, Ellis; Sahni, SartajUbicación en biblioteca:: 681.3.06 H816F2
[8] PRINCIPLES OF DATABASE AND KNOWLEDGE - BASE SYSTEMS (VOL I)Autor: Ullman, Jeffrey D.ISBN: 0-7167-8158-1 Ubicación en biblioteca: 519.683.5 U42
[9] FUNDAMENTOS DE SISTEMAS DE BASES DE DATOS Autores: Elmasri, Ramez; Navathe, Shamkant.
[10] AN INTRODUCTION TO DATABASE SYSTEMS Autor: Date, C.J.ISBN: 0-201-82458-2 Ubicación en biblioteca: 519.683.5 D232i6
[11] THE THEORY OF RELATIONAL DATABASE Autor: Maier, David
[12] DISEÑO DE BASE DE DATOS RELACIONALES Autores: De Miguel, A.; Piattini, M.; Marcos, E.
X - Bibliografia Complementaria
[1] DATA STRUCTURES AND PROGRAM DESIGN IN C Autores: Kruse, Robert L.; Leung, Bruce P.; Tondo, Clovis L.ISBN: 0-13-725649-Ubicación en biblioteca: 519.682.2681.3.06 K94
[2] DATA STRUCTURES AND ALGORITHMS Autores: Aho, Alfred V; Hopcroft, John E.; Ullman, Jeffrey D.ISBN: 0-201-00023-7 Ubicación en biblioteca: 519.683.2 A286
[3] THE DESING AND ANALYSIS OF COMPUTER ALGORITHMS Autores: Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D.ISBN: 0-201-00029-6 Ubicación en biblioteca:519.683.2 A286
[4] DATA STRUCTURE TECHNIQUES Autor: Standish, Thomas A.ISBN: 0-201-07256-4 Ubicación en biblioteca: 681.3.06 51 S785
[5] FILE STRUCTURES Autor: Salzberg, Betty ISBN: 0-13-314691-X Ubicación en biblioteca: 519.683.2 S186
[6] HANDBOOK OF ALGORITHMS AND DATA STRUCTURES Autores: Gonnet G.;Baeza Yates, R. ISBN: 0-201-41607-7
[7] A FIRST COURSE IN A DATABASE SYSTEMS Autor: Ullman, Jeffrey D.; Widom Jenifer ISBN: 0-13-861337-0 Ubicación en biblioteca: 519.683.5 U41
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
Algoritmos de ordenamiento: inserción, selección, burbujas , heapsort, quick, shell.

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

Evocaciones asociativas de respuesta múltiple.

Organización para múltiples criterios de búsqueda. 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.

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.

XIII - Imprevistos