Associative Array Model of
SQL, NoSQL, and NewSQL Databases
Jeremy Kepner1,2,3, Vijay Gadepally1,2, Dylan Hutchison4, Hayden Jananthan3,5,
Timothy Mattson6, Siddharth Samsi1, Albert Reuther1
1
2
MIT Lincoln Laboratory, MIT Computer Science & AI Laboratory, 3MIT Mathematics Department, 4University of Washington
Computer Science Department, 5Vanderbilt University Mathematics Department, 6Intel Corporation
SQL, NoSQL, and NewSQL would enable their
interoperability. Such a mathematical model is the primary
goal of this paper.

Abstract—The success of SQL, NoSQL, and NewSQL databases
is a reflection of their ability to provide significant functionality
and performance benefits for specific domains, such as financial
transactions, internet search, and data analysis. The BigDAWG
polystore seeks to provide a mechanism to allow applications to
transparently achieve the benefits of diverse databases while
insulating applications from the details of these databases.
Associative arrays provide a common approach to the
mathematics found in different databases: sets (SQL), graphs
(NoSQL), and matrices (NewSQL). This work presents the SQL
relational model in terms of associative arrays and identifies the
key mathematical properties that are preserved within SQL.
These
properties
include
associativity,
commutativity,
distributivity, identities, annihilators, and inverses. Performance
measurements on distributivity and associativity show the impact
these properties can have on associative array operations. These
results demonstrate that associative arrays could provide a
mathematical model for polystores to optimize the exchange of
data and execution queries.

SQL Era

NewSQL Era

Polystore Era

BigDAWG Polystore
[Elmore 2015]

NoSQL
Relational Model
[Codd 1970]

NewSQL
[Cattell 2010]
SQL
Google BigTable
[Chang 2006]
NewSQL

Figure 1. Evolution of SQL, NoSQL, NewSQL, and polystore

databases. Each class of database delivered new mathematics,
functionality, and performance focused on new application areas.

SQL, NoSQL, and NewSQL databases are designed for
specific applications, have distinct data models, and rely on
different underlying mathematics (see Figure 2). Because of
their differences, each database has unique strengths that are
well suited for particular workloads. It is now recognized that
special-purpose databases can be 100x faster for a particular
application than a general-purpose database [Kepner 2014]. In
addition, the availability of high performance data analysis
platforms, such as the MIT SuperCloud [Reuther 2013, Prout
2015], allows high performance databases to share the same
hardware platform without sacrificing performance.

Keywords-Associative Array Algebra; SQL; NoSQL; NewSQL;
Set Theory; Graph Theory; Matrices; Linear Algebra

I.

NoSQL Era

INTRODUCTION

Relational or SQL (Structured Query Language) databases
[Codd 1970, Stonebraker 1976] such as PostgreSQL, MySQL,
and Oracle have been the de facto interface to databases since
the 1980s (see Figure 1) and are the bedrock of electronic
transactions around the world. More recently, key-value stores
(NoSQL databases) such as Google BigTable [Chang 2008],
Apache Accumulo [Wall 2015], and MongoDB [Chodorow
2013] have been developed for representing large sparse tables
to aid in the analysis of data for Internet search. As a result, the
majority of the data on the Internet is now analyzed using keyvalue stores [DeCandia et al 2007, Lakshman & Malik 2010,
George 2011]. In response to similar performance challenges,
the relational database community has developed a new class
of databases (NewSQL) such as C-Store [Stonebraker 2005],
H-Store [Kallman 2008], SciDB [Balazinska 2009], VoltDB
[Stonebraker 2013], and Graphulo [Hutchison 2015] to support
new analytics capabilities within a database. The SQL,
NoSQL, and NewSQL concepts have also been blended in
hybrid processing systems, such as Apache Pig [Olston 2008],
Apache Spark [Zaharia 2010], and HaLoop [Bu 2010]. An
effective mathematical model that encompasses the concepts of

SQL
SQL

NoSQL
NoSQL

NewSQL
NewSQL

Polystore
Future
BigDAWG

Example

PostgreSQL

Accumulo

SciDB

Application

Transactions

Search

Analysis

All

Data Model

Relational
Tables

Key-Value
Pairs

Sparse
Matrices

Associative
Arrays

Set
Theory

Graph
Theory

Linear
Algebra

Associative
Algebra

Math
Consistency
Volume
Velocity
Variety
Analytics
Usability

Figure 2. Focus areas of SQL, NoSQL, NewSQL, and Polystore

databases.

This material is based upon work supported by the National Science Foundation under Grant No. DMS-1312831. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

1

The recognition of “one size does not fit all” [Stonebraker
& Çetintemel 2005] has led to the need for polystore databases,
such as BigDAWG [Duggan 2015, Elmore 2015], that can
contextualize queries and cast data between multiple databases
so that a user can employ the best database for a particular task
(see Figure 3). To achieve this goal, polystore databases need
to bridge SQL, NoSQL, and NewSQL databases. The
Dynamic Distributed Dimensional Data Model (D4M)
technology [Kepner 2012] was developed to provide a linear
algebraic interface to graphs stored in NoSQL databases [Byun
2012, Kepner 2013].
Subsequently, D4M has been
successfully used with both SQL [Wu 2014, Gadepally 2015]
and NewSQL [Samsi 2016] databases. The effectiveness of
D4M to seamlessly interact with these diverse databases rests
on its associative array algebra [Kepner & Chaidez 2013,
Kepner & Chaidez 2014, Kepner & Jansen 2016] that provides
a mathematics that spans sets, graphs, and matrices. The
ability of D4M (and Myria [Halperin 2014]) to bridge multiple
databases has laid the foundation for the polystore database
concept.
Visualizations

and their corresponding operations are defined in terms of
associative arrays. Fifth, the mathematical properties required
by graph algorithms and matrix mathematics are confirmed for
relational operations. Finally, performance results illustrating
the impact of these properties are presented and discussed.
II.

The relational model, based on set theory, is a key
mathematical foundation for SQL databases. The relational
model effectively consists of relational algebra, relational
calculus, and the structured query language (SQL) that balance
the theoretical, implementation, and systems design aspects of
databases. The relational model is well covered in the
literature [Maier 1983, Codd 1990, Abiteboul 1995]; only the
most relevant aspects of the model are reviewed here. Some of
the more significant mathematical contributions of the
relational model to databases include
(R1) Relations: a mathematical definition of database tables
sufficient for their representation without constraining
their implementation;
(R2) Query semantics: a mathematical definition of operations
on relations sufficient for proving the correctness of
database queries;
(R3) Proof of the equivalence of declarative and procedural
syntaxes over the above definitions that has enabled the
use of declarative semantics for database users and
procedural semantics for database builders [Codd 1972].

Applications

BigDAWG Polystore Common Interface
Analytic
Translator

Analytic
Translator

Data
Translator
SQL
SQL

Analytic
Translator

Data
Translator
NoSQL
NoSQL

Of these results, (R3) has been enormously important, but
would not be possible without (R1) and (R2). (R3) has been
critical to the success of SQL databases that follow the
relational model. (R3) has enabled the successful coexistence
of separate interfaces and languages for users and
implementers, with the confidence that neither would create a
fundamental mathematical contradiction for the other.
The relational model is based on balancing mathematical
rigor with implementation practicality.
Too much
mathematical rigor burdens a database implementation with
unnecessary mathematics. Too little mathematical rigor makes
it is difficult to know if a database implementation will work.
As with all good compromises, there have been advocates for
improvement on both sides. As cited earlier, many new
databases under the names of NoSQL and NewSQL differ from
the relational model to meet new performance and analysis
demands. Likewise, there is extensive mathematical work on
modifications to the relational model to increase its
mathematical rigor [Imieliński 1984a, Imieliński 1984b,
Kanellakis 1989, Tsalenko 1992, Plotkin 1998, Priss 2006, van
Emden 2006, Litak 2014, Hutchison 2016]. One motivation
for increasing the mathematical rigor [Kelly 2012] is to align
relations with well-established Zermelo-Fraenkel Choice (ZFC)
set theory [Zermelo 1908, Fraenkel 1922] that is the foundation
for a number of branches of mathematics.
The emerging diversity of databases has initiated a dialogue
regarding the traditional relational model and the newer graph
and matrix models. This dialogue is akin to the earlier
declarative and procedural conversation that culminated in the

NewSQL
NewSQL

Figure 3. BigDAWG polystore database architecture.

Analytic
translators contextualize queries to specific databases.
Data
translators cast data between databases.

Mathematics is one of the most important differences
among SQL, NoSQL, and NewSQL databases (see Figure 4).
The relational algebra found in SQL databases is based upon
selection, union, and intersection of special sets called
relations.
NoSQL is designed for analyzing sparse
relationships among data and relies on graph theory and graph
analysis. NewSQL databases use matrices and linear algebra to
look for patterns in numeric data.
SQL
Set Operations
out
vertex

edge
link

in
vertex

001

alice

cited

bob

002

bob

cited

alice

003

alice

cited

carl

SELECT ∗ WHERE
out vertex=alice

NoSQL
Graph Operations
bob

NewSQL
Matrix Operations

AT!

ATv

v

bob

cited

alice

carl

RELATIONS

à

cited

carl
alice

Figure 4. Mathematics of breadth-first search for SQL, NoSQL, and

NewSQL databases.

The approach to developing an associative array model of
the above databases is as follows. First, the relevant aspects of
relations are summarized. Second, the sparse matrix operations
that encompass graph algorithms and matrix mathematics are
given. Third, the associative array model that describes
NoSQL and NewSQL databases is described. Fourth, relations

2

relational model. This work seeks similar progress by
demonstrating that an associative array model can provide

Given m×n matrices A, B, and C, element-wise matrix
addition (and its graph equivalent: weighted graph union) is
denoted
C=A⊕B
or more specifically
C(i,j) = A(i,j) ⊕ B(i,j)
where i ∈ {1,...,m} and j ∈ {1,...,n}. Element-wise matrix
multiplication (and its graph equivalent, weighted graph
intersection) is denoted
C=A⊗B
or more specifically
C(i,j) = A(i,j) ⊗ B(i,j)
For a m×l matrix A, l×n matrix B, and m×n matrix C, matrix
multiplication (and its graph equivalent, multisource weighted
breadth-first search) combines addition and multiplication and
is written
C = A ⊕.⊗ B = A B
or more specifically

(A1) Associative arrays: a mathematical definition of database
tables for SQL, NoSQL, and NewSQL databases that
accurately describes their implementation;
(A2) Associative array algebra: a mathematical definition of
database queries and computations that accurately
describes the operations performed by SQL, NoSQL, and
NewSQL databases;
(A3) Equivalence of relational and array syntaxes over the
above definitions that enables the use of either in a SQL,
NoSQL, or NewSQL database.
Of these results, (A3) has the most potential to impact
polystore databases. Likewise, (A3) would not be possible
without (A1) and (A2).
The mathematical challenge of creating an associative array
model encompassing SQL, NoSQL, and NewSQL is
reconciling their mathematical differences. SQL databases
focus on set operations (subsets, unions, intersections), and the
relational model is based on an elegant approach to set theory
that provides only those attributes of formal set theory that are
required for SQL databases. NoSQL and NewSQL databases
focus on high performance data analysis (graph algorithms and
matrix mathematics) that require mathematical properties such
as associativity, commutativity, distributivity, identities,
annihilators, and inverses. Reproducing the balance that led to
the success of the relational model in another model is difficult.
Detailed analysis of this balance leads down the same welltraveled path of those who have advocated for both more or
less mathematical rigor in the relational model. Instead, just as
Alexander solved the problem of the Gordian Knot, this paper
asserts the desired outcome (relations are associative arrays)
and the implications of this assertion are then addressed.
III.

C(i,j) = ⊕k A(i,k) ⊗ B(k,j)
where k ∈ {1,...,l}. Finally, the matrix transpose (and its graph
equivalent, graph edge reversal) is denoted
T
A(j,i) = A (i,j)
The above operations have been found to enable a wide
range of graph algorithms and matrix mathematics while also
preserving the required vector-space properties [Heaviside
1887, Peano 1888] such as commutativity
A⊕B=B⊕A
A⊗B=B⊗A
T
T
T
(A B) = B A
associativity
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
(A ⊗ B) ⊗ C = A ⊗ (B ⊗ C)
(A B) C = A (B C)
distributivity
A ⊗ (B ⊕ C) = (A ⊗ B) ⊕ (A ⊗ C)
A (B ⊕ C) = (A B) ⊕ (A C)
and the additive and multiplicative identities
A⊕ =A
A⊗ =A
A
=A
where is a matrix of all 0, is a matrix of all 1, and is a
matrix with 1 along its diagonal. Furthermore, these matrices
possess a multiplicative annihilator
A⊗ =
A
=
Their corresponding inverses may also exist
A
⊕ -A
=
A(i,j) ⊗ A(i,j)-1 =
A
A-1
=
when ( ,⊕,0) and ( ,⊗,1) are groups (i.e., have inverses)
[Galois 1832].

GRAPHS AND MATRICES

The duality between graph algorithms and matrix
mathematics (or sparse linear algebra) has been extensively
covered in the literature and is summarized in the cited text
[Kepner & Gilbert 2011]. This text has further spawned the
development of the GraphBLAS math library standard
(GraphBLAS.org)[Mattson 2013] that is described in the series
of proceedings [Mattson 2014a, Mattson 2014b, Mattson 2015,
Buluc 2015, Buluc 2016]. The essence of the graph algorithms
and matrix mathematics duality are three operations: elementwise addition, element-wise multiplication, and matrix
multiplication. In brief, an m×n matrix A is defined as a
mapping from pairs of integers to values
A: {1,...,m}×{1,...,n} →
where
is the set of values that form a semiring
( ,⊕,⊗,0,1)[Kepner & Jansen 2016] with addition operation
⊕, multiplication operation ⊗, additive identity/multiplicative
annihilator 0, and multiplicative identity 1. The construction of
a sparse matrix is denoted
A = (I,J,V)
where I, J, V are vectors of the rows, columns, and values of
the nonzero elements of A.

3

Most significantly, the properties of matrices are determined
by the properties of the set of values . In other words, the
properties of determine the properties of the corresponding
matrices.
The above properties are required for the
development and implementation of data analysis algorithms.
IV.

associative array because each row label (or row key) and each
column label (or column key) in A is unique. The size of the
associative array is m = 4 and n = 4.

V.

ASSOCIATIVE ARRAYS

Associative arrays can be rigorously built up from ZFC set
theory, groups, and semirings, culminating with the
observation that linear algebra is a specialization of associative
array algebra. How associative arrays encompass graphs,
matrices, NoSQL, and NewSQL is described extensively in
[Kepner & Jansen 2016] and is only summarized here.
As described earlier, sparse matrices are a common
representation used for both graphs and linear algebra. The
standard definition of sparse matrices requires generalization to
encompass the tables found in SQL, NoSQL, and NewSQL
databases. The primary difference between a matrix and an
associative array is the specification of the row and column
indices. In a matrix, the row and column indices are drawn
from the sets of integers {1,...,m} and {1,...,n}. Associative
array row and column “keys” can be drawn from any strict,
totally ordered set (i.e., any uniquely sortable set). Associative
array row and column keys can be negative numbers, real
numbers, or character strings. The true dimensions of an
associative array are often very large (e.g., all possible finite
strings). Instead, the size of an associative array is more
commonly used and is defined as the number of nonzero rows,
m, and the number of nonzero columns, n. An equally
important quantity is the number of nonzeros in an associative
array, which is denoted by the function nnz(). The size and nnz
of an associative array can change through the course of a
calculation. There are no size constraints on associative array
operations.
Element-wise
addition,
element-wise
multiplication, and array multiplication are valid for
combinations of associative arrays of any size.
Associative arrays derive much of their power from their
ability to represent data intuitively in easily understandable
tables. Consider the list of songs and the various features of
those songs shown in Figure 5. The tabular arrangement of the
data shown in Figure 5 is an associative array (denoted A). This
arrangement is similar to those widely used in spreadsheets and
databases. Figure 5 illustrates two properties of associative
arrays that may differ from other two-dimensional
arrangements of data. First, each row key and each column key
in A unique, to allow rows and columns to be queried
efficiently. Second, associative arrays do not store rows or
columns that are entirely empty, to allow insertion, selection,
and deletion of data to be performed by associative array
addition, multiplication, and products. These properties are
what makes A an associative array and allows A to be
manipulated as a spreadsheet, database, matrix, or graph.
053013ktnA1
053013ktnA2
063012ktnA1
082812ktnA1

Artist
Bandayde
Kastle
Kitten
Kitten

Date
2013-05-30
2013-05-30
2010-06-30
2012-08-28

Duration
5:14
3:07
4:38
3:25

RELATIONS AS ASSOCIATIVE ARRAYS

A first step in adapting the relational model to associative
arrays is to define a relation in terms of associative
arrays. This step is done by asserting a relation is an
associative array and considering the implications of the
assertion.
Operationally, asserting that relations are
associative arrays means that the row keys of an associative
array are arbitrary but distinct at the time of input and output of
a relational operation. Using this definition, some of the
implications can be illustrated by a series of common questions
about relations, specifically, whether or not relations are sets,
tuples, indices, ordered, multisets (bags), or sequences.
Are relations ZFC sets? Relations in the traditional
relational model require some, but not all, properties of ZFC set
semantics. The values of associative arrays are ZFC sets. The
keys of associative arrays are ZFC sets. Expressing relations as
associative arrays means that they adhere to ZFC set semantics.
Are relations tuples? A row of an associative array is
mathematically a row vector. Mathematically, tuples are also
vectors so relations are tuples.
Are relations indices? In the past, it has been efficient in
both space and time if a relation can be represented as a tuple
of integer indices that connect to values in a table. Today, this
implementation guidance is less important and it is
mathematically more flexible to treat relations as tuples of their
actual values, which is how they are defined in associative
arrays.
Are relations ordered sets? Mathematically, ordering of
rows or columns is not required for either relations or
associative arrays. However, as a practical matter, ordering is
required for real database tables, and there is no negative
mathematical consequence for requiring rows and columns to
be ordered sets. Thus, associative array rows and columns are
ordered sets.
Are relations multisets (bags)? Identical rows are a reality
in many databases, implying that relations are multi-sets. The
row key of an associative array distinguishes rows with
identical values.
Are relations sequences? A practical approach to
implementing multiple identical rows is to view relations as a
mathematical sequence instead of a set. In a sequence, each
row is paired with a number that sets the order of the rows;
hence, the term sequence ID in SQL databases. A sequence ID
is effectively equivalent to the row key in an associative array.
NoSQL databases embrace this view to the point of fully
exposing the unique sequence ID as a user-controlled
parameter.
Defining relations as associative arrays provides new
answers to the above questions. However, new questions arise
that also must be addressed. Primary amongst these are the
differences among 0, ∅, null, empty entries, and empty rows
and columns.
To provide the necessary mathematical
properties for matrix calculations, associative arrays follow the
conventions set by sparse matrices that define 0 as the nonstored element. More specifically, the value corresponding to

Genre
Electronic
Electronic
Rock
Pop

Figure 5. Tabular arrangement of a list of songs and the various

features of those songs into an associative array A. The array A is an

4

or more specifically

the ⊕ identity and the ⊗ annihilator is the non-stored element.
Because of its mathematical properties, the 0 element is unique
and there is no distinction between 0 and “no data” or null. As
a practical matter, when it is desired to distinguish between
these states, usually a workaround can be found. A unique 0 is
useful as it does not require that exceptions be defined for
every operation.
VI.

P(iA,iB) = &j (A(iA,j) = B(iB,j))
where iA ∈ IA and iB ∈ IB. Likewise, P can computed as
P(iA,iB) = δ(A(iA,:),B(iB,:))
where δ(,) is the Kronecker delta function. If every nonzero
row in A has a nonzero row in P and if every row in B has a
nonzero column in P, then
A~B
Using the convention of restricting to the nonzero rows of A
and B, P can also be computed simply as
T
P = AB
where ⊕.⊗ is &.= or δ(,) is implied. Likewise, by the
transpose identity
T
T
P = BA
The stronger version of equivalence can obtained by imposing
the further requirement that if P is stripped of its row and
column keys, it forms a symmetric matrix where
T
P =P
Using this definition of equivalence allows most relational
operations to be defined in terms of variations on the
construction of the permutation matrix P.

QUERIES AS ASSOCIATIVE ARRAY ALGEBRA

Relational algebra and SQL have defined a wide range of
operations that are useful for executing queries on relations.
Some of these operations are union ∪, intersection ∩, set
difference \, Cartesian product ×, project Π, rename ρ, select σ,
natural join ⋈, equijoin ⋈k, theta join ⋈θ, left outer join ⟕,
right outer join ⟖, full outer join ⟗, antijoin ▷, extended
projection, and aggregation. In discussions of the relational
model, the list of operations most commonly discussed include
union ∪, intersection ∩, set difference \, project Π, rename ρ,
select σ, and theta join ⋈θ.
In practice, all computations are restricted to the nonzero
rows and nonzero columns of the associative array
representation of relations. . Likewise, since the row keys in
an associative array representation of a relation are arbitrary, it
is assumed that wherever convenient the row keys of any
associative array can be made distinct. Thus, it is common for
there to be no operations that require the comparison of two
arbitrary values. In many computations, the only operations
that need to be specified are the identities
v⊕ 0=v
v⊗1=v
and the additive inverse and multiplicative annihilator
v ⊕ -v = 0
v⊗0=0
where v ∈ . Results that can be proven under the above
conditions will hold for a wide variety of ⊕ and ⊗ operations.

B. Project
The project operation picks sets of J columns from a
relation A and is typically written in relational algebra as
ΠJ(A)
The SQL equivalent is
SELECT J(1),...,J(n) FROM A
or simply
A.J(1),...,J(n)
In terms of associative array algebra, project can be
accomplished via many expressions, such as
A ⊕.⊗ (J,J,1) or A (J,J) or A (J) or A(:,J)
given the shorthand notation for the identity array
(J,J,1) = (J,J) = (J)
and the Matlab notation A(:,J) for column selection.

A. Equivalence
In dealing with any new data representation, the first step is
to define when two representations are equivalent [Howe
2005]. Relational equivalence for associative arrays is denoted
A~B
and implies every row in A has an identical row in B, and every
row in B has an identical row in A. This definition allows
multiple identical rows. A stronger version further requires
exactly the same number of identical rows in A and B.
Equivalence can be computed via the equivalency permutation
array P of the nonzero rows in A to the nonzero rows in B
where P(iA,iB) = 1 (and 0 otherwise) if row A(iA,:) is the same
as row B(iB,:). P can be computed by using a variety of
notational conventions

C. Rename
The rename operation picks columns J from a relation A
and assigns them new names J'. Rename is written in relational
algebra as
ρJ/J'(A)
The SQL equivalent is
SELECT J(1),...,J(n) AS J'(1),...,J'(n) FROM A
In associative array algebra, rename can be accomplished with
the many expressions, such as
A ⊕.⊗ (J,J',1) or A (J,J')

T

P = A (A ⊕.⊗ B ) B
T
= A (A &.= B ) B
where ⊕ is &, ⊗ is =, and
IA is the set of nonzero rows in A
A = (IA, IA,1) is the identity array over IA
IB is the set of nonzero rows in B
B = (IB, IB,1) is the identity array over IB

D. Union
The union operation selects all the distinct rows in two
relations A and B and is written in relational algebra as
A∪B
The SQL equivalent is

5

where

∗ FROM A UNION SELECT ∗ FROM B
In associative array algebra, using the convention of distinct
row keys for nonzero rows, union can be written as
A⊕B
SELECT

T

P = A (A(:,J) ⊕.⊗ B(:,J') ) B
T
= A (A(:,J) θ B(:,J') ) B
The function θ can be any function on two rows of an
associative array that produces either a 0 or a 1 (i.e., θ ∈
{0,1}). If the operation is restricted to the nonzero rows of A
and B, then the A and B terms can be dropped and the θ
permutation array can be written as
T
P = A(:,J) θ B(:,J')

E. Intersection
The intersection operation combines the common rows in
two relations A and B and is written in relational algebra as
A∩B
The SQL equivalent is
SELECT ∗ FROM A INTERSECT SELECT ∗ FROM B
In associative array algebra, using the equivalence permutation
array, intersection can be computed with the following
expressions
T
PB or P A

I. Extended Projection
An extended projection applies a function ϕ on the subset
of columns J of a relation A and returns the output of that
function as a new relation with a column key j'. Extended
projection is written in relational algebra as
j'Πϕ(J)(A)
The SQL equivalent is
SELECT ϕ(A.J(1),...,J(n)) AS j' FROM A
In associative array algebra, extended projection can be written
as
A ⊕.⊗ (J,j')
where ⊕.⊗ = ϕ. The function ϕ can be any function on a row
of an associative array.

F. Set Difference
Set difference returns the rows in relation A that are not
found in relation B and is written in relational algebra as
A\B
The SQL equivalent is
SELECT ∗ FROM A EXCEPT SELECT ∗ FROM B
In associative array algebra, assuming the additive inverse v ⊕
-v = 0, intersection can be written using the equivalence
permutation array as
A ⊕ -PB

J. Aggregation
The aggregation operations applies an aggregate function ƒ
on all the values of column j' of relation A that share a common
value in column j. Aggregation is written in relational algebra
as
j'Gƒ(j)(A)
The SQL equivalent is
SELECT ƒj' FROM A GROUP BY j
In associative array algebra, aggregation can be written as
P ƒ.⊗ A(:,j')
where P is the permutation array defined by cross-correlating
column j with itself
T
P = A (A(:,j) ⊕.⊗ A(:,j) ) A
T
= A (A(:,j) ⊕.= A(:,j) ) A
The function ƒ can be any binary commutative function on a
column of an associative array.

G. Select
The select operation returns all rows in the relation A that
satisfy a function ϕ on the subset of columns J
σϕ(J)(A)
The SQL equivalent is
SELECT ∗ FROM A WHERE ϕ(A.J(1),...,J(n))
In associative array algebra, select can be written using the
select permutation array
PA
where
T
P = (ϕ(A(:,J)) ϕ(A(:,J)) ) ⊗ A
or
P = (ϕ(A(:,J))
The function ϕ can be any function on the J columns of a row
of an associative array that produces either a 0 or a 1 (i.e., ⊕.θ
∈ {0,1}).

VII. PROPERTIES AND PERFORMANCE
Having expressed the main relational operations in terms of
associative array algebra, the mathematical properties
necessary for graph and matrix computation can be checked.
The results of this analysis are summarized in Tables 1 and 2.
The derivation of all of these properties is beyond the scope of
this paper, but as an example, perhaps the most important
property, distributivity is derived in the context of relational
renaming over union and intersection. These operations are the
closest direct analogs to array multiplication and element-wise
addition.
Showing that renaming distributes over union is computed
as follows

H. Theta Join
A theta join returns the rows of two relations A and B
joined where they satisfy the function θ on the J columns of A
and J' columns of B and is written in relational algebra as
A ⋈θ(J,J') B
The SQL equivalent is
SELECT ∗ FROM A, B WHERE θ(A.J(1),...,J(n),B.J'(1),...,J'(n))
In associative array algebra, select can be written using the θ
permutation array as
T
T
T
PB ⊕ PP A
or P A ⊕ P PB

6

2

Assumes corresponding property in join function θ.

ρJ/J'(A ∪ B)

~ (A ⊕ B) (J,J')
= A (J,J') ⊕ B (J,J')
~ ρJ/J'(A) ∪ ρJ/J'(B)
Showing that renaming distributes over intersection is
computed as follows
T
ρJ/J'(A) ∩ ρJ/J'(B) ~ ((A (J,J')) (B (J,J') ) B (J,J')
T T
= ((A (J,J')) ( (J,J') B ) B (J,J')
T
= ((A ( (J,J') (J',J)) B ) B (J,J')
T
= (A (J) B ) B (J,J')
T
= (AB ) B (J,J')
= (PB) (J,J')
~ ρJ/J'(A ∩ B)
Because the above derivations use the corresponding properties
of associative arrays, the results can be more general than the
relational algebra would suggest. Specifically, distributivity
would still hold if rename modified the values in a manner
consistent with associative array multiplication. Likewise,
distributivity would still hold if union and intersection modified
the values in a manner consistent with element-wise addition.

One of the benefits of the properties in Table 1 is the ability
to eliminate operations if the appropriate identity can be
recognized.
Likewise, the properties in Table 2 allow
operations to be reordered to reduce execution time. These
properties are particularly useful in the polystore context when
selecting the optimal database to perform an operation. Figures
6 and 7 show the relative execution time impact of exploiting
associativity and distributivity as a function of the size of the
associative arrays. These experimental measurements were
conducted using the D4M (d4m.mit.edu) implementation of
associative arrays. A fixed 4096×4096 associative array A was
multiplied with square associative arrays B and C that varied in
size. All of the associative arrays were randomly generated
with an average of 8 nonzero entries per row or column, which
is consistent with many graph applications. The results show
the potential performance benefits of exploiting the distributive
and associative properties.
Thus, the kinds of query
optimizations that are found in many databases systems can be
applied to a broad set of computations. These optimizations
are important for polystores as they allow the movement of
computations and data to the appropriate databases.

Identity, annihilator, and inverse properties of relational
operations in terms of associative arrays. Unary functions with
parameters are treated as binary functions. The potential performance
impact of the elimination of an operation via the recognition of one of
these properties is typically O(nnz(A)).
Operation
Identity
Annihilator
Inverse
Project
Rename
Union
Intersection
Difference
A
Select
ϕ=1
ϕ=0
Theta Join
A
Extended
J = j'
ϕ=0
ϕ=1
Projection
ϕ(1,v) = v
Aggregation
A(:,j) is unique
ƒ(0,v) = 0
ƒ(0,v) = 1
ƒ(0,v) = v
Table 1.

time(A (B ⊕ C))

time((A B) ⊕ (A C))
Time(A*(B+C))/Time(A*B+A*C))

3

2.5

2

1.5

1

0.5
-3
10

10

-2

10

-1

10

0

10

1

10

2

(nnz(B)+nnz(C))/nnz(A)
(nnz(B)+nnz(C))
/ nnz(A)
Figure 6. Relative execution time of A (B ⊕ C) vs (A B) ⊕ (A C) as
a function of the size of B and C as compared to A. (A B) ⊕ (A C) is
much faster than A (B ⊕ C) when A is smaller than B and C.

time(A (B C))
time((A B) C)
Time(A*(B+C))/Time(A*B+A*C))

4.5

Commutativity, associativity, and distributivity properties of
relational operations on associative arrays. Unary functions with
parameters are treated as binary functions. The potential performance
impact of elimination of an operation via the recognition of one of
these properties is typically O(nnz(A)).
Operation
Commutativity
Associativity
Distributivity
Projection
no
yes
∪, ∩, \
Table 2.

Rename

no

yes

Union
Intersection
Difference
Select1
Theta Join2

yes
yes
no

yes
yes
no

∪, ∩, \
∩
∪

4
3.5
3
2.5
2
1.5
1
10 -3

10 -2

10 -1

10 0

(nnz(B)+nnz(C))/nnz(A)

(nnz(B)+nnz(C)) / nnz(A)

yes

1

Assumes corresponding property in select function ϕ.

7

10 1

10 2

[Chang 2008] F. Chang, J. Dean, S. Ghemawat, W. Hsieh, D. Wallach, M.
Burrows, T.Chandra, A. Fikes & R. Gruber, “Bigtable: A Distributed
Storage System for Structured Data,” ACM Transactions on Computer
Systems, Volume 26, Issue 2, June 2008.
[Chodorow 2013] K. Chodorow, “MongoDB: the definitive guide,” O'Reilly
Media, Inc.
[Codd 1970] E.F. Codd, “A Relational Model of Data for Large Shared Data
Banks,” Communications of the ACM, Vol. 13, No. 6, 37787, June,
1970.
[Codd 1972] E.F. Codd, Relational completeness of data base sublanguages,
IBM Corporation, 1972.
[Codd 1990] E.F. Codd, The relational model for database management:
version 2, Addison-Wesley Longman Publishing Co., Inc., 1990.
[DeCandia et al 2007] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati,
A. Lakshman, Alex Pilchin, S. Sivasubramanian, P. Vosshall & W
Vogels, “Dynamo: Amazon’s Highly Available Key-value Store,”
Symposium on Operation Systems Principals (SOSP), 2007.
[Duggan 2015] J. Duggan, A. Elmore, M. Stonebraker, M. Balazinska, B.
Howe, J. Kepner, S. Madden, D. Maier, T. Mattson, & S. Zdonik, “The
BigDAWG Polystore System” ACM SIGMOD Record, 44(2), pp.11-16.
[Elmore 2015] Elmore, Kraska, Duggan, Madden, Stonebraker, Maier,
Balazinska, Mattson, Cetintemel, Papadopoulis, Gadepally, Parkhurst,
Heer, Tatbul, Howe, Vartek, Kepner & Zdonik, “A Demonstration of the
BigDAWG Multi-Database System,” VLDB 2015
[Fraenkel 1922] A. Fraenkel, “Zu den grundlagen der Cantor-Zermeloschen
mengenlehre,” Mathematische annalen 86.3 (1922): 230-237
[Gadepally 2015] D4M: Bringing Associative Arrays to Database Engines, V.
Gadepally, J. Kepner, W. Arcand, D. Bestor, B. Bergeron, C. Byun, L.
Edwards, M. Hubbell, P. Michaleas, J. Mullen, A. Prout, A. Rosa, C.
Yee, A. Reuther, IEEE High Performance Extreme Computing (HPEC)
conference, Sep 2015, Waltham, MA
[Galois 1832] E. Galois, Lettre a Auguste Chevalier, 29 mai 1832.
[George 2011] L. George, HBase: The Definitive Guide, O’Reilly, Sebastapol,
California, 2011.
[Halperin 2014] D. Halperin, V. Teixeira de Almeida, L. Choo, S. Chu, P.
Koutris, D. Moritz, J. Ortiz, V. Ruamviboonsuk, J. Wang, A. Whitaker,
S. Xu, M. Balazinska, B. Howe, & D. Suciu, "Demonstration of the
Myria big data management service," ACM SIGMOD international
conference on Management of data, 2014.
[Heaviside 1887] O. Heaviside, LXII, “On resistance and conductance
operators, and their derivatives, inductance and permittance, especially
in connexion with electric and magnetic energy,” The Lon-don,
Edinburgh, and Dublin Philosophical Magazine and Journal of Science
24.151 (1887): 479-502
[Howe 2015] B. Howe & D. Maier, "Algebraic manipulation of scientific
datasets," The VLDB journal 14, no. 4 (2005): 397-416.
[Hutchison 2015] D. Hutchison, J. Kepner, V. Gadepally, & A. Fuchs,
"Graphulo implementation of server-side sparse matrix multiply in the
Accumulo database," IEEE High Performance Extreme Computing
(HPEC) Conference, Walham, MA, September 2015.
[Hutchison 2016] D. Hutchison, B. Howe & D. Suciu, “Lara: A Key-Value
Algebra
underlying
Arrays
and
Relations,”
https://arxiv.org/abs/1604.03607
[Imieliński 1984a] T. Imieliński & Witold Lipski, "The relational model of
data and cylindric algebras," Journal of Computer and System Sciences
28, no. 1 (1984): 80-102.
[Imieliński 1984b] T. Imieliński & Witold Lipski, "Incomplete information in
relational databases." Journal of the ACM (JACM) 31, no. 4 (1984): 761791.
[Kallman 2008] R. Kallman, H. Kimura, J. Natkins, A. Pavlo, A. Rasin, S.
Zdonik, E. Jones, S. Madden, M. Stonebraker, Y. Zhang, J. Hugg & D.
Abadi, “H-store: a high-performance, distributed main memory
transaction processing system,” Proceedings of the VLDB Endowment,
Volume 1 Issue 2, August 2008, pages 1496-1499.
[Kanellakis 1989] P. Kanellakis, “Elements of relational database theory,”
Brown University, Department of Computer Science, 1989.

Figure 7. Relative execution time of A (B C) vs (A B) C as a

function of the size of B and C as compared to A. (A B) C is much
faster than A (B C) when A is smaller than B and C.

VIII. SUMMARY AND FUTURE WORK
The success of SQL, NoSQL, and NewSQL databases is a
reflection of their ability to provide significant functionality
and performance benefits for specific domains: transactions,
internet search, and data analysis. The BigDAWG polystore
seeks to provide a mechanism to allow applications to
transparently achieve the benefits of diverse databases while
insulating applications from the details of these diverse
databases. Associative arrays provide a common approach to
the mathematics found in different databases: sets (SQL),
graphs (NoSQL), and matrices (NewSQL). This work presents
the SQL relational model in terms of associative arrays and
identifies the key mathematical properties of NoSQL and
NewSQL that are preserved within SQL. These properties
include associativity, commutativity, distributivity, identities,
annihilators, and inverses. Performance measurements on
distributivity and associativity show the impact these properties
can have on associative array operations. These results
demonstrate that associative arrays can provide a model for
polystores to leverage mathematical properties across databases
to optimize the exchange of data and queries.
Future work in this area will focus on a complete set of
proofs for the aforementioned relational operations, detailed
analysis of optimizations, and the potential application of
uncertainty quantification to database queries.
ACKNOWLEDGMENTS
The authors wish to acknowledge the following individuals
for their contributions: Michael Stonebraker, Sam Madden, Bill
Howe, David Maier, Chris Hill, Alan Edelman, Charles
Leiserson, Dave Martinez, Sterling Foster, Paul Burkhardt,
Victor Roytburd, Bill Arcand, Bill Bergeron, David Bestor,
Chansup Byun, Mike Houle, Matt Hubbell, Mike Jones, Anna
Klein, Pete Michaleas, Lauren Milechin, Julie Mullen, Andy
Prout, Tony Rosa, Sid Samsi, and Chuck Yee.
REFERENCES
[Abiteboul 1995] S. Abiteboul, R. Hull, & V. Vianu. Foundations of
databases. Vol. 8. Reading: Addison-Wesley, 1995.
[Balazinska 2009] M. Balazinska, J. Becla, D. Heath, D. Maier, M.
Stonebraker & S. Zdonik, “A Demonstration of SciDB: A ScienceOriented DBMS, Cell, 1, a2. (2009).
[Bu 2010] Y. Bu, B. Howe, M. Balazinska, & M. Ernst. "HaLoop: efficient
iterative data processing on large clusters," Proceedings of the VLDB
Endowment 3, no. 1-2 (2010): 285-296.
[Buluc 2015] A. Buluc, “GraphBLAS Special Session,” IEEE HPEC 2015,
Waltham, MA
[Buluc 2016] A. Buluc, “Workshop on Graph Algorithms Building Blocks,”
IPDPS 2016, Chicago, IL
[Byun 2012] C. Byun, W. Arcand, D. Bestor, B. Bergeron, M. Hubbell, J.
Kepner, A. McCabe, P. Michaleas, J. Mullen, D. O’Gwynn, A. Prout,
A. Reuther, A. Rosa, C. Yee, “Driving Big Data With Big Compute,”
IEEE High Performance Extreme Computing (HPEC) Conference, Sep
2012.
[Cattell 2011] R. Cattell, Rick. "Scalable SQL and NoSQL data stores," ACM
SIGMOD Record 39.4 (2011): 12-27.

8

[Kelly 2012] P. Kelly & M. H. van Emden, "Relational Semantics for
Databases and Predicate Calculus," arXiv preprint arXiv:1202.0474
(2012).
[Kepner 2012] J. Kepner, W. Arcand, W. Bergeron, N. Bliss, R. Bond, C.
Byun, G. Condon, K. Gregson, M. Hubbell, J. Kurz, A. McCabe, P.
Michaleas, A. Prout, A. Reuther, A. Rosa & C. Yee, “Dynamic
Distributed Dimensional Data Model (D4M) Database and Computation
System,” ICASSP (International Conference on Accoustics, Speech, and
Signal Processing), 2012, Kyoto, Japan
[Kepner 2013] J. Kepner, C. Anderson, W. Arcand, D. Bestor, B. Bergeron, C.
Byun, M. Hubbell, P. Michaleas, J. Mullen, D. O'Gwynn, A. Prout, A.
Reuther, A. Rosa, C.arles Yee, “D4M 2.0 Schema: A General Purpose
High Performance Schema for the Accumulo Database,” IEEE High
Performance Extreme Computing (HPEC) conference, Sep 10-12, 2013,
Waltham, MA
[Kepner & Chaidez 2013] J. Kepner & J. Chaidez, “The Abstract Algebra of
Big Data,” Union College Mathematics Conference, Oct 2013,
Schenectady, NY
[Kepner & Chaidez 2014] J. Kepner & J. Chaidez, “The Abstract Algebra of
Big Data and Associative Arrays,” SIAM Meeting on Discrete Math, Jun
2014, Minneapolis, MN
[Kepner 2014] J. Kepner, W. Arcand, D. Bestor, B. Bergeron, C. Byun, V.
Gadepally, M. Hubbell, P. Michaleas, J. Mullen, A. Prout, A. Reuther,
A. Rosa, & C. Yee, “Achieving 100,000,000 database inserts per second
using Accumulo and D4M,” IEEE High Performance Extreme
Computing (HPEC) Conference, Walham, MA, September 2014.
[Kepner & Jansen 2016] J. Kepner & H. Jansen,
[Lakshman & Malik 2010] A. Lakshman & P. Malik, “Cassandra: A
Decentralized Structured Storage System,” ACM SIGOPS Operating
Systems Review, Volume 44 Issue 2, April 2010.
[Litak 2014] T. Litak, S. Mikulás, & J Hidders, "Relational lattices,"
Relational and Algebraic Methods in Computer Science, pp. 327-343.
Springer International Publishing, 2014.
[Maier 1983] D. Maier, The theory of relational databases. Vol. 11.
Rockville: Computer science press, 1983.
[Mattson 2013] T. Mattson, D. Bader, J. Berry, A. Buluc, J. Dongarra, C.
Faloutsos, J. Feo, J. Gilbert, J. Gonzalez, B. Hendrickson, J. Kepner, C.
Leiserson, A. Lumsdaine, D. Padua, S. Poole, S. Reinhardt, M.
Stonebraker, S. Wallach, & A. Yoo, “Standards for Graph Algorithms
Primitives,” IEEE HPEC 2013, Waltham, MA
[Mattson 2014a] T. Mattson, “Workshop on Graph Algorithms Building
Blocks,” IPDPS 2014, Pheoniz, AZ
[Mattson 2014b] T. Mattson, “GraphBLAS Special Session,” IEEE HPEC
2014, Waltham, MA
[Mattson 2015] T. Mattson, “Workshop on Graph Algorithms Building
Blocks,” IPDPS 2015, Hyderabad, India
[Olston 2008] C. Olston, B. Reed, U. Srivastava, R. Kumar, & A. Tomkins.
"Pig latin: a not-so-foreign language for data processing," ACM
SIGMOD international conference on Management of data, pp. 10991110. ACM, 2008.

[Peano 1888] G. Peano, “Calcolo geometrico,” secondo l’Ausdehnungslehre
di H. Grassmann, 1888
[Plotkin 1998] T. Plotkin, S. Kraus, & B. Plotkin, "Problems of equivalence,
categoricity of axioms and states description in databases," Studia
Logica 61, no. 3 (1998): 347-366.
[Priss 2006] U. Priss, "An FCA interpretation of relation algebra," Formal
Concept Analysis, pp. 248-263. Springer Berlin Heidelberg, 2006.
[Prout 2015] A. Prout et al, “MIT SuperCloud Database Management
System,” IEEE High Performance Extreme Computing (HPEC)
Conference, September 2015, submitted.
[Reuther 2013] A. Reuther, J. Kepner, W. Arcand, D. Bestor, B. Bergeron, C.
Byun, M. Hubbell, P. Michaleas, J. Mullen, A. Prout, & A. Rosa,
“LLSuperCloud: Sharing HPC Systems for Diverse Rapid Prototyping,”
IEEE High Performance Extreme Computing (HPEC) Conference,
September 2013.
[Samsi 2016] S. Samsi, L. Brattain, V. Gadepally, & J. Kepner "D4M and
Large Array Databases for Management and Analysis of Large
Biomedical Imaging Data," New England Database Summit, 2016
[Stonebraker 1976] M. Stonebraker, G. Held, E. Wong & P. Kreps, “The
design and implementation of INGRES,” ACM Transactions on
Database Systems (TODS), Volume 1 Issue 3, Sep 1976, Pages 189-222
[Stonebraker 2005] M. Stonebraker, D. Abadi, A. Batkin, X. Chen, M.
Cherniack, M. Fer- reira, E. Lau, A. Lin, S. Madden, E. O’Neil, P.
O’Neil, A. Rasin, N.Tran & S. Zdonik, “C-store: a column-oriented
DBMS,” Proceedings of the 31st International Conference on Very
Large Data Bases (VLDB ’05), 2005, pages 553 – 564.
[Stonebraker & Çetintemel 2005] M. Stonebraker & U. Çetintemel, ""One
size fits all": an idea whose time has come and gone," IEEE International
Conference on Data Engineering, ICDE 2005.
[Stonebraker & Weisberg 2013] M. Stonebraker & A. Weisberg, “The Volt
DB Main Memory DBMS,” IEEE Data Eng. Bull., Vol. 36, No. 2, 2013,
pages 21-27.
[Tsalenko 1992] M.Sh. Tsalenko, "Database theory in Russia (1979–1991)(an
overview)," Database Theory—ICDT'92, pp. 51-70. Springer Berlin
Heidelberg, 1992.
[van Emden 2006] M.H. van Emden, “Set-Theoretic Preliminaries for
Computer Scientists,” Research Report DCS-304-IR, Department of
Computer Science, University of Victoria, 2006
[Wall 2013] M. Wall, A. Cordova & B. Rinaldi, Accumulo Application
Development, Table Design, and Best Practices, O’Reilly, Sebastapol,
California, US, 2013.
[Wu 2014] S. Wu, V. Gadepally, A. Whitaker, J. Kepner, B. Howe, M.
Balazinska & S. Madden, “MIMICViz: Enabling Visualization of
Medical Big Data,” Intel Science & Technology Center retreat, Portland,
OR, August, 2014
[Zaharia 2010] M. Zaharia, M Chowdhury, M. J. Franklin, S. Shenker, & I.
Stoica, "Spark: Cluster Computing with Working Sets," HotCloud 10
(2010): 10-10.
[Zermelo 1908] E. Zermelo, “Untersuchungen uber die Grundlagen der
Mengenlehre,” I., Mathematische Annalen 65.2 (1908): 261-281

9

