El problema fundamental que aborda este artículo es la reconciliación de dos filosofías de diseño de lenguajes de programación inherentemente conflictivas: la optimización de consultas basada en el orden de evaluación no determinista (típica de los sistemas de bases de datos relacionales) y la predictibilidad del comportamiento del programa, incluyendo la terminación y el rendimiento (típica de los lenguajes de programación funcionales). Esta tensión se agudiza cuando se introducen funciones definidas por el usuario (UDFs) con posibles efectos secundarios o no terminación en un contexto relacional, o cuando se intenta integrar la programación relacional en un marco funcional como λFS.

Históricamente, los sistemas de bases de datos han priorizado la eficiencia, delegando la elección del plan de ejecución a un optimizador de consultas que puede reordenar operaciones para minimizar costos. Esto contrasta con los lenguajes funcionales, donde el orden de evaluación (e.g., call-by-name vs. call-by-value) es una propiedad semántica crucial que afecta la terminación y la composición. La emergencia de sistemas que buscan unificar estos paradigmas, como Datalog o SQL con UDFs, y más recientemente λFS, expone esta dicotomía. La pregunta central es cómo diseñar una semántica que permita la optimización declarativa sin sacrificar la capacidad de razonar sobre la terminación y el rendimiento, o si es necesario comprometerse con una de las dos perspectivas.

Arquitectura del Sistema

El artículo no describe una arquitectura de sistema concreta, sino un marco conceptual para un lenguaje llamado λFS, que trata las relaciones como funciones finitas. Una relación R se modela como una función R(x) = true si x está en R, y false en caso contrario. Estas funciones tienen 'soporte finito', lo que significa que solo un número finito de entradas x resultan en un valor no predeterminado (e.g., true para booleanos, 0 para enteros). En tiempo de ejecución, estas funciones se representan mediante tablas de hash o árboles balanceados, similar a las tablas en una base de datos.

El núcleo del debate arquitectónico reside en cómo un motor de consulta (query engine) o un compilador de lenguaje (language compiler) manejaría la evaluación de expresiones conjuntivas que incluyen tanto relaciones (tablas) como predicados de caja negra (black-box predicates) que pueden no terminar. Se exploran tres enfoques: 1) Evaluación estricta de izquierda a derecha, que simplifica el modelo de costos y la predictibilidad de la terminación, pero puede ser asintóticamente ineficiente para ciertas consultas (e.g., consultas cíclicas como la 'triangle query'). 2) Orden de evaluación no determinista, que es el enfoque estándar de los optimizadores de bases de datos, permitiendo mayor flexibilidad para la optimización del rendimiento, pero complicando el razonamiento sobre la terminación. 3) 'Parallel and', una semántica de conjunción que evalúa ambos argumentos concurrentemente y termina cuando uno es falso o ambos son verdaderos, restaurando el determinismo en la terminación pero presentando desafíos de implementación eficiente.

Trade-offs

Ganancias
  • ▲ Predictibilidad de terminación y rendimiento (Left-to-Right)
  • ▲ Optimización declarativa del rendimiento (Nondeterministic Order)
  • ▲ Determinismo en la terminación con UDFs (Parallel And)
Costes
  • ▲▲ Ineficiencia asintótica para consultas cíclicas (Left-to-Right)
  • ▲ Dificultad para razonar sobre terminación y rendimiento (Nondeterministic Order)
  • ▲ Complejidad de implementación eficiente (Parallel And) 
["x for x in R if test(x) if x in S]"
Ilustra diferentes órdenes de evaluación para una consulta relacional, mostrando cómo la secuencia de filtros y la fuente de iteración afectan el rendimiento y la terminación.
for x,y in R:
  for z in S_index[y]:
    yield (x,y,z)
Demuestra cómo una conjunción de términos se traduce en bucles anidados en un modelo de evaluación de izquierda a derecha, con optimizaciones para variables 'grounded' mediante búsquedas en índices.

Fundamentos Teóricos

El problema de la no terminación y el orden de evaluación tiene raíces profundas en la teoría de lenguajes de programación y la lógica. La semántica de la no terminación tradicionalmente se aborda mediante la teoría de dominios (domain theory), un campo desarrollado por Dana Scott y Christopher Strachey en la década de 1970 para dar una base matemática a la semántica denotacional de lenguajes con recursión y efectos. La idea de 'parallel or' (y por extensión 'parallel and') se atribuye a Gordon Plotkin, particularmente en su trabajo sobre LCF (Logic for Computable Functions) en 1977, donde se discute la falla de la abstracción completa en presencia de no terminación y la necesidad de operadores que no sean estrictos en sus argumentos.

La tensión entre la optimización declarativa y la predictibilidad del comportamiento se refleja en la investigación sobre optimizadores de consultas de bases de datos, que buscan planes de ejecución óptimos sin alterar la semántica declarativa del SQL o Datalog. La ineficiencia de los planes de join binarios para consultas cíclicas, mencionada en el artículo, es un problema conocido en la optimización de consultas relacionales, que a menudo requiere algoritmos de 'worst-case optimal joins' para lograr un rendimiento aceptable. La conexión con la programación lógica, como miniKanren y Prolog (específicamente Andorra Prolog), también es relevante, ya que estos lenguajes a menudo emplean estrategias de búsqueda que se asemejan a la evaluación concurrente de conjunciones y disyunciones.