Comprehending queries over finite maps

Recent programming languages research has developed language-integrated query, a convenient technique to seamlessly embed a domain-specific database query language into a general-purpose host programming language; such queries are then automatically converted to the language understood by the target DBMS (e.g. SQL) while at the same time taking advantage of the host language’s type-checker to prevent failure at run-time. The embedded query language is often equipped with a rewrite system which normalizes queries to a form that can be directly translated to the DBMS query language. However, the theoretical foundations of such rewrite systems have not been explored to their full extent, particularly when constructs like grouping and aggregation, which are ubiquitous in real-world database queries, are involved. In this work, we propose an extension of the nested relational calculus with grouping and aggregation which can provide such foundations. Along with strong normalization and translatability to SQL we show that, remarkably, this extension can also blend with shredding techniques proposed in the literature to allow queries with a nested relational type to be executed on the DBMS.