Figure 5. Relational tables for Product database.
diately see that SQL lacks compositionality; since there is no recursion, rows
can contain only scalar values:
Ratings
Id
787
747
Rating
****
4 stars
ProductId
1579124585
1579124585
row ::= new { …, name = scalar, … }
Products
Id
1579124585
Title
The Right Stuff
Author
Tom Wolfe
Year
1979
Pages
304
Compare this with the definition
for anonymous types, where a row can
contain arbitrary values, including other rows (or nested collections):
Keywords
Id
4711
1843
2012
American
Keyword
Book
hardcover
ProductId
1579124585
1579124585
1579124585
value ::= new { …, name = value, … }
| scalar
tain referential integrity to ensure that:
the foreign-/primary-key relationships
across related tables remain synchronized across mutations to the tables
and rows; the primary key of every row
remains unique within its table; and
foreign keys always point to a valid primary key. For example, we cannot delete a row in the Products table without also deleting the related rows in the
Key words and Ratings tables.
Referential integrity implies a
closed-world assumption where transac-
tions on the database are serialized by
(conceptually) suspending the world
synchronously, applying the required
changes, and resuming the world again
when referential integrity has been re-
stored successfully, rolling back any
chances otherwise. Assuming a closed
world is, as we claim, both a strength
and a weakness of the relational mod-
el. On the one hand, it simplifies the
life of developers via ACID (atomic-
ity, consistency, isolation, durability)
transactions (although in practice, for
efficiency, one must often deal with
much weaker isolation levels) and al-
lows for impressive (statistics-based)
query optimization. The closed-world
assumption, however, is in direct con-
tradiction with distribution and scale-
out. The bigger the world, the harder it
is to keep closed.
var q = from product in Products
from rating in Ratings
from keyword in Keywords
where product.ID == rating.
ProductId
&& product.ID == keyword.
ProductID
&& rating == “****”
select new{ product.Title,
keyword.Keyword };
var q = from product in Products
join rating in Ratings on
product.ID equals rating.
ProductId
where rating == “****”
select product into FourStarProducts
from fourstarproduct in
FourStarProducts
join keyword in Keywords on
product.ID equals keyword.
ProductID
select new{ product.Title,
keyword.Keyword };
Figure 6. tabular result for books with
four-star ratings.
Depending on the encoding of the
nesting of the result of a join using flat
result sets, the SQL programmer must
choose among various flavors of INNER, OU TER, LEFT, and RIGHT joins.
Keywords
Title
The Right Stuff
The Right Stuff
The Right Stuff
American
Keyword
Book
hardcover
The result of this query is the row
set shown in Figure 6. Disappointingly,
this row set is not itself normalized.
In fact, to return the normalized
representation of our object-graph
query, we need to perform two queries
(within a single transaction) against
the database: one to return the title
and its primary key, and a second query
that selects the related keywords.
What we observe here is SQL’s lack
of compositionality—the ability arbitrarily to combine complex values from
simpler values without falling outside
the system. By looking at the grammar
definition for table rows, we can imme-
impedance mismatch
In 1984 George Copeland and David
Maier recognized the impedance mismatch between the relational and the
object-graph model just described,
5
and in the quarter century since, we
have seen an explosion of O/R (object-