Re: Operationalize orthogonality

From: Tony D <>
Date: 5 Jun 2006 06:03:30 -0700
Message-ID: <>

Hmmm ... I tried answering this before, and it appears to have gone down the memory tube. I'll try again, although I'll probably get it wrong ... :)

Marshall wrote:
> Tony D wrote:
> > mAsterdam wrote:
> > >
> > > It is imperative for any practical solution (i.e. with indexing)
> > > that ordering operators (<, >) of a type can be communicated.
> >
> > I think this needs to be handled on a type-by-type basis; some types
> > may not be amenable to ordering (types that generate other types, say
> > ?)
> I don't think there's any reason to consider any order relation on
> a type to be part of the type. It's a different relation. Also, every
> type that can carry information has multiple possible orders.

So far, I have only been considering "ordering" as the implementation of > between two values of the same type which returns a boolean result.

> Some orders may come defined by the system, or part of some
> library, but that doesn't make them fundamental. The RM doesn't
> have anything about order as part of its definition; one defines
> order on top of it.

Indeed. Order isn't fundamental. In a system about which we are reasoning, rather than one in which we're working, you can do quite well without it.

> > Also, types that you may want to use in non-equi joins.
> Note that one can consider a non-equijoin as an equijoin
> on 0 attributes with a further join on the non-equality
> relation. Equijoin is fundamental; non-equijoin is not.

Very definitely.

> Note that since equijoin is fundamental, equality must
> be supported for every type. The mechanism for
> this may be system-defined or type-author-defined,
> but the system must have some way to tell whether
> two values are the same.

This is why boolean is the only mandatory type - equality is defined as an operator between two values which returns a boolean result. Note that the two values needn't necessarily be the same. The relational operators just require an operator, called "==" or "equals" between two values, which returns a boolean result. We could implement "close enough for comfort", or "equivalent to three decimal places" or whatever. We might be disagreeing to agree here ;)

> > At the end
> > of the day, the restrict and join operators really don't care; they can
> > hand off evaluation of the comparisons to operators you've defined, and
> > as long as they return a boolean result that's fine. (Which might lead
> > to the "!!!" up ahead ...)
> Agreed.
> > > > However, there's a great big "!!!" sign on the road ahead; can you
> > > > guess what it is yet ?
> > >
> > > I am looking for them. Please share the one you see.
> >
> > In my last paragraph, I used this phrase :
> >
> > "they can hand off evaluation of the comparisons to operators you've
> > defined, and as long as they return a boolean result that's fine."
> >
> > Think about this a little further, with specific reference to complex,
> > structure types (and RVAs especially). The relational model may offer a
> > get-out clause, though.
> I'm not sure what you're referring to. Maybe it's that the equality
> function might be expensive? If so, that offers no theoretical
> impediment. Join is guaranteed to complete and return a value
> (assuming it is well-typed;) it is *not* guaranteed to be fast.

Cost isn't an issue for us here. Efficiency is an implementation issue. Think name spaces, scope and what can appear on either side of the comparison operator. Received on Mon Jun 05 2006 - 15:03:30 CEST

Original text of this message