Re: Complement in Relational Lattice

On May 31, 3:36 pm, Marshall <marshall.spi...@xxxxxxxxx> 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,
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?




.

Relevant Pages

  • 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: Complement in Relational Lattice
    ... the complement of an empty relation is not unique. ... So for a given header, the complement is unique if the value ... What you have found is a homomorphism of RL into a boolean algebra ...
    (comp.databases.theory)
  • Re: "separate entity" and individuation in mathematics
    ... > Jim Spriggs wrote: ... > by describing it as the complement of the closure of the complement ... > both of these extensions rewrite to two of the above, ...
    (sci.math)
  • Re: "separate entity" and individuation in mathematics
    ... > Jim Spriggs wrote: ... > by describing it as the complement of the closure of the complement ... > both of these extensions rewrite to two of the above, ...
    (sci.logic)
  • 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)