Hazañas informáticas VI: el sistema UNIX

Si habéis estado siguiendo esta serie de artículos, habréis podido percibir un notable patrón- los sujetos de los que hablo no suelen ser muy recientes. Internet se conoce como tal desde el 82, el modelo relacional se formuló en el 69, las funciones hash aparecen mencionadas en una publicación en el 53, el sistema RSA data del 78 y las máquina de Turing y von Neumann son de allá por los años 40.

Es decir, la hazaña informática más jovencita es más vieja que yo con sus 33 años de edad. Pero ninguna de ellas está obsoleta- es más, todas ellas siguen vigentes y es posible que algunas sobrevivan más de un siglo (sólo es posible que el criptosistema RSA quede obsoleto si algún día la computación cuántica resulta práctica- aunque con toda probabilidad sea reemplazado por un criptosistema de clave pública similar).

El que hoy nos ocupa es otro jovenzuelo- el sistema operativo UNIX nació en 1970 en un laboratorio de Bell Labs, como sistema operativo para un videojuego implementado por un equipo de programadores aburridos en el proyecto Multics. Con el pretexto de adaptarlo para el procesado de textos, Thompson, Ritchie, Kernighan, McIlroy y Ossanna asentaron una de las dos familias de sistemas operativos que aún hoy pervive con cierta popularidad (la otra sería la familia de los 360 de IBM, que es más antigua aún).

UNIX se basa en conceptos sencillos- se implementa usando el lenguaje C (hijo del recientemente fallecido Ritchie) portable, simple y eficiente en un momento en que los sistemas operativos se implementaban directamente sobre el procesador, ligándolos al hardware para el cuál estaban diseñados y dificultando su desarrollo; un sistema de archivos jerárquico, cualidades de multiusuario y multitarea… todos ellos conceptos imprescindibles hoy en día. Además, introduce la filosofía Unix de programas pequeños comunicándose entre ellos- haciéndolo extremadamente versátil pero simple, una cualidad vital para ser extremadamente apropiado para gente como los programadores.

Pero más allá de ello, UNIX fue “pionero” en el hecho de que su código (junto con el de los compiladores del lenguaje C) fueran distribuidos libremente- la condena de las prácticas monopolísticas de AT&T impedían su comercialización y por contra forzaban a distribuirlo a quien lo pidiera. Si hoy en día es increíblemente costoso desarrollar un sistema operativo, en esa época primitiva, lo era aún más; y los sistemas operativos de la época eran por tanto costosos y, al ser no portables, sólo funcionaban en un determinado tipo de hardware. La distribución de Unix, por tanto, permitía a cualquiera aprovechar su código, adaptarlo al hardware que tenían y disponer de un sistema operativo potente por un coste relativamente bajo.

Lógicamente, mucha gente se sumó al carro- compañías comerciales que lo usaron o incluso lo extendieron y comercializaron (HP, Solaris, IBM, etc.; hasta Microsoft comercializaba su propio Unix hasta el 89). Pero el desarrollo quizás más importante se dio en universidades, particularmente en la de Berkeley en California. En el 83 AT&T quedó liberada de los corsés antimonopolistas y pudo comercializar Unix, movimiento con el cual los Unix no comerciales, y en especial el de Berkeley comenzaron a cobrar importancia, ya que eran los únicos que quedaban como libremente distribuibles.

Los sistemas comerciales siguieron su camino y perduran hasta nuestros días; HPUX, AIX y especialmente Solaris aún son moderadamente populares, sobre todo en grandes entornos comerciales de computación.

Por otra parte, los sistemas académicos también siguieron su evolución paralela.  Del código de Berkeley surgieron sistemas operativos como NetBSD, FreeBSD y OpenBSD- el BSD es de Berkeley Software Distribution- y el nucleo de Darwin que está en las entrañas de Mac OS X (y según dice Apple, el iOS del iPhone, iPod Touch e iPad) es también un “BSD”.

En los 90, un estudiante de informática finlandés, frustrado por no disponer de un sistema operativo Unix viable para ordenadores personales (que en aquel entonces eran básicamente Ataris, Amigas, Macs y PCs con MS/DOS y Windows), desarrolló un sistema operativo estilo Unix, aprovechando las herramientas GNU; algo que acabo dando luz a Linux (o GNU/Linux).

Llegando hasta hoy, los Unix comerciales siguen teniendo su importancia en entornos empresariales- Linux y los BSD libres han ganado una gran importancia, OS X es el segundo sistema operativo para ordenadores personales más popular; en el ámbito móvil, Android se basa en Linux y según dice Apple, el iOS del iPhone también, con lo que en realidad, gran parte de los ordenadores de hoy en día son “Unix”- las excepciones más notables son Windows, los sistemas operativos de los mainframes (básicamente los de IBM descendientes de la serie 360) y los sistemas operativos de móviles que no son Android ni iOS (Blackberry está transicionando de su sistema operativo a QNX [un Unix], Nokia aún conserva su Series 40 para móviles de bajo coste y está matando Symbian…).

El mérito de Unix radica en simplemente eso- su sencillez y claridad de conceptos inicial han perdurado hasta nuestros días- siendo difícil la valoración de su repercusión frente a la serie 360, pero claramente siendo uno de los desarrollos informáticos más significativos de la historia de la computación.

Hazañas informáticas V: Las máquinas de Turing y Von Neumann

¿Qué es un ordenador?

A primera vista, esto parece una pregunta sencilla. ¿Es una cosa con pantalla y teclado? Si es eso, ¿es una calculadora de mesa convencional un ordenador? ¿Es una consola un ordenador? ¿Un móvil?

Antes de 1936, existían bastantes máquinas bastante parecidas a ordenadores- existían calculadoras, máquinas de codificación como la Enigma, etc.; hasta los griegos construyeron máquinas que podían calcular la posición de las estrellas en el firmamento. Sin embargo, ninguna de estas máquinas tenía la flexibilidad que tienen los ordenadores de hoy en día- las calculadoras pueden hacer operaciones matemáticas, Enigma podía codificar y decodificar textos, el mecanismo de Anticitera podía localizar los astros- pero ninguna de ellas podía hacer nada más que aquello para lo que estaban pensadas.

En 1936, Turing, uno de los padres fundadores, describió una sencilla máquina teórica que consiste en un cabezal situado sobre una cinta (infinita) que contiene símbolos. El cabezal puede desplazarse por la cinta, leyendo y escribiendo símbolos. Esta máquina tiene un estado, y según lo que lee mediante el cabezal, puede alterar su estado, desplazarse y escribir.

Esta construcción simple (la definición informal es de un par de líneas; la formal no es mucho más larga) es sin embargo muy flexible. Dada una definición de estados y comportamientos adecuados, la máquina de Turing puede realizar, por ejemplo, cualquier cálculo que se nos ocurra; dada una cinta con símbolos que describan números, puede sumarlos, multiplicarlos, etc. y en general, realizar cualquier computación que pueda realizar un ordenador de hoy en día. Esto tiene un primer interés; la máquina de Turing puede modelizar cualquier proceso informatizable, y por tanto, nos puede servir como base teórica para analizarlos- podemos describir una máquina de Turing (sus comportamientos, símbolos, movimientos, estados, etc.) que realice cualquier cálculo.

Sin embargo, podemos dar un paso más allá. Dado que podemos realizar cualquier operación computable con una máquina de Turing, esto nos lleva a decir que podríamos programar una máquina de Turing de manera que interprete los símbolos en su cinta como la descripción de una máquina de Turing- con los comportamientos del cabezal, sus estados, los símbolos etc.; y luego colocar más allá en la cinta los datos que queremos que procese. Es decir; podríamos describir el proceso de suma y luego colocarle unos números para que sume. Esta máquina de Turing podría, sin variar su programación y sólo cambiando los símbolos impresos en la cinta, realice cualquier cosa que pueda realizar una máquina de Turing- es decir, podemos obtener una máquina de Turing única “universal”- cuya programación le permite realizar cualquier cálculo computable.

Este proceso mental teórico nos sugiere una cosa interesante- podemos construir una máquina que a partir de unos “datos” (en este caso, unos símbolos en una cinta) que describen el cálculo a realizar y los datos en sí, realice cualquier operación que podamos describir- en efecto, una máquina “programable”.

Una vez más, esto tiene un interés teórico considerable, pero obviamente una máquina que procese una cinta infinita, leyendo y escribiendo símbolos de ella no parece algo muy práctico (y de hecho no lo es).

Paralelamente a las elucubraciones de Turing, otros científicos que trabajaban en máquinas de computación llegaban a ideas similares;  Konrad Zuse en Alemanía y Eckert y Mauchly en EEUU comenzaron a elaborar máquinas con conceptos de programabilidad; Zuse, aburrido de realizar cálculos en su trabajo como ingeniero aeronáutico,  creo el Z1, de programabilidad limitada y funcionamiento problemático en  1938, seguido del Z2 en 1939 y finalmente el completamente programable Z3  en 1941. Eckert y Mauchly trabajaban en el proyecto EDVAC, para crear una máquina para calcular trayectorias de artillería, al que se unió John Von Neumann en 1944. Se acredita a Von Neumann con la primera descripción “práctica” de una máquina programable ampliamente conocida publicada en 1945, que explica lo que ahora se conoce como arquitectura de Von Neumann.

La arquitectura de von Neumann es en sí muy parecida a la máquina universal de Turing, pero con una implementación física mucho más realizable- un procesador con unidades capaces de realizar cálculos aritméticos y de almacenar pequeñas cantidades de información, una memoria que almacena datos y programas, dispositivos de entrada y salida (teclados, pantallas, etc.) y lo que une a todos; el hecho de que el procesador lee instrucciones de su memoria y las va ejecutando, leyendo y modificando datos de la misma memoria y interactuando mediante sus dispositivos.

Las máquinas con arquitectura de Von Neumann eran infinitamente más versátiles que las máquinas de propósito único anteriores- eran programables y eso hacía que cualquier problema se pudiese afrontar con un programa nuevo, y que las mejoras en potencia de estas se verían traducidas en mejoras en la resolución de todos los problemas- máquinas potentes podrían resolver problemas más complejos y más grandes en menos tiempo.

Pese a mejoras conceptuales, y por supuesto, una brutal evolución tecnológica, el ordenador donde estoy tecleando esto ahora mismo es esencialmente una máquina de Von Neumann según descripciones de hace 66 años, y los problemas que puede resolver no son ni más ni menos que aquellos que podía resolver teóricamente la máquina universal de Turing tal como fue descrita hace 75 años- sorprendentemente en todo esto tiempo aún no hemos inventado nada práctico que pueda resolver algo que no pudiera resolver una máquina de Turing. Además, ahora prácticamente cada dispositivo electrónico es programable- hasta las calculadoras de escritorio son por dentro máquinas de von Neumann (aunque no sean fácilmente programables)- las máquinas de un solo propósito están casi extintas.

Así pues, en más de 60 años hemos visto una descomunal evolución en las máquinas programables- que han pasado de costar millones de euros y ocupar habitaciones a ser asequibles por todo el mundo y hacer cosas que nadie soñó cuando se crearon, pero por contra, aún no hemos superado los principios teóricos postulados por los fundadores de la informática.

Hazañas informáticas IV: Las funciones hash

Los mayores problemas de rendimiento de un sistema informático vienen causados por tener que trabajar con volúmenes grandes de información. La mayoría de algoritmos tienen un tiempo de ejecución relacionado con el tamaño de la información que manejan. Por ejemplo, encontrar el valor máximo de un conjunto de valores es directamente proporcional al tamaño del conjunto- si duplicamos el tamaño del conjunto, tardamos el doble en encontrar el  máximo.

También es obvio que el tamaño de los datos afecta también a la velocidad de las comunicaciones- bajarse un fichero de dos megas normalmente cuesta el doble que uno de un mega.

Así pues, parece una obviedad que reduciendo el tamaño de los datos con los que trabajamos, normalmente incrementaremos la velocidad de nuestros cálculos y/o nuestras comunicaciones.

Por ejemplo, si comprimimos archivos que queremos transferir, reduciendo su tamaño, los podremos comunicar más rápidamente. Existen algoritmos de compresión que permiten reducir el tamaño de los datos sin perder fidelidad, con lo cual la mayoría de veces nos interesa transmitir datos comprimidos (sobre todo en el caso común en el que la compresión es efectiva y más rápida que la transferencia en sí).

Hay algoritmos de compresión que no conservan la fidelidad con el archivo original; el popular formato de imagen jpeg permite comprimir imágenes fotográficas muchísimo, pero sacrificando la calidad de la imagen- la gracia del algoritmo es que la calidad que se pierde a menudo es imperceptible o despreciable.

Los algoritmos de compresión con pérdida son muy útiles- eliminando el requerimiento de conservar toda la información, se consiguen cotas de compresión muchísimo más elevadas de lo que se pueden conseguir mediante algoritmos que preservan todos los datos.

Existe una cosa parecida pero que da un paso más, que son las funciones hash.

Una función hash es en cierta manera una compresión- se coge unos datos de un tamaño arbitrario y se obtienen unos datos mucho más pequeños. Un hash típico da como resultado un puñado de bytes (16, 32, etc.) a partir de entradas de cualquier tamaño.

Está claro que debe haber una pérdida sustancial de información al pasar de una cosa a otra. Cierto. Es más, la mayoría de funciones hash no permiten reconstrucción alguna de los datos originales a partir del hash.

¿Para qué puede servir algo que supone esta pérdida de información?

La utilidad de las funciones hash viene dada por una propiedad muy simple. Una función hash debe ser determinista. Es decir, que para el mismo dato, el resultado de la función hash siempre tiene que ser el mismo.

Esto nos permite, por ejemplo, hacer una cosa muy interesante. Alicia se ha bajado de internet un fichero enorme y se encuentra que al intentar utilizarlo, no le funciona. ¿Se trata de que se ha bajado el fichero incorrectamente o de que su ordenador no funciona correctamente o el fichero original no era correcto?

Si el fichero fuese pequeño, la solución sería muy sencilla; se lo puede bajar más veces- cuantas más veces se lo baje, más probable será que una de las descargas sea correcta. Si se lo baja 10 veces y no funciona nunca, es poco probable que haya habido un error en la transmisión, lo más probable es que el fichero sea incorrecto en origen o ella tenga un problema usándolo.

Pero claro, si el fichero es grande y tarda mucho en descargarse, es impráctico bajarlo varias veces para asegurarse que está bien.

¿Cómo pueden ayudar las funciones hash aquí?

La persona que tiene el fichero original, puede calcular un hash del fichero y pasárselo a Alicia. Dado que el hash es pequeño, este es rápido de transferir y es más fácil comprobar su validez.

Una vez Alicia tiene el fichero que se ha descargado y su hash, puede calcular ella el hash del fichero. Si el hash que calcula es diferente al hash del fichero original, está claro que su fichero no es idéntico al fichero original- si lo fuese, el hash debería ser igual ya que la función hash debe ser determinista.

¿Ahora bien, y si los dos hashes son iguales?

Pues lógicamente, no podemos garantizar que los ficheros sean iguales. En la práctica, si escogemos las funciones hash cuidadosamente (básicamente, que cumpla que dos entradas parecidas tengan hashes muy diferentes y que la distribución de hashes generados sea uniforme), la posibilidad de que dos ficheros tengan hashes idénticos son muy reducidas. Si una función hash puede dar como resultado 16 hashes diferentes, la probabilidad de que dos entradas tengan un hash idéntico es de 16^2 o 256.

Lo bueno aquí es que si doblamos el tamaño de las salidas del hash, reducimos a una cuarta parte las posibilidades de error.

Una función hash tipica que dé hashes de 16 bytes puede dar 2 elevado a 128 posibles hashes (o 340282366920938463463374607431768211456 valores diferentes), con lo que la probabilidad de que dos hashes coincidan es microscópica (de 1 entre 2 elevado a 256, o en concreto de 1 entre 115792089237316195423570985008687907853269984665640564039457584007913129639936), con lo cuál, simplemente escogiendo una buena función hash podemos hacer comprobaciones de integridad tan fiables como deseemos con hashes muy pequeñitos.

¿Tienen las funciones hash más utilidades?

Pues sí, infinidad más. Programando muchas veces queremos almacenar datos y acceder rápidamente a ellos por un concepto concreto. Por ejemplo, querríamos almacenar todos los datos de los habitantes de España y poder acceder a ellos por su nombre.

Una solución sencilla sería guardar los datos de todos ellos en una lista y cada vez que tuviésemos un nombre, recorrer la lista hasta encontrar a la persona que buscamos.

Si hay 40.000.000 de habitantes en España, de media necesitaremos leernos la mitad de la lista (20 millones de entradas) hasta encontrar los datos de la persona.

¿Cómo podemos emplear un hash para acelerar esto?

Buscaremos una función hash que a partir de un nombre, nos pueda dar n posibles hashes. Crearemos n listas, y en cada una, guardaremos los datos de las personas cuyo nombre tenga un hash concreto.

Si escogemos una función hash que haga que cada valor hash sea más o menos equiprobable, cada lista contendrá 40.000.000/n personas.

Así pues, para localizar los datos de una persona sabiendo su nombre, calcularemos el hash de su nombre, y eso nos llevará a la lista donde están sus datos. Dentro de eso tendremos que recorrerla para encontrar sus datos, pero en vez de recorrer una lista de 40.000.000 de personas, recorreremos una lista reducida tanto como queramos.

Aquí hay un pequeño balance que hay que hacer; cuantas más listas diferentes tengamos, menos eficiente será su almacenamiento y acceso, con lo cual seguramente no será efectivo escoger una función hash con 40.000.000 dde valores hash posible (con lo cual, encontrar una persona sería prácticamente inmediato), pero seguramente con funciones hash más pequeñas, sí que consigamos un aumento sustancial del rendimiento.

Hazañas informáticas III: la criptografía asimétrica

Desde el principio de los tiempos, los humanos han deseado en ocasiones mantener la privacidad de sus comunicaciones. En tiempos de los romanos ya se utilizaban técnicas de criptografía como el cifrado César para las comunicaciones militares.

El cifrado César consiste en la sustitución simple de unas letras por otras, por ejemplo, sustituir la “a” por “c”, “b” por “d”, “c” por “e”, etc. Con lo que por ejemplo, “cifrado cesar” se convertiría en “ekhtcfq eguct”. Este sistema (y muchos otros) se basa en el secreto del sistema- sólo el emisor y receptor del mensaje conocen el método de cifrado y la manera en la que se realiza- en este caso, que cada letra se sustituye por la letra que existe a dos posiciones en el orden alfabético; lo que se conoce como clave secreta.

A pesar de que el cifrado César no ofrece prácticamente ninguna seguridad (una persona que intercepte un mensaje puede fácilmente deducir el sistema usado y desencriptarlo), sí que existen mecanismos de encriptación muy potentes basados en el secreto de la clave (básicamente, un sistema de clave secreta fuerte es aquel en el que podemos hacer que los mensajes sean más difícilmente desencriptables escogiendo claves más complejas).

Sin embargo, en muchas situaciones, los sistemas de claves secretas no son muy útiles. Para hacerlos funcionar, el emisor y el receptor deben poder compartir la clave de una manera segura antes de poder utilizarla.

Pongamos por ejemplo el caso de que queramos realizar transacciones seguras por internet, por ejemplo compras online. Como internet no es un canal de comunicación seguro (es razonablemente sencillo espiar, interceptar y alterar comunicaciones), antes de realizar cualquier compra a un vendedor online, deberíamos poder quedar con el vendedor y acordar una clave secreta por un canal seguro- por ejemplo, quedando presencialmente e intercambiando la clave, algo que no parece nada práctico.

Un investigador de una agencia de inteligencia británica dio en 1973 con un sistema tremendamente sencillo para resolver este problema. Lamentablemente, no lo pudo implementar ni publicar- ya que en ese momento no disponían de los sistemas informáticos suficientemente potentes como para hacerlo funcionar, y al formar parte de una agencia de inteligencia, se consideró un secreto de estado. En 1978, un trío de matemáticos- Rivest, Shamir y Adleman redescubrieron independientemente este sistema y lo publicaron con un nombre tomado de sus iniciales: RSA.

El sistema se basa en un concepto sencillo. En los esquemas de clave secreta, se utiliza una única clave y dos funciones matemáticas de codificación y decodificación. Formalmente, sea un mensaje m, una clave k, y dos funciones E(m,k) y D(m,k), se cumple que D(E(m,k),k)=m; es decir, que las codificar y decodificar un mensaje con la misma clave, se obtiene de nuevo el mensaje original.

El nuevo esquema RSA se basa en que las claves de codificación y decodificación son diferentes, y a pesar de que están íntimamente relacionadas, conocer una no implica conocer la otra. Con esto, yo puedo crear un par de claves; a una la llamaré clave pública y a la otra privada- siguiendo sus nombres, difundiré mi clave pública pero conservaré en secreto mi clave privada.

Así, cualquiera que quiera enviarme un mensaje, podrá coger mi clave pública y codificar el mensaje con ella. Sólo yo, con mi clave privada, podré descifrarlo.

Es decir, si pub es mi clave pública y prv mi clave privada, C la función de codificación y D la de decodificación, D(C(m,pub), prv)=m

Una propiedad interesante de este sistema es que si las funciones se escogen de manera que este proceso funciona a la inversa (puedo “decodificar” con la clave privada primero y al “recodificar” con la clave pública recupero el mensaje original también), yo puedo coger un mensaje y codificarlo con mi clave privada. Si publico el mensaje y la versión codificada, cualquiera que conozca mi clave pública podrá decodificar el mensaje que he codificado y verificar que coincide con el mensaje original. Poder codificar el mensaje de esta manera para que la gente lo pueda verificar sólo lo puede hacer el conocedor de la clave privada- así pues esta operación permite demostrar que el mensaje proviene del propietario de la clave privada. A esta operación se la denomina firma digital y tiene todas las utilidades de una firma en papel tradicional (con la ventaja que es más difícil de falsificar).

¿Cómo funciona este sistema? Pues tanto el investigador inglés como los señores RSA, tuvieron la brillante idea de realizar este esquema al ver el pequeño teorema de Fermat y/o el teorema de Euler. Estos teoremas sobre exponenciación, números primos y cocientes nos permiten encontrar una función de codificación y decodificación (exponenciación y cociente) usando como exponentes y cocientes unos números concretos basados en números primos que permiten que funcione todo esto. Las operaciones de codificación y decodificación son opuestas, y a pesar de que los números (claves) privados y públicos están profundamente relacionados, su relación no es fácilmente descubrible- para descubrirla hemos de factorizar en primos los números que lo componen, lo cuál es un problema complejo.

Lo mejor de todo es que obtener claves muy muy grandes (que hacen que la descomposición sea lenta), es muy sencillo. Podemos generar números primos gigantescos con relativa facilidad, y al componerlos, obtener un número enorme cuya descomposición es infinitamente más costosa.

El sistema RSA lo tiene todo: es muy, muy sencillo, podemos hacerlo tan difícilmente de romper como queramos (buscando primos mayores)… lo único que falla es que es relativamente lento; las operaciones de codificación son lentas. La solución aquí es sencilla- los esquemas de clave privada tienen a ser extremadamente veloces, así que normalmente lo que haremos es usar el sistema de criptografía asimétrica para intercambiar una clave para una codificación de clave privada; así el sistema de clave pública nos resuelve el problema de compartir la clave privada por un canal seguro: usamos la criptografía de clave pública para hacerlo, y a partir de entonces usamos los veloces algoritmos de clave privada para realizar el resto de comunicaciones.

Este sistema es usado hoy en día en la mayoría de aplicaciones de seguridad informática. El criptosistema RSA basado en números primos sigue siendo la implementación más popular- existe un sistema alternativo basado en “curvas elípticas” que se considera más seguro, pero es mucho más complejo y, sobre todo, que algunas de estas curvas elípticas están patentadas y no está claro si se pueden realizar implementaciones de este sistema sin pagar a sus inventores (mientras que el sistema RSA es “libre”).

Hazañas informáticas II: el modelo de datos relacional

Los primeros ordenadores se destinaron a la introducción y proceso de datos- no en vano los orígenes de IBM se remontan a la gestión del censo de habitantes de los Estados Unidos. Naturalmente, hasta el más primitivo de los sistemas de programación provee de primitivas de almacenamiento de datos, mecanismos sencillos para almacenar, organizar y acceder a datos en la memoria volátil del sistema (es decir, que estos datos se pierden al finalizar la ejecución del programa).

Rápidamente, los programadores se ocuparon de implementar funcionalidades que almacenaban estos datos en algún soporte persistente, de manera que los datos se conserven entre ejecución y ejecución del programa, y diseñaron maneras de organizar los datos de manera que las operaciones que se quieren realizar con ellos se hagan de una manera eficiente.

E. F. Codd, allá por 1969, planteó un sistema generalizado de almacenamiento y proceso de datos basado en unos principios muy sencillos.

Codd se dio cuenta que la información que típicamente se quería procesar se podía particionar en hechos simples, del siguiente estilo:

  • La factura #1 es a nombre de Javier Sánchez, a fecha 3/12/2007
  • La factura #2 es a nombre de Lucía Martínez, a fecha 5/12/2007
  • La línea 1 de la factura #32 es para “Mano de obra”, precio 300€
  • La línea 2 de la factura #32 es para “Materiales”, precio 450€

Podemos escribir estos hechos de una manera compacta empleando dos tablas:

Número de factura Nombre Fecha
1 Javier Sánchez 3/12/2007
2 Lucía Martínez 5/12/2007

 

Número de factura Línea Concepto Cantidad
32 1 Mano de obra 300€
32 2 Materiales 450€

Cuando usemos el modelo relacional, definiremos las “tablas” (relaciones) que usaremos en nuestra aplicación, especificando qué “columnas” (atributos) tendrán y qué tipo de valores podrán ponerse en cada columna (en el ejemplo anterior, números de factura, números de línea, nombres, conceptos, fechas y cantidades).

Los sistemas de bases de datos relacionales nos permiten definir con precisión estas tablas, insertar valores, actualizarlos y realizar consultas sobre ellos (e.g. ¿cuál es la fecha del último pedido de Miguel Hernández?), sin preocuparnos de la implementación real de esta estructura de datos, su almacenamiento persistente ni los algoritmos de búsqueda para las consultas.

El trabajo con las bases de datos relacionales se realiza a través de un lenguaje específico adaptado a ellas; el lenguaje más común se conoce como SQL (Structured Query Language) mediante el cuál podemos expresar cosas como:

create table facturas (
  numero_factura          numero,
  nombre                  texto,
  fecha_factura           fecha
);

Que define la tabla facturas con las columnas que hemos visto anteriormente, o:

insert into facturas(numero_factura, nombre, fecha_factura) values (1, 'Javier Sánchez', 3/12/2007);

, que nos permite insertar uno de los hechos que hemos tabulado antes y consultas como:

select max(fecha) from facturas where nombre = 'Miguel Hernández';

a la que nos referíamos anteriormente.

Fijémonos que estas consultas son “declarativas”, es decir que no hablan de cómo se deben almacenar estos datos ni realizarse estas operaciones, sino que sólo dicen “qué se quiere hacer”.

Un siguiente paso interesante en el trabajo con estas relaciones es darnos cuenta que podemos trabajar con varias tablas simultáneamente que comparten información. Por ejemplo, podríamos preguntarnos cuánto se ha gastado Ana Jiménez en concepto de mano de obra entre todos sus pedidos; la tabla de pedidos nos dice qué facturas corresponden a Ana Jiménez y la tabla de líneas de facturas nos dice qué líneas de factura son de mano de obra y por qué cantidad- podemos asociar las dos tablas mediante la columna número de factura presente en ambas. Mediante una sencilla abstracción matemática, podemos realizar consultas y operaciones sobre varias tablas utilizando las posibles asociaciones que haya entre ellas.

Como el modelo relacional es tremendamente abstracto, es apropiado para una gran cantidad de aplicaciones. Así pues, se han desarrollado implementaciones de bases de datos que utilizan el modelo relacional que podemos usar en nuestros programas en vez de tener que “reinventar la rueda” del almacenamiento de datos constantemente. Además, resulta que toda “mejora” que se introduzca en una de estas implementaciones se aprovecha inmediatamente por todas las aplicaciones que usen la implementación.  Por ejemplo, las operaciones entre varias tablas se pueden beneficiar de técnicas de optimización que hacen que las bases de datos sean muchísimo más rápidas que las implementaciones simples de estas operaciones.

Adicionalmente, las aplicaciones se benefician de otras características de los sistemas de gestión de base de datos, como son:

  • Restricciones de integridad. Podemos definir en la base de datos restricciones que deben cumplir los datos para considerarse correctos. Por ejemplo, una factura para ser correcta debe incluir un número correcto, un nombre y una fecha válida, evitando que se puedan introducir datos inválidos. Más allá, podemos decir cosas más interesantes como que el número de factura de una línea de factura debe corresponder a un número de factura en la tabla de facturas.
  • Transacciones. Muchas veces una serie de operaciones sobre una base de datos deben realizarse en conjunto o no realizarse. Por ejemplo, una transferencia bancaria debe incluir un cargo en la cuenta origen y un ingreso en la cuenta destino; claramente si una de las dos operaciones falla, la otra no puede realizarse.

Estas y otras facilidades que ofrecen las bases de datos no son triviales de implementar, y el hecho de poder aprovechar la implementación de la base de datos nos permite desarrollar nuestra aplicación más rápidamente sin tenernos que preocupar de estos complicados detalles.

Hoy en día, tras más de 40 de años desde su invención, el modelo relacional es el estándar de facto para almacenamiento de datos en aplicaciones donde la integridad de los datos es vital- y es también inmensamente popular en aplicaciones menos críticas por su conveniencia, sencillez y velocidad.

 


Hazañas informáticas I: Internet

En los inicios, había muy poquitos ordenadores- grandes como habitaciones e increíblemente caros. Muchos de estos ordenadores tenían múltiples pantallas y teclados para que los pudiesen utilizar simultáneamente muchas personas y que se rentabilizasen mejor. Cada ordenador era un mundo en sí mismo. Algunos de estos ordenadores permitían la comunicación entre personas sentadas en diferentes terminales.

Pronto, comenzaron a aparecer más y más ordenadores en el mundo. Algunos entes privilegiados podían disponer de varios ordenadores, y pronto surgió la necesidad de comunicarlos ente ellos; la capacidad de una máquina siempre nos es insuficiente y queremos realizar operaciones que aprovechen la capacidad de varios ordenadores.

Éste es un problema de fácil solución; los ordenadores trabajan con impulsos eléctricos y con compartir un medio conductor (léase, un hilo de cobre conectado a dos ordenadores), estos pueden enviarse datos codificándolos como descargas eléctricas de una manera muy similar a como funciona un solo ordenador internamente.

Este sistema ha funcionado perfectamente hasta el día de hoy- con no tantas evoluciones, existen hoy infinidad de redes con cientos de ordenadores comunicados a grandes velocidades entre sí mediante lo que es en esencia un hilo de cobre que pasa por todos ellos.

El análogo humano es una habitación llena de personas hablando a viva voz. Todo el mundo puede oír a todo el mundo y se pueden realizar todo tipo de conversaciones- un profesor puede dar clase a cientos de alumnos que le escuchan; un montón de parejas pueden estar en una sala de baile hablando entre ellas y grupos de conversación pueden formarse y deshacerse fácilmente.

Este esquema sencillo, lamentablemente, no funciona bien a gran escala. Intuitivamente vemos que compartir un solo cable de cobre entre una gran cantidad de ordenadores puede ser problemático. Nuestra sala con gente hablando deja de funcionar cuando las distancias son suficientes como para no oir- y si hay demasiada gente hablando, nace la confusión.

Los genios de ARPANET no se aturullaron delante de estos problemas y encontraron una solución simple y efectiva para este problema. Las redes locales de unos cuantos ordenadores funcionan maravillosamente bien, dijeron; no hace falta abandonar ni complicar este modelo. Sencillamente, interconectemos las redes entre sí.

Las comunicaciones locales pueden funcionar como hasta ahora. Lo único que tenemos que hacer es introducir unos dispositivos que tengan un pie en una red, y otro pie en otra. Cuando un ordenador en una red quiera comunicarse con otro ordenador en otra red, se dirigirá al dispositivo de su red que se comunica con otras redes y le entregará la información que quiere transmitir. Si el destinatario está en la otra red, el dispositivo no tiene más que entregárselo. Si no, lo único que tiene que buscar es otro dispositivo de este tipo que esté conectado con otra red que esté más cerca del destinatario y entregarle la información- así la información irá saltando de red en red hasta llegar a su destino.

Esto, en esencia, es internet. El “inter” es de interconexión de redes. El modelo se completa con un sistema de direcciones universales, las famosas IP con las que se identifica a cada dispositivo que vive en Internet- y el sistema de puertos, que identifica en cada dispositivo varios puntos de envío y recepción de datos (un puerto para el correo electrónico, un puerto para el tráfico web, etc.). Encima de esto, el sistema DNS que hace que los humanos podamos usar nombres en vez de IPs numéricas para referirnos a los dispositivos que viven en Internet y los diferentes protocolos que rigen los diferentes servicios que funcionan sobre internet.

Pese a que internet y su ecosistema asociado es infinitamente complejo, la gran virtud es que se basa en un modelo sencillo y elegante- simples redes locales interconectadas.

Próximas entregas:

  • Hazañas informáticas II: el modelo de datos relacional
  • Hazañas informáticas III: La criptografía asimétrica
  • Hazañas informáticas IV: Las funciones hash
  • Hazañas informáticas V: Las máquinas de Turing y Von Neumann
  • Hazañas informáticas VI: el sistema UNIX