Parte VIII · Los datos
Bases de datos
Se construye sobre: Axiomas y conjuntos, Algoritmos y complejidad
Piensa en el cuaderno de una tienda de barrio: cada página, un cliente; en cada página, lo que debe, lo que pagó, la dirección. Funciona hasta que el cliente se muda y hay que cambiar la dirección en tres páginas, o hasta que alguien pregunta cuánto se vendió el martes y la respuesta está repartida por todo el cuaderno. Cualquier aplicación que guarde usuarios, pagos o documentos tiene ese mismo problema multiplicado por millones, con muchas personas escribiendo al tiempo y con la obligación de no perder nada si se va la luz. Una base de datos es la respuesta a ese problema, y la mejor respuesta que conocemos salió, casi entera, de la teoría de conjuntos.
La idea de Codd
En los años sesenta los datos se guardaban en estructuras jerárquicas o en redes de registros enlazados por punteros, y los programas tenían que saber navegarlas: para encontrar las facturas de un cliente, ir al cliente, seguir el puntero a su primera factura, de ahí a la siguiente. Si cambiaba la forma de guardar, había que reescribir los programas. En 1970 Edgar F. Codd, un matemático que trabajaba en IBM, publicó un artículo que proponía separar las dos cosas: cómo se guardan los datos es asunto de la máquina; lo que los programas ven son relaciones, en el sentido exacto de las matemáticas.
Recuerda el producto cartesiano de axiomas y conjuntos. Si son conjuntos, los dominios de valores posibles (textos, enteros, fechas), una relación es simplemente un subconjunto de su producto:
Cada elemento de es una tupla, una fila; cada posición es un atributo, una columna. Eso es una tabla. La tabla de departamentos del Eje Cafetero, con su código del DANE, es el conjunto de tres tuplas . Que sea un conjunto tiene consecuencias: las filas no tienen un orden propio y no hay dos iguales. Las funciones, que también son subconjuntos de un producto, resultan ser un caso particular de relación, y esa coincidencia es la que hace funcionar todo lo que sigue.
Claves
Una clave primaria es un atributo (o un grupo de atributos) que identifica cada fila: no puede haber dos filas con el mismo valor de clave. Dicho en conjuntos, si es la clave y son filas,
Es decir: el resto de la fila es una función de la clave. El código 66 determina “Risaralda” sin ambigüedad, igual que una cédula determina a una persona. Una clave foránea es una columna que guarda la clave de otra tabla: cada municipio guarda el código de su departamento, y la base de datos se encarga de que ese código exista. Así las tablas se refieren unas a otras sin punteros: la relación entre Dosquebradas y Risaralda no es una flecha guardada en algún lado, es el número 66 repetido en dos tablas.
Normalizar: decir cada cosa una sola vez
Supón que, por comodidad, guardas todo en una tabla plana:
municipio | departamento | capital_del_depto -----------------+--------------+------------------ Dosquebradas | Risaralda | Pereira Santa Rosa de C. | Risaralda | Pereira Calarcá | Quindío | Armenia Salento | Quindío | Armenia
Funciona, pero “la capital de Risaralda es Pereira” está escrito catorce veces si pones todos sus municipios. Si un día hay que corregir ese dato, hay que corregirlo en catorce filas, y si una se te escapa la tabla se contradice a sí misma. Y no puedes registrar un departamento nuevo hasta que tenga algún municipio. Son las anomalías de actualización, inserción y borrado, y todas vienen de lo mismo: la columna de la capital no depende del municipio, depende del departamento. Hay una dependencia escondida, departamento capital, que es una función metida a la fuerza dentro de otra tabla.
Normalizar es sacar cada dependencia a su propia tabla: una de departamentos, con su capital, y otra de municipios, con la clave foránea de su departamento. Las formas normales (primera, segunda, tercera y otras más finas) son una escalera de condiciones que formalizan esa idea; la tercera, la que se usa casi siempre, pide que todo atributo que no sea parte de una clave dependa de la clave y de nada más. El resultado es una base donde cada hecho se dice una vez. Desnormalizar a propósito, repetir datos para leer más rápido, es a veces una buena decisión; lo importante es que sea una decisión.
Pedir sin decir cómo
Con relaciones, consultar es operar con conjuntos. Codd definió un álgebra con unas pocas operaciones. La selección se queda con las filas que cumplen una condición; la proyección se queda con algunas columnas; y el join pega dos tablas por sus columnas comunes. El join no es una operación nueva: es el producto cartesiano seguido de una selección,
Todos los pares posibles de municipio y departamento, 53 × 3 = 159, de los que sobreviven los 53 que concuerdan. SQL, el lenguaje que nació en IBM a mediados de los setenta sobre estas ideas y que se volvió estándar en los ochenta, es la versión escrita de esa álgebra:
SELECT m.nombre, d.nombre FROM municipios m JOIN departamentos d ON d.codigo = m.depto WHERE m.depto = 66 ORDER BY m.nombre;
Es el ejemplo más difundido del paradigma declarativo de lenguajes y paradigmas: la consulta dice qué filas quieres, no en qué orden recorrer qué. Un componente de la base, el optimizador, traduce esa frase a un plan concreto, y puede haber muchos planes para la misma pregunta. Una precisión honesta: SQL se aparta un poco de la teoría. Sus tablas admiten filas repetidas, así que son multiconjuntos y no conjuntos, y tiene un valor especial, NULL, para lo desconocido, que obliga a una lógica de tres valores donde una comparación puede no ser ni verdadera ni falsa.
Dos tablas: los 3 departamentos del Eje Cafetero, con su código DANE, y sus 53 municipios, guardados en orden alfabético. Arma la consulta y mira cuántas filas tiene que leer el motor, con y sin índice.
SELECT m.nombre FROM municipios m WHERE m.depto = 66;
| m.nombre |
|---|
| Apía |
| Balboa |
| Belén de Umbría |
| Dosquebradas |
| Guática |
| La Celia |
| La Virginia |
| Marsella |
| Mistrató |
| Pereira |
| Pueblo Rico |
| Quinchía |
| Santa Rosa de Cabal |
| Santuario |
14 filas en el resultado. El motor leyó 53 filas e hizo 53 comparaciones. Sin índice hay que mirar los 53 municipios uno por uno para saber cuáles son de Risaralda.
El índice: un árbol para no leerlo todo
Prueba en el motor de juguete la consulta de Risaralda sin índices. Los municipios están guardados en orden alfabético, así que los de Risaralda están regados por toda la tabla, y el motor no tiene más remedio que leer las 53 filas y comparar cada una para encontrar las 14 que sirven. Es la búsqueda lineal de algoritmos y complejidad: . Activa los índices y el motor usa una lista aparte con las parejas (departamento, fila) ordenadas por departamento. Una búsqueda binaria encuentra en 6 comparaciones dónde empiezan los de Risaralda, y solo se leen esas 14 filas. Con el join pasa lo mismo: para Quindío, sin índices se leen 89 filas (las 53 de la tabla, más 3 departamentos por cada uno de los 12 municipios); con la clave primaria indexada, 24.
Con 53 filas la diferencia es simpática. Con un millón, la búsqueda binaria necesita 20 comparaciones y la lineal puede necesitar un millón. Pero hay un detalle físico que cambia el diseño: los datos viven en disco, y el disco no se lee de a un número sino de a páginas de varios kilobytes, y cada lectura cuesta muchísimo más que una comparación en memoria. Por eso las bases de datos no usan un árbol binario sino un árbol B, que Rudolf Bayer y Edward McCreight propusieron a comienzos de los setenta. Cada nodo es una página entera con cientos de claves ordenadas y cientos de hijos, y el árbol se mantiene siempre balanceado: todas las hojas a la misma profundidad. Si cada nodo tiene del orden de hijos, la altura es del orden de
un logaritmo, como en la búsqueda binaria, pero en una base mucho mayor. Con 200 hijos por nodo, cuatro niveles alcanzan para claves: encontrar una fila entre más de mil millones cuesta leer unas cuatro páginas, y las de arriba casi siempre ya están en memoria. El precio es que cada escritura tiene que actualizar también el índice, y que el índice ocupa espacio. Por eso no se indexa todo, sino las columnas por las que de verdad se busca. Y fíjate en lo que muestra el motor sin filtro: si la pregunta es por la tabla entera, ningún índice ayuda, porque no hay nada que saltarse.
Transacciones: todo o nada
Pasar dinero de una cuenta a otra son dos escrituras: restar en una y sumar en la otra. Si el servidor se apaga entre las dos, el dinero desapareció. Una transacción agrupa operaciones para que la base las trate como una sola, con cuatro garantías que se resumen en una sigla acuñada a comienzos de los ochenta, ACID. Atomicidad: o pasan todas las operaciones o ninguna. Consistencia: la transacción lleva la base de un estado que cumple sus reglas (claves únicas, claves foráneas que existen, saldos no negativos si así se definió) a otro que también las cumple. Aislamiento: dos transacciones simultáneas no se estorban, idealmente como si hubieran ocurrido una después de la otra. Durabilidad: lo confirmado sobrevive a un apagón.
El truco detrás de la atomicidad y la durabilidad es casi contable: antes de tocar los datos, la base escribe en un registro, que solo crece, lo que va a hacer. Si se cae a la mitad, al despertar lee el registro y termina o deshace lo pendiente. El aislamiento perfecto es caro, y por eso las bases ofrecen niveles más relajados que permiten ciertas anomalías a cambio de velocidad; elegir el nivel es una de esas decisiones que parecen técnicas y son de negocio.
Más allá de las tablas
No todo cabe cómodo en tablas. Las bases de documentos guardan objetos anidados, como un JSON con un cliente y todas sus direcciones adentro; las de clave y valor son un diccionario gigante y rapidísimo; las de grafos guardan nodos y aristas y son buenas para preguntas del tipo “amigos de amigos”. Conviene mirarlas con sobriedad: no son el futuro que reemplaza a lo relacional, sino herramientas para patrones de uso concretos, y muchas ganan velocidad o escala renunciando a parte de las garantías de arriba. Hay un resultado que pone límites a todos: en un sistema distribuido en varias máquinas, si la red se parte y unas no pueden hablar con otras, el sistema tiene que elegir entre seguir respondiendo y garantizar que todas las respuestas son consistentes. Es el teorema CAP, conjeturado por Eric Brewer en 2000 y demostrado, en una formulación precisa, por Seth Gilbert y Nancy Lynch en 2002.
Lo relacional tampoco se quedó quieto. El álgebra de Codd, sin más, no puede calcular la clausura transitiva de una relación: dada la tabla de quién es padre de quién, no puede responder quiénes son todos los ancestros de alguien, que es justo la pregunta de la genealogía. SQL agregó consultas recursivas para eso. Y contar, por ejemplo, cuántas veces aparece cada pareja de palabras en un texto, la base de los n-gramas, es un GROUP BY de dos líneas.
Bases de vectores
La novedad de estos años son las búsquedas por parecido. En una IA que cita la ley cuento cómo un texto se convierte en un embedding, un vector de cientos de números, y cómo buscar por significado es buscar los vectores más cercanos a la pregunta. Eso no se parece a WHERE depto = 66: no hay un valor exacto que buscar, sino un punto y sus vecinos, y un árbol B, que ordena claves en una línea, no sirve para ordenar puntos en cientos de dimensiones. Compararlos todos es lineal, y con millones de fragmentos pesa.
La salida son índices aproximados: estructuras, muchas de ellas grafos que conectan cada vector con algunos de sus vecinos, que encuentran casi siempre los más cercanos visitando una fracción pequeña de los datos. Se cambia un poco de exactitud por mucha velocidad, la negociación de siempre en complejidad. No hace falta un sistema aparte: Postgres, con la extensión pgvector, guarda vectores en una columna y los indexa así, y es lo que usa Licitarus. Me gusta que sea así, porque el fragmento del pliego, su vector, el proceso al que pertenece y la empresa que lo consulta quedan en la misma base, unidos por claves foráneas, bajo las mismas transacciones.
Esa es, creo, la lección de fondo. El código de una aplicación se reescribe cada pocos años; los datos se quedan décadas. Por eso vale la pena que su forma descanse en algo más firme que la moda del momento, y pocas cosas son más firmes que un conjunto. De ahí salen también la estadística y el aprendizaje automático, que empiezan casi siempre con una consulta.