Figure 9. Relational tables for Products database with explicit relationships.
The Right Stuff
The Right Stuff
arrows, along with some axioms that
the composition of arrows should satisfy. A computational view of category
theory is that it is a highly stylized,
compact functional language. Small
as it is, it’s enough to represent all of
mathematics. For computer scientists,
category theory has proved to be a rich
source of techniques that are readily
applicable to many real-world problems. For example, Haskell’s approach
to modeling imperative programming
is lifted straight from a categorical
model of the problem.
The first powerful concept from category theory that we will use is duality.
Examples of duality abound in computer science. Every programmer is
familiar with the two dual forms of De
!(a && b) == (!a)||(!b)
!(a||b) == (!a)&&(!b)
Other examples of dualities in computer science are between reference
counting and tracing garbage collection, between call-by-value and call-by-name, between push- and pull-based
collections, and between transactional memory and garbage collection,
among many others.
Formally, given a category C of objects and arrows, we obtain the dual
category co(C) by reversing all the arrows in C. If a statement T is true in C,
then its dual statement co(T) is true
in the dual category co(C). In the context of this article, we can read “
opposite statement” for “dual statement”.
In the SQL category, child nodes
point to parent nodes when the foreign key of a child node equals the
primary key of the parent node (
Figure 10). In the noSQL category, the arrows are reversed. Parent nodes point
to child nodes when the child pointer
in the parent equals the address of the
child node in the store (see Figure 11).
In other words, the noSQL category
is the dual of the SQL category—noSQL
is really coSQL. The implication of this
duality is that coSQL and SQL are not
in conflict, like good and evil. Instead
they are two opposites that coexist in
harmony and can transmute into each
other like yin and yang. Interestingly,
in Chinese philosophy yin symbolizes
open and hence corresponds to the
open world of coSQL, and yang symbolizes closed and hence corresponds
to the closed world of SQL.
Because SQL and coSQL are mathematically dual, we can reason precisely about the tradeoffs between the
two instead of relying on rhetoric and
anecdotal evidence. The accompanying table gives a number of statements
and their duals as they hold for SQL and
If we really take the duality to heart,
we may also choose to (but don’t have
to) fine-tune our model for key-value
stores to reflect the duality between
values and computations, and that
between synchronous ACID and asynchronous BASE (basically available,
soft state, eventually consistent).
Looking up a value given its ad-
dress or key in a key-value story can
involve a computation, which in a truly
open world has potential latency and
may fail. For example, in the C# lan-
guage getters and setters, known as
properties, can invoke arbitrary code.
Perhaps an even better example of a
computation-driven key-value store
with long latency and high probabil-
ity of failure (always able to handle a
404) is the Web, with URI (Uniform
Resource Identifier) as keys, “resourc-
es” as values, and the HTTP verbs as
a primitive query and data-manipula-
tion language. On the other hand, in
a C-like key-value memory model, we
usually make the simplifying assump-
tion that a key lookup in memory takes
constant time and does not fail.
Relationship to the Real World
Our abstract model of the SQL category
did not impose any restrictions on the