I.T.I.S.
UAL
Organizaci´ on y Gesti´ on de Archivos
Curso 2009/10
´ n y Gestio ´ n de Archivos Organizacio A˜ no acad´emico: 2009-10 Centro: Escuela Polit´ ecnica Superior ´ ´ Estudios: INGENIER´IA TECNICA EN INFORMATICA DE SISTEMAS Curso: 2o Cuatrimestre: 2o Car´acter: TRONCAL Cr´editos: 3 te´oricos + 3 pr´acticos Descriptores: Estructura de Informaci´ on: Ficheros, Bases de Datos Profesor responsable: Irene Mart´ınez Masegosa Area: Ciencia de la Computaci´on e Inteligencia Artificial Departamento: Lenguajes y Computaci´on
Objetivos generales de la asignatura El estudio de las estructuras de archivos es, en esencia, la aplicaci´on de las t´ecnicas de estructuras de datos a problemas especiales asociados con el almacenamiento y recuperaci´on de datos en dispositivos de almacenamiento secundario. Los objetivos propuestos son los siguientes: Conocer las caracter´ısticas y limitaciones de los dispositivos de almacenamiento secundario y terciario. Estudiar formatos y estructuras l´ogicas de los datos. Conocer diferentes m´etodos para guardar los registros en archivos y las correspondientes organizaciones b´asicas. Estudiar las principales t´ecnicas de acceso y recuperaci´on de datos. Describir el uso y mantenimiento de diferentes tipos de ´ındices y la implementaci´on de organizaciones de archivos indexados. Evaluar la eficiencia y costo de las diferentes organizaciones de archivos y t´ecnicas de acceso. Elecci´on de la organizaci´on de archivos adecuada. 1
I.T.I.S.
UAL
Organizaci´ on y Gesti´ on de Archivos
Curso 2009/10
Programa de TEOR´IA
Parte I. Almacenando informaci´on: discos y archivos Tema 1. Almacenamiento de datos. Archivos 1.1. Jerarqu´ıa de memoria 1.2. Discos 1.3. Uso eficiente del almacenamiento secundario Tema 2. Archivos 2.1. Archivos f´ısicos y archivos l´ogicos 2.2. Operaciones principales sobre archivos 2.3. Organizaci´on de archivos Tema 3. Elementos b´ asicos de las estructuras de archivos 3.1. Estructuras de campos 3.2. Estructuras de registros 3.3. Registros de longitud fija Construcci´on de registros de longitud fija Operaciones: Inserci´on, eliminaci´on, modificaci´on 3.4. Registros y datos de longitud variable Construcci´on de registros de longitud variable Operaciones: Inserci´on, eliminaci´on, modificaci´on 3.5. Buffers y bloques de registros 3.6. Acceso a registros. Claves de b´ usqueda B´ usqueda iterativa de un registro en un archivo Acceso directo
2
I.T.I.S.
UAL
Organizaci´ on y Gesti´ on de Archivos
Curso 2009/10
Tema 4. Organizaciones b´ asicas de registros en archivos 4.1. Organizaciones b´asicas de registros en archivos Archivos de registros no ordenados: Organizaci´on Apilada. Archivos de registros ordenados: Organizaci´on Secuencial Archivos con registros enlazados: Organizaci´on Encadenada 4.2. Elecci´on de una organizaci´on de archivo
Parte II. Indexaci´on Tema 5. Conceptos b´ asicos sobre ´ındices 5.1. Archivos con ´ındices 5.2. Propiedades de los ´ındices Tema 6. Organizaciones indexadas 6.1. Organizaci´on indexada simple 6.2. Organizaci´on secuencial indexada 6.3. ´Indices secundarios. Estructura de un ´ındice secundario Operaciones b´asicas. Mejora de la estructura. Listas invertidas 6.4. Organizaciones basadas en claves secundarias Tema 7. Organizaci´ on multinivel con ´ arboles B y B+ 7.1. Introducci´on. Planteamiento del problema 7.2. Indexando con a´rboles binarios de b´ usqueda ´ Arboles AVL ´ Arboles binarios paginados ´ 7.3. Arboles B Propiedades de los a´rboles B 3
I.T.I.S.
UAL
Organizaci´ on y Gesti´ on de Archivos
Curso 2009/10
Organizaci´on del ´ındice en a´rbol B Operaciones. ´ 7.4. Arboles B+ Acceso indexado y secuencial Propiedades Operaciones Variantes de a´rboles B+ 7.5. Comparaci´on de ´arboles B y B+ ´ 7.6. Arboles B∗ Tema 8. Hashing 8.1. Caracter´ısticas y elementos b´asicos de una organizaci´on hashing 8.2. Hashing est´atico Elementos principales Algoritmos de hashing M´etodos para evitar colisiones T´ecnicas de resoluci´on de colisiones. Operaciones. 8.3. Hashing din´amico Expansi´on din´amica de archivos. Caracter´ısticas de los m´etodos de hashing din´amico. Hashing extensible
Parte III. Gesti´on de Datos Tema 9. Ordenaci´ on externa 9.1. Algoritmo Merge Sort para ordenaci´on 9.2. Uso de ´arboles B+ para ordenaci´on Tema 10. Introducci´ on a los Sistemas de Bases de Datos 10.1. Funciones de un sistema de gesti´on de Bases de Datos 10.2. Componentes 4
I.T.I.S.
UAL
Organizaci´ on y Gesti´ on de Archivos
Curso 2009/10
10.3. Sistemas de archivos versus sistemas de Bases de Datos
´ Programa de PRACTICAS Pr´ actica 1. Operaciones b´ asicas de Entrada/Salida. Registros 1.1. Implementaci´on de una librer´ıa general para gestionar registros 1.2. Crear fichero binario a partir de un fichero de datos Pr´ actica 2. Gesti´ on de ´ındices 2.1. ´Indices primario y secundarios 2.2. Crear archivo binario ordenado 2.3. Implementaci´on y gesti´on de bloques de registros 2.4. Creaci´on de un archivo de bloques de registros con ´ındice no denso 2.5. Indices secundarios con lista invertida ´ Pr´ actica 3. ´Indices con Arboles B y B+ ´ 3.1. Construcci´on de un Arbol B de orden n para archivo binario ´ 3.2. Construcci´on de un Arbol B+ para archivo de bloques Pr´ actica 4. Ficheros relativos. Hashing est´ atico 4.1. Implementaci´on de un m´etodo de dispersi´on o Hashing 4.2. Construir archivo
Las pr´ acticas se realizan en C++.
5
I.T.I.S.
UAL
Organizaci´ on y Gesti´ on de Archivos
Curso 2009/10
´ EVALUACION Para aprobar la asignatura es necesario aprobar la parte te´ orica y la parte pr´ actica. TEOR´IA: 50 por ciento de la calificaci´on final. • Nota Teor´ıa = Examen Teor´ıa + trabajos opcionales ◦ Examen de Teor´ıa: (40 puntos). Examen tipo test, que contendr´a preguntas del tipo verdadero/falso o preguntas con varias respuestas o combinaci´on de ambas. Las preguntas contestadas err´oneamente restar´an puntos a la nota. ◦ Trabajos opcionales:(hasta 10 puntos). Ejercicios propuestos en clase, trabajos te´oricos en grupo, etc ´ PRACTICAS: 50 por ciento de la calificaci´on final. • Nota pr´acticas = Examen + pr´acticas obligatorias + pr´acticas opcionales ◦ Examen de pr´ acticas (30 puntos): obligatorio. Resolver ejercicios de programaci´on y cuestiones de dise˜ no e implementaci´on relacionadas tanto con los contenidos te´oricos como pr´acticos, estudiados en la asignatura. ◦ Guiones de pr´ acticas: Pr´acticas Obligatorias: hasta 15 puntos Pr´acticas Opcionales: hasta 5 puntos • Para aprobar la parte de pr´ acticas es necesario aprobar el examen de pr´ acticas, y realizar (y defender) las pr´ acticas obligatorias . La suma de todos los puntos obtenidos deber´a ser superior a 25 puntos. No se guarda la nota de pr´acticas de cursos anteriores. Los alumnos que suspendan o no entreguen las pr´acticas en la convocatoria de junio deber´an realizar una pr´actica extraordinaria en las convocatorias de septiembre y de diciembre. En ambos casos tambi´en ser´a obligatorio realizar el examen de pr´acticas.
6
I.T.I.S.
UAL
Organizaci´ on y Gesti´ on de Archivos
Curso 2009/10
BIBLIOGRAF´IA . Estructuras de Archivos Fol98 File Structures. An Object-Oriented Approach with C++. 3th. ed M.J. Folk, B. Zoellick and G. Riccardi. 1998. Luq98 Ficheros: Organizaciones Cl´ asicas para el Almacenamiento de la Informaci´ on. I. Luque, J.A. Romero y M.A. G´omez-Nieto. 1998. Fol92b File Structures. Second edition. M.J. Folk and B. Zoellick. 1992. Fol92 Estructuras de Archivos. M.J. Folk y B. Zoellick. 1992. Tha88 File Organization and Processing. A. L. Tharp. 1988. Liv90 File Structures. Theory and Practice. P. E. Livadas. 1990. Smi87 Files and Databases: An Introduction. P. Smith and M. Barnes. 1987.
. Bases de Datos Gar00 Database System Implementation. H. Garcia-Molina, J. Ullman and J. Widom. 2000. Ram00 Database Management Systems. Second edition. R. Ramakrishnan. 2000. Sil01 Database System Concepts. Fourth edition. A. Silberschatz, H. Korth and S. Sudarshan. 2001. Elm01 Sistemas de Bases de Datos. Conceptos fundamentales. 3a edici´on. R. Elmasri y S. Navathe. 2001.
.Algoritmos Cor90 Introduction to Algorithms. T. Cormen, C. Leiserson and R. Rivest. 1990. Sed01 Algorithms, third edition. R. Sedgewick. 2001.
7
