First-Class Functions for First-Order Database Engines
Torsten Grust

Alexander Ulrich

Universität Tübingen, Germany
{torsten.grust, alexander.ulrich}@uni-tuebingen.de

arXiv:1308.0158v1 [cs.DB] 1 Aug 2013

Abstract
We describe query defunctionalization which enables off-the-shelf
first-order database engines to process queries over first-class functions. Support for first-class functions is characterized by the ability
to treat functions like regular data items that can be constructed
at query runtime, passed to or returned from other (higher-order)
functions, assigned to variables, and stored in persistent data structures. Query defunctionalization is a non-invasive approach that
transforms such function-centric queries into the data-centric operations implemented by common query processors. Experiments with
XQuery and PL/SQL database systems demonstrate that first-order
database engines can faithfully and efficiently support the expressive
“functions as data” paradigm.

1.

Functions Should be First-Class

Since the early working drafts of 2001, XQuery’s syntax and
semantics have followed a functional style:1 functions are applied to
form complex expressions in a compositional fashion. The resulting
XQuery script’s top-level expression is evaluated to return a sequence
of items, i.e., atomic values or XML nodes [8].
Ten years later, with the upcoming World Wide Web Consortium
(W3C) XQuery 3.0 Recommendation [28], functions themselves
now turn into first-class items. Functions, built-in or user-defined,
may be assigned to variables, wrapped in sequences, or supplied as
arguments to and returned from higher-order functions. In effect,
XQuery finally becomes a full-fledged functional language. Many
useful idioms are concisely expressed in this “functions as data”
paradigm. We provide examples below and argue that support for
first-class functions benefits other database languages, PL/SQL in
particular, as well.
This marks a significant change for query language implementations, specifically for those built on top of (or right into) database
kernels. While atomic values, sequences, or XML nodes are readily
represented in terms of the widespread first-order database data
models [9], this is less obvious for function items. Database kernels
typically lack a runtime representation of functional values at all.
We address this challenge in the present work.
In query languages, the “functions as data” principle can surface
in various forms.
Functions as Values. XQuery 3.0 introduces name#n as notation to refer to the n-ary function named name: math:pow#2
refers to exponentiation while fn:concat#2 denotes string concatenation, for example. The values of these expressions are
functions—their types are of the form function(t1 ) as t2
or, more succinctly, t1 → t2 —which may be bound to variables and applied to arguments. The evaluation of the expression
let $exp := math:pow#2 return $exp(2,3) yields 8, for example.

1
2
3
4
5
6
7

declare function fold-right(
$f as function(item(), item()*) as item()*,
$z as item()*, $seq as item()*) as item()*
{
if (empty($seq)) then $z else
$f(fn:head($seq), fold-right($f, $z, fn:tail($seq)))
};

Figure 1: Higher-order function fold-right (XQuery 3.0).
Higher-Order Functions. In their role of regular values, functions may be supplied as parameters to and returned from other
functions. The latter, higher-order functions can capture recurring patterns of computation and thus make for ideal building
blocks in query library designs. Higher-order function fold-right
is a prime example here—entire query language designs have
been based on its versatility [13, 18]. The XQuery 3.0 variant fold-right($f, $z, $seq) is defined in Figure 1: it reduces
a given input sequence $seq = (e1 ,e2 ,. . . ,en ) to the value
$f(e1 ,$f(e2 ,$f(. . . ,$f(en ,$z)· · · ))). Different choices for
the functional parameter $f and $z configure fold-right to perform a variety of computations:
fold-right(math:pow#2, 1, (e1 ,e2 ,. . . ,en ))
(with numeric ei ) computes the exponentiation tower ee12
the expression

XQuery is a functional language in which a query is represented as an
expression.” [11, §2]

.e n

, while

fold-right(fn:concat#2, "", (e1 ,e2 ,. . . ,en ))
will return the concatenation of the n strings ei .
Function Literals. Queries may use function(x) { e } to denote
a literal function (also: inline function or λ-expression λx.e). Much
like the literals of regular first-order types (numbers, strings, . . . ),
function literals are pervasive if we adopt a functional mindset:
A map, or associative array, is a function from keys to values.
Figure 2 takes this definition literally and implements maps2 in terms
of functions. Empty maps (created by map:empty) are functions
that, for any key $x, will return the empty result (). A map with
entry ($k,$v) is a function that yields $v if a key $x = $k
is looked up (and otherwise will continue to look for $x in the
residual map $map). Finally, map:new($es) builds a complex
map from a sequence of entries $es—an entry is added through
application to the residual map built so far. As a consequence of
this implementation in terms of functions, lookups are idiomatically
performed by applying a map to a key, i.e., we may write
let $m := map:new((map:entry(1,"one"), map:entry(2,"two")))
return $m(2) (:
"two" :)

2 Our
1 “[. . . ]

..

design follows Michael Kay’s proposal for maps in XSLT 3.0. Of
two entries under the same key, we return the entry inserted first (this is
implementation-dependent: http://www.w3.org/TR/xslt-30/#map).

1
2
3

declare function map:empty() {
function($x) { () }
};

6
7
8
9

declare function map:entry($k,$v) {
function($map) {
function($x) { if ($x = $k) then $v else $map($x) }
}
};

11
13

declare function map:new($es) {
fold-right(function($f,$x) { $f($x) }, map:empty(), $es)
};

16
17

5
6
7
8
9
11
12
13
14

14
15

3

10

10
12

2

declare function map:remove($map,$k) {
function($x) { if ($x = $k) then () else $map($x) }
};

15

Figure 2: Direct implementation of maps as functions from keys
to values (XQuery 3.0).

17
19
20

23

3
4
5
6
7
8
9
10
11

-- find completion date of an order based on its status
CREATE TABLE COMPLETION (
c_orderstatus CHAR(1),
c_completion FUNCTION(ORDERS) RETURNS DATE);

21
22

(: wrap(), unwrap(): see Section 4.1 :)

24

declare function map:empty() {
element map {}
};

26

declare function map:entry($k, $v) {
element entry {
element key { wrap($k) }, element val { wrap($v) }
}
};

30

2

-- determines the completion date of an order based on its items
CREATE FUNCTION item_dates(comp FUNCTION(DATE,DATE) RETURNS DATE)
RETURNS (FUNCTION(ORDERS) RETURNS DATE) AS
BEGIN
RETURN FUNCTION(o)
BEGIN RETURN (SELECT comp(MAX(li.l_commitdate),
MAX(li.l_shipdate))
FROM LINEITEM li
WHERE li.l_orderkey = o.o_orderkey);
END;
END;

16
18

1

-- Based on (an excerpt of) the TPC-H schema:
-- ORDERS(o_orderkey, o_orderstatus, o_orderdate, . . . )
-- LINEITEM(l_orderkey, l_shipdate, l_commitdate, . . . )

4

4
5

1

25
27
28
29
31
32

INSERT
(’F’,
(’P’,
(’O’,

INTO COMPLETION VALUES
FUNCTION(o) BEGIN RETURN o.o_orderdate; END),
FUNCTION(o) BEGIN RETURN NULL; END),
item_dates(GREATEST));

-- determine the completion date of all orders
SELECT o.o_orderkey,
o.o_orderstatus,
c.c_completion(o) AS completion
FROM ORDERS o, COMPLETION c
WHERE o.o_orderstatus = c.c_orderstatus;

Figure 4: Using first-class functions in PL/SQL.

12
13
14
15
16
17
18
19
20
21
22
23
24

declare function map:new($es) {
element map { $es }
};
declare function map:get($map, $k) {
unwrap($map/child::entry[child::key = $k][1]/
child::val/child::node())
};
declare function map:remove($map, $k) {
element map { $map/child::entry[child::key != $k] }
};

Figure 3: A first-order variant of XQuery maps.
An alternative, regular first-order implementation of maps is
shown in Figure 3. In this variant, map entries are wrapped in
pairs of key/val XML elements. A sequence of such pairs under a
common map parent element forms a complex map. Map lookup now
requires an additional function map:get—e.g., with $m as above:
map:get($m,2)—that uses XPath path expressions to traverse
the resulting XML element hierarchy. (We come back to wrap
and unwrap in Section 4.1.)
We claim that the functional variant in Figure 2 is not only shorter
but also clearer and arguably more declarative, as it represents a
direct realization of the “a map is a function” premise. Further, once
we study their implementation, we will see that the functional and
first-order variants ultimately lead the query processor to construct
and traverse similar data structures (Section 4.1). We gain clarity
and elegance and retain efficiency.
Functions in Data Structures. Widely adopted database programming languages, notably PL/SQL [4], treat functions as second-class
citizens: in particular, regular values may be stored in table cells
while functions may not. This precludes a programming style in
which queries combine tables of functions and values in a concise
and natural fashion.
The code of Figure 4 is written in a hypothetical dialect of
PL/SQL in which this restriction has been lifted. In this dialect,

the function type t1 → t2 reads FUNCTION(t1 ) RETURNS t2 and
FUNCTION(x) BEGIN e END denotes a literal function with argument x and body e.3
The example code augments a TPC-H database [34] with
a configurable method to determine order completion dates.
In lines 18 to 25, table COMPLETION is created and populated
with one possible configuration that maps an order status (column c_orderstatus) to its particular method of completion date
computation. These methods are specified as functions of type
FUNCTION(ORDERS) RETURNS DATE4 held in c_completion, a
functional column: while we directly return its o_orderdate
value for a finalized order (status ’F’) and respond with an
undefined NULL date for orders in processing (’P’), the completion date of an open order (’O’) is determined by function item_dates(GREATEST): this function consults the commitment and shipment dates of the order’s items and then returns
the most recent of the two (since argument comp is GREATEST).5
Function item_dates itself has been designed to be configurable. Its higher-order type
(DATE × DATE → DATE) → (ORDERS → DATE)
indicates that item_dates returns a function to calculate order
completion dates once it has been supplied with a suitable date
comparator (e.g., GREATEST in line 25). This makes item_dates a
curried function which consumes its arguments successively (date
comparator first, order second)—a prevalent idiom in functioncentric programming [6].
Note that the built-in and user-defined functions GREATEST
and item_dates are considered values as are the two literal func3 We

are not keen to propose syntax here. Any notation that promotes firstclass functions would be fine.
4 Type ORDERS denotes the type of the records in table ORDERS.
5 Built-in SQL function GREATEST (LEAST) returns the larger (smaller) of its
two arguments.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

declare function group-by($seq as item()*,
$key as function(item()*) as item()*)
as (function() as item()*)*
{
let $keys := for $x in $seq return $key($x)
for $k in distinct-values($keys)
return
function() { $seq[$key(.) = $k] }
};
let $fib := (0,1,1,2,3,5,8,13,21,34)
for $g in group-by($fib, function($x) { $x mod 2 })
return
element group { $g() }

Figure 5: A grouping function that represents the individual
groups in terms of closures (XQuery 3.0).

tions in lines 23 and 24. As such they may be stored in table cells—
e.g., in column c_completion of table COMPLETION—and then
accessed by SQL queries. The query in lines 28 to 32 exercises the
latter and calculates the completion dates for all orders based on the
current configuration in COMPLETION.
Once more we obtain a natural solution in terms of first-class
functions—this time in the role of values that populate tables.
Queries can then be used to combine functions and their arguments
in flexible ways. We have demonstrated further use cases for PL/SQL
defunctionalization (including offbeat examples, e.g., the simulation
of algebraic data types) in [20].
Contributions. The present work shows that off-the-shelf database
systems can faithfully and efficiently support expressive query languages that promote first-class functions. Our specific contributions
are these:
• We apply defunctionalization to queries, a source transformation
that trades functional values for first-order values which existing
query engines can process efficiently.
• We discuss representations of closures that fit database data models
and take size and sharing issues into account.
• We demonstrate how these techniques apply to widely adopted
query languages (XQuery, PL/SQL) and established systems (e.g.,
Oracle and PostgreSQL).
• We show that defunctionalization introduces a tolerable runtime
overhead (first-order queries are not affected at all) and how simple
optimizations further reduce the costs.
Defunctionalization is an established technique in programming
languages and it deserves to be better known in the database systems
arena.
The approach revolves around the concept of closure which we
discuss briefly in Section 2. Section 3 shows how defunctionalization maps queries over first-class functions to regular first-order
constructs. We focus on XQuery first and then carry over to PL/SQL
in Section 3.1. Issues of efficient closure representation are addressed in Section 4. Section 5 assesses the space and time overhead
of defunctionalization and discusses how costs may be kept in check.
Section 6 reviews related efforts before we conclude in Section 7.

2.

Functions as Values: Closures

This work deliberately pursues a non-invasive approach that enables
off-the-shelf database systems to support the function-centric style
of queries we have advocated in Section 1. If these existing firstorder query engines are to be used for evaluation, it follows that we
require a first-order representation of functional values. Closures [5,
23] provide such a representation. We very briefly recall the concept
here.

The XQuery 3.0 snippet of Figure 5 defines the higher-order
grouping function group-by which receives the grouping criterion
in terms of the functional argument $key: a group is the sequence of
those items $x in $seq that map to the same key value $key($x).
Since XQuery implicitly flattens nested sequences, group-by cannot directly yield the sequence of all groups. Instead, group-by
returns a sequence of functions each of which, when applied to zero
arguments, produces “its” group. The sample code in lines 11 to 14
uses group-by to partition the first few elements of the Fibonacci series into odd/even numbers and then wraps the two resulting groups
in XML group elements.
Closures. Note that the inline function definition in line line 8
captures the values of the free variables $k, $key, and $seq which is
just the information required to produce the group for key $k. More
general, the language implementation will represent a functional
value f as a bundle that comprises
(1) the code of f ’s body and
(2) its environment, i.e., the bindings of the body’s free variables at
the time f was defined.
Together, code and environment define the closure for function f .
In the sequel, we will use
`

x1 · · · xn

to denote a closure whose environment contains n > 0 free variables
v1 , . . . , vn bound to the values x1 , . . . , xn .6 Label ` identifies the
code of the function’s body (in the original work on closures, code
pointers were used instead [5]). In the example of Figure 5, two
closures are constructed at line 8 (there are two distinct grouping
keys $k = 0, 1) that represent instances of the literal function. If we
order the free variables as $k, $key, $seq, these closures read
`1

0

`2

(0,1,1,2,. . . )

and

`1

1

`2

(0,1,1,2,. . . ) .

(the two closures share label `1 since both refer to the same body
code $seq[$key(.) = $k]). Observe that
• closures may be nested: $key is bound to closure `2

with empty
environment, representing the literal function($x) { $x mod 2 }
(defined in line 12) whose body has no free variables, and

• closures may contain and share data of significant size: both

closures contain a copy of the $fib sequence (since free variable $seq was bound to $fib).

We will address issues of closure nesting, sharing, and size in Sections 4 and 5.
The key idea of defunctionalization, described next, is to trade
functional values for their closure representation—ultimately, this
leaves us with an equivalent first-order query.

3.

Query Defunctionalization

Query defunctionalization is a source-level transformation that
translates queries over first-class functions into equivalent firstorder queries. Here, our discussion revolves around XQuery but
defunctionalization is readily adapted to other query languages, e.g.,
PL/SQL (see Section 3.1).
The source language is XQuery 3.0, restricted to the constructs
that are admitted by the grammar of Figure 6 (these restrictions aid
brevity—defunctionalization is straightforwardly extended to cover
the full XQuery 3.0 specification). Notably, the language subset
includes
• two kinds of expressions that yield functional values (literal
functions of the form function($x1 ,. . . ,$xn ) { e } as well as
named function references name#n), and
6 If

we agree on a variable order, there is no need to save the variable names vi
in the environment.

Program
FunDecl
Expr

Var

→
→
→
|
|
|
|
|
|
|
|
|
|
|
|
|
→

FunDecl ∗ Expr
declare function QName($Var ∗ ) { Expr };
for $Var in Expr return Expr
let $Var := Expr return Expr
$Var
if (Expr ) then Expr else Expr
(Expr∗ )
Expr /Axis::NodeTest
element QName { Expr }
Expr [Expr ]
.
QName (Expr ∗ )
function ($Var ∗ ) { Expr }
QName#IntegerLiteral
Expr (Expr ∗ )
···
QName

Figure 6: Relevant XQuery subset (source language), excerpt of
the XQuery 3.0 Candidate Recommendation [28].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Expr

Case

→
|
|
|
|
|

[ constructs of Figure 6 ]
function ($Var ∗ ) { Expr }
QName#IntegerLiteral
Expr (Expr ∗ )
` Expr · · · Expr
case Expr of Case +

→

` $Var · · · $Var

⇒ Expr

Figure 7: Target language: functional values and dynamic function calls are removed. New: closure construction and elimination.
• dynamic function calls of the form e(e1 ,. . . ,en ), in which

expression e evaluates to an n-ary function that is subsequently
applied to the appropriate number of arguments.
The transformation target is a first-order dialect of XQuery 1.0
to which we add closure construction and elimination. A closure
constructor ` x1 · · · xn builds a closure with label ` and an
environment of values x1 , . . . , xn . Closure elimination, expressed
using case · · · of, discriminates on a closure’s label and then extracts
the environment contents: from the b branches in the expression
case e of
`1 $v1,1 · · · $v1,n ⇒ e1
1
..
.
`b $vb,1 · · · $vb,n ⇒ eb ,
b
if e evaluates to the closure `i x1 · · · xn , case · · · of will pick
the ith branch and evaluate ei with the variables $vi,j bound to
the values xj . We discuss ways to express the construction and
elimination of closures in terms of regular query language constructs
in Section 4.
Figure 7 shows the relevant excerpt of the resulting target
language. In a sense, this modified grammar captures the essence of
defunctionalization: functional values and dynamic function calls
are traded for the explicit construction and elimination of first-order
closures. The translation can be sketched as follows:
(1) A literal function is replaced by a closure constructor whose
environment is populated with the bindings of the free variables
referenced in the function’s body. The body’s code is wrapped
inside a new top-level surrogate function ` whose name also
serves as the closure label.
(2) A reference to a function named ` is replaced by a closure
constructor with empty environment and label `.

declare function `2($x) { $x mod 2 };
declare function `1($k, $key, $seq) {
$seq[(dispatch_1($key, .)) = $k]
};
declare function dispatch_0($clos) {
case $clos of
`1 $k $key $seq ⇒ `1($k, $key, $seq)
};
declare function dispatch_1($clos, $b1) {
case $clos of
`2 ⇒ `2($b1)
};
declare function group-by($seq, $key) {
let $keys := for $x in $seq return dispatch_1($key, $x)
for $k in distinct-values($keys)
return `1 $k $key $seq
};
let $fib := (0,1,1,2,3,5,8,13,21,34)
for $g in group-by($fib, `2 )
return
element group { dispatch_0($g) }

Figure 8: Defunctionalized first-order variant of the XQuery group-by example in Figure 5.
(3) A dynamic function call (now equivalent to an application of
a closure with label ` to zero or more arguments) is translated
into a static function call to a generated dispatcher function. The
dispatcher receives the closure as well as the arguments and then
uses closure elimination to forward the call to function `, passing
the environment contents (if any) along with the arguments.
Appendix A elaborates the details of this transformation, including
the generation of dispatchers, for the XQuery case. A syntax-directed
top-down traversal identifies the relevant spots in a given program
at which closure introduction or elimination has to be performed
according to the cases (1) to (3) above. All other program constructs
remain unchanged. The application of defunctionalization to the
XQuery program of Figure 5 yields the code of Figure 8. We find the
expected surrogate functions `1,2 , dispatchers (dispatch_n), and
static dispatcher invocations. Overall, the resulting defunctionalized
query adheres to the target language of Figure 7, i.e., the query is
first-order. Once we choose a specific implementation for closure
construction and elimination, we obtain a query that may be executed
by any XQuery 1.0 processor.
3.1

Query Defunctionalization for PL/SQL

Query defunctionalization does not need to be reinvented if we carry
it over to PL/SQL. Much like for XQuery, the defunctionalization
transformation for a PL/SQL dialect with first-class functions builds
on three core cases (see above and Figure 21 in Appendix A):
(1) the creation of function literals (applies in lines 9, 23, and 24 of
the PL/SQL example in Figure 4),
(2) references to named function values (GREATEST in line 25), and
(3) dynamic function application (applies in lines 10 and 30).
Applied to the example of Figure 4 (order completion dates),
defunctionalization generates the output of Figure 9. The resulting
code executes on vanilla PL/SQL hosts; we show a PostgreSQL 9
dialect here, minor adaptations yield syntactic compatibility with
Oracle.
PL/SQL operates over typed tables and values and thus requires
the generation of typed closures. In the present example, we use
τt1 →t2 to denote the type of closures that represent functions of
type t1 → t2 . (For now, τ is just a placeholder—Section 4 discusses
suitable relational implementations of this type.) As expected, we
find higher-order function item_dates to accept and return values
of such types τ (line 35).

1
2
3
4
5
6
7

CREATE FUNCTION `1(o ORDERS, comp τDATE×DATE→DATE) RETURNS DATE AS
BEGIN
RETURN (SELECT dispatch_2(comp, MAX(li.l_commitdate),
MAX(li.l_shipdate))
FROM LINEITEM li
WHERE li.l_orderkey = o.o_orderkey);
END;

8
9
10
11
12

CREATE FUNCTION `2(o ORDERS) RETURNS DATE AS
BEGIN
RETURN o.o_orderdate;
END;

13
14
15
16
17

CREATE FUNCTION `3(o ORDERS) RETURNS DATE AS
BEGIN
RETURN NULL;
END;

18
19
20
21
22
23
24
25
26

CREATE FUNCTION dispatch_1(clos τORDERS→DATE, b1 ORDERS)
RETURNS DATE AS
BEGIN
case clos of
`1 comp ⇒ `1(b1, comp)
`2
⇒ `2(b1)
`3
⇒ `3(b1)
END;

27
28
29
30
31
32
33

CREATE FUNCTION dispatch_2(clos τDATE×DATE→DATE, b1 DATE, b2 DATE)
RETURNS DATE AS
BEGIN
case clos of
`4 ⇒ GREATEST(d1, d2)
END;

34
35
36
37
38
39

CREATE FUNCTION item_dates(comp τDATE×DATE→DATE)
RETURNS τORDERS→DATE AS
BEGIN
RETURN `1 comp ;
END;

40
41
42
43

CREATE TABLE COMPLETION (
c_orderstatus CHAR(1),
c_completion τORDERS→DATE);

44
45
46
47
48

INSERT INTO COMPLETION VALUES
(’F’, `2 ),
(’P’, `3 );
(’O’, item_dates( `4 )),

49
50
51
52
53
54

SELECT o.o_orderkey,
o.o_orderstatus,
dispatch_1(c.c_completion, o) AS completion
FROM ORDERS o, COMPLETION c
WHERE o.o_orderstatus = c.c_orderstatus;

Figure 9: PL/SQL code of Figure 4 after defunctionalization.

COMPLETION
c_orderstatus c_completion
`2
’F’
`3
’P’
`1 `4
’O’

Figure 10: Table of functions: COMPLETION holds closures of
type τORDERS→DATE in column c_completion.
are closed and have an empty environment. Closure `1 , representing
the function literal defined at line 9 of Figure 4, carries the value of
free variable comp which itself is a (date comparator) function. We
thus end up with a nested closure.
Tables of functions may persist in the database like regular
first-order tables. To guarantee that closure labels and environment
contents are interpreted consistently when such tables are queried,
update and query statements need to be defunctionalized together,
typically as part of the same PL/SQL package [4, §10] (whole-query
transformation, see Appendix A). Still, query defunctionalization
is restricted to operate in a closed world: the addition of new literal
functions or named function references requires the package to be
defunctionalized anew.

4.

Representing (Nested) Closures

While the defunctionalization transformation nicely carries over
to query languages, we face the challenge to find closure representations that fit query runtime environments. Since we operate
non-invasively, we need to devise representations that can be expressed within the query language’s data model itself. (We might
benefit from database engine adaptations but such invasive designs
are not in the scope of the present paper.)
Defunctionalization is indifferent to the exact method of closure
construction and elimination provided that the implementation can
(a) discriminate on the code labels ` and
(b) hold any value of the language’s data model in the environment.
If the implementation is typed, we need to
(c) ensure that all constructed closures for a given function
type t1 → t2 share a common representation type τt1 →t2
(cf. our discussion in Section 3.1).
Since functions can assume the role of values, (b) implies that
closures may be nested. We encountered nested closures of depth 2
in Figure 10 where the environment of closure `1 holds a closure
labeled `4 . For particular programs, the nesting depth may be
unbounded, however. The associative map example of Section 1
creates closures of the form
`1

Likewise, PL/SQL defunctionalization emits typed dispatchers
dispatch_i each of which implement dynamic function invocation for closures of a particular type:7 the dispatcher associated with functions of type t1 → t2 has the PL/SQL signature
FUNCTION(τt1 →t2 ,t1 ) RETURNS t2 . With this typed representation
come opportunities to improve efficiency. We turn to these in the
next section.
Tables of Functions. After defunctionalization, functional values
equate first-order closure values. This becomes apparent with a look
at table COMPLETION after it has been populated with three functions
(in lines 45 to 48 of Figure 9). Column c_completion holds the
associated closures (Figure 10). The closures with labels `2 and `3
represent the function literals in lines 23 and 24 of Figure 4: both
7 Since

PL/SQL lacks parametric polymorphism, we may assume that the ti
denote concrete types. Type specialization [33] could pave the way for a
polymorphic variant of PL/SQL, one possible thread of future work.

k1 v 1

`1

k2 v2

`1

···

`1

kn vn

`3

(∗)

where the depth is determined by the number n of key/value pairs
(ki , vi ) stored in the map.
Here, we discuss closure implementation variants in terms of
representation functions CJ·K that map closures to regular language
constructs. We also point out several refinements.
4.1

XQuery: Tree-Shaped Closures

For XQuery, one representation that equates closure construction
with XML element construction is given in Figure 11. A closure
with label ` maps to an outer element with tag ` that holds the
environment contents in a sequence of env elements. In the environment, atomic items are tagged with their dynamic type such that
closure elimination can restore value and type (note the calls to
function wrap() and its definition in Figure 12): item 1 of type
xs:integer is held as <atom><integer>1</integer></atom>.
Item sequences map into sequences of their wrapped items, XML
nodes are not wrapped at all.

CJ ` x1 · · · xn K

=

CJ ` K

=
=

CJxK

element ` { element env { CJx1 K }, . . . ,
element env { CJxn K } }
element ` {}
wrap(x)

Figure 11: XQuery closure representation in terms of XML
fragments. Function wrap() is defined in Figure 12a.

1
2
3
4
5
6
7
8
9
10

declare function wrap($xs)
{
for $x in $xs return
typeswitch ($x)
case xs:anyAtomicType
return wrap-atom($x)
case attribute(*)
return element attr {$x}
default return $x
};

11
12

(a)

declare function wrap-atom($a)
{
element atom {
typeswitch ($a)
case xs:integer
return element integer {$a}
case xs:string
return element string {$a}
[. . . more atomic types. . . ]
default return element any {$a}
}
};
(b)

Figure 12: Preserving value and dynamic type of environment
contents through wrapping.
Closure elimination turns into an XQuery typeswitch() on the
outer tag name while values in the environment are accessed via
XPath child axis steps (Figure 13). Auxiliary function unwrap()
(obvious, thus not shown) uses the type tags to restore the original
atomic items held in the environment.
In this representation, closures nest naturally. If we apply CJ·K to
the closure (∗) that resulted from key/value map construction, we
obtain the XML fragment of Figure 14 whose nested shape directly
reflects that of the input closure.
Refinements. The above closure representation builds on inherent
strengths of the underlying XQuery processor—element construction and tree navigation—but has its shortcomings: XML nodes held
in the environment lose their original tree context due to XQuery’s
copy semantics of node construction. If this affects the defunctionalized queries, an environment representation based on by-fragment
semantics [36], preserving document order and ancestor context, is
a viable alternative.
Further options base on XQuery’s other aggregate data type:
the item sequence: closures then turn into non-empty sequences
of type item()+. While the head holds label `, the tail can hold
the environment’s contents: (`,x1 ,. . . ,xn ). In this representation,
neither atomic items nor nodes require wrapping as value, type, and
tree context are faithfully preserved. Closure elimination accesses
the xi through simple positional lookup into the tail. Indeed, we
have found this implementation option to perform particularly
well (Section 5). Due to XQuery’s implicit sequence flattening,
this variant requires additional runtime effort in the presence of
sequence-typed xi or closure nesting, though (techniques for the flat
representation of nested sequences apply [25]).
Lastly, invasive approaches may build on engine-internal support
for aggregate data structures. Saxon [25], for example, implements
an appropriate tuple structure that can serve to represent closures.8
4.2

PL/SQL: Typed Closures

Recall that we require a fully typed closure representation to meet
the PL/SQL semantics (Section 3.1). A direct representation of
closures of, in general, unbounded depths would call for a recursive
representation type. Since the PL/SQL type system reflects the flat
relational data model, recursive types are not permitted, however.
8 http://dev.saxonica.com/blog/mike/2011/07/#000186

case e1 of
..
.
` $v1 · · · $vn ⇒ e2

typeswitch
(e1)
..
.
case element(`) return
let $env := e1/env
let $v1 := unwrap($env[1]/node())
..
.
let $vn := unwrap($env[n]/node())
return e2

Figure 13: XQuery closure elimination: typeswitch() discriminates on the label, axis steps access the environment.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

<`1>
<env><atom><tkey >k1</tkey ></atom></env>
<env><atom><tval >v1</tval ></atom></env>
<env>
<`1>
<env><atom><tkey >k2</tkey ></atom></env>
<env><atom><tval >v2</tval ></atom></env>
<env>
···
<`1>
<env><atom><tkey >kn</tkey ></atom></env>
<env><atom><tval >vn</tval ></atom></env>
<env><`3/></env>
</`1>
···
</env>
</`1>
</env>
</`1>

Figure 14: XML representation of the nested closure (∗). tkey
and tval denote the types of keys and values, respectively.

CJ ` x1 · · · xn K

=

ROW(`,γ)

CJ ` K
CJxK

=
=

ROW(`,NULL)
x

ENVt1 →t2
id
env
..
..
.
.
γ ROW(CJx1 K,. . . ,CJxn K)

Figure 15: Relational representation for closures, general approach (γ denotes an arbitrary but unique key value).

ENVtkey →tval
id
env
γn ROW(k1 ,v1 ,ROW(`1 ,γn−1 ))
γn−1 ROW(k2 ,v2 ,ROW(`1 ,γn−2 ))
..
..
.
.
γ1 ROW(kn ,vn ,ROW(`3 ,NULL))

Figure 16: Environment table built to represent closure (∗).

Instead, we represent closures as row values, built by constructor ROW(), i.e., native aggregate record structures provided
by PL/SQL. Row values are first-class citizens in PL/SQL and, in
particular, may be assigned to variables, can contain nested row
values, and may be stored in table cells (these properties are covered by feature S024 “support for enhanced structured types” of the
SQL:1999 standard [31]).
Figure 15 defines function CJ·K that implements a row value-based
representation. A closure ` x1 · · · xn of type τt1 →t2 maps to
the expression ROW(`,γ). If the environment is non-empty, CJ·K
constructs an additional row to hold the environment contents. This
row, along with key γ is then appended to binary table ENVt1 →t2
which collects the environments of all functions of type t1 → t2 .
Notably, we represent non-closure values x as is (CJxK = x), saving
the program to perform wrap()/unwrap() calls at runtime.

CJ ` x1 · · · xn K
CJ ` K
CJxK

=
=
=

ROW(`,ROW(CJx1 K,. . . ,CJxn K))
ROW(`,NULL)
x

Figure 17: Relational representation of closures with fixed nesting depth: environment contents inlined into closure.

1
2
3
4
5
6
7
8

This representation variant yields a flat relational encoding regardless of closure nesting depth. Figure 16 depicts the table of
environments that results from encoding closure (∗). The overall
top-level closure is represented by ROW(`1 ,γn ): construction proceeds inside-out with a new outer closure layer added whenever a
key/value pair is added to the map. This representation of closure environments matches well-known relational encodings of tree-shaped
data structures [14].
Environment Sharing. ENV tables create opportunities for environment sharing. This becomes relevant if function literals are
evaluated under invariable bindings (recall our discussion of function group-by in Figure 5). A simple, yet dynamic implementation of environment sharing is obtained if we alter the behavior
of CJ ` x1 · · · xn K: when the associated ENV table already carries an environment of the same contents under a key γ, we return ROW(`,γ) and do not update the table—otherwise a new environment entry is appended as described before. Such upsert operations are a native feature of recent SQL dialects (cf. MERGE [31,
§14.9]) and benefit if column env of the ENV table is indexed. The
resulting many-to-one relationship between closures and environments closely resembles the space-efficient safely linked closures
as described by Shao and Appel in [29]. We return to environment
sharing in Section 5.
Closure Inlining. Storing environments separately from their closures also incurs an overhead during closure elimination, however.
Given a closure encoding ROW(`,γ) with γ 6= NULL, the dispatcher
(1) discriminates on `, e.g., via PL/SQL’s CASE· · · WHEN· · · END CASE,
then (2) accesses the environment through an ENV table lookup with
key γ.
With typed closures, the representation types τt1 →t2 are comprised of (or: depend on) typed environment contents. For the large
class of programs—or parts thereof—which nest closures to a statically known, limited depth, these representation types will be nonrecursive. Below, the type dependencies for the examples of Figures 2 and 4 are shown on the left and right, respectively (read
as “has environment contents of type”):
τtkey →tval
tval

tkey

τORDERS→DATE
τDATE×DATE→DATE

Note how the loop on the left coincides with the recursive shape of
closure (∗). If these dependencies are acyclic (as they are for the
order completion date example), environment contents may be kept
directly with their containing closure: separate ENV tables are not
needed and lookups are eliminated entirely. Figure 17 defines a variant of CJ·K that implements this inlined closure representation. With
this variant, we obtain CJ `1 `4 K = ROW(`1 ,ROW(`4 ,NULL))
(see Figure 10).
We quantify the savings that come with closure inlining in the
upcoming section.

5.

Does it Function? (Experiments)

Adding native support for first-class functions to a first-order query
processor calls for disruptive changes to its data model and the associated set of supported operations. With defunctionalization and its

9
10
11
12
13
14
15

declare function group-by($seq as item()*,
$key as function(item()*) as item()*)
as (function() as item()*)*
{
let $keys := for $x in $seq return $key($x)
for $k in distinct-values($keys)
let $group := $seq[$key(.) = $k] 
return
changed from Figure 5
function() { $group }
};
let $fib := (0,1,1,2,3,5,8,13,21,34)
for $g in group-by($fib, function($x) { $x mod 2 })
return
element group { $g() }

Figure 18: Hoisting invariant computation out of the body of
the literal function at line 9 affects closure size.
non-invasive source transformation, these changes are limited to the
processor’s front-end (parser, type checker, query simplification).
Here, we explore this positive aspect but also quantify the performance penalty that the non-native defunctionalization approach
incurs.
XQuery 3.0 Test Suite. Given the upcoming XQuery 3.0 standard, defunctionalization can help to carry forward the significant development effort that has been put into XQuery 1.0 processors. To make this point, we subjected three such processors—
Oracle 11g (release 11.1) [24], Berkeley DB XML 2.5.16 [1] and
Sedna 3.5.161 [15]—to relevant excerpts of the W3C XQuery 3.0
Test Suite (XQTS).9 All three engines are database-supported XQuery processors; native support for first-class functions would require
substantial changes to their database kernels.
Instead, we fed the XQTS queries into a stand-alone preprocessor
that implements the defunctionalization transformation as described
in Section 3. The test suite featured, e.g.,
• named references to user-defined and built-in functions, literal
functions, sequences of functions, and
• higher-order functions accepting and returning functions.
All three systems were able to successfully pass these tests.
Closure Size. We promote a function-centric query style in this
work, but ultimately all queries have to be executed by datacentric database query engines. Defunctionalization implements
this transition from functions to data, i.e., closures, under the hood.
This warrants a look at closure size.
Turning to the XQuery grouping example of Figure 5 again, we
see that the individual groups in the sequence returned by group-by
are computed on-demand: a group’s members will be determined
only once its function is applied ($g() in line 14). Delaying the
evaluation of expressions by wrapping them into (argument-less)
functions is another useful idiom available in languages with firstclass functions [7], but there are implications for closure size: each
group’s closure captures the environment required to determine its
group members. Besides $key and $k, each environment includes
the contents of free variable $seq (the input sequence) such that
the overall closure space requirements are in O(g · |$seq|) where g
denotes the number of distinct groups. A closure representation that
allows the sharing of environments (Section 4.2) would bring the
space requirements down to O(|$seq|) which marks the minimum
size needed to partition the sequence $seq.
Alternatively, in the absence of sharing, evaluating the expression $seq[$key(.) = $k] outside the wrapping function computes
groups eagerly. Figure 18 shows this alternative approach in which
9A

pre-release is available at http://dev.w3.org/cvsweb/2011/
QT3-test-suite/misc/HigherOrderFunctions.xml.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

BaseX

<map>
<entry>
<key><atom><tkey >k1</tkey ></atom></key>
<val><atom><tval >v1</tval ></atom></val>
</entry>
<entry>
<key><atom><tkey >k2</tkey ></atom></key>
<val><atom><tval >v2</tval ></atom></val>
</entry>
···
<entry>
<key><atom><tkey >kn</tkey ></atom></key>
<val><atom><tval >vn</tval ></atom></val>
</entry>
</map>

# free variables

native
dispatch

PostgreSQL

10 500
11 860

2 414
8 271

(a) Unary PL/SQL function.

native
dispatch

BaseX

Saxon

394
448

1 224
755

Saxon
10

1

5

10

native

402

396

467

1 144

1 451

1 725

node
sequence

2 132
743

7 685
1 527

14 535
2 485

2 133
854

7 347
1 526

12 992
2 350

# Calls

Line

1
1 500 000
732 044
732 044
732 044
729 413
38 543

50
19
1
3
28
9
14

Query/Function
SELECT o_orderkey,· · ·
dispatch_1()
`1 ()
SELECT dispatch_2(· · ·
dispatch_2()
`2 ()
`3 ()

ENV

Inline

47 874
44 249
22 748
9 270
3 554
2 942
155

40 093
35 676
22 120
9 363
3 450
2 856
149

Table 3: Profiles for the PL/SQL program of Figure 9: environment tables vs. closure inlining. Averaged cumulative time measured in ms. Line numbers refer to Figure 9.

(b) Literal XQuery function.

Table 1: Performing 106 invocations of closed functions (native
vs. dispatched calls). Wall-clock time measured in ms.

the bracketed part has been changed from Figure 5. A group’s closure now only includes the group’s members (free variable $group,
line 9 in Figure 18) and the overall closure sizes add up to O(|$seq|)
as desired. Closure size thus should be looked at with care during
query formulation—such “space leaks” are not specific to the present
approach, however [30].
With defunctionalization, queries lose functions but gain data. This
does not imply that defunctionalized queries use inappropriate
amounts of space, though. In our experiments we have found
function-centric queries to implicitly generate closures whose size
matches those of the data structures that are explicitly built by
equivalent first-order formulations.
To illustrate, recall the two XQuery map variants of Section 1.
Given n key/value pairs (ki , vi ), the function-centric variant of Figure 2 implicitly constructs the nested closure shown in Figure 14: a
non-empty map of n entries will yield a closure size of 10 · n XML
nodes. In comparison, the first-order map variant of Figure 3 explicitly builds a key/value list of similar size, namely 1 + 9 · n nodes
(Figure 19). Further, key lookups in the map incur almost identical
XPath navigation efforts in both variants, either through closure
elimination or, in the first-order case, the required calls to map:get.
Native vs. Dispatched Function Calls. As expected, the invocation
of functions through closure label discrimination by dispatchers
introduces measurable overhead if compared to native function
calls.10 To quantify these costs, we performed experiments in which
106 native and dispatched calls were timed. We report the averaged
wall-clock times of 10 runs measured on a Linux host, kernel
version 3.5, with Intel Core i5 CPU (2.6 GHz) and 8 GB of primary
memory.
Both, function invocation itself and closure manipulation contribute to the overhead. To assess their impact separately, a first
round of experiments invoked closed functions (empty environment). Table 1a documents the cost of a dispatched PL/SQL function call—i.e., construction of an empty closure, static call to the
10 Remember

5

Table 2: 106 invocations and elimination of closures of varying
size (1/5/10 free variables). Wall-clock time measured in ms.

Figure 19: Key-value map representation generated by the firstorder code of Figure 3 (compare with the closure of Figure 14).

Oracle

1

that this overhead only applies to dynamic function calls—static
calls are still performed natively.

dispatch function, closure label discrimination, static call to a
surrogate function. While dispatched function calls minimally affect Oracle 11g performance—hinting at a remarkably efficient
implementation of its PL/SQL interpreter—the cost is apparent in
PostgreSQL 9.2 (factor 3.5). In the XQuery case, we executed the
experiment using BaseX 7.3 [17] and Saxon 9.4 [3]—both engines
provide built-in support for XQuery 3.0 and thus allow a comparison
of the costs of a native versus a defunctionalized implementation
of first-class functions. BaseX, for example, employs a Java-based
implementation of closure-like structures that refer to an expression
tree and a variable environment. For the dynamic invocation of a
closed literal function, BaseX shows a moderate increase of 14 %
(Table 1b) when dispatching is used. For Saxon, we see a decrease
of 38 % from which we conclude that Saxon implements static
function calls (to dispatch and the surrogate function in this case)
considerably more efficient than dynamic calls. The resulting performance advantage of defunctionalization has also been reported
by Tolmach and Oliva [33].
In a second round of experiments, we studied the dynamic invocation of XQuery functions that access 1, 5, or 10 free variables of
type xs:integer. The defunctionalized implementation shows the
expected overhead that grows with the closure size (see Table 2):
the dispatcher needs to extract and unwrap 1, 5, or 10 environment
entries from its closure argument $clos before these values can
be passed to the proper surrogate function (Section 3). As anticipated in Section 4.1, however, a sequence-based representation of
closures can offer a significant improvement over the XML nodebased variant—both options are shown in Table 2 (rows “node” vs.
“sequence”). If this option is applicable, the saved node construction
and XPath navigation effort allows the defunctionalized invocation
of non-closed functions perform within a factor of 1.36 (Saxon) or 5
(BaseX) of the native implementation.
Environment Tables vs. Closure Inlining. Zooming out from the
level of individual function calls, we assessed the runtime contribution of dynamic function calls and closure elimination in the
context of a complete PL/SQL program (Figure 9). To this end, we
recorded time profiles while the program was evaluated against a
TPC-H instance of scale factor 1.0 (the profiles are based on PostgreSQL’s pg_stat_statements and pg_stat_user_functions
views [2]). Table 3 shows the cumulative times (in ms) over all query
and function invocations: one evaluation of dispatch_1(), includ-

ing the queries and functions it invokes, takes 44 429 ms/1 500 000 ≈
0.03 ms on average (column ENV). The execution time of the toplevel SELECT statement defines the overall execution time of the
program. Note that the cumulative times do not add up perfectly
since the inevitable PL/SQL interpreter overhead and the evaluation
of built-in functions are not reflected in these profiles.
Clearly, dispatch_1() dominates the profile as it embodies
the core of the configurable completion date computation. For
more than 50 % of the overall 1 500 000 orders, the dispatcher
needs to eliminate a closure of type τORDERS→DATE and extract the
binding for free variable comp from its environment before it can
invoke surrogate function `1 (). According to Section 4.2, closure
inlining is applicable here and column Inline indeed shows a
significant reduction of execution time by 18 % (dispatch_2()
does not benefit since it exclusively processes closures with empty
environments.)
Simplifications. A series of simplifications help to further reduce
the cost of queries with closures:
• Identify ` and ` (do not build closures with empty environment).
This benefits dynamic calls to closed and built-in functions.
• If Dispatch(n) is a singleton set, dispatch_n becomes superfluous as it is statically known which case branch will be taken.
• When constructing ` e1 · · · en , consult the types of the ei
to select the most efficient closure representation (recall our
discussion in Section 4).
For the PL/SQL program
of Figure 9, these simpliQuery/Function
Simplified
fications lead to the reSELECT o_orderkey,· · ·
36 010
moval of dispatch_2()
dispatch_1()
31 851
since the functional argu`1 ()
18 023
ment comp is statically
SELECT GREATEST(· · ·
4 770
known to be GREATEST in
`2 ()
2 923
the present example. Exe`3 ()
154
cution time is reduced by
an additional 11 % (see
column Simplified above). We mention that the execution time
now is within 19 % of a first-order formulation of the program—
this first-order variant is less flexible as it replaces the join with
(re-)configurable function table COMPLETION by an explicit hardwired CASE statement, however.
Avoiding Closure Construction. A closer look at the “native” row
of Table 2 shows that a growing number of free variables only has
moderate impact on BaseX’ and Saxon’s native implementations
of dynamic function calls: in the second-round experiments, both
processors expand the definitions of free variables inside the called
function’s body, effectively avoiding the need for an environment.
Unfolding optimizations of this kind can also benefit defunctionalization.
The core of such an inlining optimizer is a source-level query
rewrite in which closure construction and elimination cancel each
other out:
case ` e1 · · · en of
..
.
` $v1 · · · $vn ⇒ e
..
.

let $v1 := e1
..
.
$vn := en
return e

As this simplification depends on the closure label ` and the environment contents e1 , . . . , en to be statically known at the case · · · of
site, the rewrite works in tandem with unfolding transformations:
• Replace let-bound variables by their definitions if the latter are
considered simple (e.g., literals or closures with simple environment contents).

1
2
3
4
5
6
7
8

let $fib := (0,1,1,2,3,5,8,13,21,34)
let $keys := for $x in $fib return $x mod 2
for $x in for $k in distinct-values($keys)
let $group := $fib[((.) mod 2) = $k]
return `1 $group
return element group { case $x of
`1 $group ⇒ $group
}

Figure 20: First-order XQuery code for the example of Figure 18 (defunctionalization and unfolding rewrite applied).

defunctionalization
+ unfolding
+ simplifications

Oracle

Berkeley DB

Sedna

5.03
4.99
1.28

20.60
9.29
7.45

2.56
1.31
0.98

Table 4: Impact of unfolding and simplifications on the evaluation of group-by($seq, function($x) { $x mod 100 }) for
|$seq| = 104 . Averaged wall-clock time measured in seconds.

• Replace applications of function literals or calls to user-defined

non-recursive functions by the callee’s body in which function
arguments are let-bound.
Defunctionalization and subsequent unfolding optimization transform the XQuery group-by example of Figure 18 into the firstorder query of Figure 20. In the optimized query, the dispatchers dispatch_0 and dispatch_1 (cf. Figure 8) have been inlined.
The construction and elimination of closures with label `2 canceled
each other out.
Finally, the above mentioned simplifications succeed in removing
the remaining closures labeled `1 , leaving us with closure-less code.
Table 4 compares evaluation times for the original defunctionalized
group-by code and its optimized variants—all three XQuery 1.0
processors clearly benefit.

6.

More Related Work

Query defunctionalization as described here builds on a body of
work on the removal of higher-order functions in programs written in
functional programming languages. The representation of closures
in terms of first-order records has been coined as closure-passing
style [5]. Dispatchers may be understood as mini-interpreters that
inspect closures to select the next program step (here: surrogate
function) to execute, a perspective due to Reynolds [27]. Our
particular formulation of defunctionalization relates to Tolmach
and Oliva and their work on translating ML to Ada [33] (like the
target query languages we consider, Ada 83 lacks code pointers).
The use of higher-order functions in programs can be normalized
away if specific restrictions are obeyed. Cooper [12] studied such
a translation that derives SQL queries from programs that have a
flat list (i.e., tabular) result type—this constraint rules out tables of
functions, in particular. Program normalization is a runtime activity,
however, that is not readily integrated with existing query engine
infrastructure.
With HOMES [35], Benedikt and Vu have developed higherorder extensions to relational algebra and Core XQuery that add
abstraction (admitting queries of function type that accept queries
as parameters) as well as dynamic function calls (applying queries
to queries). HOMES’ query processor alternates between regular
database-supported execution of query blocks inside PostgreSQL or
BaseX and graph-based β-reduction outside a database system. In
contrast, defunctionalized queries may be executed while staying
within the context of the database kernel.

From the start, the design of FQL [10] relied on functions as
the primary query building blocks: following Backus’ FP language,
FQL offers functional forms to construct new queries out of existing
functions. Buneman et al. describe a general implementation technique that evaluates FQL queries lazily. The central notion is that of
suspensions, pairs hf, xi that represent the yet unevaluated application of function f to argument x. Note how group-by in Figure 8
mimics suspension semantics by returning closures (with label `1 )
that only get evaluated (via dispatch_0) once a group’s members
are required.
A tabular data model that permits function-valued columns has
been explored by Stonebraker et al. [32]. Such columns hold QUEL
expressions, represented either as query text or compiled plans.
Variables may range over QUEL values and an exec(e) primitive is
available that spawns a separate query processor instance to evaluate
the QUEL-valued argument e at runtime.
Finally, the Map-Reduce model [13] for massively distributed
query execution successfully adopts a function-centric style of query
formulation. Functions are not first-class, though: first-order userdefined code is supplied as arguments to two built-in functions map
and reduce—Map-Reduce builds on higher-order function constants
but lacks function variables.
Defunctionalized XQuery queries that rely on an element-based
representation of closures create XML fragments (closure construction) whose contents are later extracted via child axis steps (closure
elimination). When node construction and traversal meet like this,
the creation of intermediate fragments can be avoided altogether.
Such fusion techniques have been specifically described for XQuery [22]. Fusion, jointly with function inlining as proposed in [16],
thus can implement the case · · · of cancellation optimization discussed in Section 5. If cancellation is not possible, XQuery processors can still benefit from the fact that node identity and document
order are immaterial in the remaining intermediate fragments [19].

7.

Closure

We argue that a repertoire of literal function values, higher-order
functions, and functions in data structures can lead to particularly
concise and elegant formulations of queries. Query defunctionalization enables off-the-shelf first-order database engines to support
such a function-centric style of querying. Cast in the form of a
syntax-directed transformation of queries, defunctionalization is
non-invasive and affects the query processor’s front-end only (a
simple preprocessor will also yield a workable implementation).
Experiments show that the technique does not introduce an undue
runtime overhead.
Query defunctionalization applies to any query language that
(1) offers aggregate data structures suitable to represent closures and
(2) implements case discrimination based on the contents of such
aggregates. These are light requirements met by many languages
beyond XQuery and PL/SQL. It is hoped that our discussion of query
defunctionalization is sufficiently self-contained such that it can be
carried over to other languages and systems.
Acknowledgment. We dedicate this work to the memory of John C.
Reynolds ( April 2013).

References
[1] Oracle Berkeley DB XML. http://www.oracle.com/technetwork/
products/berkeleydb/index-083851.html.
[2] PostgreSQL 9.2. http://www.postgresql.org/docs/9.2/.
[3] Saxon. http://saxon.sourceforge.net/.
[4] Oracle Database PL/SQL Language Reference—11g Release 1 (11.1),
2009.
[5] A. Appel and T. Jim. Continuation-Passing, Closure-Passing Style. In
Proc. POPL, 1989.

[6] R. Bird and P. Wadler. Introduction to Functional Programming.
Prentice Hall, 1988.
[7] A. Bloss, P. Hudak, and J. Young. Code Optimizations for Lazy
Evaluation. Lisp and Symbolic Computation, 1(2), 1988.
[8] S. Boag, D. Chamberlin, M. Fernández, D. Florescu, J. Robie, and
J. Siméon. XQuery 1.0: An XML Query Language. W3C Recommendation, 2010.
[9] P. Boncz, T. Grust, M. van Keulen, S. Manegold, J. Rittinger, and
J. Teubner. MonetDB/XQuery: A Fast XQuery Processor Powered by
a Relational Engine. In Proc. SIGMOD, 2006.
[10] P. Buneman, R. Frankel, and R. Nikhil. An Implementation Technique
for Database Query Languages. ACM TODS, 7(2), 1982.
[11] D. Chamberlin, D. Florescu, J. Robie, J. Siméon, and M. Stefanescu.
XQuery: A Query Language for XML. W3C Working Draft, 2001.
[12] E. Cooper. The Script-Writers Dream: How to Write Great SQL in
Your Own Language, and be Sure it Will Succeed. In Proc. DBPL,
2009.
[13] J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing
on Large Clusters. In Proc. OSDI, 2004.
[14] D. Florescu and D. Kossmann. Storing and Querying XML Data Using
an RDBMS. IEEE Data Engineering Bulletin, 22(3), 1999.
[15] A. Fomichev, M. Grinev, and S. Kuznetsov. Sedna: A Native XML
DBMS. In Proc. SOFSEM, 2006.
[16] M. Grinev and D. Lizorkin. XQuery Function Inlining for Optimizing
XQuery Queries. In Proc. ADBIS, 2004.
[17] C. Grün, A. Holupirek, and M. Scholl. Visually Exploring and
Querying XML with BaseX. In Proc. BTW, 2007. http://basex.
org.
[18] T. Grust. Monad Comprehensions: A Versatile Representation for
Queries. In The Functional Approach to Data Management – Modeling,
Analyzing and Integrating Heterogeneous Data. Springer, 2003.
[19] T. Grust, J. Rittinger, and J. Teubner. eXrQuy: Order Indifference in
XQuery. In Proc. ICDE, 2007.
[20] T. Grust, N. Schweinsberg, and A. Ulrich. Functions are Data Too
(Software Demonstration). In Proc. VLDB, 2013.
[21] T. Johnsson. Lambda Lifting: Transforming Programs to Recursive
Equations. In Proc. IFIP, 1985.
[22] H. Kato, S. Hidaka, Z. Hu, K. Nakano, and I. Yasunori. ContextPreserving XQuery Fusion. In Proc. APLAS, 2010.
[23] P. Landin. The Mechanical Evaluation of Expressions. The Computer
Journal, 6(4):308–320, 1964.
[24] Z. Liu, M. Krishnaprasad, and A. V. Native XQuery Processing in
Oracle XMLDB. In Proc. SIGMOD, 2005.
[25] S. Melnik, A. Gubarev, J. Long, G. Romer, S. Shivakumar, M. Tolton,
and T. Vassilakis. Dremel: Interactive Analysis of Web-Scale Datasets.
PVLDB, 3(1), 2010.
[26] F. Pottier and N. Gauthier. Polymorphic Typed Defunctionalization.
In Proc. POPL, 2004.
[27] J. Reynolds. Definitional Interpreters for Higher-Order Programming
Languages. In Proc. ACM, 1972.
[28] J. Robie, D. Chamberlin, J. Siméon, and J. Snelson. XQuery 3.0: An
XML Query Language. W3C Candidate Recommendation, 2013.
[29] Z. Shao and A. Appel. Space-Efficient Closure Representations. In
Proc. Lisp and Functional Programming, 1994.
[30] Z. Shao and A. Appel. Efficient and Safe-for-Space Closure Conversion. ACM TOPLAS, 22(1), 2000.
[31] Database Language SQL—Part 2: Foundation (SQL/Foundation).
ANSI/ISO/IEC 9075, 1999.
[32] M. Stonebraker, E. Anderson, E. Hanson, and B. Rubenstein. QUEL
as a Data Type. In Proc. SIGMOD, 1984.
[33] A. Tolmach and D. Oliva. From ML to Ada: Strongly-Typed Language
Interoperability via Source Translation. J. Funct. Programming, 8(4),
1998.
[34] Transaction Processing Performance Council. TPC-H, a DecisionSupport Benchmark. http://tpc.org/tpch/.
[35] H. Vu and M. Benedikt. HOMES: A Higher-Order Mapping Evalution
System. PVLDB, 4(12), 2011.
[36] Y. Zhang and P. Boncz. XRPC: Interoperable and Efficient Distributed
XQuery. In Proc. VLDB, 2007.

Appendix
A.

Defunctionalization for XQuery

This appendix elaborates the details of defunctionalization for XQuery 3.0. The particular formulation we follow here is a deliberate
adaptation of the transformation as it has been described by Tolmach
and Oliva [33].
We specify defunctionalization in terms of a syntax-directed
traversal, QJeK, over a given XQuery 3.0 source query e (conforming to Figure 6). In general, e will contain a series of function
declarations which precede one main expression to evaluate. Q
calls on the auxiliary DJ·K and EJ·K traversals to jointly transform
declarations and expressions—this makes Q a whole-query transformation [26] that needs to see the input query in its entirety. All
three traversal schemes are defined in Figure 21.
E features distinct cases for each of the syntactic constructs in
the considered XQuery 3.0 subset. However, all cases but those
labeled (1)–(3) merely invoke the recursive traversal of subexpressions, leaving their input expression intact otherwise. The three
cases implement the transformation of literal functions, named function references, and dynamic function calls. We will now discuss
each of them in turn.
Case (1): Literal Functions. Any occurrence of a literal function,
say f = function($x1 ,. . . ,$xn ) { e }, is replaced by a closure
constructor. Meta-level function label () generates a unique label `
which closure elimination will later use to identify f and evaluate its
body expression e; see case (3) below. The evaluation of e depends
on its free variables, i.e., those variables that have been declared in
the lexical scope enclosing f . We use meta-level function fv () to
identify these variables $v1 , . . . , $vm and save their values in the
closure’s environment. At runtime, when the closure constructor is
encountered in place of f , the closure thus captures the state required
to properly evaluate subsequent applications of f (recall Section 2).
Note that defunctionalization does not rely on functions to be pure:
side-effects caused by body e will also be induced by EJeK.
To illustrate, consider the following XQuery 3.0 snippet, taken
from the group-by example in Figure 5:
for $k in distinct-values($keys)
return
function() { $seq[$key(.) = $k] } .
We have fv (function() { $seq[$key(.) = $k] }) = $k, $key,
$seq. According to E and case (1) in particular, the snippet thus
defunctionalizes to
for $k in distinct-values($keys)
return
`1 $k $key $seq
where `1 denotes an arbitrary yet unique label.
If we assume that the free variables are defined as in the example
of Figure 5, the defunctionalized variant of the snippet will evaluate
to a sequence of two closures:
( `1 0

`2

(0,1,1,2,. . . ) ,

`1

1

`2

(0,1,1,2,. . . ) ) .

These closures capture the varying values 0, 1 of the free iteration
variable $k as well as the invariant values of $key (bound to a
function and thus represented in terms of a closure with label `2 )
and $seq (= (0,1,1,2,. . . )).
Since we will use label `1 to identify the body of the function
literal function() { $seq[$key(.) = $k] }, case (1) saves this
label/body association in terms of a case · · · of branch (see the
assignment to branch in Figure 21). We will shed more light
on branch and lifted when we discuss case (3) below.

Case (2): Named Function References. Any occurrence of an
expression name#n, referencing function name of arity n, is replaced by a closure constructor with a unique label `. In XQuery,
named functions are closed as they are exclusively declared in a
query’s top-level scope—either in the query prolog or in an imported module [28]—and do not contain free variables. In case (2),
the constructed closures thus have empty environments. As before, a case · · · of branch is saved that associates label ` with function name.
Case (3): Dynamic Function Calls. In case of a dynamic function
call e(e1 ,. . . ,en ), we know that expression e evaluates to some
functional value (otherwise e may not occur in the role of a function
and be applied to arguments).11 Given our discussion of cases (1)
and (2), in a defunctionalized query, e will thus evaluate to a closure,
say ` x1 · · · xm (m > 0), that represents some function f .
In the absence of code pointers, we delegate the invocation of the
function associated with label ` to a dispatcher, an auxiliary routine
that defunctionalization adds to the prolog of the transformed query.
The dispatcher
(i) receives the closure as well as e1 , . . . , en (the arguments of
the dynamic call) as arguments, and then
(ii) uses case · · · of to select the branch associated with label `.
(iii) The branch unpacks the closure environment to extract the
bindings of the m free variables (if any) that were in place
when f was defined, and finally
(iv) invokes a surrogate function that contains the body of the
original function f , passing the e1 , . . . , en along with the
extracted bindings (the surrogate function thus has arity n+m).
Re (i) and (ii). In our formulation of defunctionalization for
XQuery, a dedicated dispatcher is declared for all literal functions and named function references that are of the same arity.
The case · · · of branches for the dispatcher for arity n are collected
in set Dispatch(n) while E traverses the input query (cases (1)
and (2) in Figure 21 add a branch to Dispatch(n) when an n-ary
functional value is transformed). Once the traversal is complete, Q
adds the dispatcher routine to the prolog of the defunctionalized
query through declare dispatch(n, Dispatch(n)). This meta-level
function, defined in Figure 22, emits the routine dispatch_n which
receives closure $clos along with the n arguments of the original
dynamic call. Discrimination on the label ` stored in $clos selects
the associated branch. Because dispatch_n dispatches calls to any
n-ary function in the original query, we declare it with a polymorphic signature featuring XQuery’s most polymorphic type item()*.
The PL/SQL variant of defunctionalization, discussed in Section 3.1,
relies on an alternative approach that uses typed dispatchers.
Any occurrence of a dynamic function call e(e1 ,. . . ,en ) is replaced by a static call to the appropriate dispatcher dispatch_n.
Figure 8 (in the main text) shows the defunctionalized query
for the XQuery group-by example of Figure 5. The original query
contained literal functions of arity 0 (in line 8) as well as arity 1
(in line 12). Following case (1), both have been replaced by closure
constructors (with labels `1 and `2 , respectively, see lines 16
and 20 in Figure 8). function($x) { $x mod 2 } is closed: its
closure (label `2 ) thus contains an empty environment. Dynamic
calls to both functions have been replaced by static calls to the
dispatchers dispatch_0 or dispatch_1. For the present example,
Dispatch(0) and Dispatch(1) were singleton sets such that both
dispatchers contain case · · · of expressions with one branch only.
(For an example of a dispatcher with three branches, refer to the
PL/SQL function dispatch_1 in Figure 9, line 19.)
11 Note

that EJ·K defines a separate case for static function calls of the
form name(e1 ,. . . ,en ).

DJdeclare function name($x1 , . . . ,$xn ) { e }K

=

declare function name($x1 , . . . ,$xn ) { EJeK }

EJfor $v in e1 return e2 K
EJlet $v := e1 return e2 K
EJ$vK
EJif (e1 ) then e2 else e3 K
EJ(e1 , . . . ,en )K
EJe/a::tK
EJelement n { e }K
EJe1 [e2 ]K
EJ.K
EJname(e1 , . . . ,en )K
EJfunction($x1 as t1 , . . . ,$xn as tn ) as t { e }K

=
=
=
=
=
=
=
=
=
=
=

EJname#nK

=

for $v in EJe1 K return EJe2 K
let $v := EJe1 K return EJe2 K
$v
if (EJe1 K) then EJe2 K else EJe3 K
(EJe1 K, . . . ,EJen K)
EJeK/a::t
element n { EJeK }
EJe1 K[EJe2 K]
.
name(EJe1 K, . . . ,EJen K)
` $v1 · · · $vm
()
Dispatch(n) Dispatch(n) ∪ {branch}
Lifted Lifted ∪ {lifted}
where
` = label(n)
$v1 , . . . , $vm = fv (function($x1 as t1 , . . . ,$xn as tn ) as t { e })
branch = ` $v1 · · · $vm ⇒
`($b1 , . . . ,$bn ,$v1 , . . . ,$vm )
lifted = declare function `(
$x1 as t1 , . . . ,$xn as tn ,$v1 , . . . ,$vm ) as t
{ EJeK };
`
()
Dispatch(n) Dispatch(n) ∪ {branch}
where
` = label(n)
branch = ` ⇒ name($b1 , . . . ,$bn )

EJe(e1 , . . . ,en )K

=

dispatch_n(EJeK,EJe1 K, . . . ,EJen K)

QJd1 ; . . . ;dn ; eK

=

∀ i ∈ dom(Dispatch): declare dispatch(i, Dispatch(i))
Lifted
DJd1 K; . . . ;DJdn K; EJeK

()

Figure 21: Defunctionalization of XQuery 3.0 function declarations (D), expressions (E) and queries (Q).
declare dispatch(n, {case 1 , . . . , case k }) ≡
1
2
3
4
5
6
7
8
9

declare function dispatch_n(
$clos as closure,
$b1 as item()*,. . . , $bn as item()*) as item()*
{
case $clos of
case
.. 1
.
case k
};

Figure 22: Declaring a dispatcher for n-ary functional values.
Re (iii) and (iv). Inside its dispatcher, the case branch for the closure
` x1 · · · xm for function f invokes the associated surrogate
function, also named `. The original arguments e1 , . . . , en are
passed along with the x1 , . . . , xm . Surrogate function ` incorporates
f ’s body expression and can thus act as a “stand-in” for f . We

declare the surrogate function with the same argument and return
types as f —see the types t and t1 , . . . , tn in case (3) of Figure 21.
The specific signature for ` ensures that the original semantics of f
are preserved (this relates to XQuery’s function conversion rules [28,
§3.1.5.2]).
While f contained m free variables, ` is a closed function as
it receives the m bindings as explicit additional function parameters (surrogate function ` is also known as the lambda-lifted variant
of f [21]). When case (1) transforms a literal function, we add its surrogate to the set Lifted of function declarations. When case (2) transforms the named reference name#n, Lifted remains unchanged:
the closed function name acts as its own surrogate because there
are no additional bindings to pass. Again, once the traversal is complete, Q adds the surrogate functions in set Lifted to the prolog of
the defunctionalized query. Returning to Figure 8, we find the two
surrogate functions `1 and `2 at the top of the query prolog (lines 1
to 4).

