Archivos II

Abajo

Clase 9: Archivos II

Corte de Control

El corte de control es un proceso en el cual los registros del archivo se encuentran ordenados por el valor de uno o más campos, denominados campos clave o llave, el ordenamiento puede ser ascendente –lo más común- o descendente. Este tipo de proceso generalmente es utilizado para realizar informes o reportes, en el cual se deba emitir de cada grupo –formado por el mismo valor del campo clave- totales, promedios, máximos o mínimos, etc..
En líneas generales este proceso posee una estructura que es bastante característica y que pasaremos a detallar a continuación.
Cada corte de control establece un nivel, así si existen n cortes de control, habrá n niveles, y cada uno de estos n cortes o niveles están contenidos dentro de un ciclo indefinido, a estos ciclos se le suma uno más, y representa el fin del proceso, siendo este ciclo el de mayor nivel y el más externo, luego en forma anidada se van desarrollando los ciclos internos en un orden que va de mayor nivel de corte hasta llegar al menor nivel de corte. El ciclo de mayor nivel establece el fin del proceso, siendo su condición, el fin del archivo que se está procesando, por medio de una variable de tipo boolean. Las condiciones de los ciclos internos van arrastrando las condiciones de los ciclos anteriores o más externos a la que se le suma la propia condición del ciclo, es decir, la que producirá el corte de control de ese nivel, por lo tanto, cuanto más anidado sea el ciclo, más condiciones contendrá. El ciclo externo contiene una condición, y el ciclo más interno posee n + 1 condiciones. Si un proceso requiere n cortes, entonces la cantidad de ciclos será de n + 1. Además cada corte de control obliga a que los datos se encuentren ordenados por el valor del campo clave comenzando desde el de mayor nivel hasta el de menor nivel, por ejemplo, si se requieren obtener totales de las ventas realizadas por diferentes vendedores, los datos deberían están organizados por el código de vendedor; un segundo ejemplo, si los vendedores realizan sus actuaciones en una zona y el proceso requiere informar además totales por zonas, en este caso los datos deben encontrarse ordenados primero por código de zona y luego por código de vendedor, debido a que es de esperar que primero cambien los vendedores y luego cambien las zonas.
El corte de control requiere de una lectura anticipada y en el caso del lenguaje Pascal será una lectura especial, en la cual, primero se debe determinar que no sea fin de archivo para poder leer un registro. Debido a que las próximas lecturas se realizan en otro punto del programa, la lectura especial va a ser un módulo con tres parámetros, a saber: el archivo, el registro a devolver y el estado de la operación de lectura, de tipo boolean, si es falso indicará que no fue fin de archivo y se leyó un registro, caso contrario, indicará que es fin de archivo. Las próximas lecturas del archivo se realizarán en el ciclo más interno y como última acción.
Antes de ingresar a un ciclo denominamos a esa región del algoritmo cabecera. Al salir de un ciclo, denominamos a esa región del algoritmo pié. Dentro de un ciclo, denominamos a esa región del algoritmo proceso.
En la cabecera generalmente realizamos las siguientes acciones: Inicializar, Emitir títulos y datos. En el pié generalmente realizamos las siguientes acciones: Cálculos, Emitir totales, promedios, máximos o mínimos, tomar alguna decisión. En el proceso generalmente realizamos las siguientes acciones: Cálculos, Emitir líneas de detalle, tomar alguna decisión.

A continuación se presenta un modelo de algoritmo de Corte de Control en un formato general.

IMPORTANTE:

Es necesario aplicar este módulo cuando un proceso requiera una lectura anticipada. Este método funciona siempre, es decir, aún para aquellos procesos en que no requiera lectura anticipada, pero en este último caso debemos ubicar el módulo en los dos puntos dentro del algoritmo como fuera indicado anteriormente.

Apareo de Archivos:

El apareo de archivos es un proceso que dependiendo del tipo de organización que tengan estos archivos, el algoritmo adoptará una estructura particular. Este proceso es muy empleado para la actualización del maestro a través del archivo de novedades. Las novedades tendrán que ver con altas, bajas o modificaciones o algunas de ellas solamente. Si ambos archivos poseen una organización secuencial, entonces ambos archivos deben encontrarse ordenados –ascendente o descendente- por medio del valor de una clave en común. El resultado de este proceso será un nuevo archivo de salida con la misma estructura que el maestro a actualizar, siendo este archivo el maestro actualizado. El archivo de novedades tiene la misma estructura que el maestro pero con un campo más, el cual indica el código de movimiento. Cada archivo trabajará con sus propios registros, es decir, un registro para el archivo maestro viejo, otro para el archivo de maestro nuevo y un registro para el archivo de novedades. Las situaciones de errores por alta existente o bajas o modificaciones inexistentes, se emitirán por medio del dispositivo de la impresora.
Este proceso que genera un nuevo archivo –el maestro actualizado- se denomina proceso Padre – Hijo.

El siguiente diagrama de sistema muestra el proceso Padre – Hijo.

A continuación se presentará un modelo de apareo de archivos, con un archivo maestro desactualizado y un archivo de novedades, ambos con organización secuencial, con valores de campos claves sin repetición en cada uno de los archivos y ordenados ambos por el valor de una misma clave.
Al igual que con el Corte de Control, el proceso de apareo requiere una lectura anticipada y debe ser una lectura especial en el Lenguaje Pascal, como fue indicado en el tema de Corte de Control.
Un primer proceso se realizará mientras no haya finalizado ningún archivo y en un segundo proceso, se procesará el archivo que no haya finalizado, hasta agotarlo. Por lo tanto, habrá tres ciclos en secuencia.
Dentro del primer ciclo o proceso se compararán los valores de las claves de ambos archivos, por ejemplo, ¿la clave del maestro es igual a la clave de novedades? o ¿la clave del maestro es mayor a la clave de novedades? y por descarte será que ¿la clave de maestro es menor a la clave de novedades?.
En el primer caso si la clave del registro maestro es igual a la clave del registro de novedades se deberá comparar el código de movimiento, pudiendo ser igual a ‘A’ por alta, o a ‘B’ por baja o a ‘M’ por modificación.
Si el código de movimiento es igual a ‘A’ será un error, por alta existente, es decir, el valor de esa clave se encuentra ya en el archivo maestro y el registro de maestro desactualizado deberá grabarse en el nuevo maestro –para no perderlo-.
Si el código de movimiento es igual a ‘B’ no es error y no debe grabarse en el nuevo maestro, -de esta manera lo estamos dando de baja al no aparecer en el nuevo maestro-, por lo tanto, no debemos realizar ninguna acción por este caso.
Si el código de movimiento es igual a ‘M’ no es error y debemos mover los campos a modificar indicados por el archivo de novedades al registro del maestro y luego grabarlo en el nuevo maestro.
Por último debemos realizar la lectura especial por cada uno de los archivos, es decir, tanto del maestro desactualizado como de novedades.
A continuación se detalla el proceso a realizar si la clave del registro maestro viejo es mayor a la clave del registro de novedades.
En este caso resulta que existe un registro de novedades sin su registro correspondiente en el maestro. Por lo tanto se debe determinar el código de movimiento.
Si el código de movimiento es igual a ‘A’ es correcto ya que la clave no existe en el maestro viejo y debe realizarse el alta, para ello se debe asignar los campos informados por la novedad al registro del maestro nuevo y grabar un nuevo registro en maestro nuevo. No asignarlo al registro del maestro viejo, ¿por qué?.
Si el código de movimiento es igual a ‘B’ es error, por baja inexistente.
Si el código de movimiento es igual a ‘M’ es error, por modificación inexistente.
Por último debemos realizar la lectura especial solo de novedades, -se lee del archivo cuya clave resultó menor, de esta manera aseguramos alcanzar el valor de la otra clave-.
A continuación por decantación se detalla el proceso a realizar si la clave del registro maestro viejo es menor a la clave del registro de novedades.
En este caso resulta que existe un registro de maestro sin su registro correspondiente en el de novedades. Por lo tanto, aquí no se deberá analizar el código de movimiento, ya que no existe. El registro de maestro viejo se debe grabar en el archivo maestro nuevo y se debe realizar la lectura especial solo de maestro viejo, por haber resultado su clave menor a la de novedades-.
Este primer proceso finaliza cuando uno de los archivos finalice, podría darse el caso que finalicen ambos, si los valores de las claves del último registro de cada archivo son iguales.
Debido a que no se garantiza que finalicen ambos archivos en el proceso anterior, habrá que procesar los registros restantes del archivo que no finalizó.
Si es el caso del maestro viejo que no haya finalizado el proceso finalizará cuando se hayan procesados todos los registros restantes de éste archivo. El proceso consistirá en grabar todos los registros pendientes. Debido a que traemos un registro que hemos leído pero no hemos procesado, dentro del ciclo primero grabamos el registro y luego leemos con una lectura especial el próximo registro.
Por otro lado, si es el caso del archivo de novedades el que no haya finalizado el proceso finalizará cuando se hayan procesados todos los registros restantes de éste otro archivo. El proceso consistirá en realizar las mismas acciones vistas en el caso cuando la clave de maestro viejo es mayor a la clave de novedades, solo serán correctos los registros de novedades cuyos códigos de movimientos indiquen ‘A’.

A continuación se presenta un modelo de algoritmo de Apareo de archivos en un formato general.

Éste modelo de apareo de archivos puede ser optimizado si se realizan algunos ligeros cambios. En principio vemos que las acciones alfa y beta se vuelven a reiterar cuando uno de los archivos haya finalizado.
La pregunta es ¿no podrían estas acciones realizarse solamente y en forma completa dentro del primer ciclo?. La respuesta es sí, pero realizando las siguientes modificaciones.
En principio se abandonará el ciclo si ambos archivos finalizaron. El secreto radica en asignar el valor más alto al campo clave del archivo que finalizó, si los archivos están ordenados en forma ascendente, caso contrario se asignará el valor más bajo. Esta técnica se conoce como HIGH VALUE o LOW VALUE en el segundo caso.
La lectura especial podría tener 2 parámetros, el archivo a leer y el registro a devolver.
En caso que haya finalizado el archivo se deberá mover al campo clave el valor más alto, -o el más bajo-, es decir, un valor al cual ningún dato leído podrá alcanzar. Por ejemplo, si el campo clave indicara un código de vendedor de 3 dígitos, el valor más alto sería 1000, ya que ningún dato que se lea alcanzaría a ese valor especial; un segundo ejemplo, podría ser tratándose de fechas con mes y día en un mismo campo clave, el valor más alto sería 1232 ¿por qué?.
Las condiciones del ciclo, deberán compararse, los valores de los campos claves con el valor más alto, y para abandonar el ciclo las condiciones podrían ser las siguientes:
(rMv.cmpClv ¹ HIGH_VALUE) v (rN.cmpClv ¹ HIGH_VALUE)
HIGH_VALUE es una constante con nombre definida en la sección const, p.ej.:

const
HIGH_VALUE = 1000;

De esta manera los ciclos posteriores dejarían de existir, ya que no se lo requieren. Con estos ligeros cambios el algoritmo solo quedaría con un solo ciclo.
La lectura especial podría presentar el siguiente aspecto:

Búsqueda Binaria o Dicotómica:

La búsqueda binaria es un proceso en el cual los datos deben encontrarse ordenados por el valor de la clave a buscar, generalmente en orden ascendente, pero puede ocurrir que se encuentren ordenados en forma descendente. Nuestro modelo de estudio se considera ordenado en forma ascendente. El proceso consiste en tomar el valor que se encuentre en una posición media entre las posiciones de los extremos, así tratándose de elementos que se encuentran en un archivo, esos valores extremos serían cero y filesize(f) – 1. El punto medio se obtiene de aplicar la siguiente expresión:

med <-- (pri + ult) div 2;

en donde: pri es el extremo inferior y ult es el extremo superior. Una vez obtenido el punto medio se accede a esa posición en el archivo y se lee el registro, luego se compara con el valor de la clave a buscar, pudiendo resultar alguna de las siguientes posibilidades:

1. Que el valor del registro leído sea igual al valor clave a buscar, en ese caso, el proceso de búsqueda finalizará saliendo del ciclo cambiando el estado a una variable boolean e informaremos el dato a retornar, por ejemplo, en qué posición se encontró, o un valor boolean, o el valor de un campo o todo el registro, según lo que convenga al proceso.
2. Que el valor del registro leído sea menor al valor clave a buscar, en ese caso deberá cambiarse el valor del extremo inferior, de la siguiente manera: pri <-- med + 1.
3. Caso contrario, es decir, el valor del registro leído es mayor al valor clave a buscar, en ese caso deberá cambiarse el valor del extremo superior, de la siguiente manera: ult <-- med – 1.

Este método va eliminando, por cada vez que obtenemos un punto medio, una mitad del conjunto de datos que nos va quedando, y habiendo leído el registro de esta posición, su valor no es el de la clave a buscar. Por lo tanto, aquí tenemos del porque este método recibe el nombre de búsqueda binaria o dicotómica.

Si la clave no se encuentra, el proceso finalizará cuando el valor del extremo inferior sea mayor al valor del extremo superior, es decir, cuando pri es mayor a ult.

La búsqueda binaria garantiza realizar pocos accesos al disco, si n es el tamaño del archivo, la cantidad de accesos recién se duplica con n². Por ejemplo, si n = 50000 la cantidad de accesos máximos será de 16. La expresión que determina esto está en función de log₂(n). Recordemos entonces que para poder aplicar este método, el conjunto de datos, deberá encontrarse ordenado por el valor de la clave a buscar. A continuación se describe el algoritmo para un caso general de búsqueda binaria. El mismo será una función que recibe como parámetros el archivo y la clave y retorna la posición, si se encontró un valor ³ 0, caso contrario –1.

De acuerdo a las necesidades de un proceso, el módulo de búsqueda binaria podrá ser una función si lo que se retorne es un valor simple como una posición del archivo o un estado de verdadero o falso por si se encontró o no la clave, una cadena, un real o cualquier otro valor simple. Pero si lo que hay que devolver fuera una estructura de datos, el módulo a emplear sería un procedimiento.

Búsqueda Lineal o Secuencial:

La búsqueda secuencial o lineal en archivos no es aconsejable, debido a que la cantidad de accesos a realizar para buscar el valor de una clave, en el peor de los casos será de n accesos, en el mejor de los casos será de 1 acceso y como promedio será de n/2 accesos, para un archivo con n registros.
Para aplicar la búsqueda binaria hemos visto en el tema anterior que el archivo debe encontrarse ordenado por el valor de un campo clave. El costo que tendremos en un archivo desordenado sería entonces tener que ordenarlo.
Podrían existir casos excepcionales en el cual podamos aplicar la búsqueda secuencial a un archivo desordenado, por lo tanto daremos el algoritmo correspondiente, para esta situación.
Buscar el valor de una clave en un archivo desordenado, primero debemos asegurar que el puntero al archivo esté ubicado al comienzo del mismo. Inicializamos el estado de una variable de tipo boolean en falso, y al nombre de la función le asignamos –1 para indicar que aún el valor de la clave no se ha encontrado. El proceso se realizará mientras no se haya encontrado un registro que contenga el valor de la clave a buscar y mientras no sea fin de archivo. Dentro del proceso leemos un registro, luego lo comparamos con el valor de la clave, si es igual lo hemos encontrado, modificamos el estado de una variable de tipo boolean a verdadero y asignamos al nombre de la función la posición del archivo – 1. A continuación presentamos el algoritmo de búsqueda lineal.

Por último si un archivo se encuentra ordenado en concordancia con el valor de la clave a buscar, como se vio en párrafos anteriores, la búsqueda binaria es la técnica a emplear, pero, se podría emplear la búsqueda secuencial, el único impedimento es que serán necesarios más accesos al disco, ahora bien, si descartamos este hecho real, podríamos decir que el método de búsqueda secuencial visto anteriormente podría ser aplicado, pero sabiendo que el archivo ya se encuentra ordenado, existe una variante más óptima para estos casos. El proceso finalizaría ahora no solamente si se encuentra el valor de la clave a buscar, sino que también nos detendríamos si el valor leído en una instancia se hiciera mayor al valor de la clave, ya que no tendría razón de seguir avanzando en la búsqueda, debido a que todos los valores posteriores también serían mayores. La única razón de mostrar este método consistiría en que posteriormente se verán estructuras de datos en la cual el único acceso posible sería el secuencial y con esta estructura ordenada la búsqueda finalizaría al encontrarse el valor a buscar o bien cuando hayamos alcanzado un valor mayor al buscado. El algoritmo correspondiente de una búsqueda secuencial optimizada en archivos se detalla a continuación, -en realidad jamás utilizaremos este método- ya que la búsqueda binaria sería el método a emplear. Este método se muestra al solo efecto de que más adelante se verán estructuras de datos dinámicas lineales y ordenadas por el valor de una clave, y en estos casos buscar un elemento en estas listas será únicamente secuencial, no existiendo la posibilidad de realizar búsqueda binaria, por lo tanto, será una búsqueda secuencial optimizada, en el sentido que cuando nos topemos con un valor que se hizo mayor al buscado, en ese punto detendremos la búsqueda.

Recordar: Para archivos ordenados el método de búsqueda será el dicotómico o binario, en cambio si existe una relación 1:1, es decir el valor de la clave = dirección –f. biyectiva- o transformando el valor de la clave en una dirección válida en el archivo sin que se produzcan colisiones, el direccionamiento directo es el que debe emplearse. Si el archivo estuviera desordenado la creación de archivos auxiliares para lograr accesos más rápidos a los datos del archivo es otra de las posibilidades como técnicas a emplear.
El siguiente ejemplo ilustra una situación en la cual el archivo se encuentra desordenado. Suponiendo que este archivo fuera de vendedores conteniendo como campos el código del vendedor (3 dígitos), más otros campos de interés, y sabiendo que vamos a recurrir en forma reiterada a este archivo para buscar el valor de una clave por código de vendedor, los accesos secuenciales serían reiterados y por consecuencia la velocidad de ejecución de este proceso caería por debajo de lo óptimo o deseado. Aplicar el método de búsqueda binario no podríamos realizarlo debido a que el archivo no está ordenado y si bien existe la posibilidad de ordenarlo físicamente, aplicar ese método está fuera de las posibilidades conocidas hasta ahora, es lo que se conoce como método por copia y se requieren un archivo del mismo tamaño que el original, -ahí va a quedar el archivo definitivo y ordenado-, más un espacio adicional para un archivo temporal de trabajo. Pero como dijimos anteriormente este método no vamos a emplear. Otro método podría ser indexar el archivo a través del uso de un archivo de índices, pero acá también con los conocimientos logrados hasta ahora no contamos con la información necesaria para lograr este cometido. Otra posibilidad sería en crear un archivo en el cual pueda contener todas las claves posibles. La técnica a emplear en este último caso será de la creación de un archivo cascarón que contenga todas y solo todas las posibles claves. Para el ejemplo previamente indicado este archivo constará de 1000 registros, cuyas direcciones irán de 0 a 999.
Una vez creado el archivo cascarón que reserva los espacios suficientes, se procederá a leer secuencialmente el archivo de datos, por cada registro leído se accede con direccionamiento directo a la posición en el archivo auxiliar indicada por el valor de la clave, y grabamos la referencia o dirección del valor de esa clave en el archivo de datos, y así sucesivamente hasta finalizar el recorrido en el archivo de datos.
valores claves. Por ejemplo si leemos del archivo vendedores el valor clave 349, con este valor nos ubicamos en el archivo auxiliar y grabamos 0, debido a que el primer registro leído se encuentra en esa posición, el segundo registro leído el valor clave es 231, con este valor nos ubicamos en el archivo auxiliar y grabamos 1, debido a que el segundo registro leído se encuentra en esa posición, y así sucesivamente hasta finalizar el archivo cuya posición a grabar será la posición de vendedores menos uno.
A continuación se da un ejemplo de esta situación:

Notar en el auxiliar que la dirección-clave 349, dice que se encuentra en la referencia 0 en vendedores, que la dirección-clave 231, dice que se encuentra en la dirección 1 en vendedores y así sucesivamente. Luego en el proceso, al requerir un dato de un vendedor, accedemos con la clave conocida en el auxiliar, a la dirección que coincide con su clave y con el valor que obtenemos de leer ese registro accedemos directamente a vendedores. Por ejemplo si conocemos la clave del vendedor 185 accedemos a esa posición en el auxiliar, leemos el registro y con el valor 10 accedemos a esa posición en vendedores. ¡¡¡Esto es mucho más óptimo que acceder secuencialmente a un archivo desordenado!!! incluso más rápido que acceder en forma dicotómica o binaria. El costo de aplicar este método es que debemos de contar con un espacio adicional en disco para poder crear el archivo cascarón.

Anterior: Archivos I

Siguiente: Conjuntos

Arriba