dkubb/veritas — Issue #5: Misinterpretation of the algebra for JOIN operations?
Author: d11wtq
Created: 2011-11-01 15:47:25+00:00
State: open

Problem One (possibly the only issue here is unnecessary validation?).

Joining relations with no common attributes doesn't work due to an assertion in Veritas:

``` ruby
# say, users
r = Veritas::Relation.new(
[ ["UNO", Integer], ["USERNAME", String] ],
[
[42, "Bob"]
]
)

# say, pets
s = Veritas::Relation.new(
[ ["PNO", Integer], ["PNAME", String] ],
[
[1, "Mongo"]
]
)

r.join(s) #=> Veritas::InvalidHeaderError: the headers must have common attributes
```

From page 88 of Database in Depth:

> r JOIN s
>
> is a relation with (a) a heading that is the **(set-theoretic) union** of the headings of r and s and (b) a body consisting of the set of all tuples *t* such that *t* is the (set-theoretic) union of a tuple appearing in *r* and a tuple appearing in *s*.

(snip)

> Third (also important), *cartesian product* is a special case of join, too: if *n* = 0, meaning there are no Y's and thus *r* and *s* have no common attributes at all, *r* JOIN *s* degenerates to *r* TIMES *s* .... snip ... Why? Because (a) the set of attributes common to *r* and *s* in this case is the *empty set* of attributes; (b) every possible tuple has the same value for the empty set of attributes; thus every tuple in *r* joins to every tuple in *s*, and so we get the cartesian product as stated.

Problem two (possibly solved simply by fixing the first issue):

TABLE_DEE joined with any relation, *r* should always yield the relation *r*.

``` ruby
Veritas::Relation.new([], [ [] ]).join(r) # same error is previously, but should simply return r
```

From page 89 (pre-amble about a prefix notation for Tutorial D's JOIN):

> For example, the join of parts and suppliers could alternatively be expressed as follows:
>
> JOIN { P, S }

(snip)

> The join of a single relation, JOIN { r }, is just *r* itself; this case is perhaps not of much practical importance. Perhaps surprisingly, however, **the join of no relations at all, JOIN {}, is very important indeed!**—**and the result is TABLE_DEE**.

(snip)

> - In like manner, 1 is the identity with respect to "*"; that is, for all numbers *x*, the expressions _x * 1_ and _1 * x_ are both identically equal to *x*. As a consequence, the product of no numbers is 1.
> - In the relational algebra, __*TABLE_DEE is the identity with respect to JOIN*; that is, the join of any relation *r* with TABLE_DEE is simply *r*__. As a consequence, the join of no relations is TABLE_DEE.

Let me know if I've got the wrong end of the stick or if this is indeed a bug :) I'm off to bed!