Re: Notions of Type

erk wrote:
> Marshall wrote:
> > erk wrote:
> > >
> > > Sorry if this is obvious to everyone else, but does an algebra include
> > > only operations defined on values of the type in question?
> >
> > Yes.
>
> I read elsewhere (and I'm not saying it's right) that an algebra could
> be defined as a closure over a set of types. Is that untrue?

I'm not exactly sure what that would mean.

In fact, I lack a pithy definition of algebra. (And worse, there are many senses of the word.) But one thing is common, and that is a datatype and binary operators that are closed over that datatype. Sometimes associativity of those operators is considered a requirement, but it seems a distant second to closure.

> If it's
> not true, then is there an analogous term for this algebra-like
> closure, but over multiple types?

Again, I'm not exactly sure what you mean. If by "multiple types" you mean generic types, then this is a good match for abstract algebra. For example, we can study groups, rings, fields, etc. and prove theorems about them, without having to specify which ring, etc. we are talking about.

> > Note the Tropashko algebra is a true algebra, and is complete.
>
> I've read his excellent paper, but don't have it handy; how does he
> allow what we've come to expect from relations without reference to
> attributes and their types?

Well, I would say the Tropashko operators *do* reference attributes and their types. Natural join is hard to describe without mentioning the fact that the result type is going to have the union of the attributes of the two operands.

A distinguishing characteristic, though, is that the Tropashko algebra is complete without reference to attributes *as such* as being within the data type. It has two operators, and their two operands are familiar relations from the domain of values; there is no need to reference any kind of higher-order relation.

> Or does he? While I was extremely impressed
> with what he said about joins, does the nature of an algebra imply that
> the relational model, as we know it, can never rely on an algebra
> alone?

I wouldn't say so. Completeness in the relational sense means having the same computational power as first order logic; the relational algebra is *not* Turing complete.

> > > As division by zero is undefined, either its denominator type is
> > > restricted to nonzero, or its range includes "undefined" as a value. If
> > > there's another option, I can't think of it.
> >
> > There is another option, and I would claim it's a better one than
> > either of the more popular ones you've identified: partial functions.
> > Division is a partial function. There are bazillions of partial
> > function out there, and they require at least as much attention
> > as the total ones.
>
> Agreed. Can multiple partial functions over the same domain then
> complete an otherwise "impossible" algebra? In other words, in an
> alternate reality I could define division by zero as always yielding
> 42, regardless of the domain value.

I have an answer to this, but I think it would take me about two hours to type up, and I'm hungry. I hope to get to it in the next day or two. Or maybe after dinner, who knows.

Marshall Received on Fri Aug 18 2006 - 04:12:36 CEST