Re: Complement in Relational Lattice

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

.

Relevant Pages

  • Re: Complement in Relational Lattice
    ... If A is nonempty,!A must be empty ... If A is empty,!A is the domain set of the appropriate columns. ... the complement of an empty relation is not unique. ... What you have found is a homomorphism of RL into a boolean algebra ...
    (comp.databases.theory)
  • Re: 15 set relationships?
    ... It was complement ...  The usual order of a Boolean algebra is ... We have propositions build out of atomic ... We build "complex" propositional formulas out of the atomic ones by ...
    (sci.math)
  • Re: boolean algebra
    ... + is join and ' is complement. ... he word 'boolean' in the subject is the big clue, and so can be assumed to exclude reals.. ... Maybe it's the Boolean algebra of subsets of R, ... On the other hand, if he were to not be so extremely terse, expecting an audience of mind readers to know what he means, he would have saved himself, and us, the bother of several posts that could have been avoided if OP were to write in complete sentences, had used a dozen words. ...
    (sci.math)
  • Re: Continuous maps and extending into closure
    ... Jason Pawloski wrote: ... Proving f) is contained in clis equivalent to proving that ... we want to show that x is in the complement of f). ... empty. ...
    (sci.math)
  • Re: completeness of the relational lattice
    ... Note that function A is not a homomorhism, that is the dual identity ... So function A is a true lattice homomorphism to boolean algebra of ... What would be the result of join betwwen empty ...
    (comp.databases.theory)