Это сокращение является техникой конструктивного доказательства того, что подмножество (называемое безопасным) корреляционного исчисления кортежей (TRC) менее выразительно, чем реляционная алгебра (RA). С другой стороны, Safe-TRC и RA обладают одинаковой выразительной силой. См., Например, теорему 5.3.10 . Синтаксическое ограничение «безопасность» обеспечивает независимое от домена свойство исчисления и является необходимым.
В R-СУБД SQL можно рассматривать как конкретный (декларативный) язык для TRC. Аналог RA - это процедурный план (последовательность операций), в котором компилируется выражение SQL. Таким образом, преобразование на самом деле является формальным описанием процесса компиляции. Обратите внимание, что SQL вводит такие расширения, как DISTINCT, ORDER BY, GROUP BY, которые явно выходят за рамки теории TRC и RA.
Я не знаю точной теоретической сложности конверсии, но, очевидно, она должна быть «дешевой». Фотон Колайтис утверждает, что он линейный.
Я не знаю о реализации концепции этого алгоритма для проверки концепции.