I understand there is some interest in the discussion of
binary relations in the document at
http://lambda-the-ultimate.org/node/view/25.
I don't understand why there should be any interest, these
days, in attempting to construct a data modeling approach, a database theory,
or a database query language around the concept of relations that are
exclusively of degree 2.
It is true that, pre-Codd, when mathematicians talked about
relations, they usually meant binary ones in particular. Binary ones enabled
them to think about interesting properties such as reflexivity, symmetry and
transitivity. Indeed, the chapters on relations on both of my logic primers
devolve
exclusively around these concepts and contain no mention of
relations of degree other than 2. (The
books are BEGINNING LOGIC, by E.J. Lemmon, 1965 and, a wonderful book
that I highly recommend: LOGIC,
by Wilfrid Hodges, 1977.)
[Aside: Let r be a binary relation. In case you didn't know,
r is reflexive if its predicate, r(a,b),
is true whenever a=b. It is symmetrical
if r(a,b) implies r(b,a). And it is transitive if r(a,b)&r(b,c) implies
r(a,c). It has always bothered me a
little that relational database theory doesn't address these concepts. Whether
written in SQL or Tutorial D, Chris Date's query exercise, "Give pairs of
supplier number (sx,sy) such that suppliers sx and sy supply exactly the same
set of parts", yields a relation that is reflexive, symmetrical and
transitive. Yet we have no shorthand in either of these languages for
eliminating from the result the tuples that might be deemed redundant on
account of these properties. Nor can we express any of these properties as
constraints on relvars in the database. End of aside]
Anyway, in case it is not obvious why we need relations of
degrees other than 2, I'll briefly churn out the old justifications.
For a start, some relations of degree greater than two are,
quite simply, irreducible. The relation
corresponding to the predicate, "Teacher t uses book b on course c",
for example, is ternary and has no equivalent decomposition into two or more
binaries. (As a consequence of its
irreducibility, it is "all-key", meaning that its heading is its only
candidate key.)
If temporal databases were restricted to binary relations,
they would be useless. How could we record employees' salary histories using
binary relations only? (Think of the
predicate: "Employee e was paid x dollars per month throughout interval
i.")
Relations of degree less than two are essential for query
language completeness. The relation corresponding to the query, "What are
the supplier numbers of the suppliers who can supply a purple part?", is
unary. The relation corresponding to the query, "Does anybody supply any
purple parts?" is of degree zero (because the answer in English is either
"yes" or "no").
The theory of n-ary relations being so agreeably complete and
satisfying as a basis for well-designed database languages, why would anybody
nowadays think of elevating the binary relation in particular to some special
position? Perhaps I'm missing
something.
Ed. Note: The
reason is simply that knowledge of the history of the field is absent. Those
who don't know or forget the past, are doomed to repeat it.
Posted
8/5/05
