# Re: a union is always a join!

Date: Sat, 21 Feb 2009 13:32:01 GMT

Message-ID: <lnTnl.13763$PH1.4385_at_edtnps82>

rpost wrote:

> philip wrote:

*>
*

>> Reinier, >> >> There are fundamentals of Date& Darwen's "algebra" A that you don't >> understand.

*>*

> I understood the definitions (thanks for repeating them though)

*> but I did make a major mistake regarding OR.*

*>*

>> Definitions: >> AND is JOIN. >> NOT R has exactly the tuples typed by R that are not in R.

*>*

> Note that 'the tuples typed by R' is a ambiguous.

*>*

*> I was going by Darwen's appendix "A New Relational Algebra",*

*> which doesn't mention types. Therefore I was tempted to read*

*> 'the tuples typed by R' as the join of the single-attribute*

*> projections of R. Let's call this operation RELDOM(R),*

*> and define RELNOT(R) = RELDOM(R) MINUS R. RELDOM can*

*> (obviously) be expressed in Codd's algebra, albeit not*

*> with a fixed expression.*

*>*

*> However, what you actually mean by 'the tuples typed by R' is*

*> the join of the single-attribute relations with all possible*

*> values for types of the attribute. This is also an operation,*

*> let's call it DOM. Then we can define NOT(R) = DOM(R) MINUS R.*

*> This 'absolute' NOT generally introduces domain values*

*> that weren't in R, and when the domains are big or infinite,*

*> produces very big / infinite relations. It's this NOT that*

*> I have problems with.*

*> ...*

Nice to see somebody actually trying to read the Darwen & Date definitions, though I think it's essential to recognize their intended context which is pretty much limited to a formal basis for defining their Tutorial D language and they have never suggested that an rdbms should fully evaluate/materialize <NOT>. McGoveran goes much further and I like his term - 'simple complement' better than 'absolute' because there is not much that is absolute about <NOT>. His term helps underline that A-algebra by itself is not enough to decide certain (constrained) replacements of relations. A very elementary one (I don't believe McGoveran has mentioned it publicly but it is a favourite of mine) involves candidate keys - you can't necessarily 'insert' two tuples by 'deleting' them from the simple complement, even though both are in the complement. In other words, the simple complement is not subject to any constraints beyond the eligible values of domains.

What you suggest is a 'relative' complement is not what I think McGoveran had in mind, at least based on the very few public statements he's made. From what I can make out, his point amounts to saying that a relative complement is a constrained simple complement. Received on Sat Feb 21 2009 - 14:32:01 CET