Re: TRUE and FALSE values in the relational lattice
Date: Thu, 21 Jun 2007 10:26:19 -0700
Message-ID: <1182446779.883211.130730_at_e9g2000prf.googlegroups.com>
On Jun 21, 3:14 am, Jan Hidders <hidd..._at_gmail.com> wrote:
> I would assume the following operations: (in yet another notation)
> - E * E : natural join
> - E + E : generalized union
Eh, 3 different people, 3 different notations:-)
> - {()} : the relation with empty header and a single empty tuple
OK
> - [A,B,..D] : the empty relation with header {A, B, ..., D} (possibly
> the empty set)
This is nice proposal. How abotut small letters for attributes and capital letters for relations?
One of my (yet not realized) goals is to get rid of the attributes completely. Every time we have some relational lattice identity which mentions attribute x, the x can always be thought of as a composite attribute. And in relational terms a composite attribute is either an empty relation with header x, or a or cartesian product of domains. Therefore an attribute x, being it composite or not is just a relation x which satisfies the identity
x /\ 00 = x
(empty relation constraint), or
X \/ 11 = X
(full domain constraint). Therefore, perhaps the distinction between attributes and relations is not so clear cut to warrant capital and small letter notation?
> - A=B : the equality relation with header {A, B}
> - A=c : the relation with header {A} and tuple (A:c)
Single tuple element is a relation R such that
R /\ 00 != R
and there is no relation X such that
R < X < R /\ 00
where the "<" operation is understood to be the strict lattice order:
"greater than (and not equal)"
Again, for this to become a true axion it better be transformed into attribute agnostic form, something like this:
(( (R /\ E) \/ (X /\ Y') ) /\ E ) \/ (X /\ Y) = R
X /\ 00 = X
Y /\ 00 = Y
Y' /\ 00 = Y'
E /\ 00 = X /\ Y /\ 00
R /\ 00 = X /\ Y /\ 00
X \/ Y = 00 X \/ Y' = 00 Y \/ Y' = 00
Clearly, the straightforward translation produced such an unwieldy mess that there has to be a more concise axioms.
> - R : a relation with name R (and known header)
Yes! Again, this is how algebraic identity should look like: relation variables (no attributes in parenthesis!), constant relation symbols, and algebraic operations.
> That would be roughly equivalent with unions of conjunctive queries,
> for which equivalence is known to be decidable. Adding the set
> difference or division would make it relationally complete (so, FOL)
> and make this undecidable.
>
> Actually, a (sound and complete) axiomatization would be a small but
> publishable result. It doesn't seem that impossible either. You could
> start with showing that you have enough rules to bring the thing into
> some union normal form, and then show that you also have enough rules
> to show a homomorfisme over the conjuncts. Quite interesting indeed.
> Anyone interested in thinking about a paper on that?
This is nice research program. If the other exchange taught any lessons, then spelling out every minute detail would be one of them:-) Could you please clarify (with an example!) what "homomorfism over the conjuncts" you have in mind? Received on Thu Jun 21 2007 - 19:26:19 CEST