Complement in Relational Lattice
Marshall
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
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
I am starting to think about the RL as a framework for logic.
I tend to think of anything less than or equal to 00 as false,
and everything else as true. In other words, X | 00 produces
a truth value for X: either 01 for true or 00 for false.
It is interesting to look at the above six properties in that
light. Note that the RL projected over zero attributes is
isomorphic to the two-valued boolean algebra.
This RL logic requires no inference rules. Or rather, it's
existing properties are already inference rules. No
formal system can be both complete and consistent; I wonder
which way RL goes? It it is not complete in the Turing
sense, however I often have trouble untangling the various
different senses of "complete."
Marshall
Marshall
> RL complement is well-defined. It is roughly the complement
> of the rows and the complement of the columns.
Another way to state it.
Consider the algebra of headers that is embedded
in the RL. This algebra is isomorphic to basic set
algebra, with \/ as intersection and /\ as union.
In this algebra, de Morgan's holds.
Consider the two valued algebra formed by considering
all relations as empty or nonempty. (That is, the algebra
of R \/ 00.) \/ is AND and /\ is OR. This is isomorphic to
the familiar two-valued boolean algebra. In this algebra,
de Morgan's holds.
The RL complement is formed with the header
complement in set algebra H, the boolean complement
in the row algebra B.
11 \/ H /\ B
So offhand I would expect de Morgan's to hold for
RL complements.
This one's for you Paul. ;-)
Marshall
Vadim Tropashko
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?
Marshall
wrote:
> On May 31, 3:36 pm, Marshall <marshall.spi...@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
Marshall
>
> This algebra is isomorphic to basic set
>
> This is isomorphic to the familiar two-valued
> boolean algebra.
Correction: these are one way mappings hence homomorphisms,
not isomorphisms. D'oh!
Marshall
paul c
Thank you Marshall. Somewhat mixed feelings as I was hoping to spend
the summer getting some old scooters on the road and now I'm obligated
to achieve a better understanding of the RL ideas. I must admit that I
didn't try very hard to understand RL ages ago, but was intrigued by its
approach to union, thinking that it might be a very practical engine
technique. Changing one word in the D&D Algebra definition would give
the same operator, admittedly that would pervert their analogy and which
was pointed out directly by others and indirectly too (I remember Jon H
talking about predicates that get truncated, can't remember exactly what
he said, truncated is my word, not his, still that didn't bother me). I
am guessing that part of their resistance has to do with the very name
"union" even though they suggest the name "disjoin" for the version that
parallels conventional boolean algebra. Has the same result when
headings "match", so I was surprised that people found it out-of-sorts
with D&D, since the latter stipulate that over and over anyway!
p
Marshall
> of the rows and the complement of the columns.
Another way to state it.
Marshall
> Marshall wrote:
>
> > So offhand I would expect de Morgan's to hold for
> > RL complements.
>
> > This one's for you Paul. ;-)
>
> the summer getting some old scooters on the road and now I'm obligated
> to achieve a better understanding of the RL ideas.
Don't give up on the scooters too easily. :-) All algebra and no
scooters makes Johnny a dull boy.
> I must admit that I
> didn't try very hard to understand RL ages ago, but was intrigued by its
> approach to union, thinking that it might be a very practical engine
> technique. Changing one word in the D&D Algebra definition would give
> the same operator, admittedly that would pervert their analogy and which
> was pointed out directly by others and indirectly too (I remember Jon H
> talking about predicates that get truncated, can't remember exactly what
> he said, truncated is my word, not his, still that didn't bother me).
In a way I can't articulate yet, I sense that the attribute truncation
(which was kinda weird for me at first) is actually a virtue, or
rather, a necessity, when one gets to the embedded logic
and the inference rules thereof.
> I
> am guessing that part of their resistance has to do with the very name
> "union" even though they suggest the name "disjoin" for the version that
> parallels conventional boolean algebra. Has the same result when
> headings "match", so I was surprised that people found it out-of-sorts
> with D&D, since the latter stipulate that over and over anyway!
Heh. I call the two operators "and" and "or" and write them "&" and
"|"
and that makes pretty much no one happy! But the connection with
boolean algebra and logic is too strong for me to ignore.
Plus, I really like the idea of having a separate set of operators for
the relational vs. the scalar operations. Don't know what I'm going
to do about =, though. :-) Or relational division.
Marshall
Vadim Tropashko
> On May 31, 4:37 pm, Vadim Tropashko <vadimtro_inva...@yahoo.com>
> > 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.
This homomorphism can be expressed explicitly as
A -> (A \/ 00) /\ (A \/ 11)
The formula is dual to the fundamental decomposition identity!