Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler
Joshua S. Auerbach, Martin J. Hirzel, Louis Mandel, Avraham Shinnar, Jérǒme Simèon · 2017
Algebras based on combinators, i.e., variable-free, have been proposed as a better representation for query compilation and optimization. A key benefit of combinators is that they avoid the need to handle variable shadowing or accidental capture during rewrites. This simplifies both the optimizer specification and its correctness analysis, but the environment from the source language has to be reified as records, which can lead to more complex query plans.