Datalog es Prolog al que se le han quitado cosas a propósito — sin funciones, sin negación sin restricciones, sin orden de cláusulas significativo — y de esa renuncia salen tres garantías que Prolog no puede dar: termina siempre, el resultado no depende del orden, y se puede optimizar como una consulta.
🎯 Por qué está en este programa
Datalog es un primo de la familia lógica y declarativa (Atlas), cuyo representante en el núcleo es SQL.
Aporta al programa la demostración más limpia de la tesis que atraviesa el curso (clases 118, 146 y 164): lo que un lenguaje prohíbe es lo que sus herramientas pueden prometer. Y aporta el concepto de recursión declarativa — consultar una jerarquía o un grafo sin escribir el recorrido (clase 099).
| Año | Formalizado hacia 1977; base teórica en bases de datos deductivas de los ochenta |
| Autoría | Comunidad académica de bases de datos; el nombre, de Hervé Gallaire y Jack Minker |
| Familia | Lógica y declarativa; subconjunto decidible de Prolog |
| Paradigma | Lógico declarativo, sobre relaciones |
| Tipado | Según la implementación; los datos son tuplas de constantes |
| Memoria | Gestionada por el motor |
| Ejecución | Evaluación ascendente con punto fijo (semi-naïve), o mágica |
| Estado | 🟢 En auge: análisis de programas, seguridad, bases de datos y grafos |
Datalog surgió a finales de los setenta en la intersección de dos comunidades: la lógica —de donde venía Prolog— y las bases de datos —donde el modelo relacional de Codd (ficha de SQL) acababa de ganar—.
La pregunta era: ¿qué subconjunto de la lógica se puede evaluar como una consulta a una base de datos, con garantías? Y la respuesta fue quitar tres cosas de Prolog:
Y de ahí salen las garantías: todo programa Datalog termina, y el resultado es único —el menor punto fijo—, independientemente de la estrategia de evaluación. Eso es lo que Prolog no puede prometer.
Durante los ochenta y noventa fue sobre todo académico. Y desde 2010 ha vuelto con fuerza, por una razón muy concreta: es el lenguaje ideal para el análisis de programas — donde las preguntas son relaciones recursivas sobre grafos enormes.
Este es el ejemplo canónico, y explica el paradigma entero:
% HECHOS: lo que se sabe
padre(ana, luis).
padre(luis, marta).
padre(marta, jorge).
% REGLAS: lo que se deriva
ancestro(X, Y) :- padre(X, Y).
ancestro(X, Y) :- padre(X, Z), ancestro(Z, Y). % ← recursiva
Y con eso, ancestro(ana, jorge) es cierto — sin escribir un bucle, sin una pila y sin decidir si
se recorre en anchura o en profundidad.
El motor calcula el punto fijo: aplica las reglas una y otra vez hasta que no se derivan hechos nuevos. Y como no hay funciones, el conjunto de hechos posibles es finito, así que termina siempre.
Y la comparación con los otros dos lenguajes declarativos del Atlas es lo más instructivo de esta ficha:
| Prolog | Datalog | SQL | |
|---|---|---|---|
| Recursión | sí | sí, y termina | sí, con WITH RECURSIVE |
| ¿Termina siempre? | no | sí | sí |
| ¿Importa el orden? | sí | no | no |
| Evaluación | descendente, con vuelta atrás | ascendente, punto fijo | plan del optimizador |
| Funciones y términos | sí | no | limitado |
| Optimizable como consulta | difícil | sí | sí |
Y la fila de la terminación es la que justifica el lenguaje: en análisis de programas se ejecutan reglas sobre grafos de millones de nodos, y no poder garantizar que el análisis termina lo haría inservible.
Y hay una segunda propiedad, muy práctica, que explica su vuelta: el mantenimiento incremental.
Si cambia un hecho, NO hay que recalcularlo todo:
el motor propaga solo lo que se ve afectado.
Eso es lo que permite que un análisis de código se actualice al guardar un fichero en lugar de tardar minutos, y es lo que hace viable a CodeQL y a los motores de reglas modernos.
#lang datalog), en Clojure (Datomic, Datascript) y
como biblioteca en varios lenguajes (clase 163).WITH RECURSIVE (SQL:1999) es, esencialmente, Datalog dentro de SQL.souffle -F hechos/ -D salida/ analisis.dl # Soufflé: compila y ejecuta
racket -e '(require datalog)' # dentro de Racket
# Y en Datomic o XTDB, como lenguaje de consulta de la base de datos
Es la versión que aparece en el primos.md de la clase 041, y es un contrato adaptado
(clase 040): Datalog puro no tiene entrada, salida ni aritmética general.
% Datalog puro no tiene E/S: se declaran los hechos y la regla que deriva el total.
venta(15000, 2, 0.10).
total(T) :- venta(P, C, D), T = P * C * (1 - D).
Lo que hay que ver, y es lo más interesante de la ficha.
venta(...) es un dato; la regla
total(T) declara qué significa el total, y el motor lo deriva. Nadie llama a nada.T = P * C * (1 - D) es una extensión, no Datalog puro: el Datalog original no tiene
aritmética, precisamente porque las funciones romperían la garantía de finitud. Las
implementaciones prácticas la añaden con cuidado, y declararlo es más honesto que fingir
(clase 040).⏮️ Volver al Atlas · 🗂️ Todas las fichas · 🔗 Relacionadas: Prolog · SQL · Clojure · Racket