Esta reducción es la técnica de prueba constructiva para mostrar que un subconjunto (llamado seguro) Tuple Relational Calculus (TRC) es menos expresivo que Relational Algebra (RA). También es cierto que Safe-TRC y RA tienen un poder expresivo equivalente. Ver Teorema 5.3.10 por ejemplo. La restricción sintáctica de "seguridad" garantiza la propiedad independiente del dominio del cálculo y es necesaria.
En R-DBMS, SQL puede verse como el lenguaje concreto (declarativo) para TRC. La contraparte RA es el plan de procedimiento (una secuencia de operaciones) en el que se compila una expresión SQL. Entonces, la conversión es en realidad la descripción formal del proceso de compilación. Tenga en cuenta que SQL introduce extensiones como DISTINCT, ORDER BY, GROUP BY que están claramente fuera del alcance de la teoría TRC y RA.
No conozco la complejidad teórica precisa de la conversión, pero claramente tiene que ser "barata". Kolaitis de fotones dice que es lineal.
No conozco una implementación de prueba de concepto de este algoritmo.