Submitted to Haskell Symposium 2016

Haskell Relational Record
A Pragmatic Embedded System for Type-Safe and Composable SQL Queries
Kei Hibino

Shohei Murayama

Kazuhiko Yamamoto

Asahi Net, Inc.
k.hibino@asahinet.com
shohei.murayama@asahinet.com

IIJ Innovation Institute Inc.
kazu@iij.ad.jp

Abstract

statement strings correctly, and they are not reusable. One approachto making SQL statements reusable is the integration of query functionality into programming languages. LINQ (Meijer et al. 2006) isa prominent example, and a more seamless integration is found in
SML# (Ohori and Ueno 2011).
Another notable approach, which does not require modificationof programming languages, is the use of an embedded domainspecific language (EDSL). HaskellDB (Leijen and Meijer 1999;
Bringert and Höckersten 2004) is such an EDSL in Haskell (Marlow et al. 2010), with excellent features. Since HaskellDB queries
are composable, large queries can be built from well-tested, small
queries. HaskellDB queries that compile generate syntacticallycorrect SQL statements.
In 2012, Asahi Net, Inc. attempted to use HaskellDB for its
business. Asahi Net is a Japanese Internet service provider with
about 587,000 residential customers, as of March 2016. Its businessmodel is to minimize labor expenses by automating operations,while keeping a small share of the market. For this purpose, Asahi
Net has maintained hand-written SQL statements in Java, Perl,and other programming languages. In the Java and Haskell code,
2,622 unique SQL statements are used, of which 1,770 are SELECT
statements. Note that the count does not include queries in untyped
languages, where it is difficult to make an accurate count.
Unfortunately, use of HaskellDB in practical database operations discloses its drawbacks. It is insufficient for real-world
business because it does not support some necessary operations,such as outer joins and correlative subqueries. Note that 5.0% and1.8% of the SELECT statements are outer joins and correlative subqueries, respectively, at Asahi Net. Moreover, if aggregate queries
are reused, they do not keep the structure of the corresponding tables, as described in Section 6.1. Query result types are limited toflat, heterogeneous lists, which cannot correspond to nested Haskell
records.
We developed a pragmatic EDSL for SQL, called Haskell
Relational Record (HRR), from scratch, to help programmers
write complicated, real-world SQL statements correctly. Like
HaskellDB, HRR provides composability to enable reuse of codefragments at various levels. For example, queries in HRR can becomposed using joins, as well as combined using set operations
such as union, intersection, and difference. To resolve HaskellDB
issues, we designed HRR to support a large part of the SQL standard, including outer joins and correlated subqueries.
HRR provides separate query monads for non-aggregate and aggregate queries. This ensures that aggregate query table structures
are maintained even if the queries are reused. Query results canbe of any Haskell record type, and query expressions are typed
with Haskell records so that they can be reused. To support this,we developed primitive operators which preserve correspondence
between nested Haskell record types and flat SQL structures.

Hand-written SQL statement strings are error-prone because SQL
syntax is not checked in host programming languages. One solution
to this problem is to use an embedded domain-specific language(EDSL) in a strongly-typed programming language, which generates syntactically-correct SQL statements when the code passes
type checking. HaskellDB, recognized as the first implementation of such an EDSL, enables building large queries from small,well-tested queries. Unfortunately, HaskellDB is insufficient for
real-world business because it does not support some necessary operations, such as outer joins. Moreover, aggregated queries do notkeep the structure of the corresponding tables and nested Haskell
record types are not allowed as query result types. To solve these
problems, we implemented Haskell Relational Record (HRR), a
pragmatic EDSL in Haskell that supports a large part of the SQL
standard, including outer joins and correlated subqueries. HRR
provides query composability yet handles both non-aggregate andaggregate queries correctly. HRR query results can be of any
Haskell record type. SQL expressions in queries are typed with
nested Haskell records. We show algorithms for primitive operators of record manipulation which preserve correspondence between nested Haskell records and flat SQL structures. HRR’s arrow interface provides type-safety—generated SQL statements do
not contain syntax errors, type errors, or reference errors. This also
holds when using the monad interface, aside from cases where correlated subqueries are joined. More than three years of productionuse demonstrates stability and usability of HRR.
Categories and Subject Descriptors H.2.3 [DATABASE MANAGEMENT]: Languages—Embedded System
Keywords SQL, Relational Database, Type-Safety, Composable
Query, Outer Join, Aggregation, Nested Record.

1.

Introduction

SQL (ISO 2011) is the standard query language for relational
database systems. Programs often use SQL statements to manipulate data in database systems, but hand-written SQL statement
strings are error-prone because SQL syntax is not checked in hostprogramming languages. It is difficult to write complicated SQL[Copyright notice will appear here once ’preprint’ option is removed.]

Haskell Relational Record

1

2016/8/2

If HRR code passes type checking by a Haskell compiler, running the corresponding executable generates syntactically-correct
SQL statements. The algorithm to generate SQL statements isstraightforward—no optimization is carried out. For instance, anested query is translated into a nested SQL query. When the HRR
arrow (Hughes 1998) interface is used, generated SQL statements
are valid, where “valid” means that they do not have type errors orreference errors, but they may include errors relating to null. Whenusing the monad interface, this does not hold in cases where correlated subqueries are joined—generated SQL statements containreference errors. In practice, this is not a serious problem because
database systems can always detect the errors.
When HRR queries are compiled by a Haskell compiler, theschema of target tables are obtained and necessary definitions forthe queries are automatically generated. The compiler checks thatthe queries are consistent with the generated definitions. In our
experience, this schema capture mechanism breaks down psychological barriers that make schema changes daunting. Currently,
HRR supports DB2, PostgreSQL, SQLite, MySQL, Microsoft SQL
Server, and OracleSQL. To support such a wide variety of databasesystems, HRR generates standard SQL statements only, avoiding
use of database-system-specific features. We hope that this eases
database system migration.
HRR has been in use at Asahi Net since March 2013, and morethan three years of production use demonstrates its stability andusability. We have also released HRR as open-source software.1
This paper describes HRR, primarily focusing on its type-safety
and composability which help programmers to write complicated
SQL statements correctly. The contributions of this paper are as
follows:

CREATE TABLE Employee (id
INTEGERNOT NULL, nameVARCHAR(32) NOT NULL
, dept_id INTEGERNOT NULL);

To use this table from Haskell, it is necessary to map Haskell
records to those in a database system. Haskell records representing tables can be defined manually, but hand-written definitions
are error-prone and cannot capture table schema changes. HRR
can auto-generate them using Template Haskell (Sheard and Peyton Jones 2002): when HRR code is compiled, table schemas are
obtained from a database system and Haskell records are defined
automatically. To ease the introduction of HRR into products, mappings can be customized.
If we use SQLite, and file company.db contains all of the tables
used in this paper, we should prepare the following Employee.hs
for the Employee table:{-# LANGUAGE TemplateHaskell #-}{-# LANGUAGE MultiParamTypeClasses #-}{-# LANGUAGE FlexibleInstances #-}module Employee whereimport Database.Record.TH.SQLite3$(defineTable "company.db" "employee")

The following data type is automatically defined at compile time:
data Employee = Employee {id:: !Int, name:: !String, deptId :: !Int} deriving (Show)• We provide a pragmatic EDSL for SQL which provides com-posability. HRR is type-safe when the arrow interface is used,
where “type-safe” means that generated SQL statements aresyntactically-correct and valid (i.e. with no type or reference
errors, but possibly with null errors). This also holds when using the monad interface, except in cases where correlated subqueries are joined.

2.1.1 SELECT Statement Relations
To work with auto-generated Haskell records, we need additional
components to represent SELECT statements. In HRR, such components are called relations. For the example above, the following
relation, which selects employees from the Employee table, is also
automatically created:• We show that type separation of non-aggregate and aggregate

employee :: Relation () Employeequeries brings type-safety, and converting these types into asingle query type enables query composability.

Relation is a type for relations, with two phantom parameters(Leijen and Meijer 1999). The first is the placeholder type (seeAppendix A). The second indicates the result type. Here, employee
represents a SELECT statement, with no placeholder parameters,that returns Employee values. We can print the SELECT statement
generated by the employee relation:• We show that SQL expressions in queries are typed with nested

Haskell records and provide algorithms for primitive operators of record manipulation which preserve correspondence between nested Haskell records and flat SQL structures.
This paper is organized as follows. Section 2 describes HRR by
example, and composability is discussed in Section 3. Section 4 explains how HRR code is translated into SQL statements. Section 5
discuss SQL expressions with Haskell record types. Related work
is covered in Section 6, and our conclusion is in Section 7.

2.

GHCi> print employee
SELECT id, name, dept_id FROM employee

A Relation value can be converted to an SQL string and sent to a
database system using the following function:

Basic Concepts by Example
runRelation :: (IConnection conn
,ToSql SqlValue p,FromSql SqlValue a) =>conn -> Relation p a -> p -> IO [a]This section explains the basic concepts of HRR by example.2 This
paper focuses on SELECT statements (i.e. SQL queries), which wehave found are the most challenging. Throughout this paper, themonad interface of HRR is used for simplicity.

2 To simplify explanation, this paper uses wrapper modules and definitions

Currently, HRR uses HDBC3 as a database abstraction layer.
IConnection is a typeclass, defined in HDBC, that represents
connections to database systems. SqlValue is a type of SQL value
in HDBC. The third parameter, p, holds any placeholder values.
The following example demonstrates running employee with
SQLite:exported from the relational-record-examples package, available in
Hackage.

3 http://hackage.haskell.org/package/HDBC

2.1

A Simple Query

We use the following table of employees throughout this paper:
1 http://khibino.github.io/haskell-relational-record/

Haskell Relational Record

2

2016/8/2

GHCi> :load Employee
GHCi> import Database.Relational.Query.SQLite3
GHCi> conn <- connectSqlite3 "company.db"
GHCi> runRelation conn employee ()[Employee {id = 1, name = "Smith", deptId = 100}
,Employee {id = 20, name = "Parker", deptId = 101}]

2.2

relation :: QuerySimple (Projection Flat r)-> Relation () r

Using this pattern, a relation is converted to a query monad andthen converted back to a Relation for composability, as explainedin Section 3.

A Query with Filtering

2.2.2

Relations can be built using other relations. For instance, the following is a relation that selects employees from the Employee table
whose identifier is less than n:

SQL statements consist of SQL expressions. In HRR, SQL expression components are called projections. Note that the term “projection” in this paper is different from SQL terminology, where it isused to indicate how to extract columns. The concept of projection
is precisely explained in Section 5.
Projection is a data type for projections, with two phantom
parameters. The first indicates the context of SQL expressions,taking one of the following values:

import qualified Employee as E
import Database.Relational.Query
earlyEmp :: Int -> Relation () E.Employee
earlyEmp n = relation $ doe <- query E.employee
wheres $ e ! E.id’ .<. value nreturn e• Flat — the base context• Aggregated — the return value of GROUP BY or aggregate

functions

Each component in this example is described later, and Appendix B
shows the auto generated code for Employee.hs. Note that n is justa parameter of the Haskell function, not a placeholder parameter.
Let’s choose 10 for n. In this case, earlyEmp is converted to thefollowing SQL statement:• Exists — arguments for EXISTS.
• OverWindow — arguments for OVER

The second parameter indicates the Haskell record type of the SQL
query result.

GHCi> print $ earlyEmp 10
SELECT ALL T0.id AS f0, T0.name AS f1, T0.dept_id AS f2
FROM employee T0
WHERE (T0.id < 10)

2.2.3

GHCi> runRelation conn (earlyEmp 10) ()[Employee {id = 1, name = "Smith", deptId = 100}]

wheres:: Projection Flat (Maybe Bool)-> QuerySimple ()(.<.):: Projection c a -> Projection c a-> Projection c (Maybe Bool)e:: Projection Flat Employee(! E.id’) :: Projection Flat Employee-> Projection Flat Int
value:: a -> Projection Flat a

Later, we will look at this filtering example in more detail anduse it to highlight some important concepts of HRR.
Query Monads

SELECT statements are roughly categorized into non-aggregate
and aggregate queries. HRR provides two separate monads, called
query monads, to build them. This type separation is one of the keys
to type-safety. In this paper, we use two kinds of query monads:

wheres implements the WHERE clause. It stores a query conditionin the query monad, which is QuerySimple in this example. id’ isan auto-generated accessor to id of the Employee Haskell record,in the projection level. (!) is a function that applies an accessor toa Haskell record. value creates an SQL constant expression froma Haskell constant value. (.<.) is the less-than operator in the
projection level. (.<.) returns Maybe Bool, which wheres takes
because SQL boolean is nullable. The signatures of HRR functions
used in this paper are shown in Figure 3 and Figure 6.

• QuerySimple — a query monad for non-aggregate queries,

which stores information on joining, table/column naming, filtering, ordering, etc.
• QueryAggregate — a query monad for aggregate queries,

which, in addition to the information stored by QuerySimple,
stores information on GROUP BY and HAVING, as well as ordering restrictions

2.3

As seen in earlyEmp, relations can be reused with the following
pattern:

Inner Join

In HRR, inner joins are expressed using a pair of query actions.
To give an example of an inner join, we now introduce a table fordepartments:

relation $ doe <- query <RELATION>...
return e

CREATE TABLE Department (dept_id
INTEGERNOT NULL, dept_name VARCHAR(32) NOT NULL);

The query function converts a relation to an action in the querymonad, which is specialized to QuerySimple in the above example:

The following HRR code selects pairs of employee names and theirdepartment names:

query :: MonadQuery m =>Relation () r -> m (Projection Flat r)

innerJoin :: Relation () (String, String)
innerJoin = relation $ doe <- query E.employeed <- query D.department
on $ e ! E.deptId’ .=. d ! D.deptId’
return $ e ! E.name’ >< d ! D.deptName’

QuerySimple and QueryAggregate are instances of MonadQuery.
The relation function restricts the type of the query monad toQuerySimple:

Haskell Relational Record

Filtering Expressions

Line “wheres $ e ! E.id’ .<. value n” of the example in
Section 2.2 implements the filter to select employees whose identifier is less than n. The expressions have the following types:

Running (earlyEmp 10) results in:

2.2.1

Projections for SQL Expressions

3

2016/8/2

on implements the ON clause. (><) is an operator that produces apair while (.=.) is the equal operator in the projection level. This
HRR code is converted into the following SQL statement:

aggregateRelation ::QueryAggregate (Projection Aggregated r)-> Relation () r

If the query monad is QueryAggregate, the first parameter ofProjection must be Aggregated. Type consistency is guaranteed
because aggregateRelation requires this combination. Note that
relation, described in Section 2.2.1, requires the combination ofQuerySimple and Flat.
The following is an example of an aggregate query that returns
the number of employees for each department:

SELECT ALL T0.name AS f0, T1.dept_name AS f1
FROM employee T0 INNER JOIN department T1
ON (T0.dept_id = T1.dept_id)

Running this code results in:
GHCi> runRelation conn innerJoin ()[("Smith","Personnel"),("Parker","Admin")]

2.4

Outer Join

countMembers :: Relation () (String, Int)countMembers = aggregateRelation $ doe <- query E.employeed <- query D.department
on $ e ! E.deptId’ .=. d ! D.deptId’
gDeptName <- groupBy $ d ! D.deptName’return $ gDeptName >< count (e ! E.id’)

To handle outer joins, HRR provides the queryMaybe operator,
which uses a Maybe result type to express nullability:
queryMaybe :: MonadQuery m => Relation () r-> m (Projection Flat (Maybe r))

The combinations of query and queryMaybe express the following four joins:count implements the COUNT aggregate function of SQL. groupBy
implements the GROUP BY clause. It takes a grouping element andreturns an aggregate-typed key that can be used in the result.

• query then query — inner joins• query then queryMaybe — left outer joinsgroupBy :: Projection Flat r-> QueryAggregate (Projection Aggregated r)• queryMaybe then query — right outer joins• queryMaybe then queryMaybe — full outer joinscountMembers is converted to the following SQL statement, whichuses GROUP BY:

Here is an example of a left outer join that selects departments andearly employees in the department, if they exist:

SELECT ALL T1.dept_name AS f0, COUNT(T0.id) AS f1
FROM employee T0 INNER JOIN department T1
ON (T0.dept_id = T1.dept_id)
GROUP BY T1.dept_nameouterJoin :: Relation () (String,Maybe String)outerJoin = relation $ dod <- query departmente <- queryMaybe employee
on $ e ?! E.deptId’ .=. just (d ! D.deptId’)on $ e ?! E.id’ .<. just (value 10)
return $ d ! D.deptName’ >< e ?! E.name’3.

This section discusses relation composability. As described in Section 2.2.1 and Section 2.5, the QuerySimple and QueryAggregate
query monads can be converted to relations. Relations are composable regardless of the inner query monads used.
As described later, relations using the arrow interface are always type-safe but those using the monad interface are not. If correlated subqueries are joined in the monad interface, invalid SQL
statements are generated. Even though the monad interface does
not provide perfect type-safety, HRR users tend to use it becauseof its simplicity. Fortunately, incorrect correlated subqueries can bealways detected as reference errors when executing the corresponding relations.

(?!) is the Maybe version of (!), and just is a function that
injects a value into Maybe, in the projection level. The signaturesof these functions are shown in Figure 6. This HRR relation isconverted into the following SQL statement:
SELECT ALL T0.dept_name AS f0, T1.name AS f1
FROM department T0 LEFT JOIN employee T1
ON (T1.dept_id = T0.dept_id) AND (T1.id < 10)

Running the outerJoin relation results in:
GHCi> runRelation conn outerJoin ()[("Personnel",Just "Smith"),("Admin",Nothing)]

2.5

3.1

Combining

To show combining relations with set operations, consider the following new table for past members:

An Aggregate QueryA SELECT statement with a GROUP BY clause may only selectgrouping elements and expressions using an aggregate function.
Violating this restriction is a common mistake in hand-written
SQL. Consider the following (incorrect) example:

CREATE TABLE PastMembers (year
INTEGERNOT NULL, dept_name VARCHAR(32) NOT NULL
, headcount INTEGERNOT NULL);SELECT name, dept_id, COUNT(id) -- incorrect
FROM employee
GROUP BY dept_id

The PastMembers table contains the number of employees per
department, in or before 2015. The following code extracts thisinformation:

Here, name is neither a grouping element nor an expression using
an aggregate function. Some database systems return ill-chosen
values for this kind of incorrect SELECT statement, and the mistake
may go unnoticed. This section explains how such errors can beprevented using query monads.
As explained in Section 2.2.1, QueryAggregate is used for
aggregate queries. It can be converted into a relation using thefollowing function:

Haskell Relational Record

Relation Composability

import qualified PastMembers as P
pastMembers’ :: Relation () (Int,(String,Int))
pastMembers’ = relation $ dop <- query P.pastMembers
return $ p ! P.year’ ><(p ! P.deptName’ >< p ! P.headcount’)4

2016/8/2

The following code counts the current number of employees per
department:

wheres $ e ! E.id’ .<. value n
wheres $ e ! E.deptId’ .=. d ! D.deptId’
return $ e ! E.id’

countMembers2016 :: Relation () (Int,(String,Int))countMembers2016 = aggregateRelation $ doe <- query E.employeed <- query D.department
on $ e ! E.deptId’ .=. d ! D.deptId’
gDeptName <- groupBy $ d ! D.deptName’return $ value 2016 ><(gDeptName >< count (e ! E.id’))

Here is an example relation using this correlated subquery in the
WHERE clause:
correlative :: Relation () Stringcorrelative = relation $ dod <- query department
exist <- queryList $ depEarlyEmp 10 dwheres $ exists exist
return $ d ! D.deptName’

The inner query monads of pastMembers’ and countMembers2016
are QuerySimple and QueryAggregate, respectively. They canbe composed with unionAll:

This relation selects names of departments that have at least one
early employee. queryList converts a relation to a subquery
whose return value type is a set of projections. exists implements
the EXISTS clause. They have the following signatures:

memberHistory :: Relation () (Int,(String,Int))
memberHistory =countMembers2016 ‘unionAll‘ pastMembers’

queryList :: Relation () r-> QuerySimple (ListProjection(Projection Exists) r)
exists :: ListProjection (Projection Exists) r-> p (Maybe Bool)

This code is converted to the following SQL statement:
SELECT ALL 2016 AS f0, T1.dept_name AS f1,
COUNT(T0.id) AS f2
FROM employee T0 INNER JOIN department T1
ON (T0.dept_id = T1.dept_id)
GROUP BY T1.dept_name
UNION ALL
SELECT ALL T2.year AS f0, T2.dept_name AS f1,
T2.headcount AS f2
FROM pastmembers T2

3.2

correlative is converted into the following (valid) SQL statement:
SELECT T0.dept_name AS f0
FROM department T0
WHERE (EXISTS (SELECT T1.id AS f0 FROM employee T1
WHERE (T1.id < 10)
AND (T1.dept_id = T0.dept_id)))

Joining

To show nested relations, we reuse countMembers, defined in
Section 2.5. Here is an example of nesting relations where thequery monad of countMembers2016’ is QuerySimple while thatof countMembers is QueryAggregate:

Since the correlated subquery is used in the WHERE clause, it canrefer to the table labeled with T0 in the FROM clause.
3.4

countMembers2016’ :: Relation () (Int,(String,Int))countMembers2016’ = relation $ dom <- query countMembers
return $ value 2016 >< m

Unfortunately, HRR does not provide perfect type-safety for correlated subqueries if the monad interface is used. Consider the following correlated subquery, which returns a department name for agiven employee:This code is converted into the following SQL:
SELECT ALL 2016 AS f0, T2.f0 AS f1, T2.f1 AS f2
FROM (SELECT ALL T1.dept_name AS f0,
COUNT(T0.id) AS f1
FROM employee T0
INNER JOIN department T1
ON (T0.dept_id = T1.dept_id)
GROUP BY T1.dept_name) T2

empDep :: Projection Flat Employee-> Relation () Department
empDep e = relation $ dod <- query department
wheres $ e ! E.deptId’ .=. d ! D.deptId’
return d

The following code uses this correlated subquery for joining:

Other systems, such as QUEΛ (Suzuki et al. 2016), convert a nested
query to a flat query. As seen in this example, however, HRR
translates relations to SQL queries in a straightforward manner—anested query is left as a nested query. Refer to Section 4 for details.
3.3

wrongJoin :: Relation () (String,String)
wrongJoin = relation $ doe <- query employeed <- query $ empDep e
return $ e ! E.name’ >< d ! D.deptName’

Correlation

SQL provides correlated subqueries, which use values from outerqueries. The specification allows correlated subqueries to be specified in the WHERE clause, the HAVING clause, etc., but not in the
FROM clause. In other words, correlated subqueries must not bejoined. In HRR, a correlated subquery can be expressed with afunction whose arguments are projections and return value is a relation. The following is an example of a correlated subquery that
returns identifiers for early employees in a given department:

wrongJoin is converted into the following (invalid) SQL statement:
SELECT ALL T0.name AS f0, T2.f1 AS f1
FROM employee T0
INNER JOIN (SELECT ALL T1.dept_id AS f0,
T1.dept_name AS f1
FROM department T1
WHERE (T0.dept_id = T1.dept_id)) T2
ON (0=0)

depEarlyEmp :: Int -> Projection Flat D.Department-> Relation () Int
depEarlyEmp n d = relation $ doe <- query E.employee

Haskell Relational Record

Invalid Correlation

The inner SELECT refers to the invisible outer table T0. Running
this code results in the following reference error:

5

2016/8/2

GHCi> runRelation conn wrongJoin ()*** Exception:
SqlError{ seState = "", seNativeError = 1, seErrorMsg = "... : no such column: T0.dept_id"}[<where condition>][<order by>]| Aggre <result columns><join subqueries tree>[<where condition>][<group by>][<having condition>][<order by>]This error happens because monadic scope is different from thatof SELECT statements. A monad implementation therefore does notprovide type-safety for correlated subqueries.
3.5

Table holds an auto-generated primitive relation, and Union stores
two relations concatenated with unionAll. Simpl and Aggre keep
information stored in QuerySimple and QueryAggregate, respectively. This is why relation and aggregateRelation canconvert QuerySimple and QueryAggregate to Relation, respectively.
When a Relation value is used in an aggregate or nonaggregate query monad, the inner structure of the Relation value
is not necessary; only the parameters are required. This Relation
value is stored in <join subqueries tree> when the outer
query is converted to another Relation value.
The following toSQL function summarizes the algorithm used
to convert a SubQuery value to a SELECT statement:

Arrow Interface

Opaleye developers suggested that this restriction can be implemented using arrows. Here is an arrow version of empDep:
empDepA :: Projection Flat Employee-> Relation () Department
empDepA e = relation $ proc () -> dod <- query department -< ()wheres -< e ! E.deptId’ .=. d ! D.deptId’
returnA -< d

The following is an arrow version of wrongJoin:

toSQL :: SubQuery -> String
toSQL (Table tbl) = tableToSQL tbl
toSQL (Union l r) =paren (toSQL l)++ "UNION ALL"++ paren (toSQL r)
toSQL (Flat rc jst wc ob) ="SELECT"++ intercalateComma rc++ expandJoinProduct jst -- calls toSQL++ expandWhere wc-- calls toSQL++ expandOrderBy ob
toSQL (Aggregated rc jst wc gb hc ob) ="SELECT"++ intercalateComma rc++ expandJoinProduct jst -- calls toSQL++ expandWhere wc-- calls toSQL++ expandGroupBy gb++ expandHaving hc-- calls toSQL++ expandOrderBy obwrongJoinA :: Relation () (String,String)
wrongJoinA = relation $ proc () -> doe <- query employee -< ()d <- query $ empDepA e -< ()return -< e ! E.name’ >< d ! D.deptName’

Only unit is allowed as input to query arrows. Since the argument eof empDepA is out of scope in arrow notation, the Haskell compiler
can detect it: “Not in scope: ‘e’”.

4.

Converting Relations to SQL QueriesThis section describes the internal structures of HRR and how
relations are translated into SELECT statements.
4.1

Monad Transformers for Query Monads

HRR’s query monads are implemented with monad transformers(Liang et al. 1995). In addition to a base state monad that is used
for labeling, HRR uses the following monad transformers:• writer transformer for HAVING, to accumulate restrictions

SubQuery data structures represent SELECT statements in a straightforward manner, so toSQL can simply concatenate stored information. Functions that we have not described, such as expandWhere,
also concatenate stored information with proper spacing. Note that
expandJoinProduct traverses <join subqueries tree> andcalls toSQL for each subquery.

• writer transformer for ORDER BY, to accumulate ordering keys

4.3

QuerySimple utilizes the base, FROM, WHERE, and ORDER BY transformers, while QueryAggregate utilizes the base and all of theabove transformers. As described previously, query, queryMaybe,
etc. can be used in both non-aggregate and aggregate query monads
thanks to the overloading technique described in (Jones 1995).

Since column names are unique within a table but are not globallyunique, they are prone to conflict. Self join is a basic example.
Consider the following Person table:• state transformer for FROM, to build the join tree
• writer transformer for WHERE, to accumulate restrictions• writer transformer for GROUP BY, to accumulate grouping terms

4.2

CREATE TABLE Person (id
INTEGERNOT NULL, nameVARCHAR(32) NOT NULL
, mother_id INTEGERNOT NULL);

Translation Algorithm

Relation is defined using SubQuery and two phantom type parameters:

A naive SQL statement to obtain a list of mother-child pairs would
be:

newtype Relation p r = Relation SubQuery

SELECT name, name -- incorrect
FROM person INNER JOIN person
ON (mother_id = id)

Simplified, SubQuery is defined as follows:data SubQuery = Table <auto generated table>| Union SubQuery SubQuery| Simpl <result columns><join subqueries tree>

Haskell Relational Record

Avoiding Column Name Conflicts

One cannot tell which table each name belongs to. Tables should
therefore be properly labeled, and column names should be used6

2016/8/2

HRR provides such operators of record manipulation. Thissection describes how to implement primitive operators to compose and decompose Haskell records which correspond to flat
SQL structures. In HRR, projections, (!) with accessors, andthe applicative-like style described below correspond to Haskell
records, field accessors, and the applicative style, respectively.

with proper qualifications. HRR avoids column name conflicts bygiving global unique names to tables and giving table-unique names
to columns. The concrete algorithm is as follows:
Base case: Assume that table names of existing tables ina database system are globally unique, and assume that allcolumn names are table-unique.

5.1

Recursive case: Give global-unique names to tables specified in FROM clauses, and give table-unique names to theresult elements.

HRR provides the applicative-like style that is similar to the applicative style. Consider the following data types:

This algorithm ensures table name uniqueness even if the SELECT
statements are nested. Column names used in SELECT statements
are specified with qualified names such as T.C. Even if C is notunique, T.C is global unique since T is global unique.
Code to obtain a list of mother-child pairs is as follows:data Member = Member {memName :: String, memDept :: String}
data Ids = Ids {idEmp :: Int, idDept :: Int}data MemberInfo = MemberInfo {miMem :: Member, miIds :: Ids}

selfJoin :: Relation () (String, String)
selfJoin = relation $ do
p1 <- query person
p2 <- query person
on $ p1 ! P.motherId’ .=. p2 ! P.id’
return $ p1 ! P.name’ >< p2 ! P.name’This is converted into the following SQL statement, with no column
conflict:

Here is an example of HRR relations composing projections in theapplicative-like style:

SELECT ALL T0.name AS f0, T1.name AS f1
FROM person T0 INNER JOIN person T1
ON (T0.mother_id = T1.id)

5.

memberInfo :: Relation () MemberInfo
memberInfo = relation $ doe <- query employeed <- query department
on $ e ! E.deptId’ .=. d ! D.deptId’
let mem = Member |$| e ! E.name’ |*| d ! D.deptName’
ids = Ids |$| e ! E.id’ |*| d ! D.deptId’
return $ MemberInfo |$| mem |*| ids

SQL Expressions with Haskell Records

Type errors are another common mistake in hand-written SQL
statements. The following is an incorrect SQL example that compares an integer and a string:
SELECT name
FROM employee
WHERE id = ’Smith’ -- incorrect(|$|) and (|*|) correspond with (<$>) and (<*>), respectively.
See Figure 3 for their signatures. We cannot simply use the Haskell
Applicative typeclass because function types to be mapped arelimited to Haskell record data constructors only. The above code isconverted to the following SQL statement:

Type errors can be prevented by typing SQL expressions, of course.
The correct HRR code is as follows:
pair :: Relation () String
pair = relation $ doe <- query E.employee
wheres $ e ! E.name’ .=. value "Smith"return $ e ! E.name’

SELECT ALL T0.name AS f0, T1.dept_name AS f1,
T0.id AS f2, T1.dept_id AS f3
FROM employee T0 INNER JOIN department T1
ON (T0.dept_id = T1.dept_id)

5.2

As described in Section 2.2, types of SQL expressions are represented as Projection, and the Haskell type system checks typeconsistency. This HRR code is converted into the following SELECT
statement:

Composing Accessors

In addition to projections, accessors are also used in the applicativelike style. Combining accessors and the applicative-like style, we
can define type conversion functions which are not unthinkablein the SQL world. The following code automatically generates
accessors for Member, Ids, and MemberInfo:

SELECT ALL T0.name AS f1
FROM employee T0
WHERE (T0.name = ’Smith’)$(makeRecordPersistableDefault ’’Member)$(makeRecordPersistableDefault ’’Ids)$(makeRecordPersistableDefault ’’MemberInfo)

We designed HRR to allow any Haskell record types to theresult type of queries. Since queries are used in other queries as
SQL expressions, SQL expressions should be typed with Haskell
record types in HRR.
In Haskell, field accessors of records are functions. To compose records, the applicative style (McBride and Paterson 2008)
is wildly accepted. Since field accessors are instances of Reader
monad, the applicative style can be used even with field accessors.
The following is an example to swap members of a pair using field
accessors in the applicative style:

Here is an example of an accessor converting MemberInfo back to
Employee:
toEmployee :: Pi MemberInfo E.Employee
toEmployee = E.Employee |$| miIds’ <.> idEmp’|*| miMem’ <.> memName’|*| miIds’ <.> idDept’

Pi is a type for accessors. “Pi a b” indicates that type b is extracted from type a. (<.>) is a composition operator for accessors.

swap :: (a,b) -> (b,a)
swap = (,) <$> snd <*> fst

Haskell Relational Record

Composing Projections

7

2016/8/2

Int, String, Day ∈ LType(leaf types)

X ∈ HRec
A, B, C ∈ HTypep[T 0.f 0, T 0.f 1] : PEmployee(record types)
::=

5.5

Hereafter, we call HRR accessors π functions. The following notation is used to represent the π function, to extract Haskell record B
from A:(type of record data constructor)τ ∈ Type::=

PA| A . B

xs, ys ∈ EList(Haskell list of SQL expressions)ns, ms ∈ IList(Haskell list of integer indices)T ∈ RConsx ∈ Term

πns : A . B
Here, ns is a list whose elements are indices of A. The following isthe definition of the π functions with notations defined in Figure 1:(record data constructor)::=

pxs |pxs ⊕ pys |(T-pi)
Γ ` π[n0 ,..,nw−1 ] : A . B(0 ≤ ni ≤ v − 1, v is the width of type A)(0 ≤ i ≤ w − 1, w is the width of type B)(ith leaf of Haskell record B
corresponds with ni th leaf of Haskell record A)

T h$i pxs |pxs h∗i pys |πns |πns ⊕ πms |T h$i πns |πns h∗i πms |pxs idx πns
Γ ∈ TEnv::=

Definition of π Functions

Int|String|Day|X|(A, B)|
A→B•|Γ, x : τ |Γ, T : A → B

Note that indices are of depth-first order. Figure 2 illustrates T-pi:
A.

BΓ ` x : τ means the term x is typed as τ

nsunder the type environment Γ.

0

n0

0

ni

i

Figure 1. Definitions of notations for typing rules
5.3

Primitive Operators

As describe earlier, Projection is a type for projections while Pi
is that for accessors. Primitive operators to compose and decompose records in HRR are:nw−1

• (<.>) — composing

w−1

v−1

• (!) — indexing

Figure 2. The definition of π. ni is the ith element of ns, whose
value is an index of A.

• (|$|) — mapping• (|*|) — applying

Here are examples of π functions:

In the next three subsections, we give their implementations which
preserve correspondence between Haskell record types and flat
SQL structures over the record operations.
5.4

π[1,2] : (Int, (String, Day)) . (String, Day)π[0,2] : (Int, (String, Day)) . (Int, Day)π[0,2,1] : (Int, (String, Day)) . ((Int, Day), String)

Definition of Projections

Precisely speaking, projections in HRR are correspondences between SQL expressions and Haskell data types. Internally, these
Haskell data types are represented as a list of SQL expressions.
With notations defined in Figure 1, projections can be defined asfollows:

5.6

Figure 3 summaries the signature of the primitive operators. With
these signatures, the Haskell type system infers types of phantom
parameters according to the typing rules defined in Figure 4. For
instance, the signature of (<.>) represents T-compose. Figure 3
also contains this correspondence relationship.
T-P-map restricts T (functions to be mapped) to Haskell record
data constructors. Data constructors decide the number of parameters, their types and their ordering. Since Haskell records can benested, this rule is applied recursively. For a given record, this rulecreates a tree whose leaf elements are non-record (i.e. single column) types. A record build with T-P-map and T-P-ap has such atree. A list of non-record leaf elements extracted in depth-first order is associated with a list of SQL expressions. If associations
for given records are correct, association for the record build fromthose records are also correct. In other words, depth-first ordering
is preserved. In addition to T-P-map and T-P-ap, T-map and T-ap
requires the same preservation of depth-first ordering.
Figure 5 explains the algorithm to implement these primitive
operators. All operations are implemented with list-appending andp[hexp1i,hexp2i,...,hexpwi] : P A
Here, A denotes a Haskell record type, and P A indicates the projection type. p is a constructor that takes a list of SQL expressions
and builds a value whose type is P A. A is associated with the SQL
list [hexp1i, hexp2i, ..., hexpwi], where indices are based on depthfirst ordering and w is the width of A.
The following projection is for the result type of the SQL statement for memberHistory in Section 3.1:
p[2016, T 1.dept name, COU N T (T 0.id)]: P(Int, (String, Int))
Virtual expressions are also typed. For example, e in earlyEmp,
defined in Section 2.2, does not appear in the corresponding SQL
statement but has the following projection:

Haskell Relational Record

Implementation

8

2016/8/2

-- Composing (T-compose)(<.>) :: Pi a b -> Pi b c -> Pi a c-- Indexing (T-index)(!):: Projection c a -> Pi a b -> Projection c b-- Mapping (T-P-map and T-map)(|$|) :: (ProductConstructor (a -> b), ProjectableFunctor p) => (a -> b) -> p a -> p b-- Applying (T-P-ap and T-ap)(|*|) :: ProjectableApplicative p => p (a -> b) -> p a -> p b-- Pairing(><) :: ProjectableApplicative p => p a -> p b -> p (a, b)
x >< y = (,) |$| x |*| yFigure 3. The signature of the primitive operators and pairing. ProductConstructor restricts types to Haskell record data constructors
only. Projection c and Pi a are instances of both ProjectableFunctor and ProjectableApplicative.

6.

Γ ` πns : A . B πms : B . C(T-compose)Γ, πns : A . B, πms : B . C ` πns πms : A . C

Related Work

This section describes other SQL EDSLs in Haskell.
6.1

Γ ` pxs : P B πms : B . C(T-index)
Γ, pxs : P B, πms : B . C ` pxs idx πms : P C

HaskellDB

HaskellDB is recognized as the first EDSL for SQL in Haskell. In
spite of its excellent features such as composability, we found thefollowing drawbacks:Γ ` T : B → C pxs : P B(T-P-map)Γ, T : B → C, pxs : P B ` T h$i pxs : P C• no outer join support(T is a Haskell record data constructor)• limited expression ability of result types• incorrect behaviors of aggregate queriesΓ ` T : B → C πns : A . B(T-map)Γ, T : B → C, πns : A . B ` T h$i πns : A . C

To describe the last issue, consider the following query, whichuses aggregation:4(T is a Haskell record data constructor)

countMembers2 = doe <- table employeed <- table department
restrict (e ! E.dept_id .==. d ! D.dept_id)
project $ D.dept_id << d ! D.dept_id# members << count (e ! E.id)Γ ` pxs : P (B → C) pys : P B(T-P-ap)Γ, pxs : P (B → C), pys : P B ` pxs h∗i pys : P C

members is an integral column. This HaskellDB query is converted
into the intended SQL statement:Γ ` πns : A . (B → C) πms : A . B(T-ap)
Γ, πns : A . (B → C), πms : A . B ` πns h∗i πms : A . C

SELECT dept_id2 as dept_id,
COUNT(id1) as members
FROM (SELECT dept_id as dept_id2
FROM Department as T1) as T1,(SELECT id as id1,
dept_id as dept_id1
FROM Employee as T1) as T2
WHERE ((dept_id1) = (dept_id2))
GROUP BY dept_id2

Figure 4. Typing rules for phantom parameters

πns

πms ,→ π[ns!!m|m←ms] (E-compose)pxs idx πns ,→ p[xs!!n|n←ns] (E-index)

Now consider a second query that uses the first one:

T h$i pxs ,→ pxs (E-P-map)
T h$i πns ,→ πns (E-map)

do m <- countMembers2
project $ members << m ! members

pxs h∗i pys ,→ pxs++ys (E-P-ap)

This HaskellDB query is converted into the following SQL statement:

πns h∗i πms ,→ πns++ms (E-ap)

SELECT COUNT(id1) as members
FROM (SELECT dept_id as dept_id2
FROM Department as T1) as T1,(SELECT id as id1,
dept_id as dept_id1
FROM Employee as T1) as T2
WHERE ((dept_id1) = (dept_id2))

Figure 5. The algorithms of the primitive operators

list-element-picking by indices. These implementations satisfy thepreservation of depth-first ordering. Figure 7 shows execution examples of the primitive operators.
With a projection a and π functions p1 and p2 , the following
rule holds:(a idx p1 ) idx p2 = a idx (p1Haskell Relational Record

This SQL based on an aggregate query is incorrect because the
GROUP BY clause is lost. Note that inlining the first query into thesecond one has the same issue.
4 This issue was originally reported in HaskellDB issue 22 on GitHub.

p2 )

9

2016/8/2

6.2

OpaleyeE. Meijer, B. Beckman, and G. M. Bierman. LINQ: Reconciling Object,
Relations and XML in the .NET Framework. In Proceedings of the2006 ACM SIGMOD International Conference on Management of Data,
2006.

Opaleye is another EDSL for SQL in Haskell. It supports resulttypes based on Haskell records and outer joins, and it provides
composability. To provide pragmatic aggregate queries, each column must have exactly one level of aggregation or must appear in
the GROUP BY clause (but not both). Opaleye makes use of profunctors to satisfy this condition. While HRR uses monads to build
queries, Opaleye uses arrows. As of this writing, PostgreSQL is the
only database system supported.
In join products, Opaleye automatically combines sub-query
WHERE clauses into an outer WHERE clause, which prevents captureof the projection of the left sub-query in the join-product. HRR
does not do this, as it is not easy to combine WHERE clauses ofjoin-product sub-queries that involve union-like operations (UNION,
EXCEPT, and INTERSECT), which HRR supports. This is a trade-off
between Opaleye’s type-safety and HRR’s simplicity and expressiveness of SQL statements.

7.

A. Ohori and K. Ueno. Making Standard ML a Practical Database Programming Language. In Proceedings of ACM ICFP Conference, 2011.
T. Sheard and S. Peyton Jones. Template Metaprogramming for Haskell. In
Proceedings of Haskell Workshop, 2002.
K. Suzuki, O. Kiselyov, and Y. Kameyama. Finally, Safely-Extensible andEfficient Language-Integrated Query. In Proceedings of the 2016 ACM
SIGPLAN Workshop on Partial Evaluation and Program Manipulation,
2016.

A.

HRR features

In addition to features descibed in this paper, HRR provides thefollowings:• Type-propagated placeholders

Conclusion• Window functions

We implemented Haskell Relational Record, a pragmatic, embedded domain-specific language for writing SQL statements in
Haskell. To support real-world database system operations, it supports a large part of SQL, including outer joins and correlated subqueries, which are not supported by previous works. HRR handles
non-aggregate and aggregate queries correctly, by using separate
query types. Queries are composable since non-aggregate and aggregate queries are converted into a unified query type. SQL expressions in queries are typed with nested Haskell records. We show algorithms for primitive operators of record manipulation which preserve correspondence between nested Haskell records and flat SQL
structures. HRR code is converted into syntactically-correct SQL
statements. The arrow interface provides type-safety—generated
SQL statements do not contain type or reference errors. If correlated subqueries are joined in the monad interface, generated SQL
statements are not valid. In practice, this is not a serious problem
because incorrectly joined subqueries can be always detected as
reference errors.

• Direct SQL embedding• Insertion, deletion, update with/without correlated subqueries• Customization of type mapping

B.

Code Generation

The following is an overview of the auto-generated code for
Employee.hs, expanded by Template Haskell:data Employee = Employee {id:: !Int, name:: !String, deptId :: !Int} deriving (Show)
employee :: Relation () Employee
employee = ...
id’ :: Pi Employee Int
id’ = ...

Acknowledgments
We would like to deeply thank Travis Cardwell for thoroughly
reviewing an early draft of this paper. We would like to express
our gratitude to Michael Snoyman, Andres Löh, Tom Ellis, Fumiaki Kinoshita, Hiroyuki Kurokawa, Oleg Kiselyov, and Yukiyoshi
Kameyama for their feedback.

name’ :: Pi Employee Stringname’ = ...
deptId’ :: Pi Employee Int
deptId’ = ...

ReferencesC.

B. Bringert and A. Höckersten. Student Paper: HaskellDB Improved. In
Proceedings of Haskell Workshop, 2004.
J. Hughes. Generalising Monads to Arrows. Science of Computer Programming, 37:67–111, 1998.
Information technology - Database languages - SQL. ISO/IEC 9075 standard, 2011.
M. P. Jones. Functional Programming with Overloading and HigherOrder Polymorphism, volume 925 of Lecture Notes in Computer Science. Springer-Verlag, 1995.
D. Leijen and E. Meijer. Domain Specific Embedded Compilers. In Proceedings of the 2nd Conference on Domain-Specific Languages, 1999.
S. Liang, P. Hudak, and M. Jones. Monad Transformers and Modular Interpreters. In Proceedings of the 22nd ACM SIGPLAN-SIGACT symposiumon Principles of programming languages, 1995.
S. Marlow et al. Haskell 2010 Language Report, 2010.
C. McBride and R. Paterson. Applicative Programming with Effects.
Journal of Functional Programming, 18, 2008.

Figure 6 summarizes the signatures of HRR operators used in thispaper. See also Figure 3.

Haskell Relational RecordD.

HRR operators

Execution Examples

Figure 7 shows execution examples of the primitive operators.

10

2016/8/2

-- Equal(.=.) :: Projection c a -> Projection c a -> Projection c (Maybe Bool)-- Greater than(.<.) :: Projection c a -> Projection c a -> Projection c (Maybe Bool)-- Injecting to Maybe
just :: p a -> p (Maybe a)-- Indexing for Maybe(?!) :: Projection c (Maybe a) -> Pi a b -> Projection c (Maybe b)-- Converting a non-aggregate query to a relation
relation:: QuerySimple (Projection Flat r) -> Relation () r-- Converting a aggregate query to a relation
aggregateRelation :: QueryAggregate (Projection Aggregated r) -> Relation () r-- Joining
query:: MonadQuery m => Relation () r -> m (Projection Flat r)-- Joining with Maybe values
queryMaybe :: MonadQuery m => Relation () r -> m (Projection Flat (Maybe r))-- Converting a relation to a subquery
queryList :: Relation () r -> QuerySimple (ListProjection (Projection Exists) r)-- SQL constantvalue :: a -> Projection c a-- SQL ON
on :: MonadQuery m => Projection Flat (Maybe Bool) -> m ()-- SQL WHERE (specialized for simplicity)wheres:: Projection Flat (Maybe Bool) -> QuerySimple ()wheres:: Projection Flat (Maybe Bool) -> QueryAggregate ()-- SQL GROUP BY
groupBy:: Projection Flat r -> QueryAggregate (Projection Aggregated r)-- SQL COUNT aggregate function
count:: Integral b => Projection Flat a -> Projection Aggregated b-- SQL UNION ALL
unionAll:: Relation () a -> Relation () a -> Relation () a-- SQL EXISTS
exists:: ListProjection (Projection Exists) r -> p (Maybe Bool)

Figure 6. The signatures of HRR functions. QuerySimple and QueryAggregate are instances of MonadQuery.

π[1,2]

E-compose
π[1] ,−−−−−−−→ π[[1,2]!!1] ,→ π[2]E-indexp[1,“Smith”,T 2.f 0] idx π[1,2] ,−−−−−→ p[[1,“Smith”,T 2.f 0]!!y|y←[1,2]] ,→ p[“Smith”,T 2.f 0]
E-P-map(, ) h$i p[T 2.f 0] ,−−−−−−→ p[T 2.f 0]
E-map(, ) h$i π[2] ,−−−−→ π[2]E-P-app[T 2.f 0] h∗i p[“Smith”] ,−−−−→ p[T 2.f 0]++[“Smith”] ,→ p[T 2.f 0,“Smith”]
E-ap
π[2] h∗i π[1] ,−−−→ π[2]++[1] ,→ π[2,1]Figure 7. Execution examples of the primitive operators

Haskell Relational Record

11

2016/8/2