Re: a union is always a join!

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.

>R OR Q has exactly those tuples typed by R JOIN Q which
>give a tuple from R when projected on R's attributes or give a tuple
>from Q when projected on Q's attributes.

Yes; and we can again introduce a relative variant RELOR by using RELDOM(R JOIN Q) instead of DOM(R JOIN Q).

>> Darwen's AND, OR and NOT are more general operations than
>> those of the relational algebra, but they are not any more precise.
>
>Agree.
>
>> And the price he pays for allowing them is worse than computational:
>> the tuples of the relations we create with them can no longer all
>> be regarded as expressing positive facts.
>
>Not so.
>Queries are interpreted exactly the same as always.
>Tuples that are present are true and those that are not present are
>false.

Yes, but what I meant to say is that in general, the tuples don't really express facts regarding those domain values, they just help express information about other domain values.

But I wasn't thinking straight when I wrote that (as paul c suggested): this is true for *any* operation with negation, e.g. RELOR or MINUS. It is only more conspicuous in NOT and OR, because they introduce domain values not in the original relation(s).

>> We *lose* preciseness.
>
>Not so.

OK.

>> Darwen's algebra is[...]
>> *not* implementation oriented, because NOT and OR cannot actually
>> be implemented as they are (try NOT-ing the table {A: 1, B: 1, C: 1},
>> where A, B, C can take arbitrary floating point values).
>
>Of course they can be implemented.
>It's true that they denote large relations, but that's not necessarily
>a problem.

It complicates the implementation: it is no longer possible to represent all relations as finite collections of tuples.

>First, you could allow only queries in NOT and OR that can be recast
>using MINUS and UNION.
>Second, you could allow non-query expressions but not queries in NOT
>and OR.

Yes, that was my suggestion: rewrite to Codd's algebra and reject the rest. Another idea is, of course, to use RELNOT and RELOR instead.

>Third, the cost of a query in NOT or OR is not necessarily
>unacceptable.
>It depends on the size of the attribute types rather than the number
>of tuples in the relation,

Definitely. For Booleans or enums it's acceptable to just complement literally.

>but you could allow them and and still compute them (eg if the result
>is small enough) (or in a lazy evaluation context).

Lazy evaluation doesn't help for NOT. I think you want to be smarter anyway. But I notice there are several implementations already and I haven't got a clue what they do.

>The benefit is that NOT and OR can give clearer queries even if you
>limit yourself to recastable queries
>(they roughly mean "not" and "or" in the sense that
>roughly JOIN means "and", MINUS means (limited) "and not" and UNION
>means (limited) "or").

Perhaps. I always liked how Codd's algebra separates 'horizontal' operations (PROJECT, JOIN) from 'vertical' ones (MINUS, UNION, INTERSECTION, quotient, selection). When I look at OR it doesn't look like an operation I would use. But this may just be a matter of getting used to it.

>> I would
>> venture that the first thing any implementer will attempt to do
>> is rewrite all of Darwen's expressions back to relational algebra as
>> far as possible, and throw errors on the remainder.
>
>You use "venture", "attempt" and "as far as possible" but the
>semantics are clear.

True.

[...]

>You can either think of PLUS as a named relation value or as a
>variable that doesn't happen to change.
>Otherwise everything is as usual.

Mathematically, yes. But the implementation has to treat PLUS, and mathematical operations in general, differently from the finite, extensionally defined, time-varying relations that constitute the actual information stored in a relational database.

[...]

>In your informal terms, PLUS is information about the world; that info
>just doesn't happen to change.

No, it is not. The implementation can, and had better, take advantage of the invariability of PLUS, and the typical computer hardware's buil-in support for it. You really really don't want to implement it as table lookup. Even for e.g. Boolean operators you probably want to optimize differently than you they will be optimized when implemented as table lookup.

>> Nice as an academic exercise (look, ma, I removed a concept)
>> but not as an academic result (no useful purpose).
>
>It is practical and not an exercise to simplify and generalize.
>The basic consequence is that the difference between operators and
>relations becomes only syntactic.

To the mathematician; not to the computer scientist.

>You can use a relation wherever you can use an operator and vice versa.
>This can be extended to include user-defined operations for which, again,
>the complexity for recastable queries is the same as the recast query,
>and you need a policy for non-recastable queries (and further policies
>for side-effects).
>If the D&D presentation were more formal and complete this would be
>more evident.

It is evident already, but I think this policy stuff is hard.

>BTW, using NOT and OR is equivalent to using MINUS and UNION along
>with a named single-attribute relation value
>for each type each containing all that type's values.

Yes (DOM above).

>Such a database has the same operation complexity as usual but some of
>the leaves (the type-relations) are big.
>So the cost of evaluating corresponding queries is the same.
>Again, it is notationally more elegant and exactly as computationally
>expensive
>to allow the latter with the same recast-restrictions you would apply
>to the former.

As I already said in my previous message, I see the elegance, but at the same time I find elegance in Codd's use of two kinds of operations. Obviously if you rewrite to Codd's algebra (or do something equivalent to that) you're not going to lose efficiency on the cases where this is possible. But just rejecting the rest is only going to confuse the user. Why not be honest and admit that we really expect, in our implementations, relational queries to work on finite, typically small relations, that WORKS_IN is one and PLUS is not, and that NOT doesn't do so?

>philip

-- 
Reinier