Re: Question about Date & Darwen <OR> operator

Marshall Spight wrote:
> > Well, the formal definition of <OR> and <AND> seems to be very
> > consistent with boolean logic.
> > [...]
> > Therefore, the D&D algebra
> > intuitively looks like boolean algebra, but it is certainly not.
> > Absorption, doesn't hold: relation headers monothonically increase, so
> > that there is no way for headers to match. Therefore, this nice boolean
> > logic must break somewhere. Where?
>
> My understanding of the classical definition is that an algebra
> is boolean iff:
> for binary operators +, *, unary operator ', and elements 1, 0
> 1) +, * are commutative
> 2) +, * are distributive
> 3) for all A, A+0=A, A*1=A (identity)
> 4) for all A, A+A'=1, A*A'=0 (complement)
>
> It seems to me that compliment is the problem. The algebra
> is obviously commutative. Elsewhere you've said it's distributive
> (which seems right.) If we define 0=dum and 1=dee (or what
> we've elsewhere called 00 and 01) we get identity, but it breaks
> down at complement over <OR>.
>
> A+A'= universal set for header(A)
> A*A'=10
>
> Both of these fail to satisfy 4).
>
> Now, we could choose the 1 element to be a+a', and the 0 element
> to be A*A'. Then identity and complement work. But it means that
> the 1 and 0 elements are specific to some header(A), so you
> could say it's a boolean algebra schema, rather than a boolean
> algebra. (That is, for every header, you can construct a boolean
> algebra for it, but it's not bollean in general.)

To summarize, there are actually 2 boolean algebras: the algebra of headers, or sets of attributes, and the algebra of tuples FOR A FIXED SET OF ATTRIBUTES. Now these 2 can be combined into relational lattice, although this doesn't look straigntforward. Direct product of 2 boolean algebras is boolean algebra, of course, but what is needed is an equivalency relation that puts the "matching" relations into the same equivalnce class. Here is an example

A relation

<attributes = {x}, tuples = {(x=1,y=a),(x=1,y=b),(x=2,y=a)}

is equivalent to

<attributes = {x}, tuples = {(x=1,y=a),(x=2,y=a)}

Informally, both relations assert the predicate x=1 & x=2, and the terms with y are not important.

> I have recently learned that there's an alternative way to specify
> a boolean algebra. It is much simpler but I find it harder to
> understand.
>
> A "Robbins Algebra" is an algebra that satisfies these equations:
> 1. commutative
> 2. associative
> 3. Robbins Equation: n(n(A+B)+n(A+n(B))) = A.
>
> where n() is the compliment function.
>
> It turns out that every Boolean Algebra is a Robbins Algebra,
> and vice versa. Which IIUC means that satisfying the Roobbins
> Equation is sufficient to prove distributivity.

This is a fascinating topic indeed. It illuminates how undeveloped Relational algebra is, for example, what is the axiom structure for RA? Received on Wed Sep 07 2005 - 02:10:15 CEST