Re: relational lattices from boolean algebra perspective

On Nov 6, 5:09 pm, paul c <toledobythe..._at_oohay.ac> wrote:
> Vadim Tropashko wrote:
> >http://vadimtropashko.wordpress.com/relational-lattice/
>
> How does one express de Morgan's Law in relational lattice terms?

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

where "^" is natural join, "'" is relation complement, and "+" is outer union (aka D&D <OR>). One have to express x+y in lattice terms to rewrite de Morgan's Law in pure lattice terms:

x + y = (x ^ (y v R11)) v (y ^ (x v R11)).

The other counterpart of boolean negation is relational inversion ("'") which complements relation attributes and makes "the best effort" to preserve relation content. It honors de Morgan as well (although with some twist!):

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

A composition of complement and inversion satisfies de Moragan law in lattice terms literally:

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

Several other interesting RL identities:

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

The second one is generalisation of "Fundanetal Decomposition Identity" (FDI)

x = (x ^ R00) v (x ^ R11).

which informally asserts that any relation is inner union of its header and content. Given that complement obeys double negation law, FDI can be rewritten as:

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

The dual identity:

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

also holds, while it can't be reduced to dual to FDI. The duality is skewed in subtle way, making RL much more interesting than Boolean Algebra! Received on Sat Nov 07 2009 - 03:21:29 CET