Rethinking Fixpoint Computation

SQL:1999 introduced WITH RECURSIVE—or recursive common table expressions (CTEs)—a true game changer which turned SQL into a Turing-complete programming language. WITH RECURSIVE is powerful and versatile, but proved to be notoriously hard to grasp and master.

In this line of work, we derive new CTE variants from the simple loop-based operational semantics of SQL:1999’s WITH RECURSIVE. In the absence of fixpoint-based semantics and monotonicity restrictions, these CTE variants enable a SQL authoring style that mimics imperative algorithms. This fresh look at CTEs has a beneficial impact on the readability and performance of iterative SQL queries.

Publications