Re: Relation subset operators

From: <>
Date: Sat, 6 Jun 2009 14:19:13 -0700 (PDT)
Message-ID: <>

On Jun 6, 11:43 am, wrote:
> I would go further than that into saying that previous work has only
> clarified side effects of relation operations. And a lot of it missed
> the mark into expressing properties of operations that can not be
> expressed without proper quantifiers. For instance, does the empty
> set has the same role place in relational theory, than the zero would
> have in traditional algebra. Up till, such questions have not been
> answered and these claims have neither been properly demonstrated nor
> they have been properly evaluated. However nothing prevented
> demonstrators of using such quantifier in relational operations.
> There is something in that puzzles me. The creators of the zero did
> prove and demonstrate the usefulness of such value into simplifying
> algebra before they could actually use it. Nothing similar can be
> said of all particular relation that have been created in packs and
> used (Empty sets, DEE, DUM etc...)...In a word, a lot of
> demonstrations were made using tools but nobody questionned the
> relevance of such tools before using them...That is a deep sign of
> immaturity

Share many of your sentiments:

Page 5 documents four constants, compared to Boolean algebra which has 2 constants: top and bottom (aka true and false for two-valued boolean algebras). In fact, everything exploded twice in relational lattice: there are 2 pairs of true and false constants, two versions of logical AND and OR operators (page 6, figure 1), and two versions of negation!

The last assertion goes a little beyond the scope of the paper which introduced complement as unary operation satisfying the two axioms:

x' ^ x = x ^ R00.
x' v x = x v R11.

The dual version of this operation also makes sence. Let's call it "inversion" and use the back quote "`" symbol in postfix notation to write down the defining axioms:

x` ^ x = x ^ R11.
x` v x = x v R00.

(For those readers who bothered to copy and paste in these identities into Prover9, please don't forget to add something like

op(300, postfix, "`" ).

to Language options.)

Informally, inversion complements relation header, and it could be demonstrated that the best it can do about the relation content is producing either the cartesian product of the full domains, or the empty relation. Not surprisingly, it is weaker than complement. Double inversion doesn't hold, only


The other interesting theorems:

x` v y` = (x + y)`.
x` + y` = (x v y)`.
x'`v y'`= (x ^ y )'`.

Complement and inversion can be viewed as "halves" of genuine boolean negation operator, because in relational lattice it is impossible to have a genuine negation.

Now into the main topic -- set equality join. I prefer to focus on set equality rather than set containment because I expect it to have nicer algebraic properties. For one thing, set equality join is commutative, and set containment is not. Because set join is essentially universal quantifier, and the later is often is written as "/\" (capital join "^"), lets choose the notation appropriately, so that set equality join of relations x and y is written as x/\y. What is set equality join algebraically in terms of our basic operations?

A good starting point is taking a familiar representation of relational division in terms of standard RA operations, and convert it to RL. Unfortunately, in RA there is no escape from regressing to explicit attribute usage, so lets assume that x=X(q,s) and y=Y(s,t). Then,

X(q,s) /\ Y(s,t) = ( project_q(X) join project_t(Y) ) \ project_qt( (project_q(X) join Y ) symm_diff (X join project_t(Y) ) )

Here is direct RL equivalent:

x /\ y = (x v (y^R00)`) ^ (y v (x^R00)`) ^ (
 (((x ^ y) v (x v y)`) ^ R00) v

    ( ((x v (y^R00)`) ^ y) v ((y v (x^R00)`) ^ x) )   ^ ( ((x v (y^R00)`) ^ y) ^ ((y v (x^R00)`) ^ x) )'  )

This certainly looks more verbose than RA, on a plus side however, there is no explicit reference to relation attributes; every variable is a relation! Please also note how inversion came handy when we have to construct relations with attribute sets which are set differences. After writing this (and double checking its validity in QBQL) I refused to believe that this is the shortest possible expression for set equality join. There is no way one can get any insight from such unwieldy blob!

There indeed is a nicer version:

x /\ y = ((x`*y)^(y`*x)) *
 ((x`*y)^(y`*x)) *

I especially like symmetries and dualities of this one:

x /\ y = ((x`*y)+(y`*x)) ^
 ((x`*y)+(y`*x)) *

I'm still not sure if there are shorter versions. Marshall (who is apparently in stealth mode) used to work on a program that generates all valid RL expressions, and this looks like a problem fitted for such a tool. The other curiosity is how many different RL expressions one can generate with inversions and complements alone. For example, the identities

x``` = x`.
x'' = x.

show some limitations, but what about less obvious interleavings of inversion and complement? Received on Sat Jun 06 2009 - 23:19:13 CEST

Original text of this message