Re: TRUE and FALSE values in the relational lattice

From: Vadim Tropashko <>
Date: Thu, 21 Jun 2007 14:08:39 -0700
Message-ID: <>

On Jun 21, 10:51 am, Vadim Tropashko <> wrote:
> Here is a cute identity involving set equality join (not division!),
> and equality relation:
> ((R /=\ E) /=\ E ) = R
> where the "/=\" is a symbol for set equality join.

More about equality relation. Equality relation is defined as antisymmetric equivalence relation. Unfortunately, the definition is circular because antysymmetry is defined via equality! So let's focus on equivalence relation axioms, first. We have


which can't be interpeted in any meninful way in the relational theory. Then we have

x=y implies y=x

which isn't again a meaningful statement in the relational theory, because any binary relation is symmetric in a sense that the order of attributes doesn't really matter.

This can be contrasted to Tarski relation algebra where both properties can be expressed.

Transitivity, however can be expressed. We can use set join /=\ or natural join /\ followed by projection in order to exclude "middle" column. So we have

`x=y` /=\ `y=z` = `x=z`

This again defines equivalence only, not equality. In order to define equality transitivity has to be strengthened into the following law:

R(x,y) /=\ `y=z` = R(x,z)

Again, attribute agnostic expression would require to use relation R with the same set of attributes. We therefore join the both sides of the above identity with equality `y=z` to get

R(x,y) /=\ `y=z` /=\ `y=z` = R(x,y)

Notice that atrributes of the relation R and `y=z` "overlap" in a certain way. Clearly the identity

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

is wrong.

On the other, hand we can generalize the above identity to hold for a ternary equality relation!

R(x,u,v,w) /=\ `x=y=z` /=\ `x=y=z` = R(x,u,v,w)

One more case is when attributes don't overlap, but it is valid for any relation S(x,y,z), not just equality:

R(u,v,w) /=\ S(x,y,z) /=\ S(x,y,z) = R(u,v,w) Received on Thu Jun 21 2007 - 23:08:39 CEST

Original text of this message