Author's version.
To appear in the Proceedings of FLOPS 2020 (International
Symposium on Functional and Logic Programming) as a
volume in Springer LNCS series.
Language-Integrated Query with Nested Data
Structures and Grouping
Rui Okura and Yukiyoshi Kameyama
University of Tsukuba, Japan
rui@logic.cs.tsukuba.ac.jp, kameyama@acm.org

Abstract. Language-integrated query adds to database query the power of highlevel programming languages such as abstraction, compositionality, and nested
data structures. Cheney et al. designed a two-level typed language for it andshowed that any closed term of suitable type can be normalized to a single SQL
query which does not have nested data structures nor nested SELECT clauses.
This paper extends their language to cover the GROUP BY clause in SQL to express grouping and aggregate functions. Although the GROUP BY clause is frequently used, it is not covered by existing studies on efficient implementation of
language-integrated queries. In fact, it seems impossible to express compositionof two aggregate functions by a single aggregate functions, therefore, there exists
a query with nested GROUP BY clauses which has no equivalent query without nested one. However, since several SQL such as PostgreSQL allows nested
queries, we can still ask if it is possible to convert an arbitrary query with grouping and aggregation to a single query in SQL which allows nested queries, butdisallows nested data structures such as a table of tables.
This paper solves the latter question affirmatively. Our key observation is that the
GROUP BY clause in SQL does two different kinds of things, manipulating input/output data and grouping with aggregation, the former can be transformed,
but may have complex types, while the latter cannot be transformed, but has
simple types. Hence, we decouple the GROUP BY clause and introduce primitives into our language-integrated query to obtain a calculus which can express
GROUP BY. We then show our language has the normalization property thatevery query is converted to a single query which does not have nested data structures. We conduct simple benchmarks which show that queries in our language
can be transformed to efficient SQL queries.
Keywords: database · language-integrated query · grouping · aggregation · normalization · type safety

1

Introduction

Language-integrated query is gaining an increasingly bigger attention by integrating a
database query language such as SQL with a high-level programming language. Microsoft’s LINQ is a typical example, used by various applications. Existing languages

for language-integrated query allow one to interact with a database management system, construct abstraction mechanisms and complex data structures, and compute overthem.
A classic problem in language-integrated queries is the query-avalanche problem;composing two queries and executing the result of the composition may sometimes needa huge number of transactions with a database. Another classic problem is that nested
data structures such as a list of lists are allowed in language-integrated queries, while
they are not allowed in SQL, hence they are not directly implementable. Cooper [1]proposed normalization on queries to solve these problems. He showed that a closed
query of non-nested type 1 can be always transformed (’normalized’) to a form which
does not use abstractions, nested data structures, or nested comprehensions, hence canbe translated to SQL. Moreover, the result of normalization is a single SQL query,solving the query avalanche problem. Cheney et al. [2] formalized his idea in a twolevel typed language with quotation and anti-quotation to give theoretical foundation for
it, and Suzuki et al. [3] implemented it via tagless-final encoding as an extensible typesafe framework. However, none of the studies mentioned above targeted the features ofgrouping and aggregate functions, which are indispensable in many realistic queries.
This paper addresses the problem of introducing grouping and aggregate functions
into language-integrated queries while keeping efficient implementation. Grouping (theGROUP BY clause in SQL) classifies data records based on the given keys, and computes aggregated values for each group of records. Aggregation is a reduction operation,
which computes a single value from a list of values in the same group.
An example in SQL is given as follows:
SELECT p.orderId AS oid, SUM(p.quantity) AS sales
FROM products AS p
GROUP BY p.orderId

This query gets data records from the products table, classifies them into groups
based on the orderId key, and returns, for each group, a record which consists of anorderId and the summation of the quantity. SUM is called an aggregate function, which
computes the sum of all records for each group, and the GROUP BY clause specifies
the key for this grouping. Following Cheney et al., we write for(xL) M for thefollowing SQL query:
SELECT M
FROM L AS x

and we introduce a new construct gfor(xing:

L; K) M for the SQL query with group-

SELECT M
FROM L AS x
GROUP BY K
1

We say that a table type (a bag type of a record type) is not nested, if each component type ofthe record is a basic type such as string, integer, or floating-point number. All other table types
are nested in our terminology.

While the GROUP BY clause (and the gfor clause) is simple to handle in SQL, it
is problematic as a construct in language-integrated query, which will be explained asfollows.
First, there seems no normalization rules for the combination of gfor and anothercontrol structure such as for or gfor itself. A normalization rule is a rule to transforma query to a normal form which directly corresponds to an SQL query, and Cheney etal. showed that for follows a number of normalization rules such as for(xfor(yL) M ) Nfor(yL) for(xM ) N which are sufficient to flatten nested control
structures 2 . On the other hand, gfor does not seem to have such normalization rules
which work in general. For instance, gfor(xfor(yL) M ; K) N cannot be
normalized to a natural candidate for(yL) (gfor(xM ; K) N ), which is semantically different. There are other combinations of constructors such as gfor-gfor which
also suffer from the same problem. Informally it is explained by an example: suppose
we are given a table for GPAs for all students in a university, which has several schools
and each school has departments. and we want to determine, for each school, the department whose students’ average GPA is the best among the departments in the school.
Clearly, we need to compute average per department, and then take the maximum value
per school, each of which corresponds to grouping and aggregate functions AVG andMAX. Therefore, we need to have nested gfor constructs to obtain the correct result.
It follows that our target language for SQL need to have subqueries, which means
an input (or an output) of a query is the result of another query. Several SQL dialects
including PostgreSQL indeed allow subqueries, hence we also assume that our SQL
backend allows (an arbitrary nesting of) subqueries.
Although allowing subqueries in SQL solves the problem of nested control structures, we still have a problem of nested data structures. To see this, let Q1 be gfor(xL; K) M where M has a nested data structure such that each component type ofthe record is a bag of a basic type. Let Q2 be a query for(yQ1 ) N whose type
is not nested.We expect that Q2 is normalized to a query which is translated to asingle SQL, in particular, the resulting query has no nested data structures. Unfortunately, normalization does not work for this query, since it contains gfor which isa barrier for any normalization to occur. One may think that the for construct in Q1(at the outermost position of (Q2 ) can be moved inward, and we can rewrite Q2 into
gfor(xL; K) for(yM ) N , which can be further transformed. However, thisrewriting has another problem; if N has an aggregate function which operates on grouping outside of Q2 , the aggregate function goes under this gfor, rather than grouping outside of Q2 , leading to an incorrect result. Namely, this rewriting may not be semanticspreserving.
In summary, having gfor in language-integrated query causes a big problem andmost desirable properties which Cheney et al. proved for the language without gfor will
be lost. Hence, it has been an open problem to have grouping and aggregate functions inlanguage-integrated query, while keeping the desirable properties such as normalization
to non-nested data structures.
2

Queries where a for construct exists inside another for construct are called queries with nested
control structures.

This paper solves the problem above at least partially. We start by observing that thegfor construct in language-integrated queries (or the GROUP BY clause in SQL) does
too many things; it performs not only grouping, but also aggregation and constructionof (possibly complicated) output. In the context of this study, these three processes havequite different nature, and should be treated separately.
– Grouping and Aggregation; examples are taking an average score among a department, and getting the maximum average score among a school. These operations,
if combined with other control structures, cannot be transformed, while their input and output types are restricted to basic types. (Note that aggregate functions areprovided in the target SQL, and they work on a collection of basic values and returna reduced value of the same type as input.)– Output Construction; an example is constructing a nested list whose element is a
student-score pair whose score is above the average in her department. This operation may have complicated types (arbitrarily nested types), however, they arestandard operations made from for, UNION ALL , WHERE and so on, hence, they
can be transformed by Cheney et al.’s normalization rules.
Since GROUP BY is a combination of the two, we cannot normalize it, nor its data
type may be nested, and we got stuck. A lesson learned from here is that we should
decouple the two, then we can normalize output construction to normal form, whilegrouping/aggregation have non-nested types, hence there are no obstacles to obtain aresult which has no nested data structures. This is a rather simple idea but as far as weknow, there is no similar research in this direction, and the present paper is a straightforward realization of this simple idea.
We design our source language based on Cooper’s work and Cheney et al.’s work,and add the functionality of grouping and aggregate functions by a new construct instead of the gfor construct. The new construct captures only the first process of theabove two, namely, grouping and aggregation, and the second process is represented by
the existing constructs provided by Cheney et al. We argue that most functionality of
GROUP BY in SQL can be recovered by combining the new constructs and existingones by some sort of rewriting. We introduce a type system and prove several interesting properties. We then give a set of transformation rules which transform all thetypable queries of an appropriate type 3 to a single SQL query, thus avoiding the Query
Avalanche problem completely.
The rest of this paper is organized as follows. Section 2 informally discusses how
to resolve nested clauses with grouping. Section 3 introduces our languages and transformation rules, and Section 4 introduces adding grouping to the language. And theperformance measurements for our language and implementation is explained in Section 5. Finally, we state concluding remarks in Section 6.
3

An SQL-convertible query must produce a collection of records whose fields are of base types.
Hence, we restrict our query to have this class of types.

2

Example of Grouping and Aggregation

In this section, we consider several examples for language-integrated query, and informally discuss our new primitives for aggregation and grouping. Formal development
will be presented in the next section. A database used in our example has two tables in
Fig.1

pid
110
111
210
310

products
name price
shirt
100
T-shirt
200
pants
500
suit
1000

oid
1
1
2
2
2
3

orders
pid
110
111
110
210
310
310

qty
2
3
5
10
15
20

type Ordering = {P roducts : Bag {pid : Int, name : String, price : Int},
Orders : Bag {oid : Int, pid : Int, qty : Int}}

Fig. 1. Sample database tables

The products table has (left) columns of product ID (pid), name, and price (price),while the orders table (right) has columns of order ID (oid), product ID (pid), and quantity (qty). Let us first introduce an example without grouping and aggregation as follows:
Q = for(pfor(otable(“products”))
table(“orders”))

where (p.pid = o.pid)
yield {oid = o.oid, sales = p.price ∗ o.qty}
which corresponds to the following SQL query:
SELECT o.oid AS oid, p.price * o.qty AS sales
FROM products AS p, orders AS o
WHERE p.pid = o.pid

The collection is a multiset, or a bag. The above query scans tables, and returns a bagof records consisting of two fields oid and sales, whose values are order ID and qty
multiplied by the price. In this paper, we do not consider the value NULL, and assume
all fields have some values of appropriate type.

Next, we use an aggregate function without grouping, shown below:
Q0 = yield Aα (for(pfor(otable(“products”))
table(“orders”))

where (p.pid = o.pid)
yield {sales = p.price ∗ o.qty})
Where α = {(sales, SUM, sales_sum)}which corresponds to the following SQL query:
SELECT SUM(p.price * o.qty) AS sales_sum
FROM products AS p, orders AS o
WHERE p.pid = o.pid

where SUM is an aggregate function, which computes the sum of p.price * o.qty for
all collections in the constructed table, and Aα is the new operator in our language,
standing for aggregation application.
The role of the new operator Aα is to apply aggregate functions to the components
specified in α. The component values are taken from its argument. In the above example
α = {(sales, SUM, sales_sum)} specifies that it should retrieve values from the sales
field of the argument, convert to a field named sales_sum and returns the value. The
resulting record of Aα (L) has the record type which consists of a field sales. Thus, theabove query in our language does exactly the same thing as the query in SQL.
Clearly the notation in our language is heavier than the corresponding expressionin SQL, but it is justified by the following argument. The essential difference between
the two is the position the function SUM appears at: in SQL (the lower query), SUM
appears at deep inside of the query, while in our language (the upper query), it appears
at the outermost position. Since SUM in our language appears remotely from its realargument, we need to specify which field and return field name it will pick up, and theheavier notation above is necessary. But our notation has a merit that the target table ofaggregate functions is clearer. In the above example, the target table of SUM is the argument computed by the for expression, while the target of SUM in SQL is determinedby its external context which is not always clear. In this example, there are no GROUPBY clauses in the query so the target table is the whole expression, but in general,
there may be several GROUP BY clauses around SUM, and they form a sort of binderbindee correspondence. But, since they are not really binders (no variables are used tomake the correspondence explicit) so the correspondence is fragile under rewriting, or
normalization. When designing normalization rules, we always need to consider if thebinder-bindee correspondence is kept correctly, which is quite cumbersome, and sometimes impossible (note that our language has the standard lambda binding and function
application, hence substitution for variable may occur at any time of computation).
We then add the functionality of grouping to the Aα operator. The extended operator
is denoted by G(κ,α) where α is the specification for aggregate functions as in Aα . The
extra parameter κ is a list of field names and considered as grouping keys on whichgrouping takes place. To show an example, we perform grouping with the example

above.
Q1 = G(oid,α) (for(pfor(otable(“products”))
table(“orders”))

where (p.pid = o.pid)
yield {oid = o.oid, sales = p.price ∗ o.qty})
Where α = {(sales, SUM, sales_sum)}which corresponds to the following SQL query:
SELECT o.oid AS oid, SUM(p.price * o.qty) AS sales_sum
FROM products AS p, orders AS o
WHERE p.pid = o.pid
GROUP BY o.oid

In the lower query, we have added the order ID field to the record created dynamically, which will be the grouping key as specified by the GROUP BY clause on the lastline. In the upper query, we also do the same thing, and in addition to it, the grouping
operator specifies not only α, but also order ID as the grouping key. When we executethe upper query, it groups the table create by the for clause based on the order ID field,
computes the sum of qty multiplied by price for each group, and then returns a record
consisting of the order ID field, and the summation.
The merit and demerit of expressing grouping and aggregate functions in terms of
the G(κ,α) operator inherit those for the Aα operator. In addition, one query in SQL
may have more than one GROUP BY clauses, and then the correspondence between
the GROUP BY clause and aggregate functions are even more complicated, and will
be error prone. On the contrary, our notation has its scope (its argument) as the target
table of grouping and aggregate functions, hence we seldom make any ’scope’-related
issues. Note that G(κ,α) is a natural extension of Aα , but for technical reason, G(·,α)(no grouping keys) is equivalent to yield Aα , which returns a singleton consisting ofAα . Modulo this small twist, the former extends the latter, and Aα exists only for the
purpose of explanation.
In SQL, we can group, aggregate values, and construct complicated data from them
all in one query. As we discussed in the previous section, it is problematic to do all three
things in a single primitive, therefore, our language does not have such a super operator.
Instead, our operator G(κ,α) can do grouping and aggregation only. The resulting valueof applying this operator to an expression is a bag of records consisting of the results ofaggregate functions, whose types are not nested. Any operation after applying aggregate
functions are disallowed by this primitive. For instance, the following query has nodirect counterpart in our language:
SELECT o.oid AS oid,
SUM(p.price * o.qty)/SUM(o.qty) AS average
FROM products AS p, orders AS o
WHERE p.pid = o.pid
GROUP BY o.oid

where we divide one aggregated value by another. It is still no problem to precompute values before aggregation such as SUM(p.price * o.qty).
We can recover the lost expressiveness by simple rewriting. A query which is equivalent to the above one may be written in our language as follows:
Q2 = for(qG(oid,α) (for(pfor(otable(“products”))
table(“orders”))

where (p.pid = o.pid)
yield {oid = o.oid, sales = p.price ∗ o.qty,
qty = o.qty}))yield {oid = q.oid, average = q.sales_sum/q.qty_sum}
Where α = {(sales, SUM, sales_sum), (qty, SUM, qty_sum)}Thus we divide one big process performed by the GROUP BY clause into a combination of triple nested control structures for-G(κ,α) -for. It is arguable that this decomposition (or ’decoupling’) is beneficial for performance, but we believe that, as long as
the nested data structures are concerned, our decomposition is the only way to normalize all queries systematically into a single SQL query which has subqueries but does
not have nested data structures.
The above query in our language corresponds to the following query in SQL:
SELECT q.oid AS oid, q.sales_sum / q.qty_sum AS average
FROM (SELECT o.oid AS oid,
SUM(p.price * o.qty) AS sales_sum,
SUM(o.qty) AS qty_sum
FROM products AS p, orders AS o
WHERE p.pid = o.pid
GROUP BY o.oid) AS q

which uses a subquery and performs badly if we compare it with the above single query.
In this paper, we do not talk about optimization of queries, but a very clever query
optimization engine for SQL will hopefully optimize the last one to the previous one.

3

The Language with Aggregate Functions

This section explains the base language for language-integrated query in the existingstudies, and introduces our language with aggregate functions. Grouping will be added
to the language in the next section.
3.1

Base Language

The base language Quel is essentially the same as Cooper’s source language [1] without
effects (which is ’nearly the same’ as Nested Relational Calculus [4]), and Cheney etal.’s T-LINQ [2] without quotation and code generation. Fig. 2 gives the syntax of types
and terms in Quel where t denotes a name of database tables, and l denotes a field nameof a record.

Base types
O ::= Int | Bool | String
Types
A, B ::= O | A −! B | Bag A | {l : A}
TypeenvironmentΓ ::= φ | Γ, x : A
Terms
L, M, N ::= λx. M | M N | ⊕ (M ) | M ] N | x | c| for(xM ) N | where L M | yield M | [ ]| exists M | table(t) | {l = M } | L.l

Fig. 2. Types and Terms of Quel

Types are either a basic type (integers, booleans, and strings), a function type A !
−B, a bag type Bag A, or a record type {l : A} where l : A is abbreviation of a sequence
l1 : A1 , · · · , lk : Ak for some k ≥ 0. The bag type is the type for multisets in which
the order of elements is irrelevant and the number of elements matters. A record type{l : O} where O is a basic type is called a flat type. The bag type of a flat record typeis also called a flat type. Flat types are important in the study of language-integrated
query, since SQL allows only values of flat types as input and output tables.
Terms are either lambda terms augmented with a primitive operator ⊕, a variable x,
a constant c, {l = M } (record), L.l (selection), or constructed by database primitives
such as M ] N (multiset union), for(xM ) N (bag comprehension) where L M(conditional), yield M (singleton), exists M (emptiness test), and table(t) (databasetable with name t). The term for(xM ) N corresponds to the SELECT statement in
SQL, which computes N for each element in (the value of) M , and returns their multiset
union. The term where L M returns the value of M if L returns true, and returns theempty bag [] otherwise. The term yield M creates a singleton multiset consisting of thevalue of M . The term exists M is emptiness test for a multiset M and returns a boolean
value. The variable x in λx. M and for(xL) M are bound in M . As usual, we
identify two terms which are α-equivalent.
3.2

The Language Quela

We add aggregate functions to Quel, and call the extended language Quela. Fig. 3 defines new syntax in Quela where a sequence of dots means the corresponding syntax inQuel.

Terms L, M, N ::= ... | Aα (L)A-Specα ::= {(l, }, l0 )}Fig. 3. Types and Terms of Quela

The term Aα (L) applies aggregate functions to L as specified by α. Here, α is a
finite collection of pairs of a field name and an aggregate function } such as MAX,

MIN, AVG, COUNT, and SUM.4 An example of α is {(l1 , MAX, l10 ), (l2 , SUM, l20 )},which means that we apply MAX to the values of the l1 field and SUM to the values ofthe l2 field, and returns a record consisting of these data with new field names l10 and
l20 . For simplicity, we assume that all field names in α are mutually distinct, but thisrestriction can be easily removed.
Quela has the standard call-by-value, left-to-right semantics. Let us explain how theterm Aα (L) is evaluated where α = {(l1 , }1 , l10 ), · · · , (lk , }k , lk0 )}. L is an expressionof record type whose fields are l1 , · · · , lk . For each i ≤ k, we apply the aggregate
function }i to the li -component of L to get an aggregated value which we call vi . Then
we return a record {l10 = v1 , · · · , lk0 = vk } as the result. For instance, suppose L isa bag with two elements [{l1 = 10, l2 = 20}, {l1 = 30, l2 = 10}]. Then the term
A{(l1 ,SUM,l10 ),(l2 ,MAX,l20 )} (L) is evaluated to {l10 = 40, l20 = 20}.
Quela is a statically typed language, and Fig. 4 lists a few interesting typing rules.

FOR

EXISTSΓ ` M : Bag A Γ, x : A ` N : Bag B
Γ ` for(xM ) N : Bag B

Γ ` M : Bag {li : Oi }Γ ` exists M : Bool

AGGREGATIONΓ ` L : Bag {li : Oi } α = {(li , }i , li0 )} }i : Bag Oi −! OiΓ ` Aα (L) : {li0 : Oi }Fig. 4. Type System of Quela

The first typing rule represents the one for the for-construct, or bag comprehension.
The term for(xM ) N computes a bag N for each element x in M , and takes
the multi-set-union for all the results. Hence, M and N must have bag types, and x
is bound in N . The second one is for the exists -construct. Here we need to constrain
that the argument M must have a flat bag type (Notice that the type of each field is abasic type Oi ). Otherwise, we cannot normalize such a term to an SQL query where
nested data structures are not allowed. The third typing rule is for aggregate application
Aα (L). The A-Spec α specifies which aggregate function should be used for each fieldof the given record. The aggregate function }i for the field li must have a function typeBag Oi !
− Oi , which must match the type of each field in L where Oi is a basic type.
Note that the field names in α and those in the type of L must match, which meansthat we cannot throw away any fields by aggregation (no projection is allowed). This isagain for the sake of guaranteeing the non-nested property of normal forms in Quela.
This restriction does not affect the expressiveness of Quela, since we can always insert
an explicit ’projections’ as a normal term.
Other typing rules are standard in simply typed lambada calculus, and omitted here.
4

In this study the set of aggregate functions is left unspecified, but we assume that they must
operate on simple types. See the type system.

3.3

Normalization of Quela

Cooper has shown that any query of an appropriate type in his language can be normalized to a simple form which directly corresponds to a single SQL query, thus solving so
called query avalanche problem.
We have the same property for Quela. More precisely, given a closed term in Quelawhich has a flat bag type (a bag-of-record type whose fields are of basic types) can betransformed to normal form, which is directly convertible to an SQL query. In the restof this section, we explain how we can show this property. Note that we assume thatthe target SQL to allow subqueries (or nested queries), so nested control structures are
not problematic. However, the normal form must not create or manipulate nested data
structures (such as a record of records, or a table of tables), our goal is to eliminate thelatter.
Fig. 11 in the appendix shows normalization rules essentially proposed by Cheney
et al., after slight adjustment for Quela. For the newly added primitive Aα (L) we do
not have normalization rules5 as explained in earlier section. (It is a ’barrier’ for normalization.) Hence, we need to add the term Aα (L) to the normal form of appropriate
type. Fig.5 defines the normal form for Quela.

Queries
U ::= U1 ] U2 | [ ] | F
Comprehension F ::= for(xH) F | H | Z
Table
H ::= table(t)Body
Z ::= where B Z | yield R
RecordR ::= {l = B} | x | Aα (U )Primitives
B ::= exists U | ⊕(B) | x.l | c
A − Spec

α ::= {(l, }, l0 )}Fig. 5. Normal form of Quela

Note that even if Aα (U ) is normal form (if U is), we only have to add it to R above.
For this term, U must be of a flat bag type, and so is the whole term, hence no nested
data structures are used in this term, which is the key of our proof of the non-nested
property.
U in Fig.5 is a query expression of top-level and must be a bag with a flat type,that is U of Aα (U ) must be a bag type of flat record, and if U is not normal form, it isrewritten by normalization rules. This means that, although the return type is different,
the existing syntax exists has the same properties as Aα (U ).
We will formally state the desirable properties on ’non-nestedness’ of the result of
our translation. Here, we take the minimalist approach, and we define flat types, insteadof defining nested data types and non-nested data types in general. We call a record typewhose components are basic types as flat record types. A flat bag type is the type Bag F
5When L is an empty bag, we can transform the whole expression, but it is a special case which
does not contribute general patterns.

where F is a flat record type. We sometimes say flat types for basic types, flat record
types, or flat bag types. Flat types clearly do not contain nested structures, and provide
data structures for our target SQL.
Theorem 1. 1. Normalization rules for Quela preserve typing, namely, Γ ` L : A andL
M , then Γ ` M : A.
2. For any typable term, normalization weakly terminates, namely, If Γ ` L : A,
then there is a normal form N such that L
N.
3. Suppose N is normal form, and ` N : F is derivable where F is a flat type. Then
its type derivation contains only flat types.
The item 3 is crucial in our work, as it implies that all closed normal form of flat
type does not use any nested data structures as intermediate data, which is necessary for
it to be translated to a SQL query.
Let us briefly mention the proof of the theorem.
Item 1 can be proved by straightforward induction.
Item 2 is proved by making an analogy; Quela’s aggregation is a ’barrier’ for normalization since it has no transformation (normalization) rules. In Cheney et al.’s work,
the exists primitive is the same, as it has no transformation rules other than the rarecases when its argument happens to be a value. Hence, as far as we are concerned withweak normalization property, we can treat our aggregation primitive just like the exists
primitive, and the proof of Cheney et al.’s weak normalization theorem can be re-usedwithout essential modification.
Item 3 is proved by induction on type derivation for a slightly stronger lemma: if
Γ ` N : Bag {li : Oi } is derivable for some Γ = x1 : F1 , · · · , xn : Fn where Fi
are flat types, and N is normal form, then the typing derivation does not non-flat types.
For this inductive proof, it is essential to have that our aggregation operator works overterms of flat types only. The rest of the proof is easy and omitted.
Note that, for this property to hold, we need to restrict the argument of exists primitive must have flat types; otherwise the item 3 does not hold in general.
The normal form is actually easy to translate to an SQL query. Fig.6 gives the translation for only one important case.

[[yield Aα (U )]] = SELECT }(e) AS l0
FROM t AS y WHERE B
where [[U ]] = SELECT e AS l FROM t AS y WHERE B
and α = {(l, }, l0 )}Fig. 6. Translation to SQL

For a normal form N , we write [[N ]] for its translation to SQL. For Aα (U ), we
first convert U to an SQL query, and then apply aggregate functions }i for each ei
designated by the field li . We finally collect all fields and return the answer.

3.4

Comparison with Classic Results

The statement of Theorem 1 in the previous subsection resembles the ’conservativity’
property studied in classical database theory. Among all, Libkin and Wong [5] formulated a simple calculus with aggregation, and proved that, for any query whose type hasheight n, there exists an equivalent query which has height n or lower. Here the heightis the degree of nested data structures, and by taking n as 0, we have a statement which
is very similar to the item 3 of Theorem 1.
However, there are several differences between Libkin and Wong’s work and ours,
and their result does not subsume ours (and vice versa).
The first difference is that the primitive data structure in their language is sets,
whereas ours is bags (multi-sets). This different is minor, as we can adjust their theory to the one based on multi-sets.
The second, more essential difference is that they have more normalization rules
than we have; one of their rules (in our syntax) is:A(l,SUM,l0 ) (L1 ∪ L2 ) = A(l,SUM,l0 ) (L1 ) + A(l,SUM,l0 ) (L2 )They regard this equation as a left-to-right rewrite rule. This rewriting often makes aquery rather inefficient; it replaces an aggregation to normal addition, and if L1 ∪ L2 inthe above equation is replaced by a union of 100 bags, then the right-hand side will besum of 100 elements, which is clearly slower to execute than a aggregate function.
The third difference is that their language does not have grouping, whereas ours
has, as we will see in the next section. Adding grouping to the language would makethe above efficiency problem even more serious; there is no simple way to expressgrouping and aggregation for L1 ∪ L2 in terms of those for L1 and those for L2 .
One may wonder why we successfully get the same (or very similar) theorem while
our set of normalization rules is strictly smaller than theirs. The trick is that, our primitives for aggregation (and grouping) are finer than those primitives in existing studies.6
The aggregation primitive in Libkin and Wong’s study is:Σ{{e1 | x ∈ e2 }}where e1 and e2 are expressions for queries and x is bound in e1 . The above primitive
sums up the result of e1 [ai /x] for all ai ∈ e2 . As the syntax reveals, their primitive
can manipulate input by the expression e1 , which our primitive (l, SUM, l0 ) cannot. In
our language, constructing e1 from x ∈ e2 should be expressed by another expression(it can written as for(xe2 ) [e1 ] if we ignore labels and the difference of set andmulti-set), and we can recover their aggregation primitive by combining these two. The
bonus of this decomposition is Theorem 1.
In summary, while we obtained nothing new in theory (a very similar theorem isalready known in old days, which can be adjusted to our setting), we claim that wehave made solid progress towards a practical theory as advocated by Cheney et al.,since much more efficient queries can be generated by our method. In the subsequent
sections we will back up our claim by adding groping and showing performance.
6

In the introduction of the present paper, we already explained it against SQL’s GROUP BY.

4Adding Grouping to the Language

The language Quela in the previous section does not have grouping, and this section
extends it to the language Quelg, which has grouping.
One might think that this extension is a big step, however, surprising, the differenceis quite small, since grouping with aggregation behaves quite similar to aggregation.
It cannot be normalized but it works on terms of flat types, so it does not affect theimportant property that the normal form does not have nested data structures.
We briefly explain in this section the extended language and its properties.
The extended syntax is defined in Fig. 7. We introduce a new operator G(κ,α) (L) forgrouping and aggregation, where κ is a list of field names, and represents the keys ofthis grouping, and α is the same as α in Aα (L).

Terms L, M, N ::= ... | G(κ,α) (L)

Fig. 7. Syntax of Quelg

Intuitively, G(κ,α) (L) gets an input table from (the result of computing) L, performs grouping based on the keys in κ, and then apply aggregate functions listed in κ.
The result of this computation is a table whose element is a record consisting of thekeys and the fields with the results of aggregate functions. As a simple example, theterm G(oid,{(qty,MAX,qty_max)}) (table(“orders”)) evaluates to [{oid = 1, qty_sum =3}, {oid = 2, qty_sum = 15}, {oid = 3, qty_sum = 20}].
Typing rules for Quelg are those for Quela plus the rule shown in Fig. 8.

GROUPING

Γ ` L : Bag {κi : Oi , li : Oi0 } κ = {li } α = {(li , }i , li0 )} }i : Bag Oi0 −! Oi0Γ ` G(κ,α) (L) : Bag {κi : Oi , li0 : Oi0 }Fig. 8. Type System of Quelg

The new typing rule is for grouping. To type G(κ,α) (L), we need to have L is aflat bag type Bag {κi : Oi , li : Oi0 }. The keys for grouping κ must appear in this list,
and here we assume that κi appears in the first half of this sequence. The aggregate
functions specified in α must be of function type from a bag of a basic type to the basic
type. Finally, G(κ,α) (L) has the same type as L.
For the language Quelg, the normal form becomes a bit more complicated than thosefor Quela, because the new primitive for grouping returns a value of bag type, and it isstill normal, hence each syntactic category of bag type must have the new primitive as
normal form. Fig. 9 defines the normal form for Quelg.

U ::= U1 ] U2 | [ ] | G(κ,α) (U ) | F

QueriesComprehension F ::= for(xH) F | G(κ,α) (U ) | Z

H ::= table(t) | G(κ,α) (U )Body

Z ::= where B Z | yield R | G(κ,α) (U )RecordPrimitives

R ::= {l = B} | x
B ::= exists U | ⊕(B) | x.l | c
α ::= {(l, }, l0 )}κ ::= lFig. 9. Normal form of Quelg

Finally, we define the translation from a normal form in Quelg to an SQL query.
Fig. 10 defines the most interesting case.

[[G(κ,α) (U )]] = SELECT }(x.l) AS l0
FROM [[U ]] AS x
GROUP BY x.κ
and α = {(l, }, l0 )}Fig. 10. Translation from Quelg to SQL

In the case of Quela, we analyzed the translation for U and added aggregate functions to them and we get a simple query (we do not have nested SELECT -statements).
On the other hand, in Quelg, U in G(κ,α) may be translated to an SQL query with grouping, in which case we cannot translate the whole term to a non-nested SQL. Hence, wetranslate it to nested queries. In the right hand side of the definition in Fig. 10, [[U ]] appears inside the FROM clause, which is a subquery. Note, however, that we can translate
all normal form in Quelg to a single SQL query, thanks to the property that no nested
data structures are used.

5

Implementation and Examples of Normalization

We have implemented normalization in Quelg, and translation to SQL. For this purpose, we embedded Quelg in the programming language OCaml using the tagless-final
embedding following Suzuki et al.[3], and use PostgreSQL as the backend databaseserver. The computing environment is Mac OS 10.13.2 with Intel Core i5-7360 CPU
with memory 8GB RAM, and our programs run on OCaml 4.07.1, and generated SQL
queries on PostgreSQL 11.5. The results of performance measurements will be shown
after we explain example queries.

We prepare several concrete queries in Quelg which use aggregate functions andgrouping in different ways. The database used here has two tables, the products table
and the orders table in Section 2.
The first query Q03 accesses the orders table, and produces a bag of all orders whose
oid matches the given value. The next query Q003 accesses the products table, and gets
the Orders record from Q03 , finds all the products which has the same oid value as its
input record o, and returns a bag of records with the oid and sales fields.
Q003 = λo.

Q03 = λoid.
for(otable(“orders”))

where (o.oid = oid)for(ptable(“products”))

where (p.pid = o.pid)
yield {oid = o.oid,

yield osales = p.price ∗ o.qty}
We want to compose these kinds of small queries to obtain a large, complicatedquery. It is easy to achieve in our language, since we can define a generic combinatorfor composition compose: for composition as follows:
compose = λq. λr. λx. for(yq x) r y

Then we only have to apply it to Q03 and Q003 in this order to obtain a composed query.
Here we also perform grouping and aggregation on the results, and we define a newquery Q3 as follows:
Q3 = λx. G(oid,α) (compose Q03 Q003 x)= λx. G(oid,α) (for(yQ03 x) Q003 y)where α = {(sales, SUM, sales_sum)}... (1)

We normalize Q3 N (for a concrete value N) to obtain the following normal form:
Q3 = G(oid,α) (for(ofor(ptable(“orders”))
table(“products”))

where (p.pid = o.pid ∧ o.oid > N)
yield {oid = o.oid, sales = p.price ∗ o.qty})
Where α = {(sales, SUM, sales_sum)}which is immediately translated to SQL as:
SELECT o.oid AS oid, SUM(p.price * o.qty) AS sales_sum
FROM products AS p, orders AS o
WHERE p.pid = o.pid AND o.oid > N
GROUP BY o.oid... (2)

One can see how nested control structures are resolved to result in a flat-structured
program.

After implementing our system, we have conducted performance measurement. We
measured the execution time of program transformation and SQL generation in our
implementation, and the execution time of generated SQL. We tested varying data sizefor the orders and products tables, ranging up to 10,000 records per table.
Table 1 shows the total execution time of the program transformations and SQL
generation (from (1) to (2) in the above query). In addition to Q1 to Q3 in the previous
chapters, we tested several more programs; Q4 with lambda abstraction, Q5 with apredicate, Q6 to Q8 with nested control structures, and Q9 with a nested data structure.
All queries of our system used in the experiment is available online at http://logic.cs.
tsukuba.ac.jp/~rui/quelg/. In Table.1, we measured the time to iterate the transformation
until the given term is in normal form, and we tested several cases where we allow
only minimum required normalization rules, or all normalization rules. In Table.2, we
measured the execution time of SQL.

Example
Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9

main rules

all rules

Example

0.028
0.046
0.11
0.058
0.019
0.031
0.052
0.24
0.32

0.029
0.101
1.15
0.074
0.19
0.43
0.043
5.59
9.31

Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9

All times in milliseconds.
Table 1. Time for Normalization and SQL generation

time
16.19
14.07
4.36
0.95
7.41
14.14
11.25
18.04
3732.62| products | = 10000, | orders | = 10000
Table 2. Execution time for SQL

Table 1 confirms that such programs that require normalization takes longer times
to generate SQL than those do not. However, compared to the time required to execute
a query against a database, the time for optimizations and SQL generation is negligible,
even if all normalization rules are used.
Table 2 shows the performance of subqueries (nested queries). For instance, Q7
is a query which uses only one table, but has almost the same execution time as Q1 ,which has two tables and has fewer subqueries than Q7 . It re-confirms the standard
knowledge that executing subqueries in SQL takes a long time. The query Q9 , whichcalculates the average value in a subquery, takes about 3 seconds, and the execution
time for subqueries is quite dependent on queries.
Although analyzing the execution time for different kinds of queries is beyond thiswork, we claim that our initial aim has been achieved, since all the queries used inthis experiment have been converted to single SQL queries, which run on a common

database engine (PostgreSQL). It is an interesting future work to investigate how one
can further optimize the generated SQL queries.

6

Conclusion

In this paper, we have given a tiny core language for language-integrated queries which
has grouping and aggregate functions, while retaining the pleasant properties: any closed
term of flat type (a bag-of-record type whose component types are basic types) can benormalized to a normal form, which corresponds to a single query in SQL where subqueries are allowed.
The key idea of this study is to decouple a complex job of SQL’s GROUP BY
clause into two pieces: One is grouping and aggregation which cannot be normalized
but have simple types. The other is output construction which can be normalized but
have complex types. By this decoupling, we have succeeded in getting the properties
achieved in the earlier work for the language without grouping and aggregation. Ourlanguage is not as expressive as the language with the full GROUP BY clause, but by
simply rewriting queries using such clauses, our language can host most such queries.
To our knowledge, this work is the first success case of (subset of) language-integrated
query which has the above pleasant property.
We have implemented our language by embedding our language Quelg in a hostlanguage OCaml. We have shown a concrete example and the result of simplistic performance test.
There are many directions for future work, among which the most important ones
are performance evaluation against larger examples, optimization of generated SQL,
and thorough comparison with other frameworks. Extending our language to coverother complicated database primitives is also an interesting next step.
Acknowledgements. We would like to thank Oleg Kiselyov and Kenichi Suzuki
for development of Quel and its tagless-final implementation. The second author is
supported in part by JSPS Grant-in-Aid for Scientific Research (B) No. 18H03218.

References
1. Ezra Cooper. The script-writer’s dream: How to write great SQL in your own language, andbe sure it will succeed. In Database Programming Languages - DBPL 2009, 12th International Symposium, Lyon, France, August 24, 2009. Proceedings, pp. 36–51, 2009.
2. James Cheney, Sam Lindley, and Philip Wadler. A practical theory of language-integrated
query. In ACM SIGPLAN International Conference on Functional Programming, ICFP’13,
Boston, MA, USA - September 25 - 27, 2013, pp. 403–416, 2013.
3. Kenichi Suzuki, Oleg Kiselyov, and Yukiyoshi Kameyama. Finally, safely-extensible andefficient language-integrated query. In Proceedings of the 2016 ACM SIGPLAN Workshop
on Partial Evaluation and Program Manipulation, PEPM 2016, St. Petersburg, FL, USA,
January 20 - 22, 2016, pp. 37–48, 2016.
4. Limsoon Wong. Normal forms and conservative extension properties for query languages
over collection types. J. Comput. Syst. Sci., Vol. 52, No. 3, pp. 495–505, 1996.

5. Leonid Libkin and Limsoon Wong. Aggregate functions, conservative extensions, and linear
orders. In Catriel Beeri, Atsushi Ohori, and Dennis E. Shasha, editors, Database Programming Languages (DBPL-4), Proceedings of the Fourth International Workshop on Database
Programming Languages - Object Models and Languages, Manhattan, New York City, USA,
30 August - 1 September 1993, Workshops in Computing, pp. 282–294. Springer, 1993.
6. Simon L. Peyton Jones and Philip Wadler. Comprehensive comprehensions. In Proceedingsof the ACM SIGPLAN Workshop on Haskell, Haskell 2007, Freiburg, Germany, September
30, 2007, pp. 61–72, 2007.
7. Oleg Kiselyov and Tatsuya Katsushima. Sound and efficient language-integrated query maintaining the ORDER. In Programming Languages and Systems - 15th Asian Symposium,
APLAS 2017, Suzhou, China, November 27-29, 2017, Proceedings, pp. 364–383, 2017.
8. Jacques Carette, Oleg Kiselyov, and Chung-chieh Shan. Finally tagless, partially evaluated:
Tagless staged interpreters for simpler typed languages. Vol. 19, pp. 509–543, 2009.
9. Microsoft corporation. the linq project: .net language integrated query. September 2005.
10. Torsten Grust, Jan Rittinger, and Tom Schreiber. Avalanche-safe LINQ compilation. PVLDB,
Vol. 3, No. 1, pp. 162–172, 2010.
11. Val Tannen, Peter Buneman, and Limsoon Wong. Naturally embedded query languages. In
Database Theory - ICDT’92, 4th International Conference, Berlin, Germany, October 14-16,
1992, Proceedings, pp. 140–154, 1992.
12. James Cheney, Sam Lindley, and Philip Wadler. Query shredding: efficient relational evaluation of queries over nested multisets. In International Conference on Management of Data,
SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, pp. 1027–1038, 2014.
13. Erik Meijer, Brian Beckman, and Gavin M. Bierman. LINQ: reconciling object, relations andXML in the .net framework. In Proceedings of the ACM SIGMOD International Conference
on Management of Data, Chicago, Illinois, USA, June 27-29, 2006, p. 706, 2006.
14. Atsushi Ohori, Peter Buneman, and Val Tannen. Database programming in machiavelli - apolymorphic language with static type inference. In Proceedings of the 1989 ACM SIGMODInternational Conference on Management of Data, Portland, Oregon, USA, May 31 - June2, 1989., pp. 46–57, 1989.

A

Normalization Rules of Quel

Normalization rules of Quel are given as follows:(Stage 1)(λx.N ) M
N [x := M ](ABS−β){l = M }.li
Mi
(RECORD−β)for(xyield M ) N
N [x := M ](FORYIELD)
for(x
for(y
L) M ) Nfor(yL) for(xM ) N (if y ∈/ F V (N ))(FORFOR)for(xwhere L M ) N
where L for(xM) N(FORWHERE1 )
for(x
[]) N
[]
(FOREMPTY1 )for(xM1 ] M2 ) N
for(xM1 ) N ] for(xM2 ) N(FORUNIONALL1 )where true M
M(WHERETRUE)
where false M[](WHEREFALSE)(Stage 2)for(xM ) (N1 ] N2 ) ,!
for(xM ) N1 ] for(xM ) N2for(xM ) [] ,! []where L M ] N ,!
(where L M ) ] (where L N )where L where M N ,! where L ∧ M N
where L for(xM ) N ,!
for(xM ) where L N
Fig. 11. Normalization rules of Quela(FORUNIONALL2 )(FOREMPTY2 )(WHEREUNION)(WHEREWHERE)(WHEREFOR)