Communications - April 2011

Without an index, however, this query requires a full table scan and hence takes quadratic time in the length of the Products table.

The ability to create indexes makes a closed-world assumption. For example, if we modify the previous ad-hoc query to find all pairs of Web pages where one page has a URL referencing the other, it should be obvious that building an index for this join is quite a hard task when you do not have the whole Web available inside a single database:

from p1 in WWW from p2 in WWW where p2.Contains(p1.URL) select new{ p1, p2 };

Summarizing what we have learned so far, we see that in order to use a relational database, starting with a natural hierarchical object model, the designer needs to normalize the data model into multiple types that no longer reflect the original intent; the application developer must reencode the original hierarchical structure by decorating the normalized data with extra metadata; and, finally, the database implementer has to speed up queries over the normalized data by building indexes that essentially re-create the original nested structure of the data as well.

nosQL is cosQL

At this point it feels like the conceptual dissonance between the key-value and foreign-/primary-key data models is insurmountable. That would be a pity since clearly each has its strengths and weaknesses. Wouldn’t it be great if we could give a more mathematical explanation of where the relational model shines and where the object-graph model works best? As it turns out, we can find the answer to this question by taking a closer look at the (in-memory) structures created for our running example in both models.

Let’s start by slightly simplifying the
object-graph example. We do so by re-
moving the object identity of the Rat-
ings and Authors collections to reflect
more directly how they are modeled in
the relational world. We inline the Key-
words and Ratings items directly into
the parent Product, as if we had value-
based collections. Pictorially, we move
from the diagram on the left to the one
on the right in Figure 8:
For the tabular representation, we
show explicit arrows for the relation-
ship from foreign keys to primary keys.
Again, pictorially, we move from the
diagram on the left to the one on the
right in Figure 9:
When we do a side-by-side compari-
son of the two rightmost diagrams, we
notice two interesting facts:

˲ ˲In the object-graph model, the
identity of objects is intensional—that
is, object identity is not part of the
values themselves but determined
by their keys in the store. In the rela-
tional model, object identity is exten-
sional—that is, object identity is part
of the value itself, in the form of a pri-
mary key.