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-