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 2009)
(Programa en trámite de aprobación)
(Programa presentado el 08/06/2009 15:58:20)
I - Oferta Académica
Materia Carrera Plan Año Periodo
ORGANIZACION DE ARCHIVOS Y BASES DE DATOS I LIC.EN CS.DE LA COMPUTACION 2009 1° cuatrimestre
ORGANIZACION DE ARCHIVOS Y BASES DE DATOS I PROF.EN CS.DE LA COMPUTACIÓN 2009 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 09/03/2009 19/07/2009 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
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. 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).

7. 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 Á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 a 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
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] FILE STRUCTURES Autores: Folk, Michael J.; Zoellick, Bill ISBN: 0-201-55713-4 Ubicación en biblioteca: 519.683.2 F666f2
[2] FILE ORGANIZATION AND PROCESSING Autor: Tharp, Alan L. ISBN: 0-471-61766-0Ubicación en biblioteca: 519.683.2 T367
[3] COMPUTER ALGORITHMS: KEY SEARCH STRATEGIES IEEE Computer Society Technology Series Ubicación en biblioteca:519.681.5519.878681.3.06 A638
[4] THE ART OF COMPUTER PROGRAMMING (VOL I Y III)Autor: Knuth, Donald E.Ubicación en biblioteca: 681.3.06 K74
[5] 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.
[6] FUNDAMENTOS DE SISTEMAS DE BASES DE DATOS Autores: Elmasri, Ramez; Navathe, Shamkant.
[7] AN INTRODUCTION TO DATABASE SYSTEMS Autor: Date, C.J.ISBN: 0-201-82458-2 Ubicación en biblioteca: 519.683.5 D232i6
[8] THE THEORY OF RELATIONAL DATABASE Autor: Maier, David
[9] 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, fred 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
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.

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.

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

Estudio del SGBD ORACLE.
XIII - Imprevistos