Re: Complement in Relational Lattice

On May 31, 4:37 pm, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
> On May 31, 3:36 pm, Marshall <marshall.spi..._at_gmail.com> wrote:
>
> > 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.

Ha! So for a given header, the complement is unique if the value is either minimal or maximal for that header.

> > 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,
> onto a two element boolean algebra.

Yes, and this "product" is visible in this equation:

  (11 \/ H) /\ B

from my second post.

Or you could say there are two homomorphisms:

  body -> boolean algebra and
  header -> set 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?

Um, I mostly use truth tables, but that's because I'm lame.

I'm not sure where you're going, but maybe it has something to do with lattice order? In which case I observe

  A >= !!A

Marshall Received on Fri Jun 01 2007 - 02:26:57 CEST