Re: Hashing for DISTINCT or GROUP BY in SQL

On 18/10/2010 2:31 AM, Cimode wrote:
> What is the object of optimization in a relational perspective ? What
> does it aim at, physically wise ? What are the modalities to defined
> to achieve such aim ? Don't you have the impression that the
> definition of*optimization* in such broad perspective is the
> relational theorists's way sweep the dust under the rug ?
>

I just mean that the optimizations typically used are adhoc. In algebra, we could write a 'reference' constraint, a more general form of 'foreign key' as B{F} = B{F} <AND> A{K}. That could be implemented directly.

It must be a very desireable optimization to minimize physical work even if that work is only the movement of electrons in the face of the equally desireable ability to 'update', say when a relvar is assigned. When faced with B' := B <OR> I, where the apostrophe refers to a relvar B after an 'insert', it's fairly obvious that the reference constraint can be tested against the 'before' value and only the tuples 'I' need to be tested (as opposed to all the tuples in B'). This strikes me as both a logical and physical optimization.

Being somewhat inept at relational calculus I don't have a ready example for that. I know that Codd expected his calculus to be more easily optimizable but I think that would still result in a similar situation. This may have been written about and I just haven't seen it, but there seems to be some missing implementation theory, to do with axioms, if you will, for analyzing such expressions and recognizing when the set doesn't need to be tested, ie., when only one term in an algebraic expression needs to be tested against a constraint.

(The reference constraint becomes quite convoluted when a strict foreign key constraint is desired and there are accordingly more ways to write it, but an optimization 'theory' would need to handle that too. A strict algebra won't have any keywords such as 'KEY'. A comprehensive optimization theory (eg. axioms?) for algebra expressions doesn't exist as far as I know. Even though Date points out a number of useful optimizations in his Intro book, as I recall he doesn't get down to brass tacks with the perhaps most elementary one, candidate keys.) Received on Mon Oct 18 2010 - 15:59:33 CEST