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.
Figure 8. object graph for Products collection with keywords and ratings inlined.
0
Title
The Right Stuff
Author
Tom Wolfe
Year
1979
Pages
320
Keywords Ratings
Title
Author
Year
1979
Pages
320
Keywords Ratings
Chars
American
Chars
****
Chars
The Right Stuff
Chars
Tom Wolfe
01 2
Chars
hardcover
Chars
4 stars
Chars
Book
Chars
hardcover
Chars
American
Chars
Book
0
Chars
4 stars
Chars
****