  Query optimizers built on the transformation-based Volcano/Cascades framework
are used in many database systems. Transformations proposed earlier on the
logical query dag (LQDAG) data structure, which is key in such a framework,
focus only on recursion-free queries. In this paper, we propose the recursive
logical query dag (RLQDAG) which extends the LQDAG with the ability to capture
and transform recursive queries, leveraging recent developments in recursive
relational algebra. Specifically, this extension includes: (i) the ability of
capturing and transforming sets of recursive relational terms thanks to (ii)
annotated equivalence nodes used for guiding transformations that are more
complex in the presence of recursion; and (iii) RLQDAG rewrite rules that
transform sets of subterms in a grouped manner, instead of transforming
individual terms in a sequential manner; and that (iv) incrementally update the
necessary annotations. Core concepts of the RLQDAG are formalized using a
syntax and formal semantics with a particular focus on subterm sharing and
recursion. The result is a clean generalization of the LQDAG
transformation-based approach, enabling more efficient explorations of plan
spaces for recursive queries. An implementation of the proposed approach shows
significant performance gains compared to the state-of-the-art.
