Complement in Relational Lattice
Date: 31 May 2007 15:36:17 -0700
Message-ID: <1180650977.272556.106000_at_d30g2000prg.googlegroups.com>
[Quoted] [Quoted] RL complement is well-defined. It is roughly the complement of the rows and the complement of the columns.
- !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
[Quoted] [Quoted] 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 Received on Fri Jun 01 2007 - 00:36:17 CEST