TRUE and FALSE values in the relational lattice

Given a relation R(x,y) with domains x={0,1,2}, y={'a','b'} we know from classic predicate theory that the expression

R(x=0, y='a')

evaluates to true or false. Here is how we establish this siumple fact in the relational lattice.

First, lets substitute x -> x=0 into R(x,y) and get unary relation R'(y). The formula for such substitution is

R'(y) = R(0,y) = (R /\ `x=0`) \/ `y`

where `x=0' is unary relation with one tuple {0} and attribute x, and `y` is the unary empty relation with attribute y. Informally, we select all the tuples in R such that x=0 and project the result to column y.

Next, we substitute y -> y=a into R'(y) and obtain "emptiary" relation R":

R"({}) = R(0,'a') = ( ( (R /\ `x=0`) \/ `y` ) /\ `y=a` ) \/ 00

It is instructive to apply the distributivity criteria (I lost count how many times I leveraged it!) and simplify the expression to

R(0,'a') = ( R /\ `x=0` /\ `y=a` ) \/ 00

As expected this expression is valued to 00 or 01, so Marshall was eventually right when interpreting those relations as TRUE and FALSE. Received on Tue Jun 19 2007 - 12:51:05 CDT