Lunes 23 de Agosto

Procesamiento de Datos Masivos

Objetivos: Mostrar como se resuelven los problemas de procesamiento de datos, cuando estos no caben en la memoria del computador.

Temas:

Organización de datos en archivos

Hasta el momento hemos supuesto que los datos que maneja una aplicación no son tan voluminosos y por lo tanto caben en memoria. Cuando recurrimos archivos se debe a la necesidad de conservar datos después de que termina un programa, por ejemplo para apagar el computador.

Sin embargo, exiten problemas en donde el volumen de datos es tan grande que es imposible mantenerlos en memoria. Entonces, los datos se almacenan en un conjunto de archivos, los que forman una base de datos. Una base de datos es por lo tanto un conjunto de archivos que almacenan datos con respecto al negocio de una empresa, por ejemplo.

Cada archivo se forma en base a un conjunto de líneas y cada línea esta formada por campos de información. Todas las líneas de un mismo archivo tienen la misma estructura, es decir los mismos campos de información. Diferentes archivos poseen estructuras distintas, i.e. campos de información.

Por ejemplo, el archivo cuentacorrentistas.dat de un banco contiene una línea por cada cuentacorrentista del banco y para cada persona se mantiene la siguiente información:

El archivo movimientos.dat contiene las transacciones que se realizan. Tiene los siguientes campos:

Examinaremos con estos archivos los patrones fundamentales para el procesamiento de archivos. Supondremos que los campos están separados por el caracter ":".

Selección

El patrón de selección consiste en obtener un subconjunto de las líneas que contiene un archivo. Por ejemplo, en un banco se podría querer obtener todos los cuentacorrentistas mayores de 65 años.

El siguiente programa produce el archivo mayores.dat con esta información:

    class Mayores extends Program {
      void run() {
        TextReader lect= new TextReader("cuentas.dat");
        TextWriter escr= new TextWriter("mayores.dat");
        while (true) {
          String lin= lect.readLine();
          if (lect.eofReached())
            break;
          FieldParser decod= new FieldParser(lin, ":");
          String ci= decod.readString();
          ...
          int nac= decod.readInt();

          if (nac<=1934) // Condición de selección
            escr.println(lin);
        }
      }
    }
El archivo que se produce en una selección contiene los mismos campos de información que el archivo original, pero contiene menos líneas.

Proyección

El patrón de proyección consiste en eliminar campos de un archivo. Por ejemplo, el siguiente programa proyecta el archivo de mayores de 65 extrayendo sólo el nombre y dirección:

    class Mayores2 extends Program {
      void run() {
        TextReader lect= new TextReader("mayores.dat");
        TextWriter escr= new TextWriter("mayores2.dat");
        while (true) {
          String lin= lect.readLine();
          if (lect.eofReached())
            break;
          FieldParser decod= new FieldParser(lin, ":");
          String ci= decod.readString();
          String apellidos= decod.readString();
          String nombres= decod.readString();
          String direccion= decod.readString();

          escr.println(apellidos+":"+nombres+":"+dirección);
        }
      }
    }
El archivo que se produce en una proyección siempre contiene el mismo número de líneas que el original, pero contiene menos campos.

Tanto la selección como la proyección tienen un solo archivo de entrada y un archivo de salida.

Pareo (Join)

El patrón de pareo se usa cuando se necesita reunir información que se encuentra en dos archivos. Por ejemplo, supongamos que el archivo cuentas.dat contiene los campos: carnet de identidad, nombre y número de cuenta. Por otra parte, el archivo saldos.dat contiene: número de cuenta y saldo de esa cuenta. Se desea producir un archivo cuentas-saldos.dat que contenga todas las cuentas que aparecen simultáneamente en saldos.dat y en cuentas.dat, colocando en el archivo la unión de los campos que aparecen en ambos archivos.

A modo de ejemplo, si los archivos son:

cuentas.dat              saldos.dat
-----------              ----------

10000:Pedro:100          100:475
30000:Juan:101           101:3444
20000:Diego:104          103:923
60000:Sutano:107         107:3884
80000:Megano:109         109:384
El resultado sólo debe contener las cuentas 100, 101, 107 y 109, porque ellas aparecen en ambos archivos. Por lo tanto, el archivo producido debe ser:

cuentas-saldos.dat
------------------

10000:Pedro:100:475
30000:Juan:101:3444
60000:Sutano:107:3884
80000:Megano:109:384
Para que funcione el patrón de pareo se necesita que ambos archivos estén ordenados por número de cuenta. Además ninguno de los archivos posee cuentas repetidas. En estas condiciones se puede leer secuencialmente ambos archivos y producir el tercero:

        TextReader lect= new TextReader("cuentas.dat");
        TextReader saldosLect= new TextReader("saldos.dat");
        TextWriter escr= new TextWriter("cuentas-saldos.dat");
        String saldosCuenta= "";
        String saldosLin= "";
        int saldo= 0;
        while (true) {
          String lin= lect.readLine();
          if (lect.eofReached())
            break;
          FieldParser decod= new FieldParser(lin, ":");
          String ci= decod.readString();
          String nom= decod.readString();
          String cuenta= decod.readString();
          while (compare(saldosCuenta, cuenta)<0) {
            saldosLin= saldosLect.readLine();
            if (saldosLect.eofReached())
              break;
            FieldParser saldosDecod= new FieldParser(saldosLin, ":");
            saldosCuenta= saldosDecod.readString();
            saldo= saldosDecod.readInt();
          }
          if (saldosLect.eofReached())
            break;
          if (compare(cuenta, saldosCuenta)==0)
            escr.println(lin+":"+saldo);
        }
        escr.close();
        lect.close();
        saldosLect.close();
Si bien este programa está correcto, su gran tamaño dificulta su compresión. En la próxima clase veremos la manera de dismininuir el tamaño de este programa por medio de la definición de clases de apoyo que almacenarán el contenido de las líneas de los archivos.

Resumen

Matemáticamente podemos expresar este problemas como:

Sea A un archivo con líneas {a1, a2, ...} y el archivo B con líneas {b1, b2, ...}. El pareo de los archivos A y B por el campo k es el conjunto de pares ordenados (a, b) tal que a pertenece a A y b pertenece a B y a.e=b.e.