Certamen 2 - Primer Semestre 2004

UNIVERSIDAD TÉCNICA FEDERICO SANTA MARÍA DEPARTAMENTO DE INFORMÁTICA ALMACENAMIENTO Y RECUPERACIÓN DE INFORMACIÓN CERTAMEN 2: Estructuras Básicas de Archivos Profesor: José Luis Martí L. Ayudantes: Francisco Coca - Claudio Corvalán Pregunta 1: (Criterios para escoger la Estructura de un Archivo) Responder verdadero o falso, justificando sólo éstas últimas; cada respuesta mala vale -1 punto. a) Si el número de registros de un archivo es alto, conviene que éste no sea secuencial. R.: Verdadero. b) Un archivo secuencial ordenado es lo mejor para manejar una volatilidad de inserción alta. R.: Falso, pues las inserciones son lentas al ubicar cada nuevo dato en el lugar que le corresponde, según su valor. Si el archivo no está ordenado, las inserciones son siempre al final. c) Lo fundamental para determinar si un archivo secuencial debe estar ordenado o no, es si el atributo de mayor acceso es clave única o no. R.: Falso, lo fundamental se refiere a si los accesos más frecuentes requieren salidas ordenadas por algún atributo, y/o si hay salidas basadas en condiciones de desigualdad sobre algún atributo (ej.: ...where clave < constante...) y/o si la tasa volatidad de inserción es alta o baja. En cualquier caso, da lo mismo si la clave es única o no. d) La principal ventaja del archivo relativo es que su tamaño físico va aumentando dinámicamente a medida que el volumen de registros contenidos crece. R.: Falso, pues un archivo relativo tiene un tamaño fijo, que depende del número de entradas habilitadas desde un comienzo. El cambio en su tamaño no se hace dinámicamente; debe hacerse off-line, para reorganizar su contenido al nuevo espacio de almacenamiento. e) Un archivo hashing estático no puede tener registros en overflow. R.: Falso, si los puede tener; por ende existen las técnicas de resolución de colisiones como el encadenamiento, que tiene buckets de overflow. f) La técnica de hashing lineal genera un mal rendimiento en aplicaciones distribuidas. R.: Falso, pues al no tener algún componente centralizado (nodo raíz, directorio o similar), cada nodo de una red puede tener un bucket y trabajar con una mínima interferencia del resto del sistema. g) En general, un archivo con baja actividad es mejor estructurarlo de tipo hashing. R.: Verdadero. h) El árbol B también es adecuado para organizar un archivo en base a claves secundarias. R.: Falso, no es adecuado porque las claves no necesariamente pueden quedar cercanas (por ejemplo, algunas en las hojas, y otras en la raíz o cerca de ésta), haciendo costosa su recuperación. i) Si un conjunto de registros tiene, mayoritariamente, accesos de tipo directo, el archivo que los almacene debe ser de tipo hashing o árbol. R.: Verdadero. j) Si la recuperación de los datos de un archivo es por procesos batch, sólo conviene que sea organizado como secuencial, no importando si está ordenado o no. R.: Falso, puede ser cualquier estructura de archivo, pues el tiempo de respuesta no es crítico. (30 puntos)

Pregunta 2: (Estructuras Básicas de Archivos) a) Considerar un archivo secuencial desordenado, con 120.000 registros, cada uno de 200 bytes. El tamaño del bloque es de 2 KB, el tiempo de seek de 16 mseg, la latencia rotacional media igual a 8.3 mseg y el tiempo de transferencia de un bloque de 0.8 mseg. Si de ahora en adelante, por cada 2 registros que se añaden hay uno que se borra, hasta que el total de registros activos sea 240.000: ¿Cuántas transferencias de bloques se necesitan para reorganizar el archivo?. R.: Por ser un archivo secuencial desordenado, las inserciones son al final del archivo, mientras que las eliminaciones son aleatoriamente realizadas dentro del archivo de tipo lógico, lo que se desprende de la necesidad de la reorganización, cuyo objetivo es eliminar las entradas libres que se van generando entre medio de los datos, las que generan un costo mayor en espacio en disco y de transferencias de datos, preciso de eliminar. Para alcanzar los 240.000 registros activos, a partir de los 120.000 iniciales, es preciso que se ingresen 240.000 registros nuevos, a los que se asocian 120.000 registros eliminados, dada la condición de que por cada 2 registros añadido hay uno que se borra. Así, al momento de la reorganización se tendrán 360.000 entradas asignadas al archivo, 240.000 con registros activos y 120.000 vacías debido a registros eliminados. A partir del factor de bloqueo del archivo: fb =

2.048 bytes / bloque ---------------------------200 bytes/ registro

= 10 registros / bloque

se sabe que el archivo tiene: b =

360.000 registros ---------------------------10 registros / bloque

= 36.000 bloques

Para la reorganización se necesita leer una sola vez cada bloque desde el disco, eliminando sus entradas inactivas al llenarlas con registros del siguiente bloque de datos. Luego, se tienen 36.000 bloques leidos. Al reorganizar, se tendrán 240.000 registros, los que ocuparán un total de 24.000 bloques, los que serán escritos al disco una sola vez. Finalmente, el número de bloques transferidos para la reorganización es de 60.000 bloques. ¿Cuánto tarda encontrar un registro justo antes de la reorganización?. R.: Para hallar un registro específico, en promedio, se debe recorrer la mitad del archivo, por lo que el costo de encontrarlo es de: (36.000 / 2) * (16 + 8.3 + 0.8) = 451.800 mseg ≈ 7.5 minutos ¿Cuánto tarda encontrar un registro justo después de la reorganización?. R.: Para hallar un registro específico, en promedio, también se debe recorrer la mitad del archivo, por lo que el costo de encontrarlo es de: (24.000 / 2) * (16 + 8.3 + 0.8) = 301.200 mseg ≈ 5 minutos (35 puntos)

b) Un archivo de productos tiene registros cuya clave primaria es el código del producto. Si este archivo se organiza usando hashing lineal, donde cada bucket puede guardar hasta dos registros: Mostrar cómo quedan guardados los registros, si éstos son: #Producto 29 30 42 7 59

Nombre Producto Fideos Cereal Leche en Polvo Azúcar Pack de Yoghurt

Valor

#Producto

380 1.200 1.800 400 1.000

16 23 18 25 37

R.: Inserción de los registros con claves 29 y 30: 0 29 30 Inserción del registro con clave 42: 0 30 42

1 29

Inserción del registro con clave 7: 0 30 42

1 29 7

Inserción del registro con clave 59: 0

1 29 7

2 30 42

59

Inserción del registro con clave 16: 0 16

1 29 7 59

2 30 42

Nombre Producto Queso Jugo Pan Integral Café en Polvo Mantequilla

Valor 1.800 700 900 3.000 250

Inserción de los registros con claves 23: 0 1 2 16 29 30 42

3 7 59 23

Inserción del registro con clave 18: 0 16

1 29

2 30 42

3 7 59

18

23

2 30 42

3 7 59

18

23

2 30 42

3 7 59

18

23

4

Inserción del registro con clave 25: 0 16

1 29 25

4

Inserción del registro con clave 37: 0 16

quedando finalmente como: 0 1 16 25 Queso Café en 1.800 Polvo 3.000

1 25

2 30 Cereal 1.200

3 7 Azúcar 400

42 Leche en Polvo 1.800

59 Pack de Yoghurt 1.000

18 Pan Integral 800

23 Jugo 700

4

4

5 29 37

5 29 Fideos 380 37 Mantequilla 250

A partir de la respuesta anterior, ¿cuánto cuesta responder las siguientes consultas: o select * from archivo; R.: Dado que se requiere recorrer linealmente todo el archivo, el costo es de 8 bloques. o select count(*) from archivo; R.: Ídem que el caso anterior, por lo que el costo es de 8 bloques. o select * from archivo where clave = …; R.: Existen 8 registros que se recuperan con la lectura de un único bloque, mientras que hay dos registros que se recuperan con la lectura de dos bloques. Luego, el costo promedio de la consulta es de: (8 * 1 + 2 * 2) / 10 = 1.2 bloques o select * from archivo where clave between 16 and 18; R.: Se debe evaluar la presencia de cada uno de los valores presentes en el intervalo dado, incurriendo en un bloque para la clave 16, uno para la clave 17 (y saber que no se encuentra), y dos bloques para encontrar el registro de clave 18. Luego, el costo de las tres búsquedas directas suma 4 bloques. (35 puntos) JLML/jlml. 040604.