Re: Complement in Relational Lattice

[Quoted] On May 31, 3:36 pm, Marshall <marshall.spi..._at_gmail.com> wrote:
> RL complement is well-defined. It is roughly the complement
> of the rows and the complement of the columns.
>
> 1. !A has all the columns that aren't in A
> In other words:
> A \/ !A \/ 10 = 00
> Equivalently:
> A \/ !A >= 00
>
> 2a. If A is nonempty, !A must be empty
>
> (A \/ 00 = 01) => !A \/ 00 = 00
>
> 2b. If A is empty, !A is the domain set of the appropriate columns.
>
> If C is the empty set with columns defined in 1) above,
>
> !A = 11 \/ C
>
> Case 2b presents another difference between RL algebra and
> boolean algebras: the complement of an empty relation is not unique.
> The above construction presents the smallest complement of an
> empty A, but any nonempty member of the power set of the 2b
> complement is also a complement. The 2b complement is the
> smallest complement; there is no largest complement.
> (Except in the case of 10, which has only one complement: 01.)
>
> This lack of uniqueness of the complement means that the complement
> preserves the information content of the header but not the body
> of the relation. The only information preserved from the body is
> whether the relation is empty or not. That means
>
> !!A = A iff A <= 00

A minor exception to your rule -- relation A being any cartesian product of the domains.

> Otherwise it seems to obey most of the boolean complement properties.
>
> A /\ !A = 10
> A \/ !A = 01
>
> !01 = 10
> !10 = 01
>
> As an aside, the following also holds, amusingly enough:
>
> !11 = 00
> !00 = 11

What you have found is a homomorphism of RL into a boolean algebra which is a product of the boolean algebra of the relation attributes, [Quoted] onto a two element boolean algebra. In the example on Figure 1 from the "First Steps..." this boolean algebra is the 8 element sublattice

{01, {(x=1),(x=2)}, {(y=a),(y=b)}, 11, 00, {(x=1)}/\00, {(y=a)}/\00, 10}

where {(x=1)}/\00 is an awkward (yet presize) way to express "an empty relation with attribute x". This homomorphism is missing from Figures 2 and 3!

BTW, I'm trying to approach the problem from a different angle. Why do we need all those hypothetic inverse elements for? To solve equations. Now, how do we solve equations in boolean algebra? Received on Fri Jun 01 2007 - 01:37:26 CEST