Re: Operationalize orthogonality
Date: 5 Jun 2006 06:03:30 -0700
Message-ID: <1149512610.844742.246390_at_c74g2000cwc.googlegroups.com>
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.
>