Shredding higher-order nested queries
James Cheney, Sam Lindley, Philip L. Wadler · 2012
Reconciling high-level functional programming abstractions with the capabilities of databases is a major challenge. We present a modular account of shredding, the simulation of a single nested relational query by a number of flat relational queries. Our key insight is that shredding can be greatly simplified by first rewriting the input query into a canonical normal form. Normalisation allows us to define shredding translations on types and terms independently of one another. An added benefit of normalisation is that we get higher-order terms for free, provided that the result type is a plain nested relation type (without higher order components). In order to generate SQL we consider several alternatives for generating indexes, focusing on a lightweight use of SQL OLAP features. We prove correctness of our translations, focusing on the central shredding step: shredding a nested query, running the shredded queries, and stitching the results back together yields the same results as running the nested query directly.